文档介绍：唯楚有材於斯萄盛
最优化
主讲:刘陶文
学好最优化,走遍天下都不怕
课件制作:刘陶文
第二章元约束问题的下降算法
与线性搜索
第一节元约束问题的最优性条件
第二节下降η法的一般步骤
第三节线性搜索
第一节无约束问题的最优性条件
本节,我们来介绍无约東问题最优解的奈件
考察无约束问题
minf(x),x∈R
()
这里函数∫:R″→>R是连续可微的
首先,我们介绍下降方向的概念
,d∈R,若存在数a>0,使得
f(x +ad)<f(x, Vae(0, a)
则称l是函数在处的一个下降方向;若-d是下降,则称d上升
若令
o(a)=f(x +ad)
则函数∫在处的一个下降方向等价于一元函数(a)在原点处
单调递减
关于下降方向,我们有下面简单的判别和构造定理
(x)≠0,则
(1)若向量d满足Ⅴf(x)d<0,则d是在处的一个下降方向
(2)若n阶矩阵H对称正定,则向量d=-HNf(x)是在x处的
个下降方向特别,d=-Vf(x)是在处的一个下降方向
证明:(1)由泰勒展开,我们有
f(x+ad)=f(x)+avf(x)'d+o(a)
由于Vf(x)d<0.,则当a>0且充分小时,aVf(x)d+o(a)<0
从而存在一个a>0,使得
f(x+ad )<f(x,vaE(o, a
即d是函数在处的一个下降方向
(2)当d=-HNf(x)时,由H的正定性知
Vf(r)d=-Vf(x) Hvf(x)<o
所以由(1)知,d=-HNf(x)是函数在处的一个下降方向
利用下降方向,我们很容易将一元函数的极值条件进行
推广而得到判别多维无约束问题最优解的条件
我们先来回忆一下一元函数的极值条件(关于极小值点
x∈R
R"(n>1)
一阶必要条件:f(x)=0→V(x)=0
二阶必要条件
f(x)=0
V(x)=0
f(x)≥0
Vf(x)半正定
f(x)=0
V(x)=0
二阶充分条件
f(x)>0
V2f(x)正定
(无约束问题的一阶必要条件)
设函数f:R”→)R连续可微,若x“是天约束问题()的一个局
部最优解,则有
Vf(
0
()
注意这个条件不是充分的。
例如:函数∫=x1x2的图形是一双曲抛物面
在x=(0,0)处,显然
Vf(0,0)=0
但κ不是极小点,而是双曲拋物面的鞍点
(0,0)
(元约束问题的二阶必要条件)
设函数/:R"→R二次连续可微,若x是无约束问题()的

(x)
且V2f(x)半正定
定理214(无约束问题的二阶充分条件)
设函数f:R"→R二次连续可微,若Vf(x)=0,且Vf(x
正定,则x是无约束问题(21)的一个严格局部最优解
注意:
f(x)=x4+x2
显然x=(0,0)是严格局部极小点(最小点但Vf(x)不正定

min f(x)=xi
解;:y(0-(:2)7)=(2x-20
02
由一阶必要条件Ⅴf(x)=0,得稳定点
0
4)
)
相应的 Hessian矩阵为
20
20
Vf(r)=
不定Vf(x2)
负定
Vf(xo)
正定
(4)
0不定
由二阶条件知,x3)严格局部最优,其它三点不是极值点
当是凸函数时,一阶必要条件也是充分条件
,则x是问题(21)
的最优解的充要条件是x满足Ⅴf(x)=0
证明:只需证充分性:若x满足V(x)=0,则由凸函数的
判别定理,对任意的κ∈R,有
f(r)-f(x)>Vf(x)(x-x)=0
即f(x)≥f(x)
第二节下降犷法的一般步骤
在前面我们给出了函数在点处的下降方向所满足的条件,
并给出了确定下降方向的方式,在此基础上,可构造求解
无约束问题的下降算
下降算法的基本思想:
从某个初始点κ出发,按照函数值下降的原则构造点列
{x}满足杀件
f(xk+1)<f(x1),Vk=0,1,2,
算法的目标是使得点列{x)中某个点或某个极限点是原
问题的解或稳定点。