04 凸优化问题

目录
4.1 优化问题
4.2 凸优化问题
应用
4.3 线性规划问题
4.4 二次优化问题
4.5 几何规划

4.6 广义不等式约束
4.7 向量优化

4.1 优化问题

（一）优化问题的定义

4.1.1 基本术语

Def 1 优化问题的定义[优化变量、目标函数、不等式约束、等式约束、无约束问题]
注：

1. 定义域、可行域（可行\不可行）的定义；
2. 最优值的定义、$p\ast =+\infty$问题不可行、$p\ast =-\infty$问题无下界；
3. 最优点、局部最优点、ε最优的定义
   （1）最优点、最优集（最优值可达/不可达）
   （2）ε-次优、ε-次优集
   （3）局部最优

Def 2 冗余约束、积极约束[约束起/不起作用]
Def 3 可行性问题[判定可行解的存在性、约束的一致性]

4.1.2 优化问题的标准表示

Def 4 优化问题标准形式的定义：不等式和等式约束右端值为零
示例：框约束问题
Def 5 极大化问题的定义及其标准化

（二）优化问题的等价问题（4.1.3）

Def 6 等价问题的定义：可以从一个问题的解得到另一个问题的解
简单示例：伸缩变换

产生等价问题的变换

（1）变量变换

定理1*：设 Φ ： R n → R n Φ：R_n\to R_n Φ：Rn​→Rn​是一一映射，其像包含问题的定义域D，即$D\subset \Phi (dom\Phi )$，定义函数 f ‾ i \overline f_i f​i​和 h ‾ i \overline h_i hi​为 h ‾ i = h i ( Φ ( z ) ) , i = 0 , . . . , m ， \overline h_i=h_i(Φ(z)),i=0,...,m， hi​=hi​(Φ(z)),i=0,...,m， f ‾ i = f i ( Φ ( z ) ) , i = 0 , . . . , p \overline f_i=f_i(Φ(z)),i=0,...,p f​i​=fi​(Φ(z)),i=0,...,p。标准形式问题和该问题通过变量变换x=Φ(z)联系，两个问题等价。

（2）函数的变换（目标函数和约束函数）

定理2：设 ψ 0 : R → R ψ_0:R\to R ψ0​:R→R单增； ψ 1 , . . . , ψ m : R → R ψ_1,...,ψ_m:R\to R ψ1​,...,ψm​:R→R满足：当且仅当$u\le 0$时， ψ i ( u ) ≤ 0 ψ_i(u)\leq 0 ψi​(u)≤0； ψ m + 1 , . . . , ψ m + p : R → R ψ_{m+1},...,ψ_{m+p}:R\to R ψm+1​,...,ψm+p​:R→R满足：当且仅当$u=0$时， ψ i ( u ) = 0 ψ_i(u)= 0 ψi​(u)=0，定义函数 f ‾ i \overline f_i f​i​和 ψ ‾ i \overline ψ_i ψ​i​为 f ‾ i = ψ i ( f i ( z ) ) , i = 0 , . . . , m ， \overline f_i=ψ_i(f_i(z)),i=0,...,m， f​i​=ψi​(fi​(z)),i=0,...,m， h ‾ i = ψ m + i ( h i ( z ) ) , i = 0 , . . . , p \overline h_i=ψ_{m+i}(h_i(z)),i=0,...,p hi​=ψm+i​(hi​(z)),i=0,...,p。标准形式问题和该问题等价。

示例：最小范数和最小范数平方是等价的

（3）松弛变量

定理3：将不等式约束转化为等式约束： f i ≤ 0 f_i\leq 0 fi​≤0等价于存在一个 s i ≥ 0 s_i\geq0 si​≥0满足 f i ( x ) + s i = 0 f_i(x)+s_i=0 fi​(x)+si​=0。即将每个不等式约束转换为一个等式和一个非负约束，标准形式问题和该问题等价。

（4）消除等式约束

定理4：用参数 z ∈ R k z\in R^k z∈Rk显式地参数化等式约束 h i ( x ) = 0 , i = 1 , . . . , p h_i(x)=0,i=1,...,p hi​(x)=0,i=1,...,p的解，那么可以从原问题中消除等式约束。x满足该式等价于存在 z ∈ R k z\in R^k z∈Rk使得$x=\Phi (z)$.

特例：消除线性等式约束

定理5：如果等式约束是线性的，即Ax=b，如果$b\notin R(A)$，则原问题无解；否则，令R(F)=N(A)，则其通解可以表示为 F z + x 0 Fz+x_0 Fz+x0​。

（5）引入等式约束

定理6（原问题复合函数的分解）：将原问题中目标函数 f 0 ( A 0 x + b 0 ) f_0(A_0x+b_0) f0​(A0​x+b0​)的 A 0 x + b 0 A_0x+b_0 A0​x+b0​用 y 0 y_0 y0​表示，不等式约束 f i ( A i x + b i ) ≤ 0 f_i(A_ix+b_i)\leq0 fi​(Ai​x+bi​)≤0的 A i x + b i A_ix+b_i Ai​x+bi​用 y i y_i yi​表示，并将该等式作为新的约束。

（6）优化部分变量

定理7（先优化一部分变量后优化另一部分变量）：由于 i n f x , y f ( x , y ) = i n f x i n f y f ( x , y ) inf_{x,y}f(x,y)=inf_xinf_yf(x,y) infx,y​f(x,y)=infx​infy​f(x,y)，可以通过先优化一部分变量再优化另一部分变量来达到优化一个函数的目的。

（7）上境图问题形式

定理8：将原优化问题改为min t, subject to f 0 ( x ) − t ≤ 0 f_0(x)-t\leq 0 f0​(x)−t≤0。

（8）隐式与显式约束

定理9：标准形式问题可以表示为无约束问题，定义域由可行集限定，该目标函数由于定义域可能不为开集而不可微；对于隐式约束的问题，可以将其显式化。

注：这两个问题不相同

（三）参数与谕示问题描述（4.1.4）

1. 参数问题描述[函数参数给定，可确定问题]
2. 谕示模型[不知显式的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 f_0 f0​的最优性准则

定理14（最优性条件）：凸优化问题的目标函数 f 0 f_0 f0​是可微的，X表示可行集。x是最优解当且仅当$x\in X$且 ∇ f 0 ( x ) T ( y − x ) ≥ 0 \nabla f_0(x)^T(y-x)\geq0 ∇f0​(x)T(y−x)≥0，对于任意$y\in X$。

最优性条件示例

（1）无约束问题

定理15：对于无约束的凸优化问题，最优化条件可以简化为 ∇ f 0 ( x ) = 0 \nabla f_0(x)=0 ∇f0​(x)=0。

示例：
1.无约束二次规划；
2.解析中心；

（2）只含等式约束的问题

定理16：对于只含等式约束不含不等式约束的问题，最优性条件可以表示为：
∇ f 0 ( x ) ∈ R ( A T ) ，且 A x = b \nabla f_0(x)\in R(A^T)，且Ax=b ∇f0​(x)∈R(AT)，且Ax=b。

（3）非负象限中的极小化

定理17：对于非负象限中的极小化问题，最优性条件可以表示为：
x ≥ 0 , ∇ f 0 ( x ) ≥ 0 , x i ( ∇ f 0 ( x ) ) i = 0 x\geq 0,\nabla f_0(x)\geq0,x_i(\nabla f_0(x))_i=0 x≥0,∇f0​(x)≥0,xi​(∇f0​(x))i​=0。

（三）等价的凸问题（4.2.4）

（1）消除等式约束

定理18：凸问题的等式约束是线性的，即消除线性等式约束，和优化问题的消除等式约束相同。

（2）引入等式约束

定理19：凸优化问题引入的等式约束必须是线性的，得到的优化问题的凸优化问题。

（3）松弛变量

定理20：如果原不等式约束是线性的，那么引入松弛变量，得到的优化问题是凸优化问题。

（4）上境图问题形式

定理21：上境图问题的形式中目标函数是线性的，新的约束函数是(x,t)上的凸函数，所以该问题是凸问题。

（5）极小化部分变量

定理22：如果原问题的目标函数是 x 1 , x 2 x_1,x_2 x1​,x2​上的联合凸函数，并且 f i , i = 1 , . . . , m 1 , f ‾ i , i = 1 , . . . , m 2 f_i,i=1,...,m_1,\overline f_i,i=1,...,m_2 fi​,i=1,...,m1​,f​i​,i=1,...,m2​，那么极小化部分变量的问题是凸问题。

（四）拟凸优化问题（4.2.5）

1. 拟凸优化问题的最优解

（1）局部最优解与全局最优解

定理23：拟凸优化问题的局部最优解不一定就是全局最优解[反例]。

（2）最优性条件

定理24（充分条件）：令X表示拟凸优化问题的可行集，如果$x\in X$， ∇ f 0 ( x ) T ( y − x ) > 0 \nabla f_0(x)^T(y-x)>0 ∇f0​(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 − x^+,x^- x+,x−的差；

4.3.1 示例

（1）食谱问题

（2）多面体的Chebyshev中心

Def 13 多面体内部最大球中心

（3）动态活动计划

（4）Chebyshev不等式

满足先验知识的分布下 E f 0 ( X ) Ef_0(X) Ef0​(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具有等于其谱半径（特征值最大幅值）的正实数特征值 λ p f λ_{pf} λpf​。

定理28：Perron-Frobenius特征值 λ p f λ_{pf} λpf​决定了当$k\to \infty$时， A k A^k Ak增长或消退的渐进速率。

定理29（非负矩阵理论的基本结果）：Perron-Frobenius特征值 λ p f λ_{pf} λpf​由 λ p f λ_{pf} λ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 f_0 f0​的最优性条件与上相同。

（二）锥形式问题（线性规划的推广）

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 , . . . , 2 n x_k=Et^k,t=0,...,2n xk​=Etk,t=0,...,2n，那么 x 0 = 1 x_0=1 x0​=1，并且Hankel矩阵半正定。

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

思路：已知R上的概率分布的矩，转化为SDP问题
问题：不知R上的概率分布p(t)，但已知其矩的界，计算Ep(t)的最大和最小值

（4）不完全协方差信息下的投资组合风险界定

经典的投资组合问题(4.4.1示例5)：投资组合x是优化变量，在最小平均收益和其他约束条件下极小化风险。
风险界定问题：假设投资组合已知，但关于协方差矩阵Σ只有部分信息（先验信息，即约束条件），在满足条件的所有协方差矩阵中，我们投资的最大风险是多少？

定理37：在满足给定界的所有协方差矩阵中，投资的最大风险问题可以转化为SDP问题。

关于Σ凸的先验信息 示例

1. 已知特定投资组合的方差；
2. 包含估计误差的影响；
3. 影响因素模型；
4. 关于系数的信息；

（5）图的最速混合马氏链

Def 38 无向图的定义
Def 39 无向图马氏链、转移状态矩阵、平衡分布的定义

定理38（混合速率）：马氏链状态X(t)的分布收敛到平稳分布(1/n)1的情况由P的第二大特征值，即r=max{ λ 2 , − λ n λ_2,-λ_n λ2​,−λn​}决定。称r为马氏链的混合速率。如果r=1，那么X(t)的分布不必收敛到(1/n)1，当r<1，分布渐进地以 r t r^t rt逼近(1/n)1。小的r使得马氏链更快的混合。

图的最速混合马氏链问题：寻找转移状态矩阵以极小化r，使得图的马氏链更快的收敛到平稳分布。

定理39：图的最速混合马氏链问题可以转化为SDP问题

4.7 向量优化（向量目标函数）

（一）广义和凸的向量优化问题

Def 40 广义向量优化问题的定义
Def 41 凸向量优化问题
注：目标函数值不一定能比较

（二）最优解与值

4.7.2 最优值与解

Def 42 可达目标值集合、最优解的定义：参照最小元

定理40：点x是最优的，当且仅当它是可行的并且可达目标值集合包含于 f 0 ( x ) + K f_0(x)+K f0​(x)+K

示例：最优线性无偏估计

4.7.3 Pareto 最优解和值

Def 43 Pareto最优解的定义：参照极小元

定理41：点x是Pareto最优的，当且仅当它是可行的并且可达目标值集合与 f 0 ( x ) − K f_0(x)-K f0​(x)−K的交集为{ f 0 ( x ) f_0(x) f0​(x)}

注：Pareto最优解并不唯一

4.7.4 标量化（寻找Pareto 最优解）

思路：对偶广义不等式的最小元和极小元

定理42：对应任意 λ > K ∗ 0 λ>_K^*0 λ>K∗​0，标量化问题的解是向量优化问题的Pareto解

注：要求 λ > K ∗ 0 λ>_K^*0 λ>K∗​0

定理43：（1）可以通过改变权向量λ，得到不同的Pareto 最优解；（2）某些Pareto 最优解不能由任何权向量 λ > K ∗ 0 λ>_{K^*}0 λ>K∗​0标量化得到。

凸向量优化问题的标量化

定理44：向量优化问题是凸的，那么标量化问题也是凸的。

定理45（部分逆命题 对应定理43(2)）：（1）对于凸优化问题，每个Pareto最优解 x p o x^{po} xpo，有 λ ≥ K ∗ 0 ， λ ≠ 0 λ\geq_{K^*}0，λ\neq 0 λ≥K∗​0，λ=0使得 x p o x^{po} xpo是标量化问题的解；（2）当权向量λ遍历 K ∗ K^* 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 示例

1. 正则化最小二乘
2. 投资组合优化中风险-回报的权衡

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！