1 introduction

在前面两个章节，回顾了凸集、凸函数、凸集和凸函数联系。从这章开始认识凸优化问题。
其中，关于各种典型的类别的凸优化问题，主要参考了[2]。

2 凸优化问题

2.1 优化问题的标准形式

2.1.1 优化问题的最优解

优化问题的最优解

解集可能存在两种极端情况

2.1.2 优化问题的解集

• 可行解
  如果$x_i$满足$f_i(x)、h_i(x)$，则称$x_i$是可行解。
• 最优解
  如果$x_i$,使得$f_0(x_i)=p\ast$,则称$x_i$是最优解。
• 局部最优解
  在z附近的局部区域，$x_i$是最优解，对于整个优化问题来说，是局部最优解。
  

2.1.3 常见问题的最优解

下面三个是典型的一维优化问题的最小值和最优解。

2.1.4 隐式和显式约束

• 显式约束
  $f_i和h_i是显式约束$
  
• 隐式约束
  

2.1.5 可行性问题

对$f_0(x)$并没有目标要求，设置成$f_0(x)=0$

2.2 凸优化问题

对于一般的优化问题，要求解，目前我们已经学过的方法是求导和画图迭代求解。


及其重要的性质是：凸优化问题的解集是凸集。
根据上面学的凸函数交集或拟凸函数的下水平集仍然是凸集，可以得到这一结论。

• example
  

2.3 凸优化问题的特性

2.3.1 任何局部最优解都是全局最优解

根据[1],证明非常简单，设X是局部最优解，y是全局最优解，那么在$||z-x||<R$的区间里，根据凸函数的性质得到$f_0(z)<f_0(x)$，很容易推出矛盾。

2.3.2 从支撑超平面判定最优解

从图上很容易理解这样的关系，但是问题在于，很难利用这个条件去计算最优解。
$▽f_0(x{)}^T(y-x)$定义了支撑平面，说明了任意的$y\in X$都在支撑平面的一侧，不管如何从$x\to y$在$▽f_0(x)$这个方向上都是增加的。

2.3.3 其他情况下最优解的求解

• 无约束情况下
  无约束情况，采用类似于函数求极值的方法。
  
• 只有等式约束情况下
  根据几何图像，很容易得到Ax=b对应的平面是$f_0(x)$的支撑超平面。
  有$▽f_0(x)\perp \mathcal{N}(A)$,从拉格朗日算子描述为
  存在$\nu \in R^P,使得▽f_0(x)+A\nu =0$
  
• 只有非负约束
  $看不懂$

2.3.4 等价的凸问题

• 消除等式约束
  
  
• 增加等式约束
  这个就比较容易理解，上面的逆操作
  
• 松弛变量
  如果不等式约束是线性的
  
• 上镜图形式
  
• 极小化部分变量
  极小化凸函数保持凸性不变，$\min \inf (f_0(x_1,x_2))等价于min{f}_0(x_1,x_2)$。
  类似于极小化部分变量，先从每个部分找最小值，然后通过相互比较，找到全局最小值。
  

2.3.5 各种典型的凸优化问题

下图是各种典型凸优化问题之间的联系，在回顾各种典型的凸优化问题时，重点关注各种不同的凸优化问题之间的联系。

2.4 拟凸优化

2.4.1 定义

优化问题的基本结构仍然不变，因为拟凸函数的解集是凸集，所以$f_i(x)和h_i(x)$的要求是相似的.

当$f_0(x)$是拟凸函数时，问题变成了一个拟凸优化问题。

2.4.2 和凸优化问题的区别

在深入分析之前，需要先从几何直觉上回顾一下拟凸函数和凸函数的最大区别。

• 局部极小值不是全局最小值
  
• 支撑超平面判定最优解
  

2.4.3 二分法求拟凸优化问题

拟凸函数的下水平集是凸集，对应凸函数约束如下

拟凸优化问题中的极小值p*,极小值是通过二分法试出来的。
先设一个$t_0,t_1$如果$t_0$有解，$t_1$无解，则$t_1<p\ast <t_0$,然后不断二分迭代，直到满足精度要求。

3 线性规划问题

进入这一部分，定义并不是非常难，$关键在于可视化的理解这些实际优化问题$

3.1 定义

通过找到支撑平面，很快就能找到最优解。

3.2 问题转换

3.2.1 标准形式的LP

$$\{\begin{array}{rlr}& minimize& c^{T}x\\ & subjectto& Ax=b\\ & & x\ge 0\end{array}$$
转换成标准形式[2]

3.3 典型问题

优化问题如果建模完成了，都有很成熟的工具箱，关键在于将其建模成典型的优化问题。

• 食谱问题
  用数学形式描述为：
  
  
• 多面体的切比雪夫中心
  在下面这个多边形区域中，找到一个半径最大的球。
  不等式约束：${\vec{a}}^T\vec{x}⪯\vec{b}$
  等式约束：{xc⃗+u⃗∣∣∣u∣∣2<r}\{\vec{x_c}+\vec{u}| ||u||_2<r\}{xc​​+u∣∣∣u∣∣2​<r}
  现在的问题在于，变量空间应该是$x_c,r$这两个变量，所以需要对不定式约束进行改造。
  $$\begin{array}{rl}{\vec{a}}^T\vec{x}& ={\vec{a}}^T(\overrightarrow{x_c}+\vec{u})\\ & ⪯{\vec{a}}^T\overrightarrow{x_c}+r||\vec{a}|{|}_2\end{array}$$
  问题就简化成下面这个线性规划问题
  

• 线性分式规划
  如果$f_0(x)是$线性分式函数
  
  令$e^{T}x+f=\frac{1}{z},zx=y$,很容易得到线性规划的形式
  

4 二次优化问题

4.1 定义

其中，P是正定矩阵$P\in S_{+}^n$,显然$f_0(x)和f_i(x)$都是凸函数。
$x^{T}Px+q^{T}x+r$，如果P是正定矩阵，二维二次方程的等高线图像如下：

二次优化问题的解集和方程的关系如下图。

4.2 典型例子

• 最小二乘问题
  
  进行转换
  $$\{\begin{array}{rlr}& minimize& x^T{A}^{T}Ax-2b^{T}Ax+b^{T}b\\ & subject& -x+l\le 0\\ & & x-u\le 0\end{array}$$

5 QCQP(Quadratically Constrained Quadratic Programs)

5.1 定义

标准形式

从二维图像上理解QCQP问题，如下图。

5.2 典型问题

5.2.1 min linear function over a centered ellipsoid

问题描述
$$\{\begin{array}{rlr}& minimize& c^{T}x\\ & subject& x^{T}Ax\le 1,A\in S_{+}^n\end{array}$$
对问题进行简化,设$y=A^{\frac{1}{2}}x,\bar{c}=A^{-\frac{1}{2}}c$
$$\{\begin{array}{rlr}& maximum& -{\bar{c}}^{T}y\\ & subject& y^{T}y\le 1\end{array}$$
根据柯西-施瓦茨公式
$$\begin{array}{rl}-{\bar{c}}^{T}y& \le \sqrt{{\bar{c}}^T\bar{c}}\sqrt{y^{T}y}\end{array}$$
当$y=\alpha \bar{c}$,有最大值。根据constraints计算$\alpha$.
$$y^{T}y={\alpha }^2{\bar{c}}^T\bar{c}\le 1$$
有$\alpha =\frac{1}{\sqrt{{\bar{c}}^{T}c}}$,
$$\begin{array}{rl}x& =A^{-\frac{1}{2}}y\\ & =-\alpha A^{-\frac{1}{2}}{A}^{-\frac{1}{2}}c\\ & =-\frac{1}{\sqrt{c^T{A}^{-1}c}}{A}^{-1}c\end{array}$$

5.2.2 min quadratic function over a centered ellipsoid

问题描述：
$$\{\begin{array}{rlr}& minimize& x^{T}Bx\\ & subject& x^{T}Ax\le 1\end{array}$$
通过设$y=A^{\frac{1}{2}}x,C=A^{-\frac{1}{2}}B{A}^{-\frac{1}{2}}$，问题转换成
$$\{\begin{array}{rlr}& minimize& y^{T}Cy\\ & subject& y^{T}y\le 1\end{array}$$
C是正定矩阵，有$Cv=\lambda v$。如果${\lambda }_{min}<0$,当$y=v_{min},得到最小值$
$$y^{T}Cy=-||{\lambda }_{min}||v_{min}^T{v}_{min}\le -||{\lambda }_{min}||$$
如果${\lambda }_{min}>0$,y=0的时候，得到最小值。

6 SOCP（二阶锥规划）

6.1 定义

关注inequalities,进行转换
$$x^T{A}_i^T{A}_{i}x+(2b_i^T{A}_i-c_i^T)x+b_i^T{b}_i-d_i\le 0$$
实际上是一个二项式，$A_i^T{A}_i$是正定矩阵。

6.2 QCQP和SOCP的关联

QCQP的标准形式：
$$\{\begin{array}{rlr}& minimize& x^{T}Px+x^{T}q+r\\ & subject& x^T{P}_i+x^T{q}_i+r_i\le 0\end{array}$$
设$f(x)=x^{T}Px+x^{T}q+r\le c$,进行转换得到：
$$\{\begin{array}{rlr}& minimize& c\\ & subject& x^T{P}_i^{\frac{1}{2}}{P}_i^{\frac{1}{2}}x+2x^T{P}_i^{\frac{1}{2}}{b}_i+b_i^T{b}_i-b_i^T{b}_i+r_i\le 0\\ & & x^T{P}^{\frac{1}{2}}{P}^{\frac{1}{2}}x+2x^T{P}^{\frac{1}{2}}b+b^{T}b-b^{T}b+r\le c\end{array}$$
设$\bar{A}=[A0]$, $f=[01]$, $\bar{x}=[xc{]}^T$,$\overline{A_i}=[A_{i}0]$, $\bar{A}=[A0]$
$$\{\begin{array}{rlr}& minimize& f\bar{x}\\ & subject& ||P_i^{\frac{1}{2}}\bar{x}+b|{|}_2^2\le \sqrt{b_i^T{b}_i-r_i}+c_i^{T}x\\ & & ||P^{\frac{1}{2}}x+b|{|}_2\le \sqrt{c+b^{T}b-r}\le \sqrt{d+b^{T}b-r}\\ & & c\le d\end{array}$$
最后是可以凑出SOCP的形式。

6.3 robust linear programming和SOCP的联系

问题的描述
{minimizecTxsubjectaiTx≤bi,i=1,...,mai∈ϵi:{ai+piu;∣∣u∣∣≤1} \left \{ \begin{aligned} & minimize \quad & c^Tx \\ & subject \quad & a_i^Tx \leq b_i, i=1,...,m \\ & \quad & a_i \in \epsilon_i : \{a_i +p_iu; ||u|| \leq 1\} \end{aligned} \right. ⎩⎪⎨⎪⎧​​minimizesubject​cTxaiT​x≤bi​,i=1,...,mai​∈ϵi​:{ai​+pi​u;∣∣u∣∣≤1}​
robust 的问题，很多时候需要考虑的是极限情况下，是否满足约束。
{minimizecTxsubjectsup{aiTx∣ai∈ϵi}≤bi \left \{ \begin{aligned} & minimize \quad & c^Tx \\ & subject \quad & sup \{a_i^Tx|a_i \in \epsilon_i \} \leq b_i \end{aligned} \right. {​minimizesubject​cTxsup{aiT​x∣ai​∈ϵi​}≤bi​​
单独分析极限情况下的constraints
sup{aiTx∣ai∈ϵi}=sup{(ai+piu)Tx∣∣∣u∣∣≤1}=sup{aiTx+uTpiTx∣∣∣u∣∣≤1}=aiTx+sup{uTpiTx∣∣∣u∣∣≤1}=aiTx+∣∣piTx∣∣2≤bi \begin{aligned} sup \{a_i^Tx| a_i \in \epsilon_i \} &= sup \{(a_i+p_iu)^Tx | ||u|| \leq 1 \} \\ &=sup \{ a_i^Tx+u^Tp_i^Tx | ||u||\leq 1 \} \\ &=a_i^Tx+sup \{ u^Tp_i^Tx| ||u||\leq 1 \} \\ & =a_i^Tx+||p_i^Tx||_2 \leq b_i \end{aligned} sup{aiT​x∣ai​∈ϵi​}​=sup{(ai​+pi​u)Tx∣∣∣u∣∣≤1}=sup{aiT​x+uTpiT​x∣∣∣u∣∣≤1}=aiT​x+sup{uTpiT​x∣∣∣u∣∣≤1}=aiT​x+∣∣piT​x∣∣2​≤bi​​
当$u=\frac{p_i^{T}x}{||p_i^{T}x||}$能获得最大值。此时就可以将robust linear programming 转换成SOCP问题
$$\{\begin{array}{rlr}& minimize& c^{T}x\\ & subject& ||p_i^{T}x|{|}_2\le -a_i^{T}x+b_i\end{array}$$

6.4 linear programming with random constraints

这些都属于控制和规划中的常见的情况，从socp的角度理解这些形式。
$$\{\begin{array}{rlr}& minimize& c^{T}x\\ & subject& a_i^{T}x\le b_i,i=1,...,m\\ & & a_i\sim \eta (\overline{a_i},{\xi }_i)\end{array}$$

设定满足constraints的置信度，进行转换
$$\{\begin{array}{rlr}& minimize& c^{T}x\\ & subject& P_i(a_i^{T}x\le b_i)\ge \eta ,i=1,...,m\end{array}$$

从constraints出发，令$u=a_i^{T}x$
$$\begin{array}{rl}E(u)& =E(a_i)x=\overline{a_i}x\\ var(u)& =E(u)=x^T\xi x\\ P_i(a_i^{T}x\le b_i)& ={\varphi }_i(z\le \frac{b_i-\bar{u}}{{\sigma }_u})\\ & ={\int }_{-\infty }^{\frac{b_i-\bar{u}}{{\sigma }_u}}\frac{1}{\sqrt{2\pi }}{e}^{-\frac{x^2}{2}}dx\end{array}$$

根据概率限制,计算u所能取得范围
$$\begin{array}{rl}\frac{b_i-\bar{u}}{{\sigma }_u}& \ge {\varphi }^{-1}(\eta )\\ \bar{u}+{\varphi }^{-1}(\eta ){\sigma }_u& \le b_i\\ a_i^{T}x+||{\xi }_i^{1/2}x||{\varphi }^{-1}(\eta )& \le b_i\end{array}$$

就将概率形式的不等式约束转换成常规的不等式约束了
$$\{\begin{array}{rlr}& minimize& c^{T}x\\ & subject& ||{\xi }_i^{1/2}x||\le -\frac{a_i^{T}x}{{\varphi }^{-1}(\eta )}+\frac{b_i}{{\varphi }^{-1}(\eta )}\end{array}$$

6.5 sum of norms minimization

形式如下，凸函数的和仍然是凸函数，同时它可以转换成SOCP问题，所以不用担心这个问题是否是凸优化问题。
$$\underset{x}{\min }\sum _{i=1}^p||A_{i}x+b_i|{|}_2$$

使用技巧，设$||A_{i}x+b_i|{|}_2\le t_i$
$$\{\begin{array}{rlr}& minimize& \sum t_i\\ & subject& ||A_{i}x+b_i|{|}_2\le t_i,t=1,...,p\end{array}$$

为了凑出SOCP的形式，
设$\bar{x}=[x_1{x}_2...x_n|t_1{t}_2...t_p]$,
$f=[00...0|11...1]$
$\overline{A_i}=[A_{i}0]$
$c_i=[0...1...0]$,第i项为1.
$$\{\begin{array}{rlr}& minimize& f^T\bar{x}\\ & subject& ||{\bar{A}}_{i}x+b_i|{|}_2\le c_i^{T}x,t=1,...,p\end{array}$$

6.6 max of norm minimization

凸函数集的最大值从几何上看是，凸函数上境图的交集，所以仍然是凸函数。同时它可以转换成SOCP问题，也就解决了证明是凸函数的困难。
$$\underset{x}{\min }\underset{i}{\max }||A_{i}x+b_i||$$
设$\underset{i}{\max }||A_{i}x+b_i||\le t$
$\bar{x}=[x_1{x}_2...x_{n}t]$
$f=[00...01]$
$c_i=[00...01]$
$\overline{A_i}=[A_{i}0]$
转换成标准形式
$$\{\begin{array}{rlr}& minimize& f^T\bar{x}\\ & subject& ||{\bar{A}}_{i}x+b_i|{|}_2\le c_i^{T}x,t=1,...,p\end{array}$$

6.7 problem with hyperbolic constraints

这种分式形式的双曲线函数是凸函数，凸函数之和仍然是凸函数。
$$\{\begin{array}{rlr}& minimize& \sum _{i=1}^p\frac{1}{a_i^{T}x+b_i}\\ & subject& a_i^{T}x+b_i\ge 0\\ & & c_i^{T}x+d_i\ge 0\end{array}$$
采用旧套路，设$\frac{1}{a_i^{T}x+b_i}\le t_i$
根据
$$w^2\le xy⟹||[2wx-y]|{|}_2\le x+y$$

转换成新的形式
$$\{\begin{array}{rlr}& minimize& \sum t_i\\ & subject& ||[2t_i-a_i^{T}x-b_i{]}^T|{|}_2\le a_i^{T}x+b_i+t_i\\ & & c_i^{T}x+d_i\ge 0\end{array}$$
和前面的内容类似，设
$\bar{x}=[x_1{x}_2...x_n|t_1{t}_2...t_p]$
$f=[00...0|11...1]$
$\overline{A_i}=\left[\begin{array}{cc}0& 0\\ -a_i& e_i\end{array}\right]$
$\overline{b_i}=[2-b_i{]}^T$
得到最终形式
$$\{\begin{array}{rlr}& minimize& f^T\bar{x}\\ & subject& ||\overline{A_i}x+\overline{b_i}|{|}_2\le a_i^{T}x+b_i+t_i\\ & & c_i^{T}x+d_i\ge 0\end{array}$$
类似的问题还有
$$\{\begin{array}{rlr}& minimize& \sum _{i=1}^p\frac{||F_{i}x+g_i|{|}_2^2}{a_i^{T}x+b_i}\\ & subject& a_i^{T}x+b_i\ge 0\\ & & c_i^{T}x+d_i\ge 0\end{array}$$

References

[1] https://zhuanlan.zhihu.com/p/133458743
[2] https://www.youtube.com/watch?v=dAyeNmz6p-c