优化问题

问题的标准形式${p_{122}}$

$\min f_0(x)$

$s.t. \space f_i(x)\le 0,\space i = 1,..,m$

$h_i(x)=0,\space i = 1,..,p$

描述在满足所有条件下的$x$中寻找极小化$f_0(x)$的问题。

其中$x$为优化变量，函数$f_0(x)$为目标函数或费用函数，$f_i(x)\le 0$为不等式约束，$h_0(x)=0$为等式约束，对目标函数和约束函数都有定义的点为优化问题的定义域。

问题的最优值定义为$p^*$：

$p^* = \inf \{f_0(x)|f_i(x)\le 0,h_i(x)=0\}$

当$p^*$为无穷时，则问题无可行解。

最优点和局部最优点

若$x^\star$是可行的并且$f_0(x^\star) = p^\star$，则$x^\star$为最优点，所有最优解的集合为最优集。

若问题不存在最优解，则最优值是不可达的，满足$f_0(x) \le p^\star+\epsilon$的可行解为$x$的$\epsilon -\space$次优。

局部最优$x$定义为：存在$R> 0$，使得：

$f_0(x) = \inf \{f_0(z)| f_i(z) \le 0, h_i(z) = 0, || z- x|| _2 \le R\}$

粗略的讲，这意味着$x$在可行集内的一个点的周围极小化了$f_0$。

等价问题${p_{124}}$

• 可以将最大化问题转化为标准形式（最小化问题）。
• 伸缩变换与原问题是等价的。
• 变量替换是等价的。
• 单调增的复合函数与原问题等价。
• 松弛变量
  • $f_i(x)\le 0$等价于存在一个$s_i\ge 0$满足$f_i(x)+s_i=0$。
  • 可以将不等式约束替换为一个等式和一个非负约束。
• 消除等式约束${p_{126}}$
  • 可以显式的参数化等式约束，来进行变量替换，进而消除等式约束。
  • 如$h_i(x)=0$若可以表示为$x = \phi (z)$，则可以将$x$带入不等式约束。
• 消除线性等式约束
  • 若等式约束是线性的$Ax =b$，则可以将其表示为$x = Fz+x_0$，将其带入其他约束条件。
• 引入等式约束
  • 将复合函数当做新变量，引入等式。
• 优化部分变量
  • $\inf\limits_{x,y} f(x,y) = \inf\limits_{x} \inf\limits_{y}f(x,y)$
  • 可优化一部分变量再优化另一部分变量来达到优化函数的目的。

上镜图问题形式

$\min t$

$s.t. \space f_o(x) - t \le 0$

$\space f_i(x)\le 0,\space i = 1,..,m$

$h_i(x)=0,\space i = 1,..,p$

凸优化

标准形式

$\min f_0(t)$

$s.t. \space f_i(x) \le 0,\space i = 1,..,m$

$a_i^Tx = b_i,\space i = 1,..,p$

与一般的优化问题对照，其附加要求为：

• 目标函数必须是凸的
• 不等式约束函数必须是凸的
• 等式约束函数$a_i^Tx = b_i$必须是仿射的

我们可以发现，凸优化问题的可行集是凸的，因为它是下水平集、超平面的交集。

重要性质

对于凸优化问题来说，一个基础的性质是${p_{132}}$：

其任意局部最优解也是全局最优解。

但对于拟凸优化问题，这一性质不成立。

可微函数的最优性准则

若目标函数$f_0$是可微的，对于所有$x,y\in dom f_0$，都有：

$f_0(y) \ge f_0(x) + \bigtriangledown f_0(x)^T(y-x)$

若$x$是最优解，则当且仅当$x$属于可行集且：

$\bigtriangledown f_0(x)^T(y-x) \ge 0$

无约束问题${p_{133}}$

对于无约束问题，可以简化为一个简单的最优解充要条件：

$\bigtriangledown f_0(x) = 0$

可以通过可微函数的最优性准则得到。

根据解的数量，有几种情况的可能：

• 如果等式没有解，那么没有最优点，问题无下界或最优值有限但不可达
• 可能有多解，那么这些解都是最优集

只含等式约束的问题${p_{134}}$

$\min f_0(x)$

$s.t. \space Ax = b$

我们由可微函数的最优性准则可以得到，对于任意满足$Ax = b$的$y$：

$\bigtriangledown f_0(x)^T(y-x) \ge 0$

因此，每个可行解$y$都可以写成$y= x+v$的形式，其中$v \in N(A)$。因此，最优性条件表示为：

$\bigtriangledown f_0(x)^Tv \ge 0,\space \forall v \in N(A)$

若一个线性函数在子空间中非负，则它在子空间中必恒等为0。因此，$\bigtriangledown f_0(x)^Tv = 0$，即：

$\bigtriangledown f_0(x) \perp N(A)$

即$\bigtriangledown f_0(x) \in C(A)^T$，即存在$v\in R$，使得：

$\bigtriangledown f_0(x) + A^Tv = 0$

这是经典的lagrange乘子最优性条件。

非负象限中的极小化

$\min f_0(x)$

$s.t. \space x\succeq 0$

这里的唯一不等式约束是变量的非负约束。因此，最优化条件变为：

$x\succeq 0, \space\bigtriangledown f_0(x)(y-x)\ge 0,\forall y \succeq 0$

函数$\bigtriangledown f_0(x)^Ty$只有在$\bigtriangledown f_0(x)^T\succeq0$时才有下界，因此，条件简化为$-\bigtriangledown f_0(x)^Tx\ge 0$。

但是$x \succeq 0$且$\bigtriangledown f_0(x)\succeq0$，因此必须有$\bigtriangledown f_0(x)^Tx= 0$，即：

$\sum\limits_{i=1}^{n}(\bigtriangledown f_0(x))_ix_i= 0$

因此，最优性条件可以表示为：

$x\succeq 0, \space\bigtriangledown \succeq 0,(\bigtriangledown f_0(x))_ix_i= 0$

最后一个条件称为互补性，意味着向量$x$和$\bigtriangledown f_0(x)$的稀疏模式是互补的。

等价的凸问题${p_{136}}$

• 消除等式约束

  • 只需利用标准的线性代数运算，将等式约束转换解出带入，可以保持问题的凸性。

• 引入等式约束

  • 约束必须是线性的

• 松弛变量

  • 可以将$f_i(x)\le 0$ 通过松弛变量转化为等式约束$f_i(x)+s_i = 0$，其中$f_i(x)$必须是仿射的。

• 上镜图问题形式

  $\min t$

  $s.t. \space f_o(x) - t \le 0$

  $\space f_i(x)\le 0,\space i = 1,..,m$

  $a_i^Tx = b_i\space i = 1,..,p$

• 极小化部分变量

拟凸优化

当目标函数是拟凸时，称为拟凸优化问题。

拟凸优化的重要区别是局部最优可能不是全局最优的。

可以使用二分法来解决拟凸优化问题。

线性规划

当目标函数和约束函数都是仿射时，称作LP问题：

$\min \space c^Tx+d$

$s.t. \space Gx \preceq h$

$Ax =b$

LP问题当然是凸优化问题，并且，其可行集是多面体。

标准形式与不标准形式

在标准形式的线性规划问题中，仅有的不等式约束都是分量的非负约束：

$\min \space c^Tx$

$s.t. \space Ax =b$

$x\succeq 0$

如果没有等式约束，则称为不等式线性规划：

$\min \space c^Tx$

$s.t. \space Ax \preceq b$

可以使用引入松弛变量和变量替换的方法将一般的线性规划转化为标准形式${p_{140}}$。

例子

• 食谱问题
• 多面体的chebyshev中心
• 分片线性极小化（Piecewise Linear Minimization ）

线性分式规划

$\min \space \frac{c^Tx+d}{e^Tx+f}$

$s.t. \space Gx \preceq h$

$Ax =b$

其中$dom f=\{x| e^Tx+f >0\}$

这个目标函数是拟凸的，因此为拟凸优化问题。

转为线性规划问题

如果可行集非空，则可以转化为等价的LP：

$\min \space c^Ty + dz$

$s.t. \space Gy-hz\preceq0$

$Ay - bz = 0$

$e^Ty +fz= 0$

$z\ge 0$

其中，如果$x$是可行解，那么$y = \frac{x}{e^Tx+f}$,$z = \frac{1}{e^Tx+f}$

二次优化${p_{145}}$

当凸优化问题的目标函数是（凸）二次型且约束函数为仿射时，该问题为二次规划（QP），可以表示为：

$\min \space (1/2) x^TPx + q^Tx + r$

$s.t. \space Gx\preceq h$

$Ax=b$

其中$P$为半正定对称矩阵。从集合上讲，我们是在多面体上极小化一个凸二次函数。

若在上式中，不等式约束也是（凸）二次型，那么这问题为二次约束二次规划（QCQP），此时是在椭圆的交集构成的可行集上极小化凸二次函数。

例子

最小二乘及回归${p_{146}}$

极小化凸二次函数：

$||Ax-b||^2_2 = a^TA^TAx - 2b^TAx + b^Tb$

这个问题很简单，有解析解$A^TAx = A^Tb$，可见最小二乘法这篇文章。

增加线性不等式约束后的问题为约束回归或约束最小二乘，此问题不再有简单的解析解，例如：

$\min \space ||Ax-b||^2_2$

$s.t. \space l_i\le x_i\le u_i$

这是一个二次规划。

二阶锥规划${p_{149}}$

一个与二次规划紧密相关的问题是二阶锥规划（SOCP）：

$\min \space f^Tx$

$s.t. \space ||A_ix+b_i||_2 \le c_i^Tx+d_i$

$Fx=g$

其中$x$是优化变量，称$||A_ix+b_i||_2 \le c_i^Tx+d_i$为二阶锥约束。

鲁棒线性规划

$\min \space c^Tx$

$s.t. \space a_i^Tx \le b_i ,\forall a_i \in \epsilon_i, i = 1,..,m$

其中，$a_i$是在变化的，这一鲁棒线性约束可以表示为：

$\sup \{a_i^Tx|a_i\in \epsilon_i \} \le b_i$

而$a_i$的变化可以表示为：

$a_i\in \epsilon_i = \{\hat{a_i} + P_iu| ||u||_2 \le 1\}$

因此，原约束可以表示为：

$\sup \{a_i^Tx|a_i\in \epsilon_i \} = \hat{a_i}^Tx + \sup \{u^TP_ix | ||u||_2 \le 1\} = \hat{a_i}^Tx + ||P_i^Tx||_2$

鲁棒性约束可以表示为：

$\hat{a_i}^Tx + ||P_i^Tx||_2\le b$

这是一个二阶锥规划，因此，可以将其转化为SOCP:

$\min \space c^Tx$

$s.t.\space \hat{a_i}^Tx + ||P_i^Tx||_2\le b$

几何规划

这是一类特殊的优化问题，他们的自然形式并不是凸的，但通过变量替换或目标函数、约束函数的转换，可以将其转换为凸优化问题。

单项式和正项式${p_{153}}$

函数$f$ 定义为:

$f(x) = cx_1^{a_1}x_2^{a_2}...x_n^{a_n}$

其中$c > 0$，被称为单项式函数。

以下函数被称为正项式函数：

$f(x) = \sum\limits_{k=1}^K c_kx_1^{a_{1k}}x_2^{a_{2k}}...x_n^{a_{nk}}$

其中$c_k$大于0。

正项式对于加法、数乘和非负的伸缩变化是封闭的。

单项式对于数乘和除是封闭的。

几何规划

具有以下形式的优化问题被称为几何规划（GP）：

$\min \space f_0(x)$

$s.t. \space f_i(x) \le1, i =1,...,m$

$h_i(x)=1,i=1,...,p$

凸形式的几何规划

几何规划一般不是凸优化问题，但我们可以将其转换为凸优化。

用$y_i =\log x_i$定义变量，因此$x_i = e^{y_i}$。如果$f$是$x$的单项式函数，即：$f(x) = cx_1^{a_1}x_2^{a_2}...x_n^{a_n}$，则：

$f(x) = f(e^{y_1},...,e^{y_n}) = e^{a^Ty+b}$

其中$b = \log c$，变量替换将一个单项式函数转化为以仿射函数为指数的函数。

类似，若$f$是正项式，则可以转化为：

$f(x) = \sum \limits_{k=1}^K e^{a^T_ky+b_k}$

经过变换，正项式转换为以仿射函数为指数的函数的和。

因此，集合规划可以用新变量$y$的形式表示：

$\min \sum \limits_{k=1}^K e^{a^T_ky+b_k}$

$s.t.\space \sum \limits_{k=1}^{K_i} e^{a^T_{ik}y+b_{ik}}$

$e^{g^T_iy}+h_i = 1$

如果正则式目标函数和所有约束函数都只含一项，即都是单项式，那么凸形式的集合规划将退化为一般的线性规划。