AI中的优化5-无约束非线性规划之凸性
目录
正文
一、核心概念
1. 全局最小、局部最小、严格局部最小
2. 梯度
（1）矩阵的偏导数计算（梯度）
（2）Hessian Matrix
（3）方向导数与梯度
（4）可行方向
二、最优性条件
1. FONC：对局部最小点【不足以保证局部最小】
2. SONC：对局部最小点【不足以保证局部最小】
3. SOSC: 保证局部最小
4. 应用与总结(对无约束优化问题或可行域内部点的局部最优解)
三、 凸性
1. 凸问题
凸函数（[严格凸] 等号去掉）
仿射affine函数：既凸convex又凹concave
2. 凸性判断
（1）凸函数的一阶判定条件 First-Order Condition for Convexity
（2）凸函数的二阶判定条件 Second-Order Characterization of Convexity:
（3）凸性保持
3. 凸优化的核心属性：局部最优即全局最优
4.最优性的充分条件：
•最优点 (Optimum)
◦ 局部最小值 (Local Minimum): 在一个邻域内的最低点。
◦ 全局最小值 (Global Minimum): 在整个可行域内的最低点。
•最优性条件 (Optimality Conditions)
◦ 一阶必要条件 (FONC):∇f(x*) = 0
▪ 描述了最优点的一个基本特征：梯度为零。满足此条件的点称为驻点 (Stationary Point)。
◦ 二阶必要条件 (SONC):∇²f(x*) ⪰ 0
▪ 在梯度为零的基础上，增加了对局部曲率的要求：海森矩阵必须是半正定的。
◦ 二阶充分条件 (SOSC):∇²f(x*) ≻ 0
▪ 一个更强的条件，确保该点是一个严格的局部最小值。
◦应用: 这些条件构成了一个层次化的筛选框架，用于区分驻点、鞍点 (Saddle Point) 和局部最优点。
•凸性 (Convexity)
◦ 基本定义:
▪ 凸集 (Convex Set)
▪ 凸函数 (Convex Function)
◦ 判定条件:
▪ 一阶条件：函数图形位于其任意切线的上方。
▪ 二阶条件：海森矩阵在整个定义域内均为半正定。
◦核心属性: 对于凸优化问题，任何局部最优解同时也是全局最优解。这一特性极大地简化了求解过程。
本章将首先系统地阐述用于识别和验证最优点的一阶和二阶最优性条件，然后深入探讨凸性这一强大概念，它为优化问题提供了坚实的理论保障，并解释了为何它能将复杂问题转化为可解问题。
正文
上一章讲了线性规划，这一章讲非线性规划。
首先，什么是非线性规划？如果理解了线性规划，那么很简单，如下图所示：
对于非线性规划，凸性仍旧是一个非常重要的讨论点。LP中，我们也首先讨论了凸集、凸组合，进而得到某顶点处会得到最优的结论，从而通过单纯形法等方法进行求解。
那么，接下来，首先我们要辨析几个概念
一、核心概念
1. 全局最小、局部最小、严格局部最小
（Global Minimum Point VS Local Minimum Point VS Strict Local Minimum Point）
add(1) 内点
add(2) station point
station point分:
local minimizer【Hessian矩阵正定】
VS local maximizer【Hessian矩阵负定】
VS saddle points(非极值驻点，成为鞍点 比如x^3的x=0情况）【Hessian矩阵不定】
2. 梯度
（1）矩阵的偏导数计算（梯度）
（2）Hessian Matrix
（3）方向导数与梯度
方向导数定义：函数定义域的内点对某一方向求导得到的导数。
当然，与普通函数的导数类似，方向导数也不是百分之百存在的，需要函数满足在某点处可微defferentiable，才能计算出该函数在该点的方向导数。
方向导数和梯度的关系：
函数在某点的梯度是这样一个向量，它的方向与取得最大方向导数的方向一致，而它的模为方向导数的最大值[2]。
给定一个函数 f 和一个向量 d，我们可以构建一个一维函数g（α）= f（x+ αd）。以下定理展示了 g 的导数与 f 的梯度之间的关系。它表明，方向导数可以表示为梯度与 d 的点积。
一阶&二阶
（4）可行方向
设x ∈ Ω。若存在 δ > 0使得对于任意0 < α ≤ δ ，x + αd ∈ Ω，则向量d = 0称为x处的可行方向。
二、最优性条件
1. FONC：对局部最小点【不足以保证局部最小】
如果一个点是局部极小点，那么该点的任何可行方向都与梯度正相关。
在无约束（或 interior point）情况下
必要不充分 例：f=x^3 满足FONC但并非局部最小
2. SONC：对局部最小点【不足以保证局部最小】
在无约束（或 interior point）情况下
[∇f(x) = 0 is called a critical point or stationary point]可以用来证明驻点不是极值点；因为还有Saddle point的存在【saddle point: 驻点但二阶导是indefinte】
3. SOSC: 保证局部最小
4. 应用与总结(对无约束优化问题或可行域内部点的局部最优解)
针对无约束优化问题或可行域内部点（Interior Point，因为在内部点，约束条件不起作用）的局部最优解：
| min | max | |
|---|---|---|
| FONC (一阶必要条件) | 梯度为零 | 梯度为零 |
| SONC (二阶必要条件) | FONC 成立且Hessian 矩阵半正定（Positive Semi-Definite, PSD） | NegativeSemi-Definite |
| SOSC (二阶充分条件) | FONC 成立且Hessian 矩阵严格正定（Positive Definite, PD） | NegativeDefinite |
应用：
- 使用 FONC 和 SONC 来确定所有可能的候选解。然后，利用充分条件验证它们是否最优。
- 如果一个问题只有一个驻点，并且可以推断出该问题必定存在一个有限的最优解，那么这个点必定是（全局）最优解
题目练习
综上，最优性条件为我们提供了一个从识别候选点（FONC）到验证其性质（SONC 和 SOSC）的完整框架。然而，这些条件通常只能保证局部最优性。接下来我们将引入凸性——一个能将局部最优与全局最优联系起来的强大概念。
三、 凸性
在优化理论中，凸性是一道至关重要的分水岭，它区分了那些我们通常能够有效求解的“易”问题和那些计算上可能极其困难的“难”问题（有凸性就是易问题）。当一个优化问题具有凸性时，我们就拥有了强大的理论工具来保证找到的解不仅是局部的，更是全局的。
1. 凸问题
满足以下条件的优化问题为凸问题
凸函数（[严格凸]等号去掉）
仿射affine函数：既凸convex又凹concave
2. 凸性判断
（1）凸函数的一阶判定条件First-Order Condition for Convexity
可微f为凸，当且仅当
（2）凸函数的二阶判定条件Second-Order Characterization of Convexity:
二阶连续可微f为凸当且仅当 二阶导半正定
（3）凸性保持
kf, f+f,max(f,f), f(ax+b)
3. 凸优化的核心属性：局部最优即全局最优
凸函数中，任何局部极小点同时也是全局极小点。（Theorem 5.15）
因此，凸优化问题只需找到一个局部极小点即可。
【注：凸函数并不一定存在局部极小点或者全局极小点】
4.最优性的充分条件：
f凸且可微时：thenx∗是局部极小值
interior point情况下
对于凸函数而言，一阶必要条件既是必要条件也是充分条件，以确保某点成为全局极小值！若函数f为凸函数且x*为内点，则当且仅当∇f（x*）=0时，x*才是全局极小值。
参考阅读
[1]通俗理解方向导数、梯度|学习笔记 - 知乎 (zhihu.com)
[2]终于理解了方向导数与梯度 - 飞奔的可亦 - 博客园 (cnblogs.com)
[3] 上课的notes