凸优化理论学习三|凸优化问题（一）

系列文章目录

凸优化理论学习一|最优化及凸集的基本概念
凸优化理论学习二|凸函数及其相关概念

---

一、优化问题

（一）标准形式的优化问题

• 优化目标：minimize $f_0(x)$
• 约束条件：
  • 非等式约束：$f_i(x)\le 0，i=1,...,m$
  • 等式约束：$h_i(x)=0，i=1,...,p$

（二）可行点和最优点

• 如果$x\in dom{f}_0$ 并且满足约束条件，则 $x\in R_n$ 是可行的
• 最优值 p ∗ = i n f { f 0 ( x ) ∣ f i ( x ) ≤ 0 , i = 1 , . . . , m , h i ( x ) = 0 , i = 1 , . . . , p } p^{*}=inf\{f_0(x)|f_i(x)\leq 0,i=1,...,m,h_i(x)=0,i=1,...,p\} p∗=inf{f0​(x)∣fi​(x)≤0,i=1,...,m,hi​(x)=0,i=1,...,p}
• 如果问题不可行，则$p^{\ast }=\infty$
• 如果问题无下界，则$p^{\ast }=-\infty$
• 如果$f_0(x)=p^{\ast }$，则可行点$x$是最优点
• $X_{opt}$是最优点的集合

（三）局部最优点

如果存在$R>0$ 使得 x 在以下情况下是最优的：

• $minimize(overz)f_0(z)$
• $subjectto$
  • $f_i(z)\le 0,i=1,...,m$
  • $h_i(z)=0,i=1,...,p$
  • $||z-x|{|}_2\le R$

那么$x$即为局部最优点。

（四）隐式和显式约束

• 显式约束：
  • 非等式约束：$f_i(x)\le 0，i=1,...,m$
  • 等式约束：$h_i(x)=0，i=1,...,p$
  • 如果$m=p=0$，即没有约束，此时问题为无约束问题
• 标准形式优化问题具有隐式约束
  $$x\in D=\bigcap _{i=0}^{m}dom{f}_i\cap \bigcap _{i=1}^{p}dom{h}_i$$

（五）可行性问题

如果目标函数恒等于零,那么其最优解要么是零(如果可行集非空),要么是∞(如果可行集是空集)。我们称其为可行性问题：

• 目标：0
• 约束条件：
  • $f_i(x)\le 0,i=1,...,m$
  • $h_i(x)=0,i=1,...,p$

二、凸优化问题

（一）标准形式的凸优化问题

• 目标：最小化$f_0(x)$
• 约束条件：
  • $f_i(x)\le 0,i=1,...,m$
  • $a_i^{T}x=b_i,i=1,...,p$

其中：目标和不等式约束$f_0,f_1,...,f_m$是凸的；等式约束是仿射的，通常写为 $Ax=b$；凸优化问题的可行集和最优集是凸的；如果 $f_0$ 是拟凸的，$f_1,...,f_m$ 是凸的，$h_1,...,h_p$ 是仿射的，则问题是拟凸的。

考虑一个标准形式问题的例子：

• 目标：最小化 $f_0(x)=x_1^2+x_2^2$
• 约束条件：
  • $f_1(x)=\frac{x_1}{(1+x_2^2)}\le 0$
  • $h_1(x)=(x_1+x_2{)}^2=0$

易知目标函数$f_0$是凸的，并且可行集$\{(x_1,x_2)|x_1=-x_2\le 0\}$也是凸的；但是约束条件$f_1$不是凸的，$h_1$不是仿射的，因此它不是一个凸问题。这个问题可以等价为以下凸问题：

• 目标：最小化 $x_1^2+x_2^2$
• 约束条件：
  • $x_1\le 0$
  • $x_1+x_2=0$

（二）局部最优与全局最优

凸问题的任何局部最优点都是（全局）最优的

可微分 $f_0$ 的最优性准则：

对于凸问题，点$x$是最优解的一个充分必要条件：

• 点$x$是可行解，即$x$属于可行集合$X$
• 对于任何可行点$y$，都满足梯度条件：${\nabla }^2{f}_0(x{)}^T(y-x)\ge 0$

这个条件表明，如果 $x$ 是最优解，那么任何与之可行的点 $y$ 的方向上的梯度内积都是非负的。这实际上是凸问题最优解的一个重要性质，称为一阶条件。这种条件确保了最优解的局部性质，即在最优解附近，目标函数不会在可行方向上下降。另一方面，如果 $x$ 满足这个条件，那么根据凸优化的性质，它意味着 $x$ 是最优解。这个条件表明，如果梯度与任何可行方向的变化都是非负的，那么该点是全局最优解的候选者。

如果梯度 $\nabla f_0(x)$ 在点$x$ 处非零，则它确实定义了可行集 $X$ 在点 $x$ 处的一个支撑超平面。

应用举例：

• 无约束问题：$x$ 最小化 $f_0(x)$ 当且仅当 $\nabla f_0(x)=0$
• 等式约束问题：$x$ 最小化 $f_0(x)$ 且满足 $Ax=b$ 当且仅当存在$v$使得：
  $$Ax=b,\nabla f_0(x)+A^{T}v=0$$
• 非负正交坐标系上的的最小化问题：$x$ 最小化 $R_{+}^n$ 上的 $f_0(x)$ 当且仅当：
  • $x$的所有分量非负：$x\ge 0$
  • 对于所有的分量$i$，如果$x_i=0$，则其对应的梯度分量$\nabla f_0(x{)}_i$非负
  • 对于所有的分量$i$，如果$x_i>0$，则其对应的梯度分量$\nabla f_0(x{)}_i$等于0

（三）一些标准凸问题

1、线性规划 (LP)

线性规划（LP）是一种特殊形式的凸优化问题，其目标函数和约束函数都是仿射的，可行集是多面体（即由线性不等式和等式构成的凸多面体）。这使得线性规划问题具有一些特殊的性质和解决方法。

• 目标函数：最小化$c^{T}x+d$
• 约束条件：$Gx\le h$，$Ax=b$
  

饮食问题：

分段线性最小化问题可以转化为线性规划（LP）问题
>等价的线性规划问题即为：

• 目标函数：最小化t
• 约束条件： $a_i^{T}x+b_i\le t,i=1,...,m$，$x\in R^n,t\in R$

这个线性规划问题的变量包括 $x$ 和 $t$，约束条件描述了函数 $f_0(x)$ 的上确界（epigraph）。通过将凸分段线性函数转化为等价的线性规划问题，我们可以使用线性规划算法来求解原始的凸分段线性函数最小化问题。

多面体的切比雪夫中心：
Chebyshev center$x_{cheb}$是多面体 $P$ 的中心，即它是一个点，使得对于多面体 $P$ 中的每个点 $x$，从$x_{cheb}$​到 $x$ 的欧几里得距离小于或等于到 $P$ 的边界的最大距离。这等价于说，Chebyshev center 是可以包容在 $P$ 内的最大球的中心。中心$x_{cheb}$和球的半径 $r$可以通过以下方式找到：

• 对于每个约束$a_i^{T}x\le b_i$，要求在球$B$内部找到与约束最靠近的点，即对于每个$i$，找到最大化$a_i^T(x_{cheb}+u)$的$u$，其中$||u|{|}_2\le r$，这相当于在球内找到一个与约束最接近的边界点
• 找到这些最近的点的最小值，即最大化$r$，同时满足所有约束。这等价于最大化球的半径，使得球包含在多面体P中。

用线性规划表示为：

• 最大化 $r$
• 约束条件：$a_i^T{x}_{cheb}+r||a_i|{|}_2\le b_i,i=1,...,m$
  

2、二次规划 (QP)

二次规划（Quadratic Programming，简称QP）是一种优化问题，其目标是最小化或最大化一个二次型目标函数，其变量受到一组线性等式和不等式约束的限制。通常的形式如下：

• 目标函数：最小化$(1/2)x^{T}Px+q^{T}x+r$
• 约束条件：$Gx\le h$，$Ax=b$

其中，$P$是对称正定矩阵

最小二乘法：

• 目标函数：最小化 $\Vert Ax-b{\Vert }_2$
• 解析解： $x^{\ast }=A†b$ （$A†$ 是伪逆）
• 可以添加线性约束，例如：
  • $x>0$（非负最小二乘法）
  • $x_1\le x_2\le ...\le x_n$（等渗回归）

具有随机成本的线性规划：

• 目标函数：最小化 ${\bar{c}}^{T}x+\gamma x^T\Sigma x$
• 约束条件：$Gx\le h,Ax=b$

其中，$c$是随机成本，$\gamma >0$ 为风险厌恶参数，控制预期成本和方差（风险）之间的权衡

3、二次约束二次规划 (QCQP)

二次约束二次规划（Quadratically Constrained Quadratic Programming，QCQP）问题是在二次目标函数下，满足一组二次不等式约束条件。通常的形式如下：

• 目标函数：最小化$(1/2)x^T{P}_{0}x+q_0^{T}x+r_0$
• 约束条件：$(1/2)x^T{P}_{i}x+q_i^{T}x+r_i,i=1,...,m$，$Ax=b$

其中，$P$是对称正定矩阵，目标和约束是凸二次的；如果$P_1,...,P_m\in S_n^{+}+$，可行域是 m 个椭球与仿射集的交集。

4、二阶锥规划（SOCP）

Second-Order Cone Programming (SOCP)是一类凸优化问题，它涉及到二阶锥约束，通常具有以下形式：

• 目标函数：最小化$f^{T}x$
• 约束条件：$||A_{i}x+b_i|{|}_2\le c_i^{T}x+d_i,i=1,...,m$，$Fx=g$

其中，不等式约束又叫二阶锥约束（SOC）：$(A_{i}x+b_i,c_i^{T}x+d_i)\in second-orderconein{R}^{n_i+1}$。如果$n_i=0$，二阶锥规划就会退为线性规划，如果$c_i=0$，二阶锥规划退为二次约束二次规划 (QCQP)。

鲁棒线性规划问题： 假设约束向量 $a_i$是不确定的情况，也就是说鲁棒线性规划（Robust Linear Programming）涉及到在不确定条件下寻找最优解。

• 目标函数：最小化$c^{T}x$
• 约束条件：$a_i^{T}x\le b_i,i=1,...,m$

对于这种不确定性，常见的处理方式有确定性最坏情况方法和随机方法两种。

确定性最坏情况方法：约束必须适用于所有 $a_i\in E_i$（不确定性椭球）

• 确定性最坏情况方法的基本形式：
  • 目标函数：最小化$c^{T}x$
  • 约束条件：$a_i^{T}x\le b_{i}forall{a}_i\in E_i,i=1,...,m$
• 确定性最坏情况方法的原理：不确定性椭球形式为 E i = { a ˉ i + P i u ∣ ∣ ∣ u ∣ ∣ 2 ≤ 1 } E_i=\{\bar{a}_i+P_iu|\ ||u||_2\leq 1\} Ei​={aˉi​+Pi​u∣ ∣∣u∣∣2​≤1}，其中${\bar{a}}_i\in R$是中心，$P_i\in R^{n\times n}$是决定半轴的奇异值/奇异向量。最终可以等价于以下形式的二阶锥规划问题：
  • 目标函数：最小化$c^{T}x$
  • 约束条件：${\bar{a}}_i^{T}x+||P{T}_{i}x|{|}_2^2\le b_i,i=1,...,m$

随机方法：把$a_i$看成一个随机变量，约束必须以一定的概率$\eta$成立

• 随机方法的基本形式
  • 目标函数：最小化$c^{T}x$
  • 约束条件：$prob(a_i^{T}x\le b_i)\ge \eta ,i=1,...,m$
• 随机方法的基本原理：假设$a_i\sim N({\bar{a}}_i,{\Sigma }_i)$，所以$a_i^{T}x\sim N({\bar{a}}_i^{T}x,x^T{\Sigma }_{i}x)$，$prob(a_i^{T}x\le b_i)=\Phi (\frac{b_i-{\bar{a}}_i^{T}x}{||{\Sigma }_i^{1/2}x|{|}_2})$，$prob(a_i^{T}x\le b_i)\ge \eta$可以被表示${\bar{a}}_i^{T}x+{\Phi }^{-1}(\eta )||{\Sigma }_i^{1/2}x|{|}_2\le b_i$。当$\eta >1/2$时，可以等价于以下形式的二阶锥规划问题：
  • 目标函数：最小化$c^{T}x$
  • 约束条件：${\bar{a}}_i^{T}x+{\Phi }^{-1}(\eta )||{\Sigma }_i^{1/2}x|{|}_2\le b_i,i=1,...,m$

4、凸椎形式问题

在凸优化中，凸锥形式的问题是一种重要的形式，涉及到优化目标函数以及约束条件均为凸锥函数或凸锥集。具体而言，考虑以下凸锥形式的问题：

• 目标函数：$最小化$c^Tx$
• 约束条件：$Fx+g{\le }_{K}0$，$Ax=b$

其中，$K$表示一个凸椎，通常是一个封闭的凸椎

5、半定规划 (SDP)

半定规划（Semidefinite Programming，SDP）是一类重要的凸优化问题，它涉及到优化一个线性函数，其变量是对称半正定矩阵。半定规划的一般形式如下：

• 目标函数：最小化$c^{T}x$
• 约束条件：$x_1{F}_1+x_2{F}_2+...+x_n{F}_n+G\le 0$，$Ax=b$

其中，$F$和$G$为对称矩阵（$F_i,G\in S^k$），不等式约束称为线性矩阵不等式（LMI）。

示例：矩阵范数最小化

6、LP、SOCP与SDP

LP 和等效的 SDP：
SOCP 和等效的 SDP：