有约束优化

形式：

$\min f(\boldsymbol{x})\\s.t. h_i(\boldsymbol{x})=0,\quad i=1,...,m\\g_j(\boldsymbol{x})\leq0,\quad j=1,...,p,$

对偶理论

弱对偶定理(Weak duality)：设为原优化问题的最小值为拉格朗日对偶函数，则

$\forall\boldsymbol{\lambda},\boldsymbol{\mu}\geq0,o^*\geq d(\boldsymbol{\lambda},\boldsymbol{\mu})$

拉格朗日函数（Lagrangian）

思想：将约束函数以线性加权的形式加入目标函数，得到的函数：

$L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{i=1}^m\lambda_i h_i(\boldsymbol{x})+\sum_{j=1}^p\mu_jg_j(\boldsymbol{x})$

或者

$L(x,\lambda,\mu)=f(x)+\lambda^Th(x)+\mu^Tg(x)$

其中，和称为拉格朗日乘子。

拉格朗日对偶函数（Lagrange dual function）

$d(\lambda,\mu)=\min_{x\in\mathbb{R}^n}L(x,\lambda,\mu)=\min_{x\in\mathbb{R}^n}f(x)+\sum_{i=1}^m\lambda_ih_i(x)+\sum_{j=1}^p\mu_jg_j(x)$

弱对偶定理：设为原优化问题的最小值为拉格朗日对偶函数，则

$\forall\lambda,\mu\geq0,o^*\geq d(\lambda,\mu)$

证明：因为后面两项之和一定 ……

是一个关于的凹函数。( 在几何上是一系列仿射函数的极小值。)

于是可以将原问题转化成

$\max_{\lambda,\mu\geq0}d(\lambda,\mu)=\max_{\lambda,\mu\geq0}\min_{x\in\mathbb{R}^n}L(x,\lambda,\mu)$

由于凹性+max，于是转化成了一个关于的凸优化问题。

该问题称为原问题对偶问题
（）称为对偶变量
称为对偶间隙，对偶间隙为0时，两个问题有相同的最优值，称为强对偶性成立。
- 仅有线性不等式约束的凸优化问题对偶间隙为0
- 大部分凸优化问题的对偶间隙为0

仅含等式约束问题（拉格朗日乘子法）

$\min f(\boldsymbol{x})\\s.t. h_i(\boldsymbol{x})=0,\quad i=1,...,m$

拉格朗日定理

正则点

对于满足的点，如果梯度向量是线性无关的，那么称是该约束条件的一个正则点。

等价于：雅可比矩阵满秩（），。

拉格朗日定理

如果是优化问题min s.t. 且的极小值，且是正则点，那么一定存在向量，使得
。

换句话说：如果是极值点，那么目标函数在的梯度可以表示为约束函数在该点处的梯度的线性组合。

等同于无约束优化问题：的一阶必要条件。

$\begin{cases}\nabla_xL(x^*,\lambda)=\nabla f(x^*)+\sum_{\mathrm{i}=1}^\mathrm{m}\lambda_i\nabla h_i(x^*)=0\\\nabla_{\lambda_i}L(x^*,\lambda)=h_i(x^*)=0\mathrm{~}\forall i=1,...,m&\end{cases}$

拉格朗日乘子法

通过求解上面的方程组，找到极值点。其中方程组包含个方程和个未知数。

一般约束问题（KKT）

$\min f(\boldsymbol{x})\\s.t. h_i(\boldsymbol{x})=0,\quad i=1,...,m\\g_j(\boldsymbol{x})\leq0,\quad j=1,...,p,$

等式约束中拉格朗日定理的成立条件要求是一个正则点，含不等式约束中也要保证极值点是一个正则点。

起作用的约束和不起作用的约束

起作用的约束： 对于不等式约束，如果点处，那么称该不等式是处起作用的约束；如果处，则称为不起作用的约束。

正则点

如果 $\nabla h_i(x^),\nabla g_j(x^{\}),1\le i\le m, j\in\{j:g_j(x^{*})=0\} $是线性无关，则称$ x^{*}$ 是一个正则点。

即：等式约束+起作用的不等式约束的梯度线性无关。

KKT定理

设一阶连续可微，是正则点且局部极小点，那么必然存在和，使得以下条件成立。

$bbb$

对于不起作用的约束，一定成立，对于起作用的约束，。

KKT条件主要是分类讨论。

（拉格朗日条件）
（互补松弛条件）

约束问题的求解算法

投影法
罚函数法（或外点法，求解等式不等式约束优化问题）
内点法（或障碍函数法，求解不等式约束优化问题）

投影法

投影法一般将可行域内“离最近的点”定义，即求。