03-凸優化問題

一、一般優化問題
二、凸優化問題
- 2.1 凸優化問題定義
- 2.2 凸優化問題的最優解
- 2.3 等價問題化簡
三、擬凸優化問題
四、典型凸優化問題
- 4.1 線性規劃(LP)
- 4.2 線性分式規劃
- 4.3 二次規劃(QP)
- 4.4 二次約束二次規劃(QCQP)
- 4.5 二次錐規劃(SOCP)
- 4.6 魯棒線性規劃
- 4.7 幾何規劃(GP)
- 4.8 半正定規劃(SDP)
五、向量優化

凸優化從入門到放棄完整教程地址：https://www.cnblogs.com/nickchen121/p/14900036.html

一、一般優化問題

一般優化問題的形式為

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &h_{i}(x)=0, \quad i=1, \ldots, p \end{aligned} \\$

其中 $f_0(x)$ 為目標函式，$f_i(x)$ 為不等式約束函式， $h_i$ 為等式約束函式，優化問題的最優解為

$p^{\star}=\inf \left\{f_{0}(x) | f_{i}(x) \leq 0, i=1, \ldots, m, h_{i}(x)=0, i=1, \ldots, p\right\} \\$

注：$p^*$ 使用 $\inf$ 函式的原因是因為，最優解可能是趨近一個值，

如果 $p^*=\infty$，則問題不可行；如果 $p^*=-\infty$ 則該問題沒有下界，

最優解則有 $f_0(x)=p^*$，區域最優解(local optimal)有

$\begin{aligned} \text{minimize} (\text{over } z) \quad& f_{0}(z) \\ \text{s.t.} \quad&f_{i}(z) \leq 0, \quad i=1, \ldots, m, \quad h_{i}(z)=0, \quad i=1, \ldots, p \\ &\|z-x\|_{2} \leq R \end{aligned} \\$

也即只在一個小的鄰域內考慮優化問題，

注意：

有的優化問題有最小值，但是沒有可行解，比如 $f_0(x)=1/x$；
有的問題根本就沒有最小值，比如 $f_0(x)=-\log x$
有的問題只有區域最小值，比如 $f_0(x)=x^3-3x$

上面提到的優化問題中有等式和不等式約束，這些我們都稱為顯式約束(explicit constraints)

同時由于 $x$ 應屬于各個函式的定義域內，因此還有隱式約束(implicit constraint)，即

$x \in \mathcal{D}=\bigcap_{i=0}^{m} \operatorname{dom} f_{i} \cap \bigcap_{i=1}^{p} \operatorname{dom} h_{i} \\$

注：隱式約束其實就是目標函式 $f_0$ 的定義域，不要忽視了上述 $\mathcal{D}$ 包含了 $f_0$ 的定義域

沒有顯式約束的優化問題被稱為無約束優化問題(unconstrained)，比如

$\text { minimize } \quad f_{0}(x)=-\sum_{i=1}^{k} \log \left(b_{i}-a_{i}^{T} x\right) \\$

是一個無約束優化問題，包含了隱式約束 $a_i^Tx< b_i$，

其實有約束優化問題也可以轉化為無約束優化問題，只需要加一個指示函式，一開始提到的一般優化問題就可以利用 $\delta_C$ 轉化為下面的無約束優化問題，不過這種轉化可能并沒有太大的意義

$\min_x f_0(x)+\delta_{C}(x) \\ \delta_C(x)=\begin{cases}0&f_i(x)\le0,h_i(x)=0 \\ \infty \end{cases} \\$

注：上述的約束優化問題轉化為無約束優化問題，在未來約束優化演算法的時候可能會用到

除了優化問題，還有一種可行解問題(Feasibility problem)，也就是給定一系列約束來尋找是否有可行解

$\begin{aligned} \text {find} \quad& x \\ \text { s.t.} \quad& f_{i}(x) \leq 0,\quad i=1, \ldots, m \\ & h_{i}(x)=0,\quad i=1, \ldots, p \end{aligned} \\$

這實際上也可以轉化為一般優化問題

$\begin{aligned} \text {minimize} \quad& 0 \\ \text { s.t.} \quad& f_{i}(x) \leq 0,\quad i=1, \ldots, m \\ & h_{i}(x)=0,\quad i=1, \ldots, p \end{aligned} \\$

注：可行解問題，就是尋找一個可行域，也就是所有可行解的集合

二、凸優化問題

2.1 凸優化問題定義

注：凸優化問題和普通優化問題的區別就是對目標函式和約束條件做了各種限

凸優化問題(Convex optimization problem)要求目標函式為凸函式，而且定義域為凸集，這樣可以利用凸函式和凸集的優良性質簡化問題，因此凸優化問題的一般形式為

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &Ax=b, \qquad\qquad\qquad\qquad\quad\bigstar \end{aligned} \\$

其中要求目標函式和約束函式 $f_0,f_1,...,f_m$ 均為凸函式，

Remarks：需要注意這里還要求等式約束均為仿射函式，這是因為我們希望定義域是凸集，假設等式約束 $h_i$ 不是線性的，即使 $h_i$ 是凸函式，$\{x|h_i(x)=0\}$ 也不一定是凸集，比如二次等式約束 $\Vert x\Vert_2=r$，得到的定義域就是一個球面，顯然不是一個凸集，這對優化不利，

有時候我們直接拿到的優化問題并不符合上面的形式，但是可以經過化簡得到等價問題，就是凸的了，比如

$\begin{aligned} \text { minimize } \quad& f_{0}(x)=x_{1}^{2}+x_{2}^{2}\\ \text { s.t. } \quad& f_{1}(x)=x_{1} /\left(1+x_{2}^{2}\right) \leq 0\\ &h_{1}(x)=\left(x_{1}+x_{2}\right)^{2}=0 \end{aligned} \\$

經過簡單化簡就有

$\begin{aligned} \text { minimize } \quad& x_{1}^{2}+x_{2}^{2}\\ \text { s.t. } \quad& x_{1} \leq 0\\ &x_{1}+x_{2}=0 \end{aligned} \\$

2.2 凸優化問題的最優解

對于凸優化問題有一個極其重要的性質，就是

凸優化問題的區域最優解就是全域最優解

證明也很簡單，若 $x^*$ 為區域最優解，只需要假設另外一個全域最優解 $y\ne x^*,f(y)$ ，那么利用凸函式的性質，就可以在 $x^*$ 的鄰域內匯出矛盾，如下圖圖示，

凸優化問題的最優解還有一個很好的判據

$x$ 為最優解，當且僅當
$\nabla f_{0}(x)^{T}(y-x) \geq 0 \quad \text { for all feasible } y \\$

證明程序只需要應用凸函式的一階等價定義即可，即 $f(y)\ge f(x)+\nabla f^T(x)(y-x)$，

這個怎么直觀理解呢？還記得我們之前在擬凸函式那里提到的“支撐超平面”嗎？實際上 $f_0(x)$ 定義了一個等高線，由于 $f_0$ 是一個凸函式，因此這個等高線實際上圍成了一個凸集，這個凸集也就是一個下水平集，而這里的 $\nabla f_0(x)$ 就是這個下水平集的一個支撐超平面，正如下圖所示，同時注意，$\nabla f_0(x)$ 也代表著函式指上升的方向，如果說對任意定義域內的 $y$，都有 $\nabla f_{0}(x)^{T}(y-x) \geq 0$ 成立，那么說明我們從 $x$ 走到 $y$ 總會使 $f_0$ 增大，也就是說 $x$ 就是最優解，對應最小值，

注：其實還可以從內積的角度考慮，由于 $\nabla f_0(x)$ 和 $y-x$ 兩者形成鈍角，也就是說 $y-x$ 一定在 $f_0(x)$ 形成的等高線和 $\nabla f_0(x)$ 形成的支撐超平面之內，如果在之外，那么內積就會 $\leq 0$，也就會形成一個鈍角

利用上面這兩個性質，我們可以對很多型別的凸優化問題的最優解有一個認識，

無約束優化問題：對無約束優化問題，$x$ 為最優解，當且僅當

$x\in\text{dom} f_0,\quad \nabla f_0(x)=0 \\$

等式約束優化問題：$\min\quad f_0(x),\qquad s.t.\quad Ax=b$，則有 $x$ 為最優解，當且僅當存在 $\nu \in \mathcal{N}(A)$

$x \in \operatorname{dom} f_{0}, \quad A x=b, \quad \nabla f_{0}(x)+A^{T} \nu=0 \\$

證明：因為 $Ax=b$ 實際上定義了一個超平面，如果 $x$ 為最優解，那么 $\nabla f_0(x)$ 一定沒有這個平面內的分量，也就是說 $\nabla f_0(x)\in \ker(A)^\perp$，也就是說 ${\nabla f_0(x) }^T \nu = 0$，再使用 KKT 條件，即可得到上述結果，

2.3 等價問題化簡

有時原始優化問題比較難，可以通過等價轉換進行簡化，

消去等式約束：比如對一般的凸優化問題，等式約束實際上定義了一個超平面，這可以表示為特解 + 一組基的形式

$Ax=b \iff x=Fz+x_0 \text { for some } z \\$

原始凸優化問題就可轉化為

$\begin{aligned} \text { minimize (over }z) \quad& f_{0}\left(F z+x_{0}\right)\\ \text { s.t. } \quad& f_{i}\left(F z+x_{0}\right) \leq 0, \quad i=1, \dots, m \end{aligned} \\$

添加等式約束：實際上就是上面的一個逆程序，這個程序中需要添加一個等式約束 $y=Ax+b$，由于添加了變數 $y$，會使問題變數數增加，同時優化變數也需要加上 $y$，

引入松弛變數：比如對于線性不等式約束的優化問題

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& a_i^Tx\le b_i,\quad i=1,...,m \end{aligned} \\$

可以引入松弛因子 $s_i$，得到

$\begin{aligned} \text { minimize } \quad& f_{0}(x)\\ \text { s.t. } \quad& a_i^Tx + s_i = b_i,\quad i=1,...,m \\ & s_i \ge0,\quad i=1,...,m \end{aligned} \\$

例子：下面兩個優化問題是等價的嗎？其中 $W^TW=I$

$\min_x f(x)+g(Wx) \\ \min_c f(W^T c)+g(c) \\$

不一定等價，由于 $W^TW=I$，若 $W$ 為方陣，則二者等價，否則說明 $W\in R^{m\times n},m\ge n$，也即 $W$ 為一個瘦高型的矩陣，如果我們取 $f\equiv 0$，那么很顯然 $\min_x g(Wx)$ 與 $\min_c g(c)$ 并不等價，因為 $W$ 列不滿秩，

epigraph 形式：任意標準形式的凸優化問題都可以轉化為下面的形式

$\begin{aligned} \text { minimize } \quad& t\\ \text { s.t. } \quad& f_{0}(x) -t \leq 0\\ \quad& f_{i}(x) \leq 0, \quad i=1, \ldots, m\\ &Ax=b \end{aligned} \\$

這種變化很重要，可以將優化目標轉化為約束函式，對于后面一些典型凸優化問題的轉化很有用，

對某些變數最小化：實際上就是對于存在多個優化變數時，提前通過計算消去一些變數

$\begin{aligned} \text { minimize } \quad& f_{0}\left(x_{1}, x_{2}\right)\\ \text { s.t. } \quad& f_{i}\left(x_{1}\right) \leq 0, \quad i=1, \dots, m \end{aligned} \iff \begin{aligned} \text { minimize } \quad& \tilde{f}_{0}\left(x_{1}\right)\\ \text { s.t. } \quad& \tilde{f}_{i}\left(x_{1}\right) \leq 0, \quad i=1, \dots, m \end{aligned} \\$

其中 $\tilde{f}_0(x_1)=\inf_{x_2}f_0(x_1,x_2)$，

三、擬凸優化問題

擬凸函式跟凸函式有一些相似的性質，尤其是擬凸函式的任意下水平集都是凸集，因此很多時候對于擬凸問題，也可以用凸優化的一些方法有效解決，

擬凸優化問題(Quasi convex optimization) 的一般定義為與凸優化基本相同，只不過目標函式 $f_0(x)$ 可以是擬凸函式，但約束函式 $f_1,...,f_m$ 仍需要是凸函式，

Remarks：我個人覺得這里其實約束函式也可以是擬凸函式？因為即使是擬凸函式，$f_i(x)\le0$ 也可以得到凸的定義域？

但是此時擬凸優化問題就沒有凸優化那么好的性質了，比如區域最優解不一定是全域最優解

注：盡管如此，由于擬凸函式任意下水平集 $\{x|f(x)\le t\}$ 都是凸集，我們可以利用這個性質將其轉化為凸函式 $\phi_t(x)\le0$ 來表示，由此就可以用凸優化來求解，

例子

最簡單的例子，擬凸函式 $f(x)$ 的下水平集可以表示為 $\{x|f(x)\le t\}$，我們可以用函式 $\phi_t(x)\le0$ 來等價表示

$\phi_t(x)=\begin{cases}0 & f(x)\le t \\ \infty \end{cases} \\$

不過這種表示方法意義不大，這個函式不連續不可微，我們還有其他的表示方法比如

$\phi_t(x)=\text{dist}\left(x,\{z|f(z)\le t\}\right) \\$

另外，如果擬凸函式 $f_0(x)$ 有一些特定的性質，比如 $f_0(x)=p(x)/q(x)$，其中 $p(x)$ 為凸函式，而 $q(x)>0$ 為凹函式（容易證明此時 $f_0$ 為擬凸函式），那么我們還可以取 $\phi_t(x)$ 為

$\phi_t(x)=p(x)-t q(x) \\$

擬凸優化問題的求解

假如當前擬凸優化問題的最優解為 $p^*$，那么對于尋找可行解問題

$\begin{aligned} \text{find} \quad& x \\ s.t. \quad& \phi_{t}(x) \leq 0, \quad f_{i}(x) \leq 0, \quad i=1, \ldots, m, \\ &A x=b \end{aligned} \\$

如果 $p^* \leq t$，則該問題有可行解，如果 $p^* \gt t$ ，則沒有可行解，因此對于原始凸優化問題，可以利用二分法迭代求解

注：如果能找到 $x$，表明問題存在可行解，由于 $f_0(x) \leq t$ ，自然可以得出 $p^* \leq t$，不存在可行解，則就是 $f_0(x) \gt t$，則就是 $ p^* \gt t$

四、典型凸優化問題

4.1 線性規劃(LP)

注：目標函式和約束函式都是線性的

線性規劃(Linear program)問題的一般形式為

$\begin{aligned} \text{minimize} \quad& c^{T} x+d \\ \text{s.t.} \quad& G x \preceq h \\ &A x=b \end{aligned} \\$

聯系我們前面提到的凸優化問題最優解性質，有 $c^T(y-x)\ge0$，也即目標函式的等高線是一系列超平面

例子 1：對于 piecewise-linear minimization 問題(無約束優化)

$\text { minimize } \max _{i=1, \ldots, m}\left(a_{i}^{T} x+b_{i}\right) \\$

可以轉化為

$\begin{aligned} \text { minimize} \quad& t\\ \text { s.t.} \quad& a_i^Tx + b_i \le t \end{aligned} \\$

例子 2：多面體的切比雪夫中心(Chebyshev center)

$\mathcal{P}=\left\{x | a_{i}^{T} x \leq b_{i}, i=1, \dots, m\right\} \\$

可以用優化問題表示為

$\begin{aligned} \text{maximize} \quad& r\\ \text{s.t.} \quad& a_{i}^{T} x_{c}+r\left\|a_{i}\right\|_{2} \leq b_{i}, \quad i=1, \ldots, m \end{aligned} \\$

4.2 線性分式規劃

注：目標函式是線性分式函式，約束函式是線性函式

線性分式規劃(Linear-fractional program) 的一般形式為

$\begin{aligned} \text{minimize} \quad& f_0(x) \\ \text{s.t.} \quad& G x \preceq h \\ &A x=b \end{aligned} \\$

其中 $f_0(x)=\frac{c^Tx+d}{e^Tx+f},\quad \text{dom}f_0(x)=\{x|e^Tx+f>0\}$，這個問題可以等價轉化為線性規劃，

4.3 二次規劃(QP)

注：目標函式是二次的，約束函式是線性的

二次規劃(Quadratic program)的一般形式為

$\begin{aligned} \text{minimize} \quad& (1/2)x^TPx+q^Tx+r \\ \text{s.t.} \quad& G x \preceq h \\ &A x=b \end{aligned} \\$

其中 $P\in S_{+}^n$，

與線性規劃不同的是，目標函式的等高線變成了橢球面

例子：最小二乘就是最經典的二次規劃的例子，$\min \Vert Ax+b\Vert_2^2$

4.4 二次約束二次規劃(QCQP)

注：目標函式和不等式約束函式都是二次的

二次約束二次規劃(Quadratically constrained quadratic program)的一般形式為

$\begin{aligned} \text{minimize} \quad& (1/2)x^TP_0x+q_0^Tx+r_0 \\ \text{s.t.} \quad& (1/2)x^TP_ix+q_i^Tx+r_i \le 0 \\ &A x=b\end{aligned} \\$

其中 $P_i\in S_{+}^n$，

一般會限制 $P_1,...,P_m\in S_{++}^n$，也就是不能為 0 矩陣(有什么意義嗎？不關鍵)

4.5 二次錐規劃(SOCP)

注：不等式約束是二階錐約束，也就是是一個二階錐

二次錐規劃(Second-order cone programming)的一般形式為

$\begin{array}{cl} \text { minimize } & f^{T} x \\ \text { s.t. } & \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, \quad i=1, \ldots, m \\ & F x=g \end{array} \\$

其實 SOCP 比前面幾種問題都更廣泛，他們都可以看作是 SOCP 的一種情況

4.6 魯棒線性規劃

對于優化問題，有時候我們的引數比如 $a_i,b_i$ 等都是不確定的，他們可能是在一定范圍內屬于某個集合，也可能是一個隨機變數，這個時候就引入了魯棒優化的概念，

注：魯棒優化，其實就是對于不確定的引數 $a_i$，我們要求對于 $a_i$ 的所有可能值都考慮進去，再對問題進行轉化，然后使其變成一個穩定的線性規劃

對于線性規劃問題來說，比如

$\begin{aligned} \text{minimize} \quad& c^{T} x+d \\ \text{s.t.} \quad& a_i^Tx\le b_i \end{aligned} \\$

一種是考慮確定性模型，也即

$\begin{aligned} \text{minimize} \quad& c^{T} x+d \\ \text{s.t.} \quad& a_i^Tx\le b_i \text{ for all } a_i\in\mathcal{E}_i \end{aligned} \\$

如果 $\mathcal{E}_{i}=\left\{\bar{a}_{i}+P_{i} u |\|u\|_{2} \leq 1\right\}$ 是一個橢球，則該問題可以轉化為一個 SOCP 問題

$\begin{aligned} \text{maximize} \quad& c^Tx\\ \text{s.t.} \quad& \bar{a}_{i}^{T} x+\left\|P_{i}^Tx\right\|_{2} \leq b_{i}, \quad i=1, \ldots, m \end{aligned} \\$

另一種是隨機性模型，即

$\begin{aligned} \text{minimize} \quad& c^{T} x \\ \text{s.t.} \quad& \operatorname{prob}\left(a_{i}^{T} x \leq b_{i}\right) \geq \eta, \quad i=1, \ldots, m \end{aligned} \\$

假如 $a_i\sim\mathcal{N}(\bar{a}_i,\Sigma_i)$ 服從高斯分布，則該問題同樣可以轉化為一個 SOCP 問題

$\begin{aligned} \text{maximize} \quad& c^Tx\\ \text{s.t.} \quad& \bar{a}_{i}^{T} x+\Phi^{-1}(\eta)\left\|\Sigma_{i}^{1 / 2} x\right\|_{2} \leq b_{i}, \quad i=1, \ldots, m \end{aligned} \\$

4.7 幾何規劃(GP)

首先定義單項式函式(monomial function) $f(x)=cx_1^{a_1}x_2^{a_2}\cdots x_n^{a_n},\quad \text{dom}f=R_{++}^n$，其中 $c>0,a_i$ 為任意實數；

正項式函式(posynomial function) $f(x)=\sum_k c_k x_1^{a_{1k}} x_2^{a_{2k}}\cdots x_n^{a_{nk}},\quad \text{dom}f=R_{++}^n$

注：正項式其實可以看成多項式，因為 $x_i$ 的項式個數是不確定的

然后就可以定義幾何規劃(geometric program)了

$\begin{aligned} \text{minimize} \quad& f_0(x) \\ \text{s.t.} \quad& f_i(x)\le 1,\quad i=1,...,m \\ &h_i(x)=1,\quad i=1,...,p \end{aligned} \\$

其中 $f_i$ 為正項式，$h_i$ 為單項式，

首先說明，這個優化問題并不一定是凸的，因為 $a_i$ 可以取任意實數，比如 $a_i=1/2$ 就不是凸的，那么我們這里為什么要介紹這個問題呢？別急，一會稍微做一個變換我們就可以解決這個問題了，那還有一個問題，這種形式的函式有什么意義呢？為什么專門引入這樣一種非凸優化問題呢？我們看這個單項式函式 $cx_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}$，像不像體積或者面積的運算式？這也是他被稱為“幾何規劃”的原因吧，

好，現在我們怎么把這個非凸的問題轉化為凸優化問題呢？加個 $\log$ 就行啦！對單項式來說

$\begin{aligned} \log f(x) &= \sum_i a_i \log x_i +\log c = a^Ty+b \\ f(x) &= e^{a^Ty+b} \end{aligned} \\$

對多項式來說

$\log f(x)=\log \left(\sum_i \exp(a_i^Ty+b_i)\right) \\$

這么一來，取完對數后的問題就是凸的了，而且我們也知道 $\log$ 是一個單射函式，原始優化問題就變成了

$\begin{aligned} \text{minimize} \quad& \log \left(\sum_k \exp(a_{0k}^Ty+b_{0k})\right) \\ \text{s.t.} \quad& \log \left(\sum_k \exp(a_{ik}^Ty+b_{ik})\right)\le 0,\quad i=1,...,m \\ &Gy+d=0 \end{aligned} \\$

注：其實絕大多數情況看到連乘，都可以想到 $\log$ 函式

4.8 半正定規劃(SDP)

注：半正定規劃的不等式約束是定義在凸錐上的，其他的和普通的凸優化問題極其相似

前面所講到的都是標量函式，約束條件也都是函式值與 0 比大小，而前面的章節中我們也提到了廣義不等式，對于正常錐則可以定義不等號，所以我們可以定義一種凸優化問題，這種凸優化問題的約束條件不再是普通不等式，而是廣義不等式

$\begin{aligned} \text{minimize} \quad& f_0(x) \\ \text{s.t.} \quad& f_i(x)\preceq_{K_i} 0,\quad i=1,...,m \\ &Ax=b \end{aligned} \\$

其中 $f_0:R^n\to R$ 為凸函式，$f_i:R^n\to R^{k_i}$ 為關于正常錐 $K_i$ 的凸函式，

注意這種帶有廣義不等式約束的凸優化問題與普通凸優化問題有著相同的性質，比如可行集為凸的，區域最優解就是全域最優解等，

一種簡單形式的凸優化問題就是向量形式的，也就是說目標函式與約束都是仿射函式

$\begin{aligned} \text{minimize} \quad& c^Tx \\ \text{s.t.} \quad& Fx+g\preceq_K 0 \\ &Ax=b \end{aligned} \\$

這種向量形式的廣義不等式實際上就是對每個元素進行比較，因此實際上可以按照每一行拆分成多個不等式，如果取 $K=R_+^m$ 就與普通的線性規劃(LP)沒什么區別了，

接下來要介紹的就是重頭戲半正定規劃(Semide?nite program)了，我們取 $K=S^n_+$

$\begin{aligned} \text{minimize} \quad& c^Tx \\ \text{s.t.} \quad& x_1 F_1+x_2F_2+\cdots+x_nF_n+G\preceq_K 0 \\ &Ax=b \end{aligned} \\$

其中 $F_i,G\in S^n$，

這里的不等式約束就是大名鼎鼎的線性矩陣不等式(linear matrix inequality, LMI)，

如果說我們現在有兩個不等式約束怎么辦呢？

$x_1 \hat{F}_1+x_2\hat{F}_2+\cdots+x_n\hat{F}_n+G\preceq_K 0 \\ x_1 \tilde{F}_1+x_2\tilde{F}_2+\cdots+x_n\tilde{F}_n+G\preceq_K 0 \\$

合成一個更大的矩陣就可以了，實際上這種操作在后面也會經常見到

$x_{1}\left[\begin{array}{cc} \hat{F}_{1} & 0 \\ 0 & \tilde{F}_{1} \end{array}\right]+x_{2}\left[\begin{array}{cc} \hat{F}_{2} & 0 \\ 0 & \tilde{F}_{2} \end{array}\right]+\cdots+x_{n}\left[\begin{array}{cc} \hat{F}_{n} & 0 \\ 0 & \tilde{F}_{n} \end{array}\right]+\left[\begin{array}{cc} \hat{G} & 0 \\ 0 & \tilde{G} \end{array}\right] \preceq 0 \\$

這是因為分塊對角矩陣為正定矩陣等價于每一個子塊都為正定矩陣，

例子 1：半正定規劃之所以重要，是因為他的形式更廣泛，前面說 SOCP 包含了 LP、QP、QCQP，而半正定規劃則包含了 SOCP！比如下面的 SOCP 問題就可以轉化為 SDP

$\begin{aligned} SOCP:\qquad \text{minimize}&\quad f^{T} x \\ \text{s.t.}&\quad \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, \quad i=1, \ldots, m \\ \\ SDP:\qquad \text{minimize}&\quad f^{T} x \\ \text{s.t.}&\quad \left[\begin{array}{cc} \left(c_{i}^{T} x+d_{i}\right) I & A_{i} x+b_{i} \\ \left(A_{i} x+b_{i}\right)^{T} & c_{i}^{T} x+d_{i} \end{array}\right] \succeq 0, \quad i=1, \ldots, m \end{aligned} \\$

例子 2：最小化矩陣的最大特征值 $\min \lambda_{\max}(A(x))$，也可以通過半正定規劃來描述

$\begin{aligned} \text{minimize} \quad& t \\ \text{s.t.} \quad& A(x)\preceq tI \end{aligned} \\$

其中優化變數為 $x\in R^n,t\in R$，這種等價轉化是因為 $\lambda_{\max}(A)\le t\iff A\preceq tI$，

例子 3：最小化矩陣范數 $\min \Vert A(x)\Vert_2=\left(\lambda\left(A\left(x\right)^TA\left(x\right)\right)\right)^{1/2}$，也可以等價為SDP

$\begin{aligned} \text{minimize}&\quad t \\ \text{s.t.}&\quad \left[\begin{array}{cc} t I & A(x) \\ A(x)^T & tI \end{array}\right] \succeq 0 \end{aligned} \\$

五、向量優化

注：向量優化的函式都是基于錐定義的，也就是它完全是從一個高維的角度看待凸優化問題，因此在進行向量優化的時候，需要注意向量優化的可行解也是在錐上定義的，因此就最優解可能會出現兩種結果，也就是最優解可能是一個集合 $\mathcal{O}$，如果 $f_0(x)$ 是關于錐的最小元，則稱作最優解；如果 $f_0(x)$ 是關于錐的極小元，則稱為 Pareto optimal，

前面介紹的所有優化問題的目標函式都是標量（盡管約束可能會出現廣義不等式），如果目標函式為向量怎么辦呢？前面的章節中我們介紹了廣義的凸函式，同樣也是基于錐定義的（實際上高維空間中“比大小”我們一般都需要通過錐來定義），

一般的向量優化問題可以表示為

$\begin{alignat}{} &\text{minimize(w.r.t. K)} \quad& f_0(x) \\ &\text{s.t.} \quad& f_i(x)\le 0,\quad i=1,...,m \\ & &h_i(x)=0,\quad i=1,...,p \end{alignat} \\$

凸的向量優化問題只需要將上面的等式約束換為仿射函式 $Ax=b$，同時要求 $f_0$ 為 $K-$convex 的，$f_1,...,f_m$ 為凸的，

向量約束優化問題的最優解相當于在下面的集合中尋找最優解

$\mathcal{O}=\{f_0(x)|x \text{ feasible}\} \\$

前面在將廣義不等式和凸集的時候，我們講過最小元和極小元的概念，這兩個概念是不是已經忘得差不多啦！反正我基本全忘了......讓我們來復習一下，

復習：最小元與極小元
下面兩幅圖分別表示最小元和極小元

利用對偶錐，我們可以獲得最小元的等價定義，即
$x$ 是集合 $S$ 關于 $\preceq_{K}$ 的最小元 $\iff$ 對任意的 $\lambda \succ_{K*} 0$，$x$ 為 $\lambda^Tz$ 在集合 $S$ 上的唯一最小解

什么意思呢？也就是說任意的 $\lambda\in K^*$，實際上都代表了一個法向量，也就是一個支撐超平面，如果 $x$ 是最小元，則意味著對任意一個 ($K^*$所定義的) 支撐超平面來說，$x$ 都是支撐點，就像下面這條幅圖一樣

而極小元的定義是什么呢？

充分條件：若對于某些 $\lambda \succ_{K*} 0$，$x$ minimizes $\lambda^Tz$ over $S$，$\Longrightarrow$$x$ 為極小元
必要條件：$x$ 為凸集$S$ 的極小元，$\Longrightarrow$ 存在非 0 的 $\lambda \succ_{K*} 0$ 使得 $x$ minimizes $\lambda^Tz$ over $S$

我們來看充分條件，只需要存在某一個 $\lambda\in K^*$，使得 $x$ 為對應支撐超平面的支撐點就可以了，比如下面這幅圖，藍色的點，我們可以找到這樣一個藍色的支撐超平面，使其為支撐點，所以它就是一個極小元；而對于紅色的點來說，無論如何不可能找到一個支撐超平面，使其為支撐點，因此他就有可能不是極小元，因為這只是充分條件（對這個例子來說他就不是極小元），

簡單總結一下：

最小元：無論沿著錐 $K^*$ 里邊哪一個方向走，$x$ 都是最小值點，那么他就是最小元；
極小元：如果沿著其中某一個方向走，$x$ 是最小值點，那么他就是極小元，

復習完了最小元和極小元，不要忘了正事，我們要考慮向量約束優化問題中的最優解

$\mathcal{O}=\{f_0(x)|x \text{ feasible}\} \\$

這是一個集合，如果 $f_0(x)$ 是關于錐 $K$ 的最小元，那么對應的 $x$ 就被稱為最優解(optimal)；如果 $f_0(x)$ 是關于錐 $K$ 的極小元，那么對應的 $x$ 則被稱為 Pareto optimal，

例子：假如我們取 $K=R_+^q$，其中

$f_0(x)=(F_1(x),...,F_q(x)) \\$

相當于有 $q$ 個不同的目標 $F_i$，最好的情況當然是希望 $F_i$ 都是最小的，

若 $x^*$ 為最小元（存在）就說明任意其他可行解 $y$ 都有 $f_0(x^*)\le f(y)$，正是我們希望的；

而如果只能得到極小元 $x^{po}$，就有對任意可行解 $y$，$f_0(y)\preceq f_0(x^{po})\Longrightarrow f_0(x^{po})=f(y)$，這是什么意思呢？

首先不可能存在另一個 $y$ 使得每一個元素都有 $F_i(y)\le F_i(x^{po})$，要不然 $x^{po}$ 出現在這里的意義是什么？我們直接選擇 $y$ 作為極小元不就好了嗎？如果存在那也頂多是 $F_i(y)=F_i(x^{po}),\forall i$，這種情況下 $y$ 跟 $x^{po}$ 其實沒什么區別了，
第二點，有可能存在某些 $y$，滿足對一些 $i$ 有 $F_i(y)>F_i(x^{po})$，而對另一些 $i$ 則有 $F_i(y)<F_i(x^{po})$ ，這意味著 $y$ 在某些方面表現得比 $x^{po}$ 差，但在另一些方面則表現得更好，這實際上體現了我們在不同因素之間的一種權衡，

注：上面用數學術語抽象的講了 Pareto optimal，很難理解，這里對 Pareto optimal 做一種現實意義的解釋，由于絕大多數現實問題需要考慮很多的條件的，比如房價需要考慮價格、地區、環境等，那如果我們傾向于不同的考慮因素，則會形成不同的 Pareto optimal，畢竟現實問題是很難出現最優解的

參考文獻：Stephen Boyd, Lieven Vandenberghe: Convex Optimization

參考資料：https://www.zhihu.com/column/convex

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288271.html

標籤：其他

上一篇：TensorFlow簡介

下一篇：TensorFlow簡介