LP，QP，QCQP，SOCP，SDP

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

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

（$Ax\leq b$ のもとで変数 $x$ を動かして $c^{\top}x$ を最小化するという意味）

ただし，$A$ は行列，$b,c,x$ はベクトルとします。

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

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

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

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

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

二次の項が存在しない場合（$Q=O$ の場合）は LP になるので，QP は LP を含んでいます。

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

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

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

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

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

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

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

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

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

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

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

$\mathrm{s.t.}\:\:A_0+x_1A_1+\cdots +x_mA_m\succeq O$

ただし，$x$ は $m$ 次元ベクトルで，$x_1,\cdots,x_m$ はその要素を表します。また，$A_0,\cdots,A_m$ は対称行列です。

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

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