系列文章目錄

凸優化理論學習一|最優化及凸集的基本概念
凸優化理論學習二|凸函數及其相關概念

---

一、優化問題

（一）標準形式的優化問題

• 優化目標：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^{?}=\infty$
• 如果問題無下界，則$p^{?}=?\infty$
• 如果$f_0(x)=p^{?}$，則可行點$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=\underset{i=0}{\overset{m}{?}}dom{f}_i\cap \underset{i=1}{\overset{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$，都滿足梯度條件：${?}^2{f}_0(x{)}^T(y?x)\ge 0$

這個條件表明，如果 $x$ 是最優解，那么任何與之可行的點 $y$ 的方向上的梯度內積都是非負的。這實際上是凸問題最優解的一個重要性質，稱為一階條件。這種條件確保了最優解的局部性質，即在最優解附近，目標函數不會在可行方向上下降。另一方面，如果 $x$ 滿足這個條件，那么根據凸優化的性質，它意味著 $x$ 是最優解。這個條件表明，如果梯度與任何可行方向的變化都是非負的，那么該點是全局最優解的候選者。

如果梯度 $?f_0(x)$ 在點$x$ 處非零，則它確實定義了可行集 $X$ 在點 $x$ 處的一個支撐超平面。

應用舉例：

• 無約束問題：$x$ 最小化 $f_0(x)$ 當且僅當 $?f_0(x)=0$
• 等式約束問題：$x$ 最小化 $f_0(x)$ 且滿足 $Ax=b$ 當且僅當存在$v$使得：
  $$Ax=b,?f_0(x)+A^{T}v=0$$
• 非負正交坐標系上的的最小化問題：$x$ 最小化 $R_{+}^n$ 上的 $f_0(x)$ 當且僅當：
  • $x$的所有分量非負：$x\ge 0$
  • 對于所有的分量$i$，如果$x_i=0$，則其對應的梯度分量$?f_0(x{)}_i$非負
  • 對于所有的分量$i$，如果$x_i>0$，則其對應的梯度分量$?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^{?}=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～N({\bar{a}}_i,{\Sigma }_i)$，所以$a_i^{T}x～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：