不等书约束优化

1. 不等式约束

$min \ \ \ f_0(x), \ \ x\in R^n$

subject to

$f_i(x)\leq 0, \ i=1,...m$

$h_j(x)=0, j=1,....p$

其中:$f_i(x)$是凸函数，$h_j(x)是仿射函数$

2. 求解步骤

http://xiaoyc.com/duality-theory-for-optimization/

2.1 拉格朗日函数

$L(x,\lambda,\nu)=f_0(x)+\sum\limits_{i=1}^m\lambda_if_i(x)+\sum\limits_{j=1}^p \nu_jh_j(x)$

固定x，拉格朗日函数是关于$\lambda和\nu$的仿射函数

2.2 原函数不容易求解，求解拉格朗日对偶函数

$g(\lambda,\nu)=\inf\limits_{x\in D}(f_0(x)+\sum\limits_{i=1}^m \lambda_if_i(x)+\sum\limits_{j=1}^p \nu_ih_i(x))$

2.3 对偶函数的最大值是原问题的最小值；即对偶间隔是0；需要满足

$f_0(x^*)=g(\lambda^*,\nu^*)=\inf\limits_{x}(f_0(x)+\sum\limits_{i=1}^m\lambda_i^*f_i(x)+\sum\limits_{i=1}^p\nu_i^*h_i(x))$

$\leq f_0(x^*)+\sum\limits_{i=1}^m\lambda_i^*f_i(x^*)+\sum\limits_{i=1}^p\nu_i^*h_i(x^*) \leq f_0(x^*)$

2.4 此时，求解凸优化问题，等于求解KKT方程

• $f_i(x^*)\leq 0$.......$i=1,...,m$

• $h_i(x^*)=0$..........$i=1,..,m$

• $\lambda_i^*\geq 0$........$i=0,...,m$

• $\lambda_i^*f_i(x^*)=0$.......$i=1,...,m$

• $\bigtriangledown f_0(x^*)+\sum\limits_{i=1}^m\lambda_i^*\bigtriangledown f_i(x^*)+\sum\limits_{i=1}^p \nu_i\bigtriangledown h_i(x^*)=0$

3. KKT条件的充分必要性

http://xiaoyc.com/duality-theory-for-optimization/

3.1 再讨论Slater条件

• 若$f_1,...,f_k$是仿射函数，则存在点$x$满足

$f_i(x)\leq 0$.................. $i=1,...,k$

$f_i(x)< 0$ ............. $i=k+1,...,m$

则原问题是凸优化问题，则强对偶性成立

3.2 对偶问题的求解方法

• 定义驻点法
• 隐函数求解
• 共轭函数法

3.3 最优条件

• 互不松弛条件

$f_0(x^*)=g(\lambda^*,\nu^*)=\inf\limits_{x}(f_0(x)+\sum\limits_{i=1}^m\lambda_i^*f_i(x)+\sum\limits_{i=1}^p\nu_i^*h_i(x))$

$\leq f_0(x^*)+\sum\limits_{i=1}^m\lambda_i^*f_i(x^*)+\sum\limits_{i=1}^p\nu_i^*h_i(x^*) \leq f_0(x^*)$

取得等号

• 必要性（对任何优化问题）

KKT条件的必要性：对任何优化问题，最优解一定满足KKT条件

• 充分性（对凸优化问题）

对于一阶可微的凸优化问题，且满足slater条件，则KKT是最优解的必要条件

4. kkT条件的几何解释（1阶）

可行下降的方向