实用最优化算法设计

基础概念

• Optimization：minimization or maximization of a function subject to constraints on its variables.
  优化问题的标准形式：
  变量x，目标函数f(x)——需要最大化or最小化的值（objective function），约束函数c_i(x)——x的等式或不等式（constraint function），表征了对变量取值的限制。
• unconstrained optimization & constrained optimization：是否有约束函数
• linear programming：如果目标函数和约束函数都是线性函数，那么优化问题也称为线性规划（linear programming）

Unconstrained Optimization

• 无约束优化问题：即在整个实数域上优化目标函数
• global minimizer（全局最小）：整个定义域上最小
  weak local minimizer: 存在领域在其中最小（小于等于其他值）
  strict/strong local minimizer: 存在领域在其中最小（小于其他值，不包括其自身）
  isolated local minimizer: 存在领域在其中是唯一的local minimizer
  注：孤立极小一定是严格极小，但反之不然。
  即严格极小不一定是孤立的，在其邻域内有可能存在另一个严格极小。
  eg. 你是你们这一届最好的不妨碍你身边的人是他们寝室最好的。

Recognizing a Local Minimum

• 如何判断x 是否是Local Minimizer：
  最朴素的方法：对x\的immediate vicinity内的所有点，判断f(x*)是否比它们都小。注：immediate vicinity指一个非常小的邻域。
  但如果对于一个光滑的函数，我们有更简便的方法：
  特别地，对于二阶可微的函数f(R^n->R)，可通过分析其梯度和Hessian矩阵来判断——泰勒展开。

必要条件

• 局部极小值的一阶必要条件（First-Order Necessary Conditions）：
  若x*是局部极小值，且函数f在x*的一个开区间内连续可微，则\(\bigtriangledownf(x^)=0\)
  通常如果\(\bigtriangledownf(x^)=0\)，则\(x^*\)称为稳定点（stationary point）。因此局部极小值一定是稳定点。

• 局部极小值的二阶必要条件（Second-Order Necessary Conditions）：
  若x*是局部极小值，且\(f(x)和\\bigtriangledown^2f(x^*))在x*的一个开区间内都存在而且连续，则\(\bigtriangledownf(x^*)=0\)且\(\bigtriangledown^2f(x^*)\)是半正定的。

充分条件

• 局部极小值的二阶充分条件（Second-Order Sufficient Conditions）
  如果\(\bigtriangledown^2 f(x^)\)在x\的一个开区间内连续，且\(\bigtriangledownf(x^*)=0\) & \(\bigtriangledown^2f(x^*)\)是正定的，则x*是局部极小值点。
  注：二阶充分条件并非必要条件，即局部极小值点不一定满足这些充分条件。
  且对于一般的无约束问题，取到充分必要条件很困难。
  eg. \(x^4\)，x=0时局部极小，但不存在Hessian矩阵（自然也非正定）。

Global Minimizer VS Local Minimizer

• 一般情况下，我们很难寻找全局极小值（尤其当函数有多个局部极小值时），但对于某些特殊函数，我们可以将问题进行简化。
• 如对于凸函数（convex function），局部极小值也是全局最小值。

Convex Function

何为 convex

convex可指一个集合，也可指一个函数。

• 针对集合：若一个集合S是凸集（convex set），则对于任意x、y属于S，\(\alpha x + (1-\alpha)y \in S\)，对任意\(\alpha \in [0,1]\)都成立。
• 针对函数：若一个函数f是凸函数（convex function），则1、其定义域S是凸集，2、对S内任意x、y，\(f(\alpha x + (1-\alpha)y) \leq \alpha f(x)+(1-\alpha)f(y)\)，对任意\(\alpha \in [0,1]\)都成立。
• 对于凸函数，粗糙理解：中点的函数值小于函数值的中点，即函数形状是下凸的。
• 严格凸函数：上式严格小于（\(x \neq y \)且\(\alpha\)为0–1的开区间）
• 凹函数f（concave function） ：-f是凸函数

convex programming

• 目标函数为凸函数
• 等式约束函数为线性
• 不等式约束函数为凹函数

求凸函数全局最小值

定理：若f是凸函数，则f的局部极小值就是全集最小值。额外的，如果f可微，则任何稳定点也是全局最小值。

信赖域

也是迭代方法，在当前迭代点附近，建立简单的数学模型（如泰勒展开），认为在迭代点的邻域附近这个模型都是成立。
minimizer: 最小值点（即x值）
Minimum：最小值（即y值）
minima：