非线性规划样本

非线性规划

如果目的函数或约束条件中具有一种或各种是变量非线性函数，咱们称此类规划问题为非

线性规划（nonlinearprogramming,可简记为NP）。

普通地，解非线性规划问题要比解线性规划问题困难多，由「它不像解线性规划问题有单纯

形法这一通用办法，非线性规划当前还没有适合于各种问题普通算法，各个办法均有自己特

定应用范畴.

非线性规划基本概念和基本原理

第一节非线性规划数学模型

例：某金属制品厂要加工一批容积为1米3长方形容器，按规格规定，上下底材料为

25元/m2,侧面材料为40元/m2,试拟定长、宽、高尺寸，使这个容器成本最低。

设容器长为以宽为瓦则高为跖

依照题意得：

min/（M，x,）=50XR2+80]―-—（x（+x2）]

x^x2>0

例：某公司经营两种设备，笫一种设备每件售价30元，第二种设备每件售价为4S0元，依照

记录，售出一件第一种设备所需营业时间平均为0.5小时，第二种设备为B时,其中团是第二

种设备售出数量，已知该公司在这段时间内总营业时间为800小时，试决定使其营业额最大

营业筹划。

解：设该公司筹划经营第一种设备为2件，第二种设备为13件，依照题总得：

maxf（JV]yx2）=30为+450x2

•0.5x,4-（2-1-0.25X2）X2<800

X1,x2>0

由这两个例子可以看出，这两个例子在高等数学中代表了两类不同类型极值问题。例1

是无条件极值：例2是有条件极值。

如果令U是n维空间13上点，则普设非线性数学模型为:

min

//；（/）=0,i=1,2,…，m

gjW20,J=1,2,…，/

13为目的函数，E为约束条件，X为自变量。若某个约束条件是13不等式，不等式两边乘以

“-1”。

第二节极值问题

设团是定义在n维欧式空间空间团上某•区域13上n元函数，其中巴

对于团如果存在某一种。使得所有与B距离不大于03,（即13）,均满足区则称0为用在目

上局部极小点。田为局部极小值。

若所日田，HM有近则称（3为（3在（3上严格局部极小点。13为严格局部极小信。

若点瓦对于所有13,均满足团，则称U为13在团上全局极小点。团为全局极小值。

若对于所有国且回，均有氏则称3为由在图上严格全局极小点。（3为严格全局极小值。

如果将上述不等式反向，即可得到局部极大值与全局极大值定义。

定理1:极值必要条件

设（3是定义在自上某一区域用上函数,（3是团内一点，若自在回处可微且获得局部极值，则必有巧或圆,

上式点称为驻点，或平稳点。即在区域内部，极点必是驻点.（3称为3在点X处梯度。但反过

米，驻点不一定是极值点。如点（0,0）母国数13狂点，但不是极值点。

定理2:极值充要条件

设团是定义在B上某一区喇上函数,且在图上二次持续可微，团是团内一点，若ta在它处满足团

且对任意非零向量Y,有色则称（3在点目处获得严格局部极小值。这里同是用在点21处海赛矩阵。

若回则（3在点13处获得严格局部极大值。

山定理2看出，驻点处海赛矩阵13是正定矩阵时，函数团在点回处获得极小值。驻点处海赛矩

阵13是负定矩阵时，函数（3在点团处获得极大值。

定理3:设0是定义在13上函数，且在点0处存在二阶持续偏导数，若团是团局部极小点，则（3,且

图半正定。

需要指出是，定理2不是必要条件，定理3不是充分条件。

例：对于无约束问题

minf(X)=x：+=()；+xQ

解：由于0

令（3,得驻点0,

12x；+4君8万典

并且〃CO=

8X}X24*：+12^2

_o0

因此//（/）=

_00

日不是正定矩阵，但用在点13处获得最小值，即由为住严格局部极小点。

解：由于（3

令包，得伺

02020

//(/),//（A）,〃(元)

2X2-20-202

__90-_20

〃（K）=,//a,,）=

L0-2jLC2]

13是不定，因而13不是极值点；13是负定，故G3是极大点。团是正定，故团是严格极小点。

例：minf{X}=）；一

解：由于ffl,

令0,得用

〃⑴=〃⑴=12。

06*2）[00

日是半正定矩阵，但在13任意团邻域13内，总可以取到团，使得（3,即（3不是局部极小点。

例：minf（X）=­x1-x}-

33

解：由于团

令ffl,得团

0],〃(见)=\2O-

//(T)=:।

0-2]LO2

:

//(i3)=[■O-

02.

13是不定，因而13不是极值点;

13是负定，故(3是极大点。团是正定，故13是严格极小点。

非线性规划图解问题

图解法可以给人以直观概念，当只仃两个白变量时，非线性规划也像线性规划同样，可以运

用图解法。

例：用图解法求解非线性规划。

[minf[X}=(X,-2)2+(x,-I)2

例：＜

为+莅-5=0

若令目的函数瓦C为某一常数。则图就代表一条曲线，称为等位线或等高线。等值线田与直线

AB相切，切点为我

例：用图解法求解非线性规划。

2

minf(X)=(4-2尸+(x2-I)

天十々-5A0

x2>0

解：画出目的函数等值线

0,它表达一族中心在（2,1）上同心圆。

画出约束区域：先画13,这是一条抛物线，再画不等式瓦但所代表约束区域。则抛物线孤AB

CD为约束集。由动点A出发抛物线ABCD移动时，弧AB段，目的函数值下降，在BC

段函数值上升，弧CD段，目的函数值下降，并且在D点是可行域上使目的函数值最小点，

它是全局最长处。其坐标由约束方程组可得.最长处（4,1）,最优值机

第三节凸函数及其性质

一、凸函数

凸集、凸函数是研究非线性规划问题所不可缺少内容，关于凸集概念参见我性规划某些,

这里重要简介凸函数概念。

定义：设例是定义在n维欧式空间空何田中某个凸集团上函数，若对任意一种实数期以及图中任

意两点（3和（3,恒有13,

则称rco是定义在凸集c上凸函数。

若对任意一种实数团以及乐幽,恒有12,则称B是定义在凸集13上严格凸函数。

若上述不等式反向，称团分别为0上凹函数及严格凹函数。

下面给出凸函数与凹函数几何意义

即函数图形上任意两点连线处处不在这个函数图形下方，称它为凸函数，下凸。

线性函数既是凸函数，乂是凹函数。

下面简介凸函数性质。

性质I:设例是凸集用上凸函数,况且用则:在

性质2：设仍是凸集13上两个凸函数，姐和函数的仍是由上凸函数。

性质3：设田是凸集目上凸函数，对任意实数团13仍是凸集田上凸函数。

由性质2、性质3可得：

凸集B上有限个凸函数团正系数线性组合瓦仍是凸集团上凸函数。

性质4:设团是定义在凸集图上凸函数，则对每一种实数图，集合回是凸集。集合田称为实数13水

平集。

值得注意是，性质4逆命题不成立。

例：当团时，团是13上严格凹出数，而不是凸函数。

但对于一切瓦水平集13是凸集.

下面简介凸函数鉴定办法。

定理：设（2是凸集（3上具备一阶持续偏导数，则同是目上凸函数回对于任意两点（3,必有目

不等式是严格不等式时，即得严格凸函数充要条件。

即一种可微函数时凸函数O函数图形上任意一点处切平面位于•曲面下方。

定理：设团是凸第13上具备二阶持续偏导数，则13是13上凸函数U海赛矩阵13时整个团上是半正

定。

喇赛矩阵用是正定，则仍是严格凸函数,反之不成立。

凹函数和上面成果类似，在此就不重且。

例：设团，其中回是n阶对称矩阵,则

（1），是一"上凸函数O0为半正定矩阵。

（2）F是""上严格凸函数O0为正定矩阵。

证：二次函数闭在团上具备二阶持续偏导数，且

13由定理知，（1）成立。

卜面证（2）:由于团是闭上严格凸函数，当且仅当

0,任意①

即等价干£（「）＞f（X）+（OX+bY（Y—才）.X.YeR\XY.

由于13是二次函数,13为对称矩阵，因此上式等价于

13即故（3为正定矩阵。

例：证明（3为凹函数

证：

2222

df„dfodfdf.

ex：84333月

故EE为负定矩阵，故团为严格凹函数。

咱们懂得，普通来说，函数局部极值并•定就是全局极值，而解非线性翅划时，所求地

优解必要是目的函数在某个可行域上所有极值。但对于一类所给凸规划来比下面将看到,

其局部最优解必然是全局最优解。

定理：设团是凸集团上一种凸函数，则使得团获得极小值点集必是一种凸集，并HJ3任一局部极

小值也是它在（3上全局极小值。

该定理阐明，对于凸集上凸函数，所有极小点位于批准凸集中，即所有极小点集合形成•种

凸集，并且局部极小值也是全局极小值.

定理：设图是凸集团上一阶可微凸函数，点此且为田内点，则同为B在同上全局极小点用对于所有

国有同

由定理可知，当团为13内点时，上式对于任意（3都成立，即它意味着回，也就是，对于凸集

上凸函数，驻点就是全局极小点。

当前咱们回到非线性规划中：

非线性规划数学模型为:

minf〈X)(1)

力,(¥)=0,i=1,2,•••,Z7⑵

g,Cr)>0,j=1,2,...,/(3)

它与线性规划类似，把满足约束条件（2〉、（3）点称为可行点（可行解）。

所有可行解集合称为可行域。若某个可行解使目的函数（1）值最小，就称它为最优解。

下面咱们考虑一种比较特殊非线性规划：

minf{X}

n=M兄CONO,j=1,2,-,/}

其中,例是凸函数,13为凹函数5为凹函数），这样非线性规划称为凸规划。可以证明，凸划可

行域是凸集。

由此可知，凸规划局部最优解就曷它个局最优解。因而，凸规划是一种较简朴非线性规划。

例：求解依线性规划

min/(/)=-2*+1

S(才)=一1；+4^(+-5>0

s衣&(*)=-V)-2x2+4>0

xv/之0

解:晒塞矩阵为:

82f(X)d2fW'8?当(4)求孤了)

肃dxxdx2-2O"Ox；己丫0丫2[-20

〃⑴=1—，6（才）828(才)32©⑴一|00

才/(4)d2f(X}_02_

dxdxdx"2

21血百ax2_

由于B为正定矩阵，故13为严格凸函数：B为半定矩阵，所觉得为凹函数，B为线性函数，可以看

作凹函数。

因此，该非线性规划为凸规划。

如图所示，图中A点为最长处比目的函数最优侑为心

第四节下降迭代算法

对于求可微函数最优解，从理论上讲，咱们是•方面令函数梯度等于零（0）,求得驻点,

然后运用充分条件进行鉴别，求最优新。

但在实际中，对于普通n元函数目来说，由于团得到经常是一种非线性方程组，求它解相

称困难。此外诸多实际问题目的函数对各自变最偏导数不存在，从而无法运用上面所说求它

驻点，因而这时经常使用迭代法。

所谓迭代法，就是从已知点用出发，按照某种规则（即算法），求出比田更好解瓦（若极小化问

题，叫再按照此规则求出比国更好点画…如此重复这个过程，便产生一种点列瓦在一定条

件下，下降迭代算法产牛•点列收敛于原问题解。即团飒

称该点列卜叫收敛于工

由于算法产生点列使目的函数值逐渐减小，称这--算法为下降算法。

收敛速度

设算法产生点列，刚攵敛到解团且团,团，若存在（3,及一种与迭代次数k无关常数由，使

1.线性收敛：当团，（3时称为线性收敛速度。

2.超线性收敛：当0,0,或0,0IM,称为超线性收敛速度

3.二阶收敛：当G）,k充分大时有目

普通地以为，具备超线性收敛或二阶收敛速度算法是比较迅速算法。但是应当结识到,

对任意一种算法，收敛性和收敛速度理论成果并不保证算法在实际应用（执行）时一定有好

实际计算效果。一方面，由「这些理论成果白身不能保证算法一定行好侍性；另一方面是它

们忽视了计算过程中十分重要舍入误笄影响。

对于•不同问题，要依照详细状况来选取算法，由丁•咱们事先并不懂得最优解，迭代到什么时

候停止呢？惯用准则是：

（1）|片旬-卜£、,『（M，】））_£（『*））］<Q

卜-r（/u））||

-/

⑶|"（心））|</

迭代中咱们从•点出发沿卜降可行方向找•种新、性质有所改进点。

△下降方向：

设回，若存在0,使同则称（3为12点下降方向。

△可行方向：设瓦若存在瓦使团称团为田点可行方向。

同步满足上述两个性质方向称下降可行方向。

4.1惯用搜索算法构造

在以上迭代过程中，选用搜索方向以是最核心一步，计算各种算法区别，重要在于拟定

搜索方向办法不同。

拟定步长算法也向诸各种，步氏送定是由使目的附数值沿搜索方向下降最多根据，即沿

射线13求£极小。

即选用回使团由于这•工作是求觉得13变0•元函数13极小点13,故称为一维搜索或线性搜

索。由此拟定步氏为最佳步长。

一维搜索有一种重要性质：在搜索方向上所获得最长处处梯度和该方向正交。

即=0,

表述为定理如下:

定理：设目的函数（3具备一阶持续偏导数，回按下述产生:

f（M）+4/力=+2*））｝

¥（&.1）=一+"幻

则有

由于函数团在某点梯度和该点等值面切线正交，on个人一维搜索方向和其上最长处处等

值面相切。

第五节一维搜索

定理：设(3在13上单峰,13。那么

1°若13,则团,团；如左下图

2°若瓦则回团：如右下图

一、分数法(斐波那锲法)

分数法是寻找单峰函数极小点-一种办法。

设团在区间13上只有一种极值点团则对区间团内任意两点回国并计算心贝!必有下列两种

状况之一：

(1)0,此时必有此

(2)0,此时必有此

通过上面讨论，咱们懂得，只要在区间£3内取两个不同点，并算出这两点函数值，加以比较,

就能把搜索区向0缩小成团或巳。

如果继续缩社区间闭或同就需要在区间闭或片内取一点团，并计算出Pi值，并与目比较。

若团则田:

a,则a.

这样如此继续卜.去，就能越来越精准地预计出以位置,固然，如果无限地搜索卜.去，可以

精准地求出极小点机但实际计算时只能使g包括在某个社区间内，且此时社区间长度不超过

某一给定精度就可以了。如通过n次搜索后来，已知（2位于区间田中，且13,其中回是事先给定

精度，这时区间团中点都可以作为13近似点.

因而，当前咱们关怀是：进行n次搜索后，能把区间团缩小到什么限度？或者说，计算

n次函数值后来能把多长区间缩小成K度为1区间？

用13表达计算n个函数值能缩短为单位区间最大原区间氏度，显然有国

这是由于至少要计算两次函数值才干缩短区间，只计算零次或一次函数值是不能缩短

区间长度，故只有区间长度自身等于1时才行。

现考虑计算函数值两次情形：咱（把计算函数值点称为试算点或试点。

在区间（3内任取两点13,计算函数值以缩短区间，缩短后区间为B或13,显然，这两个区间长度

之和必不不大于ta区间长度。也就是说计算两次函数值普通无法把长度不不大于2区间缩

短成单位区间，但是对于长度为2区词，可以用如图办法选用试点瓦图中13为任意小正数,

缩短后区间长度我1+田，故缩短后区间长度近似等于1。由此得：

F?=2

依照同样办法，可行

握=3,居=5,片=8,片=13,•••

序列（3递推公式为:13

运用公式可计算出（3值如下:

n012345678910II

1123581321345589144

这里人就是普通所说裴波那锲数。

由以上讨论知，计算n次函数值所能获得最大缩短率（缩短后长度与原区间长度比）为

(3。

如团，即计算20个函数值可以把原区间长度为L区间缩短为B区间长度。

当前对于寻找近似极小点来说，如果但愿误差不超过区只需将原区间团缩短为包括极小点向

区间长度不竭过13区间就叮以了。这时计算函数值次数n只要满足：

0即可。rr时给出区间缩短绝对精度。规定。

分数法求近似极小点环节

(1)给出精度瓦求出使团最小整数n,

由团定出两个试点0,出

(2)计算例与13:

若同取(3

并令0,13。

若团，取团，

并令3,团。

(3)计算一比较它们大小。办法同(2)o

(4)当迭代到1<=91时，

Xn-l=Xn-\~(练-2+4-2)/2

这时无法比较函数值例与圆来拟定最后区间比为此取

Xn.\=(*+%)/2

*

X-I=4-2+(限2_*)*(1/2+£)

其中回是一种很小正数，这样就可以比较图与例值以拟定最后区间团，在田与6中其函数值较

小者为近似极小点，相应函数值为近似极小值。

例：试用分数发，求函数团在区间13上近似极小点和近似极小值，并规定误差不超过0.2。

解：不难验证,团在区间团上是仅有唯一收小点单峰函数，极小点为团，极小值团。下面运用分数

法求解。

已知GJ,故n=7,又知G,GJ

，取百=—2,b]-0.4762,

*2=4+3-可)4/8=-1.0476

*；=3=-0.4762

f(x2)=1.0499,f(^)=0.7504](*2)>fix?

取团，这样始终下去，最后可得：

由于瓦因而取团取(3为近似极小点，近似极小值以

二、0.618法(黄金分割法)

由上节讨论知，用分数法以n个试点来缩短某一区间时，区间长度第一次能短率为虱其

后各次分别为:便,图，…，瓦现将以上数列分为奇数项和偶数项，可以证明，这两个数量收敛

于同一种极限：

7+V5=0.6180339887118948

2

以不变区间缩短率0.618代替分数法每次不同缩短率，就得到黄金分割法(0.518法工它可

以当作是分数法近似，实现起来比较容易，效果也好。

详细算法如下：

例：为了提高某种化工产品质量指标，需要在制作过程中加入某种原料，已知其最佳加入量

在1000克到克之间某•点，当前通过实脸办法找到该点。

按0.618法来获取该点。

先做第一次实验，其加入量为:1000+0.382(-1000)=1382g：

再做第二次实验，加入成为：1000+0.618(—1000)=1618g：

(I)(2)

1OOO13822000

比较这两次实险成果。

如果第⑵点较第⑴点效果好，则去掉1000至1382这段，然后在留下一段中再找出第⑵点对

称点，做第三次实验，其加入量为1382+0.618(—1382)=1764g,

再比较第一次与第三次实验成果。

<^>17C4

<!><2>♦'

IOOO13H22000

如果依然是第⑵点较第(3)点效果好，则去掉1764至这一段，然后在留下一段中再找出

第⑷点对称点，做第四次实验，其加入量为1382+0.618(1764-1382)=1528g：

O

<■><-♦>

I4MM>."N，―门上2O«»<»

如果依然是第⑷点较第⑵点效果好，则去掉1618至1764这一段，对留下1382至1618这一

段中继续实验卜去就能找到最长处，这样可以用至少实验次数找到最佳加入量。

例：川黄金分割法求函数

山)=卜/2，%-2

[-x+3,x>2

在区间(3上极大点，规定缩短后长度不不不大于原区间长度15%。

解：已知⑸则

X、=0.382(3-0)=1.146,x\=0.618((3-0)=1.854,

F(S)=0.573,F(*；)=0.927

由于胤故原区间缩短匆3,令瓦瓦故原区间缩短为团。

令此故原区间缩短为田，

令㈣(2,故原区间缩短为&

由于g,以达到精度规定，停止迭代，得近似极大点和极大值团，此题精准最优解为巴

三、牛顿法（Newton）（切线法〉

上面咱们所讨论办法，只是对•某些点函数值大小进行比较，而函数自身并没有得到充分

运用，至于函数某些解析性质，更是宅无运用，下面简介牛顿法当函数性质具备较好解析性

质时，计算效果要比分数法、0.618法更好。

当前仍设13在［3上仅有一种极小点单峰函数，且具备二阶导数。

咱们懂得，如果函数13在处取极小值，则必It助因而求此函数极小点，只需求山羽在团内零点

即可。

对团在团点展开：

4'）=4J*4）1{xjxxj/2\o（xxj

取二次式（略去高阶项）：

团，用团作为®近似。

一方面求制导数，并令其等于零。

/（*）=尸（乙）+尸（*/*一相）=0,

得a,取［3为新迭代点。

以上过程即Newton法。

特点：二阶、局部收敛。（算法框怦见下页）

、a"on法算法框图

当团在团上仅有三阶导数,团，以及必，则切线法产生点列收敛到g在团中唯一极小点。

当团是具备极小点二次函数时，牛顿法可以•步达到极小点。

当13三阶导数在团内不不大于零时，迭代初始点田应在b端点附近，田三阶导数在司内不大于零时,

迭代初始点13应在a端点附近。

例：求minf(x}=tan-1tdt

解:0,0

迭代公式:0

取团算成果：

Axk夕dJ।/r（xA）

110.7854

2

2-O.57GH-0.4187

1.3258

30.1169-0.1164

1.0137

4>0.001095-0.001Q9S

xs«x，=0

取(3计算成果如卜.:

A

1.1071

2-3.5357-1.2952

13.50

313.95不收敛•

例：用牛顿法求13在区间团上极小点。

解：由于瓦由此可知，在团上瓦而在团上有唯一极小点跖

下面用牛顿法来求。

2(3初始点选在接近5一端，取初始点瓦并取精度13。

EL计算血胤计算电血

计算

0,0,停止迭代。

取x*=3.0001,f(**)=3.0000009»

四、抛物线法(插值法)：

1.插值法概念

假定咱们给定问题是在某一拟定区间内谋求函数极小点位置，但是没有函数表达式，只有若

干实瞬点处困数值。咱们可以依照这些函数值，构成一种与原目的函数相接近低次插值多项

式，用该多项式最优解作为原函数最优解近似解，这种办法是用低次插值多项式逐渐遇近原

目的函数极小点近似求解办法，称为播值办法或函数逼近法。

上面牛顿法需要计算卧-阶导数、二阶导数，“物很豆杂时，计算起来相称困潍。抛物线法是

一种多项式逼近，即用一种二次多项式13来逼近所给函数瓦并用13极小点来近似13极小点，在

整个计算过程中，只需要计算(3值。其基本思想就是用二次三项式来逼近目的函数。

2.插值法与出探法区别

实验点位置拟定办法不同。在试探法中实脸点位置是由某种给定规律拟定，并未考虑函数值

分布。例如：黄金分割法是按照等比例0.618缩短率拟定。而在插值法中，实验点位置是按

函数值近似分布极小点拟定。试探法仅仅运用/实验点函数值进行大小比较，而插值法还要

运用函数值自身。因此，当函数具备较好解析性质时，插值办法比试探办法效果更好。

3.二次插值法概念

运用原目的函数上三个插值点，构成一种二次插值多项式，用该多项式最优的作为原函数最

优解近似解，逐渐逼近原目的函数极小点，称为二次插值办法或抛物线法。

4.二次插值函数构成

设一维目的函数搜索区间为⑼取三点0,其中回取区间端点，即

a<—*1，/—6

而且为区间内一种点，开始可以取区间中点，即

=0.5（$

x2十公）

计算函数值/；=

过函数曲线上三点团作二次插值多项式团，满足条件

夕（巧）=力*:+屈勺+J=f\

■尸（*2）=力啊？+欧2+6=6

P,s）=力/2+/3+G=6

解方程组，得待定系数ABC分别为

（巧一+（*3-+（*1—巧）/

（a-&）（4-Vj）

x2）（x2-

（考-考）44-（Xj-4」+（xf-*；）/；

15=----------:-----------:-------------------------------

（X,-X.,）（x2-X3）（*3-*1）

（*3-X2）X2X3/J-（*]-*3）*1*34+（*2—尸1）*]*24

（*3-3）

（占-X2）（々-/）

于是函数国就是一种拟定二次多项式，称二次插值函数，如图所示，虚线某些即为二次插值

函数