04 凸優化問題

目錄
4.1 優化問題
4.2 凸優化問題
應用
4.3 線性規劃問題
4.4 二次優化問題
4.5 幾何規劃

4.6 廣義不等式約束
4.7 向量優化

4.1 優化問題

（一）優化問題的定義

4.1.1 基本術語

Def 1 優化問題的定義[優化變量、目標函數、不等式約束、等式約束、無約束問題]
注：

定義域、可行域（可行\不可行）的定義；

最優值的定義、$p?=+\infty$問題不可行、$p?=?\infty$問題無下界；

最優點、局部最優點、ε最優的定義
（1）最優點、最優集（最優值可達/不可達）
（2）ε-次優、ε-次優集
（3）局部最優

Def 2 冗余約束、積極約束[約束起/不起作用]
Def 3 可行性問題[判定可行解的存在性、約束的一致性]

4.1.2 優化問題的標準表示

Def 4 優化問題標準形式的定義：不等式和等式約束右端值為零
示例：框約束問題
Def 5 極大化問題的定義及其標準化

（二）優化問題的等價問題（4.1.3）

Def 6 等價問題的定義：可以從一個問題的解得到另一個問題的解
簡單示例：伸縮變換

產生等價問題的變換

（1）變量變換

定理1*：設$\Phi ：R_n\to R_n$是一一映射，其像包含問題的定義域D，即$D?\Phi (dom\Phi )$，定義函數${\overline{f}}_i$和${\overline{h}}_i$為${\overline{h}}_i=h_i(\Phi (z)),i=0,...,m，$${\overline{f}}_i=f_i(\Phi (z)),i=0,...,p$。標準形式問題和該問題通過變量變換x=Φ(z)聯系，兩個問題等價。

（2）函數的變換（目標函數和約束函數）

定理2：設${\psi }_0:R\to R$單增；${\psi }_1,...,{\psi }_m:R\to R$滿足：當且僅當$u\le 0$時，${\psi }_i(u)\le 0$；${\psi }_{m+1},...,{\psi }_{m+p}:R\to R$滿足：當且僅當$u=0$時，${\psi }_i(u)=0$，定義函數${\overline{f}}_i$和${\overline{\psi }}_i$為${\overline{f}}_i={\psi }_i(f_i(z)),i=0,...,m，$${\overline{h}}_i={\psi }_{m+i}(h_i(z)),i=0,...,p$。標準形式問題和該問題等價。

示例：最小范數和最小范數平方是等價的

（3）松弛變量

定理3：將不等式約束轉化為等式約束：$f_i\le 0$等價于存在一個$s_i\ge 0$滿足$f_i(x)+s_i=0$。即將每個不等式約束轉換為一個等式和一個非負約束，標準形式問題和該問題等價。

（4）消除等式約束

定理4：用參數$z\in R^k$顯式地參數化等式約束$h_i(x)=0,i=1,...,p$的解，那么可以從原問題中消除等式約束。x滿足該式等價于存在$z\in R^k$使得$x=\Phi (z)$.

特例：消除線性等式約束

定理5：如果等式約束是線性的，即Ax=b，如果$b\in /R(A)$，則原問題無解；否則，令R(F)=N(A)，則其通解可以表示為$Fz+x_0$。

（5）引入等式約束

定理6（原問題復合函數的分解）：將原問題中目標函數$f_0(A_{0}x+b_0)$的$A_{0}x+b_0$用$y_0$表示，不等式約束$f_i(A_{i}x+b_i)\le 0$的$A_{i}x+b_i$用$y_i$表示，并將該等式作為新的約束。

（6）優化部分變量

定理7（先優化一部分變量后優化另一部分變量）：由于$in{f}_{x,y}f(x,y)=in{f}_{x}in{f}_{y}f(x,y)$，可以通過先優化一部分變量再優化另一部分變量來達到優化一個函數的目的。

（7）上境圖問題形式

定理8：將原優化問題改為min t, subject to $f_0(x)?t\le 0$。

（8）隱式與顯式約束

定理9：標準形式問題可以表示為無約束問題，定義域由可行集限定，該目標函數由于定義域可能不為開集而不可微；對于隱式約束的問題，可以將其顯式化。

注：這兩個問題不相同

（三）參數與諭示問題描述（4.1.4）

參數問題描述[函數參數給定，可確定問題]

諭示模型[不知顯式的f，需要詢問諭示；可知部分先驗信息]

4.2 凸優化問題

（一）凸優化問題的定義（4.2.1）

Def 7 標準形式的凸優化問題（凸優化問題）的定義

定理10（可行集的性質）： 凸優化問題的可行集是凸的。

Def 8 擬凸優化問題的定義：目標函數擬凸而非凸

定理11（最優集的性質）：由于凸\擬凸問題的目標函數下水平集是凸集，又根據定理10，其ε-次優集是凸的，且最優集是凸的。如果目標函數嚴格凸，那么最優解包含至多一個點。

注：凹/擬凹最大化問題的定義

凸優化問題的抽象形式

Def 9 抽象的凸優化問題：凸集上極小化凸函數的問題

定理12：抽象的凸優化問題可等價變形為標準凸優化問題（凸優化問題）

注：抽象的凸優化問題不是凸優化問題

（二）凸優化問題的最優解

4.2.2 局部最優解與全局最優解

定理13：凸優化問題的任意局部最優解是全局最優解

4.2.3 可微函數$f_0$的最優性準則

定理14（最優性條件）：凸優化問題的目標函數$f_0$是可微的，X表示可行集。x是最優解當且僅當$x\in X$且$?f_0(x{)}^T(y?x)\ge 0$，對于任意$y\in X$。

最優性條件示例

（1）無約束問題

定理15：對于無約束的凸優化問題，最優化條件可以簡化為$?f_0(x)=0$。

示例：
1.無約束二次規劃；
2.解析中心；

（2）只含等式約束的問題

定理16：對于只含等式約束不含不等式約束的問題，最優性條件可以表示為：
$?f_0(x)\in R(A^T)，且Ax=b$。

（3）非負象限中的極小化

定理17：對于非負象限中的極小化問題，最優性條件可以表示為：
$x\ge 0,?f_0(x)\ge 0,x_i(?f_0(x){)}_i=0$。

（三）等價的凸問題（4.2.4）

（1）消除等式約束

定理18：凸問題的等式約束是線性的，即消除線性等式約束，和優化問題的消除等式約束相同。

（2）引入等式約束

定理19：凸優化問題引入的等式約束必須是線性的，得到的優化問題的凸優化問題。

（3）松弛變量

定理20：如果原不等式約束是線性的，那么引入松弛變量，得到的優化問題是凸優化問題。

（4）上境圖問題形式

定理21：上境圖問題的形式中目標函數是線性的，新的約束函數是(x,t)上的凸函數，所以該問題是凸問題。

（5）極小化部分變量

定理22：如果原問題的目標函數是$x_1,x_2$上的聯合凸函數，并且$f_i,i=1,...,m_1,{\overline{f}}_i,i=1,...,m_2$，那么極小化部分變量的問題是凸問題。

（四）擬凸優化問題（4.2.5）

1. 擬凸優化問題的最優解

（1）局部最優解與全局最優解

定理23：擬凸優化問題的局部最優解不一定就是全局最優解[反例]。

（2）最優性條件

定理24（充分條件）：令X表示擬凸優化問題的可行集，如果$x\in X$，$?f_0(x{)}^T(y?x)>0$，對于任意$y\in$X/{x}。

2. 通過凸可行性問題求解擬凸優化問題

定理25：可以通過求解凸可行問題判斷擬凸優化問題的可行性，即得出最優值p*大于或者小于給定值t。

求解方法：二分法

4.3 線性規劃問題

Def 10 線性規劃問題（LP）的定義及幾何含義

線性規劃的標準形式與不等式形式

Def 11 標準形式：不等式約束是分量的非負約束；
Def 12 不等式形式：線性規劃問題沒有等式約束；

將線性規劃轉換為標準形式

step 1. 引入松弛變量；
step 2. 將變量表示為兩個非負變量$x^{+},x^{?}$的差；

4.3.1 示例

（1）食譜問題

（2）多面體的Chebyshev中心

Def 13 多面體內部最大球中心

（3）動態活動計劃

（4）Chebyshev不等式

滿足先驗知識的分布下$E{f}_0(X)$的最小可能值

（5）分片線性極小化

4.3.2 線性分式規劃

Def 14 線性分式規劃的定義
ps. 線性分式規劃問題是擬凸優化問題

1. 轉換為線性規劃

定理26：線性分式規劃可以轉換為線性規劃問題

2. 廣義的線性分式規劃

Def 15 廣義線性分式規劃的定義：目標函數是r個線性分式函數的最大值
示例：Von Neumann增長問題

4.4 二次優化問題

4.4.1 二次規劃（QP）

Def 16 二次規劃（QP）的定義
Def 17 二次約束二次規劃（QCQP）的定義

示例

（1）最小二乘及回歸

Def 18 回歸分析（最小二乘逼近）
Def 19 約束回歸（約束最小二乘）

（2）多面體間距離

（3）方差定界（4.3.1示例(4)）

給定先驗知識的約束下，最大化方差

（4）關于隨機費用的線性規劃

Def 20 隨機費用函數
Def 21 極小化風險敏感費用

（5）Markowitz投資組合優化

Def 22 投資組合優化問題的定義：達到最小可接收平均回報率的約束下尋找極小化回報方差
擴展：（1）允許空頭；（2）考慮線性交易成本；

4.4.2 二階錐規劃（SOCP）

Def 23 二階錐規劃的定義
示例
（1）魯棒線性規劃
（2）隨機約束下的線性規劃
（3）極小表面

4.5 幾何規劃（GP）

$可以將不是凸優化的問題（幾何規劃）轉換為凸優化問題$
Def 24 單項式、多項式的定義

4.5.2 幾何規劃的定義

Def 25 幾何規劃的定義
Def 26 幾何規劃的擴展：可以轉換為GP的問題

4.5.3 凸形式的幾何規劃（轉換為凸問題）

定理26：可以將幾何規劃問題轉換為凸問題

Def 27 凸形式的幾何規劃定義（對比于 正項式形式的幾何規劃）

示例

（1）Frobenius范數的對角化伸縮
ps. 矩陣A的Frobenius范數定義為矩陣A各項元素的絕對值平方的總和
（2） 懸梁臂的設計
（3）通過Perron-Frobenius定理極小化譜半徑

定理27（Perron-Frobenius定理）*：非負矩陣A具有等于其譜半徑（特征值最大幅值）的正實數特征值${\lambda }_{pf}$。

定理28：Perron-Frobenius特征值${\lambda }_{pf}$決定了當$k\to \infty$時，$A^k$增長或消退的漸進速率。

定理29（非負矩陣理論的基本結果）：Perron-Frobenius特征值${\lambda }_{pf}$由 ${\lambda }_{pf}$=inf{$\lambda |Av\le \lambda v$對某些$v\ge 0$}給出。

優化問題：選擇x以極小化A(x)的Perron-Frobenius特征值，其中A的元素為某些基本變量x的正項式函數。根據定理27和29可以將該問題轉換為GP。

示例：細菌數量動態特性的簡單模型
思路：最大化細菌數量衰減速率$\to$由定理28，目標函數為Perron-Frobenius特征值

4.6 廣義不等式約束

（一）廣義不等式約束

Def 28 廣義不等式意義下的凸優化問題：將不等式約束函數擴展為向量并利用廣義不等式
性質：

定理30：可行集、任意下水平集和最優集是凸集。

定理31：廣義不等式意義下的凸優化問題的任意局部最優集是全局最優集

定理32：對于可微函數$f_0$的最優性條件與上相同。

（二）錐形式問題（線性規劃的推廣）

4.6.1 錐形式問題

Def 29 線性目標函數和仿射的廣義不等式約束函數

ps. 如果K是非負象限，則為線性規劃。

錐形式問題的標準形式與不等式形式

Def 30 標準形式：標準形式的錐形式問題
Def 31 不等式形式：不等式形式的錐形式問題
.

4.6.2 半定規劃（錐形式問題的特例）

Def 32 半定規劃的定義：K為半正定矩陣的錐形式問題

半定規劃的標準形式與不等式形式

Def 33 標準形式：標準形式的半定規劃
Def 34 不等式形式：不等式形式的半定規劃

多線性矩陣不等式與線性不等式

Def 35 線性目標，等式、不等式約束、多個線性矩陣不等式約束的問題

定理33：將該問題轉換為一個SDP問題

4.6.2 示例

（1）二階錐規劃

定理34：二階錐規劃可以轉換為錐形式問題

（2）矩陣范數的最小化

（3）矩問題轉換為SDP問題

Def 36 隨機變量的矩
Def 37 矩問題（moment problem）指研究概率分布是否被其各階矩惟一決定的問題

定理35*：存在R上的概率分布使得$x_k=E{t}^k,t=0,...,2n$，那么$x_0=1$，并且Hankel矩陣半正定。

定理36*：（1）如果$x_0=1$，并且Hankel矩陣正定，那么存在R上的概率分布使得$x_k=E{t}^k,t=0,...,2n$；（2）如果$x_0=1$，并且Hankel矩陣半正定，那么存在R上的概率分布序列收斂到x，其中$x_k=E{t}^k,t=0,...,2n$

思路：已知R上的概率分布的矩，轉化為SDP問題
問題：不知R上的概率分布p(t)，但已知其矩的界，計算Ep(t)的最大和最小值

（4）不完全協方差信息下的投資組合風險界定

經典的投資組合問題(4.4.1示例5)：投資組合x是優化變量，在最小平均收益和其他約束條件下極小化風險。
風險界定問題：假設投資組合已知，但關于協方差矩陣Σ只有部分信息（先驗信息，即約束條件），在滿足條件的所有協方差矩陣中，我們投資的最大風險是多少？

定理37：在滿足給定界的所有協方差矩陣中，投資的最大風險問題可以轉化為SDP問題。

關于Σ凸的先驗信息 示例

已知特定投資組合的方差；

包含估計誤差的影響；

影響因素模型；

關于系數的信息；

（5）圖的最速混合馬氏鏈

Def 38 無向圖的定義
Def 39 無向圖馬氏鏈、轉移狀態矩陣、平衡分布的定義

定理38（混合速率）：馬氏鏈狀態X(t)的分布收斂到平穩分布(1/n)1的情況由P的第二大特征值，即r=max{${\lambda }_2,?{\lambda }_n$}決定。稱r為馬氏鏈的混合速率。如果r=1，那么X(t)的分布不必收斂到(1/n)1，當r<1，分布漸進地以$r^t$逼近(1/n)1。小的r使得馬氏鏈更快的混合。

圖的最速混合馬氏鏈問題：尋找轉移狀態矩陣以極小化r，使得圖的馬氏鏈更快的收斂到平穩分布。

定理39：圖的最速混合馬氏鏈問題可以轉化為SDP問題

4.7 向量優化（向量目標函數）

（一）廣義和凸的向量優化問題

Def 40 廣義向量優化問題的定義
Def 41 凸向量優化問題
注：目標函數值不一定能比較

（二）最優解與值

4.7.2 最優值與解

Def 42 可達目標值集合、最優解的定義：參照最小元

定理40：點x是最優的，當且僅當它是可行的并且可達目標值集合包含于$f_0(x)+K$

示例：最優線性無偏估計

4.7.3 Pareto 最優解和值

Def 43 Pareto最優解的定義：參照極小元

定理41：點x是Pareto最優的，當且僅當它是可行的并且可達目標值集合與$f_0(x)?K$的交集為{$f_0(x)$}

注：Pareto最優解并不唯一

4.7.4 標量化（尋找Pareto 最優解）

思路：對偶廣義不等式的最小元和極小元

定理42：對應任意$\lambda {>}_K^{?}0$，標量化問題的解是向量優化問題的Pareto解

注：要求$\lambda {>}_K^{?}0$

定理43：（1）可以通過改變權向量λ，得到不同的Pareto 最優解；（2）某些Pareto 最優解不能由任何權向量$\lambda {>}_{K^{?}}0$標量化得到。

凸向量優化問題的標量化

定理44：向量優化問題是凸的，那么標量化問題也是凸的。

定理45（部分逆命題 對應定理43(2)）：（1）對于凸優化問題，每個Pareto最優解$x^{po}$，有$\lambda {\ge }_{K^{?}}0，\lambda =0$使得$x^{po}$是標量化問題的解；（2）當權向量λ遍歷$K^{?}$非負的非零向量，標量化非負可以得到所有Pareto最優解。

示例：矩陣集合的極小上界
求解：1. 標量化；2. 部分逆命題
幾何含義

（三）多準則優化

4.7.5 多準則優化

Def 44 多準則優化問題
Def 45 凸的多準則優化問題
Def 46 目標值大小的比較：x至少與y一樣好；x比y更優

（1）最優解

定理46：多準則優化的最優解相當于所有標量優化問題的最優解

（2）Pareto最優解

Def 47 Pareto最優解的含義
Def 48 最優權衡分析：強權衡、弱權衡

Def 49 最優權衡曲面
示例：雙準則問題 的結論及推廣

（3）標量化多準則問題

思路：通過加權和目標來標量化多準則問題

權值的選擇：在最優權衡曲面上搜索，如何設置或改變權

4.7.6 示例

正則化最小二乘

投資組合優化中風險-回報的權衡

總結

以上是生活随笔為你收集整理的04 凸优化问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。