无约束最优化方法

约束规划问题一般形式：

$$\begin{split} &\min f(x),&\quad x\in \mathbb{R}^{n} \\ &\text{s. t. }&c_{i}(x)=0,\quad i\in E=\{1,2,\dots, l\} \\ & &c_{i}(x)\leq 0, \quad i\in I=\{l+1,l+2,\dots, l+m\} \end{split}$$

局部解的必要条件

一阶必要条件

考虑上述约束规划问题，这里我们假设$f(x),c_i(x),(i=1,2,…,l+m)$是连续可微函数。我们引进Lagrange函数：

$$L(x,\lambda)=f(x)+\sum_{i=1}^{l+m}\lambda_{i}c_{i}(x)$$

设约束问题中 $f(x),c_i(x),(i=1,2,…,l+m)$具有连续可微的一阶偏导数，若$x^∗$是该约束问题的局部解，在$x^∗$处存在$\lambda^*=(\lambda_{1}^*, \lambda_{2}^*,\dots, \lambda_{l+m}^*)^T$使得：

$$\nabla_{x}L(x^{*}, \lambda^{*})=\nabla f(x^{*})+\sum_{i=1}^{l+m}\lambda_{i}^{*}\nabla c_{i}(x^{*})=0$$

其中

$$\begin{gather} c_{i}(x^{*})=0, i\in E=\{1,2,\dots,l\} \\ c_{i}(x^{*})\leq 0, i\in I=\{l+1,l+2,\dots,l+m\} \\ \lambda_{i}^{*}\geq 0, i\in I=\{l+1,l+2,\dots,l+m\} \\ \lambda_{i}^{*}c_{i}(x^{*})=0, i\in I=\{l+1,l+2,\dots,l+m\} \end{gather}$$

上述一阶必要条件被称为Kuhn-Tucker条件，或简称K-T条件；满足上式的点为K-T点；称$λ^∗$为$x^∗$处的Lagrange乘子（Lagrange Multiplier）.

约束限制条件成立的充分条件

若在前述约束优化问题的局部解$x∗$处下述两条件之一成立：

$$c_{i}(x), i\in E\cup I(x^{*})$$

则在 $x∗$ 处约束限制条件成立。此时必存在 $λ^∗$ 使得K-T条件成立。

凸函数

区间$[a,b]$上定义的函数$f$，若它对区间中任意两点$x1,x2$均有：

$$f(\frac {x_1+x_2}{2}) \leq \frac{f(x_1)+f(x_2)}{2}$$

对实数集上的函数，可通过求解二阶导数来判别：

• 若二阶导数在区间上非负，则称为凸函数
• 若二阶导数在区间上恒大于0，则称严格凸函数

仿射函数也是凸函数，只是不是严格凸函数。

凸优化问题

凸优化问题是特殊的约束最优化问题。其一般形式形式和约束最优化问题一样。

假设f、g、h在定义域内是连续可微的，且目标函数f和不等式约束函数g是凸函数，等式约束h是仿射函数（线性函数），则这种约束最优化问题称为凸优化问题。
因此凸优化问题特征的重要特征：

• 目标函数f，不等式约束函数g是凸函数
• 等式约束h是仿射函数
• 满足约束最优化问题的一般形式

凸二次规划问题

凸二次规划问题是凸优化问题的一个特殊形式，当目标函数是二次型函数且约束函数 g 是仿射函数时，就变成一个凸二次规划问题。凸二次规划问题的一般形式为

$$\begin{matrix} \min_{x} &\frac{1}{2}x^TQx+c^Tx\\ s.t.&Wx \leqslant b \end{matrix}$$

若 Q 为半正定矩阵，则上面的目标函数是凸函数，相应的二次规划为凸二次规划问题；此时若约束条件定义的可行域不为空，且目标函数在此可行域有下界，则该问题有全局最小值。

若Q为正定矩阵，则该问题有唯一的全局最小值。
例如，最简单的正定矩阵就是单位矩阵。

凸二次规划问题的特征：

• 目标函数f是二次型函数函数
• 等式约束h是仿射函数
• 等式约g是仿射函数
• 满足约束最优化问题的一般形式

常用的二次规划问题求解方法有：

• 椭球法
• 内点法
• 增广拉格朗日法
• 梯度投影法

参考

概述性文章

最优化理论与凸优化到底是干嘛的？https://blog.csdn.net/qq_39422642/article/details/78816637
二次规划 https://blog.csdn.net/lilong117194/article/details/78204994

按照顺序

凸优化基础简述：https://blog.csdn.net/philthinker/article/details/78023085
无约束最优化问题的一般结构与规划方法：https://blog.csdn.net/philthinker/article/details/78191864
约束规划问题与凸二次规划：https://blog.csdn.net/philthinker/article/details/78510361

这些基础铺垫比较全

无约束最优化方法：https://blog.csdn.net/lansatiankongxxc/article/details/45873597
凸优化-对偶问题：http://www.hanlongfei.com/convex/2015/11/05/duality/
[x]凸优化问题，凸二次规划问题QP，凸函数：https://blog.csdn.net/promisejia/article/details/81241201
数学优化入门：凸优化: https://blog.csdn.net/lipengcn/article/details/52815690

涉及到锥

Farkas引理的几何意义 https://zhuanlan.zhihu.com/p/29525513
一步一步走向锥规划 - QP：https://www.jianshu.com/p/ffe239b124c1

涉及到模式识别

凸优化问题实例：LASSO：https://blog.csdn.net/lyj2014211626/article/details/79133145