非线性规划的最优条件
最优性条件是用于刻画最优解的几何或代数刻画，它是最优化的重要理论。我们可以应用相关工具刻画出一些问题的解及判断相关解是否为最优解。同时，由迭代结构可知，除下降方向外，我们需要知道介绍计算步长的方法 本节知识点有无约束规划问题的一阶最优性条件和二阶最优性条件、约束规划问题的一阶必要条件（KKT条件）及二阶充分性条件、精确和不精确线搜索。难点为约束问题一阶必要条件的代数表达及求解、判别二阶充分条件所需向量的向量空间计算。
一个无约束优化问题
\[\min_{\boldsymbol{x} \in \mathbb{R}^n} f(\boldsymbol{x}) \tag{1}\]- 如果 \(\boldsymbol{x}^* \in \mathbb{R}^n\) 使得 \(f(\boldsymbol{x}) \ge f(\boldsymbol{x}^*)\) 对任意 \(\boldsymbol{x}\) 成立，那么是全局极小点
- 如果这个点只有一个，那么是严格的全局极小点
- 如果 \(\boldsymbol{x}^* \in \mathbb{R}^n\) 使得 \(f(\boldsymbol{x}) \ge f(\boldsymbol{x}^*)\) 在 \(\boldsymbol{x}^*\) 的领域成立，那么是局部极小点
- 如果这个极小点只有一个，那么是严格的局部极小点
无约束优化问题一阶必要条件
如果 \(\boldsymbol{x}^*\) 是无约束优化问题 (1) 的局部极小点，则 \(f(\boldsymbol{x})\) 在 \(\boldsymbol{x}^*\) 处一阶连续可微，即
\[\nabla f(\boldsymbol{x}^*) = 0\]无约束优化问题二阶充分条件
设 \(f(\boldsymbol{x})\) 在 \(\boldsymbol{x}^*\) 处二阶连续可微，如果 \(\nabla f(\boldsymbol{x}^*) = 0\) 并且 Hesse 矩阵 \(\nabla^2 f (\boldsymbol{x}^*)\) 正定，则 \(\boldsymbol{x}^*\) 是无约束优化问题 (1) 的严格局部极小点。
如果 \(f(\boldsymbol{x})\) 是可微凸函数，那么 \(\boldsymbol{x}^*\) 是无约束优化问题 (1) 的全局极小点的充分必要条件为 \(\nabla f(\boldsymbol{x}^*) = 0\)
带约束规划问题的最优性条件
考虑一个约束优化问题
\[\begin{aligned} \min \quad & f(\boldsymbol{x}) \\ \text{s.t.} \quad & \boldsymbol{h}(\boldsymbol{x}) = 0 \\ & \boldsymbol{g}(\boldsymbol{x}) \ge 0 \end{aligned} \tag{2}\]其中 \(f:\mathbb{R}^n \to \mathbb{R}\) ，\(\boldsymbol{h}:\mathbb{R}^n \to \mathbb{R}^m\) ， \(\boldsymbol{g}: \mathbb{R}^n \to \mathbb{R}^l\)
KKT 条件
另一种写法
\[\begin{aligned} \min \quad & f(\boldsymbol{x}) \\ \text{s.t.} \quad & h_i(x) = 0 \\ & g_j(x) \ge 0 \end{aligned}\]定义 Lagrange 函数
\[L(x,w,v) = f(x) - \sum_{i=1}^{m}w_ih_i(x) - \sum_{j=1}^{l}v_jg_j(x)\]求 K-K-T 点需要求解下列系统
\[\begin{aligned} & \nabla_x L(x,w,v) = 0 \qquad & (1) \\ & h_i(x) = 0 & (2)\\ & g_j(x) \ge 0 & (3)\\ & v_j g_j (x) =0 & (4)\\ & v_j \ge 0 & (5) \end{aligned}\]其中 (1) 为梯度条件，(2)(3) 为可行条件，(4)(5) 为互补松弛条件。
KKT 条件另一本书的写法
\[\begin{aligned} \min \quad & f(\boldsymbol{x}) \\ \text{s.t.} \quad & h_i(\boldsymbol{x}) = 0 \\ & g_j(\boldsymbol{x}) \le 0 \end{aligned}\]定义 Lagrange 函数
\[L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(x) + \sum_{i=1}^{m}\lambda_ih_i(\boldsymbol{x}) + \sum_{j=1}^{l}\mu_jg_j(\boldsymbol{x})\]求 K-K-T 点需要求解下列系统
\[\begin{aligned} & \mu_j \ge 0 \qquad & (1) \\ & \nabla_x L(x, \lambda, \mu) = 0 & (2)\\ & \mu_j g_j (x) =0 & (3)\\ & h_i(x) = 0 & (4)\\ & g_j(x) \le 0 & (5) \end{aligned}\]其中 (1) 为梯度条件，(2)(3) 为可行条件，(4)(5) 为互补松弛条件。
