有约束的最优化问题

最优化问题一般是指对于某一个函数而言, 求解在其指定作用域上的全局最小值问题, 一般分为三种情况, 这三种方法求出来的解都有可能有局部最小值, 只有当函数是凸函数的时候, 才可以得到全局最小值
- 无约束问题, 一般求解方式为梯度下降法, 牛顿法, 坐标轴下降法, $ \displaystyle \min \limits_{x}f(x)$
- 等式约束条件, 求解方式为拉格朗日乘子法, $\displaystyle \min \limits_{x}f(x), s.t: h_k(x)=0, k=1,2,\cdots, p$
- 不等式约束条件, 求解方式为KKT条件 $\displaystyle \min \limits_{x}f(x), s.t: h_k(x)=0, k=1,2,\cdots, p, g_j(x) \le 0, j=1, 2, \cdots, q$

拉格朗日乘子法

$\displaystyle \min \limits_{x}f(x), s.t: h_i(x)=0, i=1,2,\cdots, p$ $\displaystyle \min \limits_{x}f(x) + \displaystyle \sum_{i=1}^{p} \alpha_i h_i(x); \quad \alpha_i \ne 0$

对偶问题

在优化问题中, 目标函数f(x)存在多种形式, 如果目标函数和约束条件都为变量x的线性函数, 则称问题为线性规划; 如果目标函数为二次函数, 则称优化问题为二次规划; 如果目标函数或者约束条件为非线性函数, 则称最优化问题为非线性规划. 每个线性规划问题都有一个对偶问题

对偶问题的对偶是原问题
无论原始问题是否是凸的, 对偶问题都是凸优化问题
对偶问题可以给出原始问题的一个下界
当满足一定条件的时候, 原始问题和对偶问题的解是完美等价的

KKT条件

KKT条件是泛拉格朗日乘子法的一种形式, 主要应用在当我们的优化函数存在不等值约束的情况下的一种最优化解决方式; KKT条件即满足不等值约束的条件

$\displaystyle \min \limits_{x}f(x); \quad s.t.: h_k(x)=0, k=1,2,\cdots,p; \quad g_j(x) \le 0, j=1, 2, \cdots, q$ $L(x, \alpha, \beta) = f(x) + \sum_{i=1}^{p}\alpha_ih_i(x) + \sum_{i=1}^{q}\beta_ig_i(x);\quad\alpha_i \ne 0, \beta_i \lt 0$ $\min \limits_{x}L(x, \alpha, \beta)$

KKT条件总结

拉格朗日取得可行解的充要条件, $\nabla_xL(x, \alpha, \beta) = 0$
将不等式约束转换后的一个约束, 称为松弛互补条件, $\beta_ig_i(x) = 0, \quad i=1,2,\cdots,q$
初始约束条件, $h_i(x)=0, \quad i=1,2,\cdots,p$
初始约束条件, $g_i(x)\le0,\quad i=1,2,\cdots,q$
不等式约束需要满足的条件, $\beta_i\ge0,\quad i=1,2,\cdots,q$