最优化基础（五）
无约束问题的最优性条件
引入下列记号:
g(x)=∇f(x), gk=∇f(xk), G(x)=∇2f(x), Gk=∇2f(xk)
一阶必要条件: 设
f(x) 在开集
D 上一阶连续可微. 若
x∗∈D 是
f(x)的一个局部极小点, 则必有
g(x∗)=0.
二阶必要条件:设f(x)在开集D上二阶连续可微. 若x∗∈D是f(x) 的一个局部极小点, 则必有g(x∗)=0 且G(x∗) 是半正定矩阵.
二阶充分条件:设f(x)在开集D 上二阶连续可微. 若x∗∈D 满足条件g(x∗)=0 及 G(x∗)是正定矩阵, 则x∗ 是f(x) 的一个局部极小点.
定理: 设f(x) 在Rn 上是凸函数并且是一阶连续可微的. 则x∗∈Rn 是f(x) 的全局极小点的充要条件是g(x∗)=0.
无约束优化问题的算法框架
在数值优化中, 一般采用迭代法求解无约束优化问题
min f(x)
的极小点. 迭代法的基本思想是: 给定一个初始点
x0, 按照某一迭代规则产生一个迭代序列
{xk}. 使得若该序列是有限的, 则最后一个点就是问题的极小点; 否则, 若序列
{xk} 是无穷点列时, 它有极限点且这个极限点即为问题的极小点.
算法 (无约束问题的一般算法框架)
步0 :给定初始化参数及初始迭代点x0. 置k:=0.
步1 :若xk 满足某种终止准则, 停止迭代, 以xk作为近似极小点.
步2 :通过求解xk处的某个子问题确定下降方向xk.
步3 :通过某种搜索方式确定步长因子ak, 使得f(xk+akdk)<f(xk).
步4 :令xk+1:=xk+akdk,k:=k+1, 转步1.
定义: 若存在α¯>0, 使得对任意的α∈(0,α¯] 和dk≠0, 有
f(xk+αdk)<f(xk)
则称
dk为
f(x) 在
xk 处的一个下降方向.
引理: 设函数f:D⊂Rn→R在开集D 上一阶连续可微, 则dk为f(x) 在xk 处一个下降方向的充要条件是
∇f(xk)Tdk<0
定义: 若某算法只有当初始点
x0充分接近极小点
x∗ 时, 由算法产生的点列
{xk} 才收敛于
x∗, 则称该算法具有局部收敛性. 若对于任意的初始点
x0, 由算法产生的点列
{xk} 都收敛于
x∗, 则称该算法具有全局收敛性.