次のように最適化の問題を解決する方法を見つけようとしています。複数回選択できる 22 の異なるオブジェクトがあります。f多重度を取り、合計値を計算する評価関数があります。
fは、線形 (アフィン) 項の分数にわたる積であり、許可された領域では微分可能であり、滑らかですらあります。
22 個の変数に関して f を最適化したいのですが、特定の合計が特定の値を超えてはならないという追加の条件があります (たとえば、a,...,v が私の変数である場合a + e + i + m + q + s <= 9)。これにより、すべての変数が制限されます。
f が厳密に単調である場合、これは (最小限に変更された) ナップザック ソリューションによって最適に解決できます。ただし、関数は凸ではありません。つまり、空のナップザックでオブジェクト A を取る方が B よりも優れている場合、3 番目のオブジェクト C を追加する場合でもこの選択が有効であると仮定することは不可能です (C は B の利点を A よりも良くするように変更する可能性があるため)。これは、貪欲なアルゴリズムを使用できないことを意味します。
このような問題を最適な (または少なくともほぼ最適な) 方法で解決する同様のアルゴリズムはありますか?
編集:要求に応じて、問題の例(簡単にするために5つの変数a、b、c、d、eを選択しました)、たとえば、
f(a,b,c,d,e) = e*(a*0.45+b*1.2-1)/(c+d)
(すべての変数は 1 回だけ表示されます。これが役立つ場合) また、たとえばa+b+c=4、d+e=3
問題は、a、b、c、d、e を整数として最適化することです。凸関数に当てはまる最適化アルゴリズムはたくさんありますが、非凸関数にはほとんどありません...