全部笔记的汇总贴（视频也有传送门）：中科大-凸优化
min t s . t . A T ( x ) A ( x ) − t 2 I ≤ 0 t ≥ 0 ⇔ min t s . t . [ t I A ( x ) A T ( x ) t I ] ⪰ 0 t ≥ 0 ⇔ min t s . t . Y = [ t I A ( x ) A T ( x ) t I ] （ 线 性 ） Y ⪰ 0 （ 半 正 定 ） t ≥ 0 （ 线 性 ） \min t\\s.t. A^T(x)A(x)-t^2I\le0\\t\ge0\\\;\\\Leftrightarrow \\\min t\\s.t.\;\left[ \begin{matrix} tI& A(x) \\ A^T(x) & tI \\ \end{matrix} \right]\succeq0\\t\ge0\\\;\\\Leftrightarrow\\\min t\\s.t.\;\;Y=\left[ \begin{matrix} tI& A(x) \\ A^T(x) & tI \\ \end{matrix} \right]（线性）\\Y\succeq0（半正定）\\t\ge0（线性） mints.t.AT(x)A(x)−t2I≤0t≥0⇔mints.t.[tIAT(x)A(x)tI]⪰0t≥0⇔mints.t.Y=[tIAT(x)A(x)tI]（线性）Y⪰0（半正定）t≥0（线性）
一、多目标优化问题
min f 0 ( x ) s . t . f i ( x ) ≤ 0 , i = 1 , ⋯ , m h i ( x ) = 0 , i = 1 , ⋯ , P f 0 : R n → R g , f i : R n → R , h i : R n → R \min\;f_0(x)\\s.t.\;f_i(x)\le0,i=1,\cdots,m\\h_i(x)=0,i=1,\cdots,P\\f_0:\R^n\rightarrow\R^g,f_i:\R^n\rightarrow\R,h_i:\R^n\rightarrow\R minf0(x)s.t.fi(x)≤0,i=1,⋯,mhi(x)=0,i=1,⋯,Pf0:Rn→Rg,fi:Rn→R,hi:Rn→R
例
min R i s k m i n − I n c o m e s . t . R e s o u r c e s \min\;\;Risk\\min\;-Income\\s.t.\;\;Resources minRiskmin−Incomes.t.Resources
例
min
−
s
p
e
e
d
min
−
q
u
a
l
i
t
y
s
.
t
.
r
e
s
o
u
r
c
e
s
\min\;\;-speed\\\min\;\;-quality\\s.t.\;\;resources
min−speedmin−qualitys.t.resources
pareto optimal front上任意点，若找到另一解，使之在某个指标上更优，必在另外某指标上变得更美。
若
{
f
0
(
x
)
}
\{f_0(x)\}
{f0(x)}在
R
k
\R^k
Rk中为凸，
f
(
x
)
f(x)
f(x)为凸，
h
i
(
x
)
h_i(x)
hi(x)为仿射，则必可通过下述方法求得Pareto front上一点。
min
∑
i
=
1
q
λ
i
f
0
i
(
x
)
λ
i
≥
0
s
.
t
.
f
i
(
x
)
≤
0
,
i
=
1
,
⋯
,
m
h
i
(
x
)
=
0
,
i
=
1
,
⋯
,
P
\min\;\sum_{i=1}^q\lambda_if_{0i}(x)\;\;\lambda_i\ge0\\s.t.\;\;f_i(x)\le0,i=1,\cdots,m\\h_i(x)=0,i=1,\cdots,P
mini=1∑qλif0i(x)λi≥0s.t.fi(x)≤0,i=1,⋯,mhi(x)=0,i=1,⋯,P
通过遍历
{
λ
i
}
\{\lambda_i\}
{λi}可找出所有点。
例：Ridge Regression
b = A x + e , A ∈ R m ∗ n , b ∈ R m , e ∈ R m , x ∈ R n min ∣ ∣ b − A x ∣ ∣ 2 2 min ∣ ∣ x ∣ ∣ 2 } min ∣ ∣ b − A x ∣ ∣ 2 2 + λ ∣ ∣ x ∣ ∣ 2 2 （ 岭 回 归 ） ⇔ min ∣ ∣ b − A x ∣ ∣ 2 2 s . t . ∣ ∣ x ∣ ∣ 2 2 ≤ ε b=Ax+e,A\in\R^{m*n},b\in\R^m,e\in\R^m,x\in\R^n\\\left. \begin{array}{r} \min\;\;||b-Ax||_2^2\\ \\\min\;\;||x||^2 \end{array} \right\} \min\;||b-Ax||^2_2+\lambda||x||_2^2（岭回归）\\\;\\\Leftrightarrow\min\;||b-Ax||_2^2\\s.t.\;\;||x||_2^2\le\varepsilon b=Ax+e,A∈Rm∗n,b∈Rm,e∈Rm,x∈Rnmin∣∣b−Ax∣∣22min∣∣x∣∣2⎭⎬⎫min∣∣b−Ax∣∣22+λ∣∣x∣∣22（岭回归）⇔min∣∣b−Ax∣∣22s.t.∣∣x∣∣22≤ε