优化理论（二）：最优条件

Conditions of Optimality

考虑对 $f(x)$ 在极小值点 $x^\ast$ 进行泰勒展开，则有

\gdef\wrap#1{\Big[#1\Big]} f(x) = f(x^\ast) + \wrap{\nabla f(x^\ast)}^T \Delta x^\ast + \frac12 \wrap{\Delta x^\ast}^T\wrap{\nabla^2 f(x^\ast)} {\Delta x^\ast} + R

其中 $\Delta x^\ast=x-x^\ast$ , $R$ 是包含高次 $\Delta x^\ast$ 的多项式。

如果梯度向量 $\nabla f(\bold{x})=0$ ，这就说明 $\bold{x}$ 是一个稳定点 stationary point，例如极值点、鞍点、拐点等等。此时，我们可以通过 Hessian Matrix 进一步判断 $\bold{x}^\ast$ 究竟是极小值点、极大值点、或是鞍点。

如果 quadratic form 满足

\gdef\wrap#1{\Big[#1\Big]} \wrap{\Delta x^\ast}^T\wrap{\nabla^2 f(x^\ast)} {\Delta x^\ast}\gt 0, \Delta x^\ast\ne 0

即 quadratic form 恒大于 $0$ ，我们称 Hessian Matrix 为 positive definite. 若不等号为 $\gt 0$ ，则称之为 positive semidefinite. 类似的，可以定义出 negative definite 和 negative semidefinite. 若既有可能 positive 又有可能 negative，则称为 indefinite.

也可以通过检查 Hessian Matrix 的所有 eigenvalues 来判断。若全都 $\gt 0$ 则为 positive definite；若全都 $\ge 0$ ，则为 positive semidefinite.

……无约束条件的优化问题

First-Order Necessary Condition

如果 $\bold{x}^\ast$ 是极小值点，则 $f(\bold{x})$ 在该点处的 Gradient Vector 为 $0$ .

\text{\(\bold{x}^\ast\) is a local minimum}\implies \nabla f(\bold{x}^\ast)=0

Second-Order Necessary Condition

如果 $\bold{x}^\ast$ 是函数 $f(\bold{x})$ 的极小值点，则 $f(\bold{x})$ 在此处的二阶导为 positive definite 或者 positive semidefinite.

\text{\(\bold{x}^\ast\) is a local minimum}\implies \text{\(\nabla^2f(\bold{x})\) is \textbf{positive (semi)definite}}

Second-Order Sufficient Condition

若 $\nabla^2 f(\bold{x}^\ast)$ 是 positive definite 的，并且满足了 First Order Necessary Condition，那么， $\bold x=\bold x^\ast$ 是 $f(\bold x)$ 的极小值点。

如果 $\bold x_0$ 只满足必要条件，但不满足任何充分条件，我们无法断定 $\bold x_0$ 是极小值点。

……有约束条件的优化问题

新的问题：最优解的点可能会出现在边界上

为了解决这个问题，我们对约束条件乘上 Lagrange multiplier $\lambda$ 然后加到 objective function 里面，组成新的复合 objective function Lagrange Function (Lagrangean) $L$ .

\begin{aligned} &L(\bold x, \lambda, s)\\ =&f(\bold x)\\ +&\sum_{j=1}^m \lambda_j \Big[ g_j(\bold x) + s_j^2 \Big] \\ + &\sum_{k=1}^l \lambda_{m+k}\Big[ h_k(\bold x) \Big] \end{aligned}

其中 $s$ 为 slack variable， $\lambda_i$ 是 Lagrange Multiplier。Lagrange Function 的设计使得我们可以像处理 unconstrained problem 那样处理 constrained problems，通过 $\lambda$ 和 slack variable 保证约束的满足。

此时也要把 $\lambda,s_j$ 也看成是变量，对其求导并令其导数为 $0$ .

Conditions of Optimality 使用条件

当且仅当 $\bold x_0$ 是 Regular point 的时候才可以对 constrained problem 使用 unconstrained problem 的判定技巧。

Regular point 是指，等式约束以及 active 的不等式约束在 $\bold x_0$ 处的一阶导数 $\nabla h_k(\bold x_0),\nabla g_j(\bold x_0)$ 是 线性无关 (linearly independent) 的

Karush-Kuhn-Tucker Conditions（有约束情形下的一阶导必要条件）

通过对 Lagrange function 求导，我们既可以得到约束条件，又可以得到 $f(\bold x)$ 的导数：

\nabla L(\bold x^\ast, \lambda, s)=\nabla f(\bold x^\ast) + \sum_{j=1}^m\lambda_j\nabla g_j(\bold x^\ast) + \sum_{k=1}^l \lambda_{m+k}\nabla h_k(\bold x^\ast)=0 \\ \frac{\partial L}{\partial \lambda_j}=g_j(\bold x^\ast) +s_j^2=0\\ \frac{\partial L}{\partial \lambda_{m+k}}=h_k(\bold x^\ast)=0\\ \frac{\partial L}{\partial s_j}=2\lambda_js_j=0

$\lambda_j$ 需要非负， $\lambda_{m+k}$ 则随意
对 $s_j^2$ 项求导可知，要么 $s_j=0$ 要么 $\lambda_j=0$ （或者都是）

Second Order Necessary Condition（有约束情形下的二阶导必要条件）

若 $\bold x=\bold x^\ast$ 是 $f(\bold x)$ 的极小值点，则 Lagrange Function 的 Hessian Matrix 的 Quadratic form 满足：

(\Delta \bold x^\ast)^T \, \nabla^2L(\bold x^\ast, \lambda^\ast, s^\ast) \, (\Delta \bold x) \ge 0

其中 $\Delta\bold x^\ast\ne 0$ 并且与 Active Constraints 的 Gradient Vector 互相 Orthogonal，即

[\nabla g_j(\bold x^\ast)]^T \Delta\bold x^\ast=0, \text{where \(g_j(\bold x^\ast)\le 0\) is active}\\ [\nabla h_k(\bold x^\ast)]^T \Delta\bold x^\ast=0

这是为了保证 $\Delta \bold x^\ast$ 的移动方向是 feasible 的.

Second Order Sufficient Condition（有约束情形下的二阶导充分条件）

若 Lagrange Function 的 Hessian Matrix 满足

(\Delta \bold x^\ast)^T \nabla^2L(\bold x^\ast,\lambda^\ast,s^\ast) \Delta\bold x^\ast\gt 0

并且 $\Delta\bold x^\ast\ne 0$ 满足

\begin{cases} \nabla g_j(\bold x^\ast)^T\Delta\bold x^\ast=0,&\text{if \(\lambda_j^\ast\gt 0\)}\\ \nabla g_j(\bold x^\ast)^T\Delta\bold x^\ast\le 0,&\text{if \(\lambda_j^\ast= 0\)}\\ \nabla h_k(\bold x^\ast)^T\Delta\bold x^\ast=0,&k=\set{1,2,\dots,l} \end{cases}