非线性规划的最优条件

最优性条件是用于刻画最优解的几何或代数刻画,它是最优化的重要理论。我们可以应用相关工具刻画出一些问题的解及判断相关解是否为最优解。同时,由迭代结构可知,除下降方向外,我们需要知道介绍计算步长的方法 本节知识点有无约束规划问题的一阶最优性条件和二阶最优性条件、约束规划问题的一阶必要条件(KKT条件)及二阶充分性条件、精确和不精确线搜索。难点为约束问题一阶必要条件的代数表达及求解、判别二阶充分条件所需向量的向量空间计算。

一个无约束优化问题

(1)minxRnf(x)
  • 如果 xRn 使得 f(x)f(x) 对任意 x 成立,那么是全局极小点
    • 如果这个点只有一个,那么是严格的全局极小点
  • 如果 xRn 使得 f(x)f(x)x 的领域成立,那么是局部极小点
    • 如果这个极小点只有一个,那么是严格的局部极小点

无约束优化问题一阶必要条件

如果 x 是无约束优化问题 (1) 的局部极小点,则 f(x)x 处一阶连续可微,即

f(x)=0

无约束优化问题二阶充分条件

f(x)x 处二阶连续可微,如果 f(x)=0 并且 Hesse 矩阵 2f(x) 正定,则 x 是无约束优化问题 (1) 的严格局部极小点。

如果 f(x) 是可微凸函数,那么 x 是无约束优化问题 (1) 的全局极小点的充分必要条件为 f(x)=0

带约束规划问题的最优性条件

考虑一个约束优化问题

(2)minf(x)s.t.h(x)=0g(x)0

其中 f:RnRh:RnRmg:RnRl

KKT 条件

另一种写法

minf(x)s.t.hi(x)=0gj(x)0

定义 Lagrange 函数

L(x,w,v)=f(x)i=1mwihi(x)j=1lvjgj(x)

求 K-K-T 点需要求解下列系统

xL(x,w,v)=0(1)hi(x)=0(2)gj(x)0(3)vjgj(x)=0(4)vj0(5)

其中 (1) 为梯度条件,(2)(3) 为可行条件,(4)(5) 为互补松弛条件。

KKT 条件另一本书的写法

minf(x)s.t.hi(x)=0gj(x)0

定义 Lagrange 函数

L(x,λ,μ)=f(x)+i=1mλihi(x)+j=1lμjgj(x)

求 K-K-T 点需要求解下列系统

μj0(1)xL(x,λ,μ)=0(2)μjgj(x)=0(3)hi(x)=0(4)gj(x)0(5)

其中 (1) 为梯度条件,(2)(3) 为可行条件,(4)(5) 为互补松弛条件。