非线性规划运决筹胜帷千幄非线性规划里之之中外Non-linear Programming第1页
非线性规划基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法第2页
基本概念非线性规划问题非线性规划方法概述第3页
非线性规划问题例1曲线的最优拟合问题已知某物体的温度ϕ与时间t之间有如 ϕ下形式的经验函数关系： ct3ϕ=c+ct+e (*) 12其中c，c，c是待定参数。现通过测 123试获得n组ϕ与t之间的实验数据(t,ϕ)， iii=1，2，…,n。试确定参数c，c，c， 123使理论曲线(*)尽可能地与n个测试点 t(t,ϕ)拟合。 iinct23imin [ϕ−(c+ct+e)]∑i12ii=1第4页
例2 构件容积问题x3设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S， 圆锥部分的高h和圆柱部分的高x之 2x2比为a。确定构件尺寸，使其容积最 大。 x12⎧max V=(1+a/3)πxx12⎪⎪. πxx+ax+2πxx+πx=S⎨112121⎪ x≥0,x≥012⎪⎩第5页
数学规划Tnn设x=(x,...,x)∈R，f(x);g(x),i=1,...,p;h(x),j=1, ,...,q:RaR1nij如下的数学模型称为数学规划(Mathematical Programming, MP)： ⎧min f(x)⎪. g(x)≤0,i=1,...,p ⎨i⎪ h(x)=0,j=1,...,qj⎩⎧g⎫(x)≤0,i=1,...,p⎪⎪inX=x∈R⎨⎬约束集或可行域h(x)=0,j=1,...,q⎪⎪j⎭⎩MP的可行解或可行点∀ x∈X第6页
向量化表示T令 g(x)=gxgx ((),...,())1pTh(x)=(h(x),...,h(x))， 1pnpnq其中，g:RaR,h:RaR，那么(MP)可简记为 min f(x)⎧⎪. g(x)≤0或者minf(x) ⎨x∈X⎪ h(x)≤0 ⎩当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。第7页
最优解和极小点*定义 对于非线性规划(MP)，若x∈X，并且有 *f(x)≤f(x), ∀ x ∈X **则称x是(MP)的整体最优解或整体极小点，称f(x)是 (MP)的整体最优值或整体极小值。如果有 **f(x)<f(x), ∀ x ∈X, x≠x *则称x是(MP)的严格整体最优解或严格整体极小点，称 *f(x)是(MP)的严格整体最优值或严格整体极小值。 **定义 对于非线性规划(MP)，若x∈X，并且存在x的一个 *n*领域N(x)={x∈Rx−x<δ} (δ>0,δ∈R)，使 δ**f(x)≤f(x), ∀ x∈N(x)X， δI**则称x是(MP)的局部最优解或局部极小点，称f(x)是(MP)的局部 最优值或局部极小点。如果有 ***f(x)<f(x), ∀ x∈N(x)X, x≠x， δI**则称x是(MP)的严格局部最优解或严格局部极小点，称f(x)是(MP) 的严格局部最优值或严格局部极小点。 第8页
非线性规划方法概述nnn定义 设f:RaR,x∈R,p∈R,p≠0，若存在δ>0 ，使f(x+tp )<f(x), ∀t∈(0,δ)则称向量p是函数f(x)在点x处的下降方向。 nn定义 设X⊂R,x∈X,p∈R,p≠0，若存在t>0，使 x+ tp∈X则称向量p是函数f(x)在点x处关于X的可行方向。 第9页
非线性规划基本迭代格式第1步 选取初始点x，k:=0; 0k第2步 构造搜索方向p； k第3步 根据p，确定步长t； kk+1kk第4步 令x=x+tp， kk+1若x已满足某种终止条件，停止迭代，输出 k+1近似解x；否则令k:=k+1，转回第2步。 第10页
凸函数和凸规划凸函数及其性质凸规划及其性质第11页
凸函数及其性质n定义 设S⊂R是非空凸集，f:SaR，如果对任意的α∈(0,1)有121212f(αx+(1−α)x)≤αfx+−αfx，∀xx∈S ()(1)(),则称f是S上的凸函数，或f在S上是凸的。如果对于任意的α∈(0,1)有 121212f(αx+(1−α)x)<αf(x)+(1−α)f(x)，x≠x 则称f是S上的严格凸函数，或f在S上是严格凸的。 若-f是S上的（严格）凸函数，则称f是S上的（严格）凹函数，或f在S上是（严格）凹的。 第12页
n定理 设S⊂R是非空凸集。 n（1） 若f:RaR是S上的凸函数，α≥0，则αf是S上的凸函数； n（2） 若f,f:RaR都是S上的凸函数，则Sf+f是上的凸函数。 1212nn定理 设S⊂R是非空凸集，f:RaR是凸函数，c∈R，则集合 H{(f,c)=x∈Sf(x)≤c} S是凸集。 第13页
n定理 设S⊂R是非空开凸集，f:SaR可微，则 （1） f是S上的凸函数的充要条件是 1T212112∇f(x)(x−x)≤f(x)−f(x)， ∀ x,x∈S 11∂f(x)∂f(x)1T1其中∇f(x)=(,....,)是函数f在点x处的一阶 1n∂x∂x导数或梯度。 （2） f是S上的严格凸函数的充要条件是 1T21211212∇f(x)(x−x)<f(x)−f(x)， ∀ x,x∈S,x≠x 第14页
n定理 设S⊂R是非空开凸集，f:SaR二阶连续可导，则f是2S上的凸函数的充要条件是f的Hesse矩阵∇f(x)在S上是半正定的。2 当∇f(x)在S上是正定矩阵时，f是S上的严格凸函数。（注意：该逆命题不成立。） 222⎡⎤∂f(x)∂f(x)∂f(x)....⎢⎥2∂x∂x∂x∂x∂x1121n⎢⎥222∂f(x)∂f(x)∂f(x)⎢⎥...⎢2⎥∂x∂x∂x∂x∂x22122n∇f(x)=⎢⎥ ..⎢⎥⎢⎥..⎢⎥222∂f(x)∂f(x)∂f(x)⎢⎥2⎢⎥∂x∂x∂x∂x∂x⎣n1n2n⎦第15页
凸规划及其性质⎧min f(x)⎪. g(x)≤0,i=1,...,p (MP)⎨i⎪ h(x)=0,j=1,...qj⎩⎧g(x)≤0,i=1,...,p⎫⎪⎪inX=x∈R⎨⎬约束集h(x)=0,j=1,...,q⎪⎪j⎭⎩如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。第16页
定理 对于非线性规划(MP)，若g(x),i= 1,...,pin皆为R上的凸函数，h(x),j=1,...,q皆为线性函数， j并且f是X上的凸函数，则(MP)是凸规划。 定理凸规划的任一局部最优解都是它的整体最优解。第17页
一维搜索方法¾精确一维搜索方法法目标函数为单变量的非线性 规划问题称为一维搜索问题 Newton法min ϕ (t) t≥0¾非精确一维搜索方法(0≤t≤t)max其中t∈R。 Goldstein法Armijo法第18页
法（近似黄金分割法）*函数ϕb](t)称为在[a,上是单谷的，如果存在一个t∈[a,b]，使得ϕ (t)**在[a,t]上严格递减，且在[t,b]上严格递增。区间[a,b]称为ϕ(t)的单 谷区间。 第1步 确定单谷区间[a,b]，给定最后区间精度ε>0; 第2步 计算最初两个探索点 t=a+(b−a)=b−(b−a )1t=a+(b−a )2并计算ϕ=ϕ(t)，ϕ=ϕ(t)； 1122第3步 若ϕ≤ϕ，转第4步。否则转第5步； 12第4步 若t−a≤ε，停止迭代，输出t。否则令b:=t， 212t:=t，t:=b−(b−a)，ϕ:=ϕ，计算ϕ=ϕ(t)，转第3步； 2112111第5步 若b−t≤ε，停止迭代，输出t。否则令a:=t， 121t:=t，t:=a+(b−a)，ϕ:=ϕ，计算ϕ=ϕ(t)，转第3步。 1221222第19页
Newton法min ϕ(t) ′′其中ϕ(t)是二次可微的，且ϕ(t)≠0。 第1步 给定初始点t，ε>0，k:=1； 1′′′第2步 如果ϕ(t)<ε，停止迭代，输出t。否则，当ϕ(t)=0时，停止， kkk′′解题失败；当ϕ(t)≠0时，转下一步； k′ϕ(t)k第3步 计算t=t−，如果t−t<ε，停止迭代，输出t。否则k+1kk+1kk+1′′ϕ(t)kk:=k+1，转第2步。 第20页
Goldstein法y=ϕ(t)ϕ(0)y=ϕ(0)+mϕ(0)t1y=ϕ(0)+ϕ(0)ty=ϕ(0)+mϕ(0)t2abcd第21页
Goldstein法步骤第1步 给定满足0<m<m<1的正数m,m，增大探索点系数α>1； 1212初始探索点t∈(0,+∞)（或(0,t]）。令a:=0,b:=+∞（或t），k:=0 0max00max第2步 计算ϕ(t) k′若ϕ(t)≤ϕ(0)+mtϕ(0)，进行第3步；否则，令a:=a ,b:=tk1kk+1kk+1k转第4步； ′第3步 若ϕ(t)≥ϕ(0)+mtϕ(0)，停止迭代，输出t。否则，令 k2kka:=t,b:=b k+1kk+1k若b<+∞，进行第4步；否则，令t:=αt,k:=k+1，转第2步； k+1k+1ka+bk+1k+1第4步 取t:=，令k:=k+1，转第2步。 k+12第22页
Armijo法y=ϕ(t)ϕ(0)y=ϕ(0)+mϕ(0)ttMtkk取定0<m<1<M，用一下两个式子限定t不太大也不太小： k′ϕ(t)≤ϕ(0)+mtϕ(0) kk′ϕ(Mt)>ϕ(0)+mMtϕ(0) kk第23页
无约束最优化方法min f(x) (UMP)Tnn其中x=(x,...,x)∈R，f:RaR 1n无约束问题的最优性条件最速下降法共轭方向法第24页
无约束问题的最优化条件nnn定理 设f:RaR在点x∈R处可微。若存在p∈R，使 T∇f(x)p<0 则向量p是f在点x处的下降方向。 nn*定理 设f:RaR在点x∈R处可微。若x是(UMP)的局部最优解，则 * ∇f(x)=0 nn2*定理 设f:RaR在点x∈R处的Hesse矩阵∇f(x)存在。若 *2*∇f(x)=0，并且∇f(x)正定 *则x是(UMP)的局部最优解。 n*nn定理 设f:RaR，x∈R，f是R上得可微凸函数。若有*∇f(x)=0 *则x是(UMP)的整体最优解。 第25页
最速下降法n设（NMP）问题中的目标函数f:RaR一阶连续可微 0第1步 选取初始点x，给定终止误差ε>0，令k:=0； kkk第2步 计算∇f(x)，若∇f(x)≤ε，停止迭代，输出x。否则进行第3步；kk第3步 取p=−∇f(x) kkkk第4步 进行一维搜索，求t，使得f(x+tp)=minf(x+tp) kkt≥0k+1kk令x=x+tp，k:=k+1，转第2步。 k第26页
共轭方向法in定理 设A是n阶实对称正定矩阵，p∈R(i=0,1,...,n−1)是 01n−1非零向量。若p,p,...,p是一组A共轭方向，则它们一定是线性无 关的。 n定义 设A为n阶实对称，对于非零向量p,q∈R，若有 TpAq=0 in则称p和q是相互A共轭的。对于非零向量组p∈R,i=0,1,...,n−1，若有 iTjpAp= ()0, i,j=0,1,...,n−1 i≠j01n则称p,p,...,p是A共轭方向组，也称它们为一组A共轭方向。 第27页
二次严格凸函数的无约束最优化问题1TTminfx=xAx++ ()bxc（AP） 2n其中A是n阶实对称正定矩阵，b∈R，c∈R 01n−1定理 对于问题(AP)，若p,p,...,p为任意一组A共轭方向，则由任意初始点0n01n−1x∈R出发，依次沿p,p,...,p进行精确一维搜索，则最多经n次迭代可达(AP) 的整体最优解。 第28页
F-R法步骤0第1步 选取初始点x，给定终止误差ε>0； 000第2步 计算∇f(x)，若∇f(x)≤ε，停止迭代，输出x；否则，进行第3步； 00第3步 取p=−∇f(x)，令k:=0； kkkkk+1kk第4步 进行一维搜索求t使得f(x+tp)=minf(x+tp)，令x=x+tp； kkkt≥0k+1k+1k+1第5步 计算∇xf(x)，若∇f(x)≤ε，停止迭代，输出；否则，进行第6步； 0n第6步x:=x 若k+1=n，令，转第3步；否则进行第7步； 2k+1∇f(x)k+1k+1k第7步 用F-R公式取p=−∇f(x)+λp，其中λ=。令k:=k+1， kk2k∇f(x)转第4步。 第29页
约束最优化方法⎧min f(x)⎪. g(x)≤0 i=1,...,p⎨i(MP)⎪ h(x)=0 j=1,...,q j⎩nnx∈R, f:RaR ng:RaR, i=1,...,pi其中nh:RaR j=1,...,qj约束最优化问题的最优化条件简约梯度法惩罚函数法第30页
约束最优化问题的最优化条件⎧g(x)≤0,i=1,...,p⎫⎪⎪inX=x∈R⎨⎬h(x)=0,j=1,...,q⎪⎪j⎭⎩**J={1,2,...,q}，即h(x)=0, j∈J∀ x∈X令j**I(x)={i| g(x)=0,i∈I}inn**定理 设f:RaR和g:RaR,i∈I(x)在点x处可微， i**n*g,i∈I\I(x)在点x处连续，h:RaR,j∈J在点x处连续 ij***可微，并且各∇g(x), i∈I(x), ∇h(x), j∈J线性无关。若 ij****x是(MP)的局部最优解，则存在两组实数λ,i∈I(x)和μ,j∈J， ijK-T条件使得 *****⎧∇f(x)+λ∇g(x)+μ∇h(x)=0∑∑iijj⎪*j∈Ji∈I(x) ⎨**⎪λ≥0, i∈I(x)⎩i第31页
*定理 对于(MP)问题，若f, g,i∈I, h,j∈J在点x处连续可微， ij**可行点x满足(MP)的K-T条件，且f, g,i∈I(x)是凸函数，h ,j∈Jij*是线性函数，则x是(MP)的整体最优解。 第32页
简约梯度法min f(x)⎧⎪. Ax=b ⎨()⎪ x≥0⎩nnm其中，x∈R, f:RaR，r(A)=m，b∈R m×nnX={x∈R| Ax=b, x≥0}lk定理 对于非线性规划问题()，设f是可微函数，x∈X，并且有分解lkk⎛⎞⎛⎞xpBBkkk⎜⎟⎜⎟x=，x>0。若p=由下式确定， Bkk⎜⎟⎜⎟xp⎝N⎠⎝N⎠kk⎧⎧−r, r≤0⎪iikkk⎪p:p= i∉I⎨NiBkkk⎪ (*) −xr r>0⎨⎩iii⎪k−1kp=−BNp⎩BkkN则 kkk（1） 当p≠0时，p是f在点x处关于X的可行下降方向； lkk（2） p=0的充要条件是x是问题()的K-T点。 第33页
Wolfe法步骤0第1步 选取初始可行点x∈X，给定终止误差ε>0，令k:=0; lkk第2步 设I是x的m个最大分量的下标集，对矩阵A进行相应分解 BA=(B,N) kkk⎛⎞∇f(x)Bk⎜⎟第3步 计算∇f(x)=，然后，计算简约梯度 k⎜⎟∇f(x)⎝N⎠k−1Tkkr=−(BN)∇f(x)+∇f(x) NkkBNkkk记r的第i(i∉I)个分量为r； NBikk第4步 按(*)式构造可行下降方向p。若p≤ε，停止迭代，输出kx； 否则进行第5步； 第5步 进行有效一维搜索，求解 kkminf(x+tp) k0≤t≤tmaxk得到最优解t，其中 k⎧+∞ p≥0⎪kkt=⎧， ⎫⎨xmax⎪ikkkmin−p<0 p<0或者p=0⎨⎬i⎪k1≤i≤np⎪i⎭⎩⎩k+1kk令x=x+tp，k:=k+1，转第2步 k第34页
惩罚函数法思想：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把(MP)问题的求解转换为求解一系列无约束非线性规划问题。9罚函数法9障碍函数法第35页
罚函数法⎧min f(x)⎧⎪g(x)≤0,i=⎫1,...,p⎪⎪. g(x)≤0,i=1,...,p⎨iX=x∈R⎨⎬h(x)=0,j=1,...,q⎪⎪⎪j⎭⎩ h(x)=0,j=1,...,qj⎩设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。pqc22p(x)=c[max(g(x),0)]+[h(x)]c∑∑ij罚函数2i=1j=1F(x)=f(x)+p(x)ccmin第36页 F(x)c
实际应用中，选取一个递增且趋于无穷的正罚函数参数列min F(x)=f(x)+p(x)**cckkpqc2k2p(x)=c[max(g(x),0)]+[h(x)]∑∑***其中ckijk2i=1j=1第37页
罚函数法计算步骤0第1步 选取初始点x，罚参数列{c}(k=1,2,...)， k给出检验终止条件的误差ε>0，令k:=1； 第2步 按(***)构造函数p(x)，再按(**)构造(MP) ck的增广目标函数，即F(x)=f(x)+p (x)cckkk−1第3步 选用某种无约束最优化方法，以x为初始点， kk求解min F(x)，设得到最优解x。若x已满足某种 ckk终止条件，停止迭代，输出x。否则令k:=k+1，转第2步； 第38页
障碍函数法min f(x)⎧⎨. g(x)≤0,i=1,...,p⎩iT令g(x)=(g(x),...,g(x))1p可行域X的内部记为 onX={x∈R| g(x)<0} 在可行区域的边界上筑起一道“墙”，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。第39页
构造障碍函数o当x∈X时， pp1B(x)=−d或B (x)=−dln[−g(x)]dk∑dk∑ikkg(x)i=1i=1i其中，d为罚参数或罚因子 kF(x)=f(x)+B(x)ddkkmin F(x), k=1,2,...dk第40页
障碍函数法步骤0o第1步 选取初始点x∈X，罚参数列{d}(k=1,2,...)， k给出检验终止条件ε>0，令k:=1； 第2步 做障碍函数B(x)，构造增广目标函数 dkF(x)=f(x)+B (x)ddkkk−1第3步 选用某种无约束最优化方法，以x为初始点求解 omin F(x), x∈X dkkk得到最优解x。若x已满足某种终止条件，停止迭代，输出 kx。否则，令k:=k+1，转第2步。 第41页
