LP,QP,QCQP,SOCP,SDP

連続最適化問題の有名なクラス

LP:線形計画問題

QP:二次計画問題

QCQP:二次制約つき二次計画問題

SOCP:二次錐計画問題

SDP:半正定値計画問題

(QP,QCQP の二次項の行列 QQ が半正定値という制限のもと)下に行くほど表現力が高い問題です。

LP(線形計画問題)

minxcx\min_{x}\:\:c^{\top}x

s.t.Axb\mathrm{s.t.}\:\:Ax\leq b

AxbAx\leq b のもとで変数 xx を動かして cxc^{\top}x を最小化するという意味)

ただし,AA は行列,b,c,xb,c,x はベクトルとします。

一次不等式で表される領域内で一次関数の値を最小化する問題です。大学入試でも(行列の形で表記されるわけではありませんが)出題されます。 →領域における最大・最小問題(線形計画法)

Ax=bAx=b という等式制約や,x0x\geq 0 という不等式制約の形で記述することもありますが,いずれも変数を追加したりすることで,AxbAx\leq b という形で書き直せます。以下でも複数表現が可能な問題を紹介しますが,そのうちの1つの形のみ示します。

QP(二次計画問題)

minx12xQx+cx\min_x\:\:\dfrac{1}{2}x^{\top}Qx+c^{\top}x

s.t.Axb\mathrm{s.t.}\:\:Ax\leq b

QQ は対称行列です。QP は二次関数の最小化問題です。高校数学でも1変数の二次関数の最大化,最小化は勉強します。

二次の項が存在しない場合(Q=OQ=O の場合)は LP になるので,QP は LP を含んでいます。

QOQ\succeq O→半正定値行列)の場合を扱うことが多いです。一般に QP と言うと,QQ が半正定値でない場合も含みますが,解くのが圧倒的に難しくなります。

QCQP(二次制約つき二次計画問題)

minx12xQ0x+a0x\min_x\:\:\dfrac{1}{2}x^{\top}Q_0x+a_0^{\top}x

s.t.12xQix+aixbi(i=1,,n)\mathrm{s.t.}\:\:\dfrac{1}{2}x^{\top}Q_ix+a_i^{\top}x\leq b_i\:(i=1,\cdots,n)

Qi(i=0,,n)Q_i\:(i=0,\cdots,n) は対称行列です。QCQP は制約条件も二次(以下の)関数にしたものです。制約が一次の場合も含んでいるので,QCQP は QP を含んでいます。

QP と同様に,QiO(i=0,,n)Q_i\succeq O\:(i=0,\cdots,n) の場合が扱いやすい問題になります。

SOCP(二次錐計画問題)

minxfx\min_x\:\:f^{\top}x

s.t.Aix+bi2cix+di(i=1,,n)\mathrm{s.t.}\:\:\|A_ix+b_i\|_2\leq c_i^{\top}x+d_i\:(i=1,\cdots,n)

f,bi,cif,b_i,c_i はベクトル,did_i はスカラー,AiA_i は行列です。制約の左辺 Aix+bi2\|A_ix+b_i\|_2 はベクトル Aix+biA_ix+b_i の長さを表します。→ノルムの意味とL1,L2,L∞ノルム

SOCP では x12+x22x1+3\sqrt{x_1^2+x_2^2}\leq x_1+3 のような制約条件も扱えるというわけです。

QiO(i=0,,n)Q_i\succeq O\:(i=0,\cdots,n) である QCQP は SOCP の形で書ける(→参考文献[1] 3-3)ので SOCP は QCQP(の一部)を含んでいます。

SDP(半正定値計画問題)

minxcx\min_x\:\:c^{\top}x

s.t.A0+x1A1++xmAmO\mathrm{s.t.}\:\:A_0+x_1A_1+\cdots +x_mA_m\succeq O

ただし,xxmm 次元ベクトルで,x1,,xmx_1,\cdots,x_m はその要素を表します。また,A0,,AmA_0,\cdots,A_m は対称行列です。

上記の形の制約条件を LMI(Linear Matrix Inequality)と言います。SOCP の制約条件は LMI の形で書ける(→参考文献[1] 3-6)ので SDP は SOCP を含んでいます。

参考文献[1]:Optimization Models and Applications

QQ が半正定値の場合はよいのですが,一般の QP は NP 困難なので困っちゃいます。