最適化問題の解法

質問

最適化問題の解法に関するご質問です。
(マニアックな質問ですがお付き合いください・・)
定義：
X_j(1<=j<=N)（行列サイズ＝d×1）、
A_i(1<=i<=N)（対角行列、行列サイズ＝d×d）、
B（行列サイズ＝d×1）、
i = (1, ... , 1)'

目的関数：min_{X_k} { |B-Σ_[i=1,N]A_i*X_i|^2 +βΣ_[k=1,N]|B*X_k|^2 }

最終的には、X = (X_1, ... ,X_N)を求めたいです。
必要であれば、「制約条件：W_i'*i=1」を使っても構いません。
この制約条件をもとに下記のように式を変形しました。

目的関数：min_{X_k} { Σ_[i=1,N]Σ_[j=1,N]{X_i'*A_i'*A_j*X_j}+βΣ_[k=1,N]{X_k'*B'*B*X_k} }
制約条件：X_i'*i=1

この最適化問題を解くのに頭を抱えています。
解法を導くことができる方、ヒントを持っている方がいらっしゃいましたら、ぜひともご教授お願い致します。
よろしくお願い致します。

回答No.3

kts2371148 · ベストアンサー

すいません、私が勘違いしているのかもしれませんが、
この問題は、

f(x1,x2,…,xN) = （ x1,x2,…,xN の２次関数 ）

を最小化すればいいのでしょうか？

もしそうだったら、
∂f/∂x1 = 0
∂f/∂x2 = 0
…
∂f/∂xN = 0
の連立一次方程式の解が答えになるような気がするのですが、
気のせいでしょうか？

頓珍漢な回答だったら、すいません。

お礼

参考にさせていただきました。ありがとうございました。

回答No.2

Tacosan

#1 です.
おっと, X = (X_1, ..., X_N) は正方行列とは限らないのか....
Y_{ij} = X_i' X_j という変数 (i, j ∈ { 1, ..., N }) を導入すると, Y_{ij} に関する 1次式 + Y = (Y_{ij}) が半正定値なので SDP になります. で rank Y ≦ d, と.
N = d, つまりランク制約のない問題なら SDP は「簡単に解ける」しアルゴリズムも存在するんですが (そのあと Choresky 分解すればいい), そうでないと無理かなぁ? d << N だと多分ダメ.
ランク制約があるので, 一般的に言って厳密解を求めるのは困難だと思います.

お礼

参考にさせていただきました。ありがとうございました。

補足

初めににお詫びをさせてください。
目的関数は下記のように訂正お願い致します。
申し訳ございませんでした。

誤　min_{X_k} { |B-Σ_[i=1,N]A_i*X_i|^2 +βΣ_[k=1,N]|B*X_k|^2 }
正　min_{X_k} { |B-Σ_[i=1,N]A_i*X_i|^2 +βΣ_[k=1,N]|Q*X_k|^2 }
Q:N×Nの行列

Tacosan様
SDPが使えそうだとの御助言ありがとうございます。
私は数理計画法に少し疎いので、とても参考になります。
もしSDPの入門書などご存知でしたら、ぜひ教えてください。

それと、目的関数の第一項を展開しますとB'*A_i*X_iがでて、第二項にはX_k'*Q'*Q*X_kがでるためYで表すことができません。
こちらの技術不足で申し訳ありませんが、どのように第一項をYで表現するのでしょうか？

ランクに関してですが、今回の場合はd>=Nを想定しています。

回答No.1

Tacosan

ん～, 問題の大きさを変えてもいいなら半定値計画法 (semidefinite programming, SDP) になるかな?