无约束问题的最优条件
- 2021 年 5 月 29 日
- 筆記
目录
无约束问题的最优条件
考虑无约束优化问题：
\[\begin{aligned} \min & f(x) \\ \text { s.t. } & x \in X \subseteq R^{n} \end{aligned}
\]
\]
- 若f(x)为凸函数 则 \(x^*\)是最优解 \(\Leftrightarrow\) \(\nabla f\left(x^{*}\right)=0_{\circ}\)
- 若f(x)为一般函数
- 一阶必要条件（First-Order Necessary Conditions）
假设\(f(x)\)在\(x^*\)处是可微的，如果\(x^*\)是局部最小值，那么\(\nabla f\left(x^{*}\right)=0\) - 二阶必要条件（Second-Order Necessary Conditions）
假设\(f(x)\)在\(x^*\)处是二阶可微的，如果\(x^*\)是局部最小值，那么\(\nabla f\left(x^{*}\right)=0\)和\(\nabla^{2} f\left(\mathbf{x}^{*}\right)\)是半正定矩阵 - 二阶充分条件（Second-Order Sufficient Conditions）
假设\(f(x)\)在\(x^*\)处是二阶可微的，如果\(x^*\)是局部最小值，那么\(\nabla f\left(x^{*}\right)=0\)和\(\nabla^{2} f\left(\mathbf{x}^{*}\right)\)是正定矩阵
- 一阶必要条件（First-Order Necessary Conditions）
回顾泰勒定理（Taylor’s Theorem）
为了证明，我们回顾一下泰勒定理
如果f在R上连续可微，则
\[f(x+p)=f(x)+\nabla f(x+t p)^{\top} p$$$$t \in(0,1)
\]
\]
如果f在R上二次连续可微，则可以得到
\[f(x+p)=f(x)+\nabla f(x)^{\top} p+\frac{1}{2} p^{\top} \nabla^{2} f(x+t p) p
\]
\]
具体推导如下
一阶必要条件（First-Order Necessary Conditions）
假设\(f(x)\)在\(x^*\)处是可微的，如果\(x^*\)是局部最小值，那么\(\nabla f\left(x^{*}\right)=0\)
\(proof\)如下：
二阶必要条件（Second-Order Necessary Conditions）
假设\(f(x)\)在\(x^*\)处是二阶可微的，如果\(x^*\)是局部最小值，那么\(\nabla f\left(x^{*}\right)=0\)和\(\nabla^{2} f\left(\mathbf{x}^{*}\right)\)是半正定矩阵
\(proof\)如下：
二阶充分条件（Second-Order Sufficient Conditions）
假设\(f(x)\)在\(x^*\)处是二阶可微的，如果\(x^*\)是局部最小值，那么\(\nabla f\left(x^{*}\right)=0\)和\(\nabla^{2} f\left(\mathbf{x}^{*}\right)\)是正定矩阵
\(proof\)如下：
参考
- Nocedal, Jorge, & Wright, Stephen J. (0). Numerical optimization. 2nd ed.. Springer.
