文档介绍:最优化理论与算法帅天平北京邮电大学数学系§7,,无约束极值问题——称为无约束极值问题(UNLP)--(非极小点的充分条件)设f(x)在点x*处可微,若存在方向d(0)Rn,使得f(x*)'d<0,则存在>0,使得对任意(0,),有f(x*+d)<f(x*).此时,我们称d为f(x)在x*(x)在x*可微,则f(x*+d)=f(x*)+f(x*)d+||d||(x*;d),其中(x*;d)0(当0).2,-无约束3移项且两边同除以(0),得(f(x*+d)-f(x*))/=f(x*)d+||d||(x*;d)由于f(x*)d<0且(x*;d)0当>0使得对任意(0,),f(x*)d+||d||(x*;d)<-3(极小点的必要条件)设x*处是问题(UNLP)(x)在x*可微时,则梯度f(x*)=(x)在x*f(x*)=0且Hessian矩阵H(x*)-无约束4(2).(x)在x*的二次可微性,有f(x*+d)=f(x*)+f(x*)d+dH(x*)d/2+||d||(x*;d)(I),其中(x*;d)0(0).由(1)的证明有f(x*)=,得=dH(x*)d/2+||d||(x*;d)(II).因x*局部极小,对充分小有f(x*+d)f(x*)2222f(x*+d)-f(x*)22证明(1).若f(x*)0,作d=-f(x*).则有f(x*)d<,存在>0使得f(x*+d)<f(x*),(0,),此与x*为局部极小相矛盾,故f(x*)=-无约束5d’H(x*)d/2+||d||(x*;d)02由(II),显见对充分小的成立,对0取极限,则有d’H(x*)d0,从而,H(x*)半正定定义1若f(x)在点x*处可微,且f(x*)=0,则称x*为f(x)(0)Rn,(二阶充分条件).假设f(x)在x*点二次可微,若f(x*)=0且Hessian矩阵H(x*)是正定的,则x*是(UNLP)的一个(严格)局部极小点3,-*二次可微,故对任意x,有f(x)=f(x*)+f(x*)(x-x*)+(x-x*)H(x*)(x-x*)/2+||x-x*||(x*;x-x*),这里(x*;x-x*)0,当xx*.假设命题不真,x*不是局部极小,则存在序列{xk}收敛到x*并使得f(xk)<f(x*)对每一k成立。定义序列(xk-x*)/||xk-x*||=’kH(x*)dk/2+(x*;xk-x*)0(k)但对每一k,||dk||=1,从而{dkj}d,当kj,这里||d||=f(x*)=0,我们有dH(x*)d0,-无约束7证明.(必要性)若x*全局最优,,f(x*)=0.(充分性)设f(x*)=0,则f(x*)(x-x*)=0,x*En由f(x)可微凸,有()f(x)f(x*)+f(x*)(x-x*)=f(x*),(充要条件).假设f(x):RnR是可微的凸函数,则x*是(UNLP)的全局最小点当且仅当f(x*)=-无约束8Date10最优化理论