非线性无约束规划

非线性无约束规划第一页，共四十五页，2022年，8月28日1）方向导数设M0位数量场u=u(M)中的一点,从点M0出发引一条射线l,在l上点M0的附近取一动点M,记如果时，下列表达式的极限存在则称之为M0处沿着l方向的方向导数.记为当时,表示函数u沿l是增加方向,当时,表示函数u沿l是减小方向。1.方向导数与梯度第二页，共四十五页，2022年，8月28日2）直角坐标系中方向导数的计算公式定理1.若函数u=u(x,y,z)在点M0(x0,y0,z0)处可微;

为l的方向余弦,则函数u在点M0处沿l方向导数必然存在，且有下面公式计算其中是在M0附近的偏导数.例题1

求函数在点M(1,0,1)处沿着方向的方向导数解:

第三页，共四十五页，2022年，8月28日3)梯度：根据方向导数公式可以知道是其变化率最快的方向,称为梯度,记为Gradu.如果用表示l线上的单位矢量,则方向导数可以写成梯度的性质：1)方向导数等于梯度在该方向的投影.即2)数量场u=u(M)中任一点M处的梯度,垂直于过该点的等值面,且指向u(M)增大的一方.例3

设为点M(x,y,z)的矢径的模,试证第四页，共四十五页，2022年，8月28日2.海瑟矩阵海瑟矩阵是对称形式：第五页，共四十五页，2022年，8月28日3非线性规划问题的展开形式

多元函数泰勒公式的矩阵形式：其中线性函数：f(X)=CTX+B=cixi

+B二次函数：f(X)=(1/2)XTQX+CTX+Bf(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x*)(x-x*)+o‖x-x*‖2第六页，共四十五页，2022年，8月28日4凸集、凸函数和凸规划1）凸函数

定义:

设集合SRn为凸集，函数f:SR

若x(1),x(2)S,(0,1)，均有

f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。性质:当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数第七页，共四十五页，2022年，8月28日2.2凸集、凸函数和凸规划(续)定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数，设1,2>0,1f1+2f2,1f1-2f2是否凸函数？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？

凸规划=凸可行集+凸目标函数第八页，共四十五页，2022年，8月28日凸函数与凹函数(续)凸函数的判定:

如果函数f(X)的Hesse矩阵处处半正定，则f(X)为凸函数，若f(X)正定，则f(X)为严格凸函数。注:

该命题的逆命题不成立例题检验函数的凸性。第九页，共四十五页，2022年，8月28日无约束问题的最优性条件1.必要条件：若X*是函数f(X)的局部最大点，则在该点必有f(X*)=0以及Hesse矩阵2f(X*)半正定定义:

对于可微函数f(X),称使其梯度为零向量的点为平稳点（驻点）。2.若X*是驻点，则其为极值点的充分条件:1)若H(X*)半正定，X*为局部极小点；若H(X*)正定，X*为孤立局部极小点；2)若H(X*)半负定，X*为局部极大点；若H(X*)负定，X*为孤立局部极大点；3)若H(X*)不定，X*为鞍点；(阅读课本的例题)第十页，共四十五页，2022年，8月28日6最优化问题的数值解VS解析解1.解析解与数值解注意获得解析解的困难性。2、收敛性概念：考虑(fs)设迭代算法产生点列{x(k)}S.1)算法的理想收敛：设x*∈S是(fs)的最优解，如果x*∈{x(k)}，或者虽然

x(k)

≠x*，但是k，满足则称算法收敛到最优解x*。

第十一页，共四十五页，2022年，8月28日

概念:

1)

局部最优:2)全局最优:3)严格全局最优

以及

4)

全局收敛：对任意初始点x(1),算法均收敛。

5)局部收敛：当x(1)

充分接近解x*时，算法才收敛。第十二页，共四十五页，2022年，8月28日2.实用收敛性：

定义解集

S*={x|x具有某种性质}

例：S*={x|x---g.opt}

S*={x|x---l.opt}

S*={x|f(x)=0}

S*={x|f′(x)≤β

}(β为给定实数,称为阈值

当下列情况之一成立时，称算法收敛：

1°x(k)∈S*;2°k，{X(k)}任意极限点∈S*第十三页，共四十五页，2022年，8月28日8.收敛速度

设算法产生点列{x(k)},收敛到解x*,且x(k)≠x*，k，1.线性收敛：当k充分大时成立2.超线性收敛：3.二阶(次)收敛：

﹥0，当k充分大时有第十四页，共四十五页，2022年，8月28日定理：设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*，k，那么证明只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||

，除以||x(k)–x*||并令k→∞，利用超线性收敛定义可得结果。8、收敛速度（续）第十五页，共四十五页，2022年，8月28日4.1常用的搜索算法结构考虑（fs）

常用一种线性搜索的方式构造{xk}序列来求解迭代中从一点出发沿下降可行方向找一个新的、更优的点。△下降方向：设∈S，d∈Rn,d≠0,若存在，使，称d为

在点的下降方向。minf(x)

s.t.

x∈S第十六页，共四十五页，2022年，8月28日4常用的搜索算法结构△可行方向：设∈S，d∈Rn,d≠0,若存在使，称d为该点的可行方向。

同时满足上述两个性质的方向称下降可行方向。第十七页，共四十五页，2022年，8月28日迭代算法的停止标准1）2）3）对于无约束问题可以用第十八页，共四十五页，2022年，8月28日10常用的搜索算法结构线性搜索求，新点使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)是否满足停机条件？停k=k+1yesno第十九页，共四十五页，2022年，8月28日11一维搜索一元函数求极小及线性搜索均为一维搜索。常用于求：

minf(x(k)+

d(k))=φ()s.t.

∈S

S有3种情况（-∞，+∞）或（0，+∞）或[a,b]一、缩小区间的精确一维搜索：考虑问题(P)minφ()

s.t.∈[α,β]

为此先介绍不确定区间及单峰函数的概念△不确定区间：[α,β]含φ(α)的最小点，但不知其位置第二十页，共四十五页，2022年，8月28日单峰的概念一、缩小区间的精确一维搜索（续）若对任意λ1,λ2,α≤1<2

≤β满足：

1º若

2

≤

*，则φ(

1)>φ(

2);

2º若

1

≥λ*，则φ(

1)<φ(

2).则称φ(

)在[α,β]

上强单峰。

若只有当φ(1)≠φ(*)，φ(2)≠φ(*)时，上述1º,2º式才成立，则称φ(

)在[α,β]

上单峰。

α

*

12

β强单峰

α

*

β单峰第二十一页，共四十五页，2022年，8月28日设f(X)是目标函数，如果是在给定Xk和方向矢量Pk下，通过f(x)=f(xk+akPk)

的极小化而产生则称为最优步长。根据单变量的驻点条件:以及复合函数的求导法则可得：1.精确一维搜索（假定求目标函数极小值）第二十二页，共四十五页，2022年，8月28日2一维搜索一、缩小区间的精确一维搜索（续）

定理：设Ф：R→R

在[α，β]上单峰，α≤x1

＜x2≤β

。那么

1°若Ф(x1)≥Ф(x2)，则去除[，x2

]；如左下图

2°若Ф(x1)＜Ф(x2)，则去除[x2，β]；如右下图

α

x1

x2

β

αx1

x2β第二十三页，共四十五页，2022年，8月28日12一维搜索2、黄金分割法（0.618法）选二点x1<x2,比较f(x1)

与f(x2),可去掉[a,x1]或者[x2,b]

考虑下面分割条件：

1°对称：x1

-a=b-x2……①

（使“坏”的情况去掉，区间长度不小于“好”的情况）

2°保持缩减比λ=(保留的区间长度／原区间长度)不变。（使每次保留下来的节点，在下一次的比较中成为一个相应比例位置的节点)。如图所示,推导缩减比λ第二十四页，共四十五页，2022年，8月28日黄金分割法的步骤:1)

确定初始区间为[a,b],初始区间的长度L=b-a,容差>0,k=12)计算初始分割点，x1=a+0.382L,f1=f(x1);x2=a+0.618L,f2=f(x2)3)消去大端值，计算新的分割点：若f1>f2,置a=x1,x1=x2,b=b,f1=f2,x2=a+b-x1,f2=f(x2)

若f1<=f2,置b=x2,x2=x1,a=a,f2=f1,x1=a+b-x2,f1=f(x1)4)收敛检查；如果(b-a)/L<=,则按照下面方式输出结果：若f1<f2,置x*=x1,f*=f1,a=a,b=x2;计算终止。否则，置x*=x2,f*=f2;,a=x1,b=b计算终止。否则，置k=k+1,返回3).通过上面分析可以估计给定容差的迭代次数N>lg

/log0.618例题用黄金分割法求解

minf(x)=x2-6x+10第二十五页，共四十五页，2022年，8月28日牛顿-拉夫逊法(牛顿切线法)

为了找到导数函数对应的驻点，采用根近似假设xk是当前驻点的近似解，则该点的f’(x)函数线性近似可以表示为

f’(x)f’(xk)+f”(xk)(x-xk)令此式为零，得出下一个近似点为

xk+1=xk-f’(xk)/f”(xk)收敛检查：例题:

用牛顿切线法求解

minf(x)=2x2+16/x第二十六页，共四十五页，2022年，8月28日2、二次插值法：

用设f(x)是区间[a,b]上的连续单峰函数，x1,x2,x3

是该区间上三个相邻点，它们的函数值分别为f1,f2,f3,且满足两边大中间小的条件，f1>f2<f3,求系数

ao,a1,a2,使得二次函数

q(x)=a0+a1(x-x1)+a2(x-x1)(x-x2)

在这三点上与f(x)的函数值相等,可得到所有的系数。由dq/dx=0可得例题用二次插值法求解minf(x)=2x2+16/x，在区间[1,1.5]内的最小值。第二十七页，共四十五页，2022年，8月28日3-3多维梯度法(f)

minf(x)

s.t.f:Rn→R(

f连续可微)

取极值的必要条件：若x*－l.opt.←→▽f(x*)=0(驻点)

说明：

f(x)

≥f(x*)+▽Tf(x*)(x-x*),x.

故

f(x*)

≤f(x)，

x.(由于▽Tf(x*)=0

)1.最速下降法

方向：在迭代点x(k)

取方向d(k)=－▽f(x(k))

步长:精确一维搜索第二十八页，共四十五页，2022年，8月28日最速下降法（续）特点：

1)全局收敛,线性收敛;2)缺点:易产生扭摆现象而造成早停

(当x(k)距最优点较远时,速度快,而接近最优点时,速度下降)原因1：

f(x)=f(x(k))+▽Tf(x(k))(x-x(k))+o||x-x(k)||

当x(k)接近l.opt.时▽f(x(k)

)→0，于是高阶项

o||x-x(k)||的影响可能超过▽Tf(x(k))(x-x(k))

。原因2：第二十九页，共四十五页，2022年，8月28日最速下降法的流程x(1),ε>0,k=1||▽f(x(k))

||<ε?Yesstop.x(k)–解Nod(k)=－▽f(x(k))解minf(x(k)+λd(k))s.t.λ>0得x(k+1)=x(k)+λkd(k)k=k+1例题3-9用最速下降法求解:第三十页，共四十五页，2022年，8月28日3Newton法及其修正一、Newton法：

设f(x)二阶可微，取f(x)在x(k)点附近的二阶Taylor近似函数：

qk(x)=f(x(k))+▽Tf(x(k))(x-x(k))+(x-x(k))T▽2f(x(k))(x-x(k))

求驻点：

▽qk(x)=▽f(x(k))+▽2f(x(k))(x-x(k))=0

当▽2f(x(k))正定时，令上述方程解为x(k+1),有极小点：

Newton迭代公式:

x(k+1)=x(k)-[▽2f(x(k))]-1▽f(x(k))停止条件:||f(x(k))||<第三十一页，共四十五页，2022年，8月28日Newton法的计算流程x(1),ε>0,k=1

x(k+1)=x(k)+p(k)||f(x(k))||<?STOP.x(k+1)—l.optYesNok=k+1实用中，判断若▽2f(x(k))

非正定时进行相应处理例题3-11用Newton法计算Pk+1=-[▽2f(x(k))]-1▽f(x(k))第三十二页，共四十五页，2022年，8月28日特点：1)二阶收敛，局部收敛。（当x(k)充分接近x*时,局部函数可用正定二次函数很好地近似，故收敛很快）2)当f(x)为正定二次函数时，从任意初始点可一步迭代达到最优解说明:

设f(x)=xTQx+PTx+r,Qn×n对称正定,P∈Rn,r∈R.x(1),▽f(x(1))=Qx(1)+P▽2f(x(1))=Q迭代：

x(2)=x(1)-Q–1(Qx(1)+P)=-Q–1P(驻点即opt.)主要缺点：

(1)局部收敛

(2)用到二阶Hesse阵，且要求正定

(3)需计算Hesse阵逆或解n阶线性方程组，计算量大Newton法：（续）第三十三页，共四十五页，2022年，8月28日6、Newton法的改进（续）--------自己阅读和体会(1)为减小工作量，取m（正整数），使每m次迭代使用同一个Hesse阵，迭代公式变为：

x(km+j+1)=x(km+j)-[▽2f(x(km))]-1▽f(x(km+j))j=0,1,2,…,m-1,k=0,1,2,…

特点：收敛速度随m的增大而下降

m=1时即Newton法，m→∞即线性收敛。(2)带线性搜索的Newton法：在Newton迭代中，取d(k)=-[▽2f(x(k))]-1▽f(x(k)),

加入线性搜索：minf(x(k)+λkd(k))

求得λk,x(k+1)=x(k)+λkd(k)

特点：可改善局部收敛性，当d(k)为函数上升方向时，可向负方向搜索，但可能出现±d(k)均非下降方向的情况。第三十四页，共四十五页，2022年，8月28日二、算法流程图x(1),ε>0d(1)=-▽f(x(1)),k=1k=k+1k=1||▽f(x(k))||<ε?Stop.x(k)—解解minf(x(k)+λd(k))s.t.λ>0得λkx(k+1)=x(k)+λkd(k)

k=n?x(1)=x(n+1)d(1)=-▽f(x(1)),k=1求βkd(k+1)=-▽f(x(k+1))+βkd(k)yNyN重新开始第三十五页，共四十五页，2022年，8月28日6共轭梯度法共轭的概念:

对于方向pi,pj相对于nn对称正定矩阵Q共轭，则基本公式:停止条件:第三十六页，共四十五页，2022年，8月28日共轭梯度法算法特点1、全局收敛（下降算法）；线性收敛；2、每步迭代只需存储若干向量(适用于大规模问题)；3、有二次终结性（对于正定二次函数，至多n次迭代可达opt.）例题3-10

用共轭梯度法求解第三十七页，共四十五页，2022年，8月28日目标函数(f)minf(x),f:Rn→R1、基本思想：

用对称正定矩阵H(k)近似▽2f(x(k))的逆,而H(k)的产生从给定H(1)开始逐步修整得到。2、算法框图：x(1),H(1)对称ε>0,k=1d(k)=-H(k)▽f(x(k))一维搜索得λkx(k+1)=x(k)+λkd(k)||x(k+1)-x(k)||<ε?修正H(k)产生H(k+1)Stop.x(k+1)----解k=k+1yN5变尺度法第三十八页，共四十五页，2022年，8月28日5、变尺度法的主要特点：

⑴只需用到函数一阶梯度

(Newton法用到二阶Hesse阵）⑵下降算法，故全局收敛；⑶不需求矩阵逆；（计算量小）⑷一般可达到超线性收敛；（速度快）⑸有二次终结性。二DFP(Davidon(1959),FletcherandPowell(1963))法:

1、DFP法：以下省去各量上标，x,s,y,H

表示第k

步的量，等表示第k+1步的量。第三十九页，共四十五页，2022年，8月28日二、1、DFP法：（续）Ex.用DFP法求解minf(X)=10x12+x22解：取初始点x(1)=(1∕10,1)T,H(1)=I(单位矩阵)得到如下结果：（计算过程见下页）第四十页，共四十五页，2022年，8月28日第四十一页，共四十五页，2022年，8月28日2、BFGS法

BFGS(Broyden(1970),Fletcher(1970),Goldfarb(1970),Schanno(19