max関数を含む関数の最適化

質問

最適化の初学者です。微分不可能関数の最適化に困っています。

例えば、次（添付画像）の関数fを最小化する(x_1,x_2,...,x_n)はどう求めたらよいのでしょうか。

f(x_1,x_2,…,x_n)=Σ_{1≦i≦n}{ (max_{1≦j≦n}{x_{j}*r_{i,j}}-x_{i})^2 }

ただし、任意のi, jに関してr_{i,j}は与えられているものとします。

回答No.2

ask-it-aurora

各変数はどこに属しているのでしょうか．たとえば整数だけとか，正の実数だけとか，すべての実数を考えているとか．

解析的に解ける corner case は r_{i, j} = 0 の場合ですが，ふつうに偏微分して連立方程式を解けば
(x_1, ..., x_n) = (-y_1/2, ..., -y_n/2)
のときに最小値
f(x_1, ..., x_n) = (Σ(y_i)^2)/2
をとることがわかります．けれども変数の範囲次第ではもっと難しくなりますし．

「|r_{i, j}| が微小なときには大体上のような解になるはず」くらいしかぱっと見ではわかりません．解けたときの検算くらいにしか使えませんが，参考までに．

## 係数の対称性を仮定したりすると，もうすこし非自明な場合でも明示的に解けたりするかも．

回答No.1

ask-it-aurora

何か条件を省略していませんか．

文字通りに読むと(x_1, ..., x_n) = (0, ..., 0) とすれば f(x_1, ..., x_n) = 0 で間違いなく最小値を達しますが．

補足

失礼いたしました。右辺に次式を足したものをfとした場合はどうでしょうか。

Σ_{1≦i≦n}((x_{i}+y_{i})^{2})

ただし、任意のiに関してy_{i}は与えられているものとします。

そもそも解析的に解ける部類の問題なのかどうかさえわからず困り果てています。