【Convex Optimization Stanford】Lec5. Duality 对偶问题

前言

我们总在追寻爱情的本质，追寻心动的起源，总在寻找真爱，可是真爱是什么，每个人的标准都不一样，我们又如何才能找到呢？

共轭函数的性质：

仿射包的定义和性质：

矩阵的列空间$\mathcal{R}(A)$：

拉格朗日对偶

一开始的讨论并非一个凸优化问题，仅讨论对于一个一般的优化问题，不一定是凸的。

拉格朗日对偶与共轭函数

拉格朗日对偶问题

弱对偶与强对偶

约束资格

定义：
在凸优化问题中，保持该问题和其对偶问题是强对偶的条件称为约束资格。（constraint qualification）

Slater资格约束

涉及的概念

• 严格可行点（strict feasible point):
  指的是严格满足所有优化问题约束条件的点。并且要求该点在可行域的$\mathcal{D}$的内部，
• 内部(int)和相对内部(relint)：
  

省流版

1. 可行域$\mathcal{D}$内存在至少一个严格可行点
2. 仅针对凸优化问题

可判断满足KKT条件。且能保证原问题一定有最优解。

注意：条件可放宽为：

1. 可行域$\mathcal{D}$的相对内部存在至少一个严格可行点
2. 该点对于线性不等式不需要严格
3. 凸优化问题

一些例子

LP

QP

省流版

1. LP问题，除非原问题与对偶问题没有可行解，否则$p^{\ast }=d^{\ast }$
2. QP问题永远满足$p^{\ast }=d^{\ast }$

非凸问题的强对偶情况

几何差值法

KKT条件

即：
如果一个问题满足强对偶，且$x,\lambda ,v$分别是原问题和对偶问题的最优解，则一定满足以下四个条件：

1. 满足原始的约束条件
2. 满足对偶约束
3. 满足互补松弛
4. 拉格朗日函数对x的梯度等于0

强对偶+最优（原函数+对偶函数）—》KKT性质

互补松弛项

省流版：就是所有不等式项约束的加权和为0，才能让$\mathcal{L}(x^{\ast },{\lambda }^{\ast },v^{\ast })=f_0(x^{\ast })$。

KKT在凸优化问题的性质

凸优化问题+满足KKT条件-----》最优解

需要说明的是：第四条件之所以能推出这个的原因，是因为该问题为凸优化问题，则所有的函数$f_i(x)$都是凸函数，因此其线形组合也是凸函数，即拉格朗日函数是凸函数，因此其全局只有一个最优点，且该最优点就是全局最优点。

最后这个KKT和Slater条件的关系，因为Slater条件如果满足，则说明该凸优化问题是一个强对偶问题，且原函数有最优值，因此对于一个$x$，只要能找到一对$\lambda ,v$，使得他们满足KKT条件，则他们一定是最优的。实际上，只用到了Slater条件中的凸优化问题和一定有解的两个性质，强对偶性实际上并没有用上，只是强对偶性用于作应证。

扰动和敏感性分析

对偶与问题重构

通常的方式：

1. 引入新的变量或等式约束
2. 将显式约束改为隐式或反之亦反
3. 变换目标函数或限制函数的形式

引入新变量并加入等式限制

大概意思就是用新的变量表达久的变量，并将其相等关系作为限制条件写入。

隐式限制

实际上就是通过对偶的形式，让隐式约束在对偶过程中消掉，从而在对偶问题的计算过程中，能够更加简化。

带有泛化不等式约束的情况

把泛化不等式给拆开，拆成单个函数即可。

半正定规划