网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

Convex optimization 4.2 ---Strong duality

2021/5/7 17:55:45 人评论

1 Introduction 在4.1节,我们回顾了对偶的原理、如何构建、作用,在4.2继续应用对偶条件,尤其是强对偶条件,帮助我们分析和解决优化问题。 2 Certificate of suboptimality 对于标准的优化问题: {minf0(x),x∈Rnsubf…

1 Introduction

在4.1节,我们回顾了对偶的原理、如何构建、作用,在4.2继续应用对偶条件,尤其是强对偶条件,帮助我们分析和解决优化问题。

2 Certificate of suboptimality

对于标准的优化问题:
{ m i n f 0 ( x ) , x ∈ R n s u b f i ( x ) ≤ 0 , i = 1 , . . . m h i ( x ) = 0 , i = 1 , . . . , p \left \{ \begin{aligned} & min \quad & f_0(x), x \in R^n \\ & sub \quad & f_i(x) \leq 0, i=1,...m \\ & \quad & h_i(x) =0,i=1,...,p \end{aligned} \right. minsubf0(x),xRnfi(x)0,i=1,...mhi(x)=0,i=1,...,p
拉格朗日方程
L ( x , λ , ν ) = f 0 ( x ) + ∑ i m λ i f i ( x ) + ∑ i p ν i h i ( x ) L(x, \lambda, \nu)=f_0(x)+\sum \limits_i^{m} \lambda_if_i(x)+ \sum \limits_i^p\nu_ih_i(x) L(x,λ,ν)=f0(x)+imλifi(x)+ipνihi(x)
对偶形式方程
g ( λ , ν ) = i n f x L ( x , λ , ν ) g(\lambda, \nu)=\mathop{inf} \limits_x L(x, \lambda, \nu) g(λ,ν)=xinfL(x,λ,ν)
假定 x ∗ 是 最 优 解 , p ∗ = f 0 ( x ∗ ) x^*是最优解,p^*=f_0(x^*) xp=f0(x); 而 x ^ ∗ 、 λ ^ ∗ 、 ν ^ ∗ \hat{x}^*、\hat{\lambda}^*、\hat{\nu}^* x^λ^ν^是通过迭代计算的估计值,有下面的关系
f 0 ( x ) − p ∗ ≤ f 0 ( x ) − g ( λ ^ ∗ , ν ^ ∗ ) ∣ f 0 ( x ^ ∗ ) − p ∗ ∣ ≤ ∣ f 0 ( x ^ ∗ ) − g ( λ ^ ∗ , ν ^ ∗ ) ∣ ≤ ε \begin{aligned} f_0(x)-p^* & \leq f_0(x)-g(\hat{\lambda}^*, \hat{\nu}^*) \\ |f_0(\hat{x}^*)-p^*| & \leq |f_0(\hat{x}^*)-g(\hat{\lambda}^*, \hat{\nu}^*)| \leq \varepsilon \end{aligned} f0(x)pf0(x^)pf0(x)g(λ^,ν^)f0(x^)g(λ^,ν^)ε
当迭代的时候,误差小于限制时,认为结束。但如果并不是强对偶, ε \varepsilon ε并不容易确定到底是多少。
用 这 种 方 法 进 行 评 估 预 测 值 的 误 差 , 一 般 也 是 应 用 在 强 对 偶 条 件 下 。 \color{red}{用这种方法进行评估预测值的误差,一般也是应用在强对偶条件下。}

3 complementary slackness

3.1 定义

原问题转换成对偶问题后,很自然会对两个问题中的最优解 x ∗ → ( λ ∗ , ν ∗ ) x^* \to (\lambda^*, \nu^*) x(λ,ν)之间的联系产生兴趣。
f 0 ( x ∗ ) ≥ g ( λ ∗ , ν ∗ ) ≥ i n f x ( L ( x , λ ∗ , ν ∗ ) ) ≥ i n f x ( f 0 ( x ) + ∑ i m λ i ∗ f i ( x ) + ∑ i p ν i ∗ h i ( x ) ) ≥ f 0 ( x ∗ ) + i n f x ( ∑ i m λ i ∗ f i ( x ) ) \begin{aligned} f_0(x^*) &\geq g(\lambda^*, \nu^*) \\ &\geq \mathop{inf} \limits_x(L(x, \lambda^*, \nu^*)) \\ & \geq \mathop{inf} \limits_x (f_0(x)+\sum \limits_i^{m} \lambda_i^*f_i(x)+ \sum \limits_i^p\nu_i^*h_i(x)) \\ & \geq f_0(x^*)+\mathop{inf} \limits_x(\sum \limits_i^{m} \lambda_i^*f_i(x)) \end{aligned} f0(x)g(λ,ν)xinf(L(x,λ,ν))xinf(f0(x)+imλifi(x)+ipνihi(x))f0(x)+xinf(imλifi(x))

此时,显而易见如果问题满足强对偶条件,则下列条件成立
λ 1 ∗ f 1 ( x ) = . . . = λ m ∗ f m ( x ) = 0 i n f x ( L ( x , λ ∗ , ν ∗ ) ) = L ( x ∗ , λ ∗ , ν ∗ ) \begin{aligned} \lambda_1^*f_1(x)=...=\lambda_m^*f_m(x)=0 \\ \mathop{inf} \limits_{x}(L(x,\lambda^*, \nu^*))=L(x^*,\lambda^*, \nu^*) \end{aligned} λ1f1(x)=...=λmfm(x)=0xinf(L(x,λ,ν))=L(x,λ,ν)
这其实就是KKT条件,其中一个条件1就是complementary slackness.
指 的 是 如 果 优 化 问 题 满 足 强 对 偶 条 件 , 则 λ 1 ∗ f 1 ( x ) = . . . = λ m ∗ f m ( x ) = 0 \color{red}指的是如果优化问题满足强对偶条件,则\lambda_1^*f_1(x)=...=\lambda_m^*f_m(x)=0 λ1f1(x)=...=λmfm(x)=0

3.2 应用

p ) { m i n c T x s u b A x ≤ b x ≥ 0 → d ) { m i n b T λ s u b A T λ ≥ c λ ≥ 0 p) \left \{ \begin{aligned} & min \quad & c^Tx \\ & sub \quad & Ax \leq b \\ & \quad & x \geq 0 \end{aligned} \right. \quad \to \quad d) \left \{ \begin{aligned} & min \quad & b^T\lambda \\ & sub \quad & A^T\lambda\geq c \\ & \quad & \lambda \geq 0 \end{aligned} \right. p)minsubcTxAxbx0d)minsubbTλATλcλ0
给具体的数值
c = [ 1 − 2 3 ] A = [ 1 1 − 2 2 − 1 − 3 1 1 5 ] b = [ 1 4 2 ] c= \begin{bmatrix} 1 \\ -2 \\ 3 \end{bmatrix} \quad A= \begin{bmatrix} 1 & 1 & -2 \\ 2 & -1 & -3 \\ 1 & 1 & 5 \end{bmatrix} \quad b= \begin{bmatrix} 1 \\ 4 \\ 2 \end{bmatrix} c=123A=121111235b=142

对于线性规划,有一个非常重要的性质[4], 即 对 偶 问 题 的 对 偶 问 题 是 原 问 题 。 \color{red}即对偶问题的对偶问题是原问题。
加上这个性质之后,complementary slackness,可以拓展成
λ 1 ∗ f 1 ( x ) = . . . = λ m ∗ f m ( x ) = 0 x 1 ∗ f ˉ 1 ( x ) = . . . = x m ∗ f ˉ m ( x ) = 0 \begin{aligned} \lambda_1^*f_1(x)=...=\lambda_m^*f_m(x)=0 \\ x_1^*\bar{f}_1(x)=...=x_m^*\bar{f}_m(x)=0 \end{aligned} λ1f1(x)=...=λmfm(x)=0x1fˉ1(x)=...=xmfˉm(x)=0
代入具体的数值之后,上面的问题变成
p ) { m i n x 1 − 2 x 2 + 3 x 3 s u b x 1 + 2 x 2 − 2 x 3 ≤ 1 2 x 1 − x 2 − 3 x 3 ≤ 4 x 1 + x 2 + 5 x 3 ≤ 2 x 1 ≥ 0 , x 2 ≥ 0 , x 3 ≥ 0 → d ) { m i n λ 1 + 4 λ 2 + 2 λ 3 s u b λ 1 + 2 λ 2 + λ 3 ≥ 1 λ 1 − λ 2 + λ 3 ≥ 1 − 2 λ 1 − 3 λ 2 + 5 λ 3 ≥ 3 λ 1 ≥ 0 , λ 2 ≥ 0 , λ 3 ≥ 0 p) \left \{ \begin{aligned} & min \quad & x_1-2x_2+3x_3 \\ & sub \quad & x_1+2x_2-2x_3 \leq 1 \\ & \quad & 2x_1-x_2-3x_3 \leq 4 \\ & \quad & x_1+x_2+5x_3 \leq 2 \\ & \quad & x_1 \geq0, x_2 \geq0, x_3 \geq0 \end{aligned} \right. \quad \to \quad d) \left \{ \begin{aligned} & min \quad & \lambda_1+4 \lambda_2+2 \lambda_3 \\ & sub \quad & \lambda_1+2 \lambda_2+ \lambda_3 \geq 1 \\ & \quad & \lambda_1- \lambda_2+ \lambda_3 \geq 1 \\ & \quad & -2 \lambda_1-3 \lambda_2+5 \lambda_3 \geq 3 \\ & \quad & \lambda_1 \geq0, \lambda_2 \geq0, \lambda_3 \geq0 \end{aligned} \right. p)minsubx12x2+3x3x1+2x22x312x1x23x34x1+x2+5x32x10,x20,x30d)minsubλ1+4λ2+2λ3λ1+2λ2+λ31λ1λ2+λ312λ13λ2+5λ33λ10,λ20,λ30

假设找到一个最优解
{ x 1 ∗ = 9 7 x 2 ∗ = 0 , x 3 ∗ = 1 7 , → { f 1 ( x ∗ ) = 0 , f ˉ 1 ( λ ) = 0 f 2 ( x ∗ ) < 0 , λ 2 = 0 f 3 ( x ∗ ) = 0 , f ˉ 3 ( λ ) = 0 \left \{ \begin{aligned} x_1^*&= \frac{9}{7} \\ x_2^*&= 0, \\ x_3^*&= \frac{1}{7}, \end{aligned} \right. \quad \to \quad \left \{ \begin{aligned} f_1(x^*)&= 0,\bar{f}_1(\lambda)=0 \\ f_2(x^*)&< 0, \lambda_2=0\\ f_3(x^*)&= 0,\bar{f}_3(\lambda)=0 \end{aligned} \right. x1x2x3=79=0,=71,f1(x)f2(x)f3(x)=0fˉ1(λ)=0<0,λ2=0=0fˉ3(λ)=0
得到了根据推导出来的关系,代入对偶问题中进行验证,查看是否符合。

4 KKT condition

4.1 定义

slater条件是证明强对偶的充分条件,KKT条件则是证明强对偶的充分必要条件。
在这里插入图片描述

4.2 应用

在凸优化这门课上,我们能解决的问题主要是那几类,普遍都是凸优化问题。用KKT证明强对偶很少,反而利用强对偶这个前提,利用KKT条件,求解最优解。
{ m i n 1 2 x T p x + q T x + r , p ∈ s + n s u b A x = b \left \{ \begin{aligned} & min \quad & \frac{1}{2}x^Tpx+q^Tx+r, p \in s_+^n \\ & sub \quad & Ax=b \end{aligned} \right. minsub21xTpx+qTx+r,ps+nAx=b
根据条件4, L ( x , ν ) = 1 2 x T p x + q T x + r + ν T ( A x − b ) L(x,\nu)=\frac{1}{2}x^Tpx+q^Tx+r+\nu^T(Ax-b) L(x,ν)=21xTpx+qTx+r+νT(Axb)
d L d x = p x ∗ + q + A T ν = 0 A x ∗ = b \begin{aligned} \frac{dL}{dx}=px^*+q+A^T\nu=0 \\ Ax^*=b \end{aligned} dxdL=px+q+ATν=0Ax=b
得到了一个重要的条件,方便后面的计算。

5 Perturbation and sensitivity analysis

5.1 定义

很多时候,约束需要调试才能合理的给出,这时扰动和敏感性分析就非常重要。
c ) { m i n f 0 ( x ) s u b f i ( x ) ≤ 0 , i = 1 , . . . , n h i ( x ) = 0 , i = 1 , . . . , p → p ) { m i n f 0 ( x ) s u b f i ( x ) ≤ u i , i = 1 , . . . , n h i ( x ) = v i , i = 1 , . . . , p c) \left \{ \begin{aligned} & min \quad & f_0(x) \\ & sub \quad & f_i(x)\leq 0, i=1,...,n \\ & \quad & h_i(x)=0,i=1,...,p \end{aligned} \right. \quad \to \quad p) \left \{ \begin{aligned} & min \quad & f_0(x) \\ & sub \quad & f_i(x)\leq u_i, i=1,...,n \\ & \quad & h_i(x)=v_i,i=1,...,p \end{aligned} \right. c)minsubf0(x)fi(x)0,i=1,...,nhi(x)=0,i=1,...,pp)minsubf0(x)fi(x)ui,i=1,...,nhi(x)=vi,i=1,...,p
在 进 一 步 深 入 讨 论 之 前 , 需 要 搞 清 楚 , 引 入 p e r t u b a t i o n 之 后 , 改 变 的 到 底 是 什 么 ? \color{red}在进一步深入讨论之前,需要搞清楚,引入pertubation之后,改变的到底是什么? pertubation
放 宽 了 限 制 条 件 , 直 接 改 变 了 x 存 在 的 区 域 \color{blue}放宽了限制条件,直接改变了x存在的区域 x
在这里插入图片描述
对于原问题 p ∗ p^* p是最优解,
p ∗ ( u , v ) = i n f x { f 0 ( x ) ∣ ∃ x ∈ D , f i ( x ) ≤ u i , h i ( x ) = v i } p^*(u,v)=\mathop{inf} \limits_x \{ f_0(x) | \exists x \in D, f_i(x)\leq u_i, h_i(x)=v_i \} p(u,v)=xinf{f0(x)xD,fi(x)ui,hi(x)=vi}
如果原问题是凸问题,则 p ∗ ( u , v ) 是 关 于 u , v 的 凸 函 数 p^*(u, v)是关于u,v的凸函数 p(u,v)u,v
从上境图很容易理解,集合A是 f i , h i , f 0 f_i, h_i, f_0 fi,hif0对应凸集的交集,所以仍然是凸集。
A = { ( u , v , t ) ∣ ∃ x ∈ D , f i ( x ) ≤ u i , h i ( x ) = v i , f 0 ( x ) ≤ t } A=\{ (u,v,t) | \exists x \in D, f_i(x)\leq u_i, h_i(x)=v_i, f_0(x)\leq t \} A={(u,v,t)xD,fi(x)ui,hi(x)=vi,f0(x)t}

5.2 global pertubation

引入了扰动量之后,当然很关心,扰动量对问题最小值的影响,即 p ∗ ( 0 , 0 ) 和 p ∗ ( u , v ) 的 关 系 。 p^*(0,0)和p^*(u,v)的关系。 p(0,0)p(u,v)
对于一般问题,他们之间的联系太多复杂,先从强对偶条件入手。
D ( 0 , 0 ) 表 示 未 加 扰 动 前 的 定 义 域 d o m x , D ( u , v ) 表 示 添 加 扰 动 后 的 定 义 域 d o m x 。 D(0,0)表示未加扰动前的定义域dom{x},D(u,v)表示添加扰动后的定义域domx。 D(0,0)domx,D(u,v)domx
p ∗ ( 0 , 0 ) = g ( λ ∗ , ν ∗ ) ≤ f 0 ( x ) + ∑ i m λ i ∗ f i ( x ) + ∑ i p ν i ∗ h i ( x ) , x ∈ D ( 0 , 0 ) ≤ f 0 ( x ) + λ T u + ν T v , x ∈ D ( u , v ) \begin{aligned} p^*(0,0) & =g(\lambda^*, \nu^*) \\ & \leq f_0(x)+\sum \limits_i^{m} \lambda_i^*f_i(x)+ \sum \limits_i^p\nu_i^*h_i(x),x\in D(0,0) \\ & \leq f_0(x)+\lambda^Tu+ \nu^Tv,x\in D(u,v) \\ \end{aligned} p(0,0)=g(λ,ν)f0(x)+imλifi(x)+ipνihi(x)xD(0,0)f0(x)+λTu+νTvxD(u,v)
搞 不 懂 从 x ∈ D ( 0 , 0 ) → x ∈ D ( u , v ) 上 面 的 式 子 为 何 还 会 继 续 成 立 ? \color{red}搞不懂从x \in D(0,0) \to x \in D(u,v)上面的式子为何还会继续成立? xD(0,0)xD(u,v)
总之,根据上面的式子很容易得到
p ∗ ( u , v ) ≥ p ∗ ( 0 , 0 ) − λ T u + ν T v , x ∈ D ( u , v ) p^*(u,v) \geq p^*(0,0)-\lambda^Tu+ \nu^Tv, x \in D(u,v) p(u,v)p(0,0)λTu+νTv,xD(u,v)

p ∗ ( u , v ) 和 p ∗ ( 0 , 0 ) 的 关 系 可 以 用 下 面 的 图 表 示 : p^*(u,v) 和 p^*(0,0)的关系可以用下面的图表示: p(u,v)p(0,0)
关 于 为 何 直 线 和 凸 函 数 P ∗ ( u , v ) 相 切 ? 凸 函 数 和 直 线 有 且 只 有 一 个 交 点 , 那 必 然 只 能 是 相 切 。 \color{red}关于为何直线和凸函数P^*(u,v)相切?凸函数和直线有且只有一个交点,那必然只能是相切。 线P(u,v)线
− λ 是 凸 函 数 p ∗ ( u , v ) 在 点 ( 0 , 0 ) 处 的 导 数 。 \color{red}-\lambda 是凸函数p^*(u,v)在点(0,0)处的导数。 λp(u,v)(0,0)
在这里插入图片描述
得到了global pertubation关系之后,对如何调节约束,有了一个大致的指导。
在这里插入图片描述
根据这个不等式,可以定性的得到,调节对最小值的影响。

5.3 local pertubation

在5.2,我们用几何图像说明了为何 凸 函 数 g ( u . v ) 在 ( 0 , 0 ) 点 处 的 关 于 u 的 偏 导 是 − λ 凸函数g(u.v)在(0,0)点处的关于u的偏导是-\lambda g(u.v)(0,0)uλ.
用代数证明的过程,这里进行省略。主要是结论
∂ p ∗ ( u , v ) ∂ u i ∣ ( u , v ) = ( 0 , 0 ) = − λ i ∂ p ∗ ( u , v ) ∂ v i ∣ ( u , v ) = ( 0 , 0 ) = − ν i \begin{aligned} \frac{\partial p^*(u,v)}{\partial u_i}|_{(u,v)=(0,0)} & =-\lambda_i \\ \frac{\partial p^*(u,v)}{\partial v_i}|_{(u,v)=(0,0)} & =-\nu_i \end{aligned} uip(u,v)(u,v)=(0,0)vip(u,v)(u,v)=(0,0)=λi=νi
这个时候,如果在 p ∗ ( 0 , 0 ) p^*(0,0) p(0,0)进行细微的调节,就可以利用泰勒展开,定量的得到细微调整的影响。

References

[1] https://www.youtube.com/watch?v=_muH67CqTME&list=PL-DDW8QIRjNOVxrU2efygBw0xADVOgpmw&index=17
[2] https://www.youtube.com/watch?v=tFWjzEQMq2g&list=PL-DDW8QIRjNOVxrU2efygBw0xADVOgpmw&index=18
[3] https://www.youtube.com/watch?v=JFbC2uoN7e4&list=PL-DDW8QIRjNOVxrU2efygBw0xADVOgpmw&index=20
[4] https://www.youtube.com/watch?v=COQtsv1SohQ&list=PL-DDW8QIRjNOVxrU2efygBw0xADVOgpmw&index=21
[5] https://zhuanlan.zhihu.com/p/259516554

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?