运筹学——非线性规划

《运筹学——非线性规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《运筹学》第六章非线性规划Prof.梁军jliang@iipc.zju.edu.cn0571-879538836.1非线性规划问题与数学模型先看两个例子：1非线性规划的提法如果目标函数或约束条件方程中存在任何非线性因子，则问题为非线性规划。非线性规划在工程、军事、经济等许多领域都得到广泛的应用。例2-8设平面上有m个点，找覆盖这m个点的最小园盘。解设m个点为pii,1,2,m，则平面上任一点x到这m个点的距离最大者满足fx()maxxpi（2-28）1im则以x为园心，fx()为半径的园

2、盘必覆盖这m个点，于是问题转化为求解最小半径的园盘问题minmax1imxpi（2-29）这是一个无约束的非线性规划问题。非线性规划的一般形式为minfx()(2-33)st..gx()0,i1,2,mihx()0,j1,2,l(2-34)j式中，目标函数fx()，不等式约束条件gxi()和等式约束条件hxj()至少一个是非线性函数。当不存在约束条件，即决策变量x可取任意点时，minfx()(2-35)称为无约束非线性规划问题。非线性规划的约束条件有时写成域约束形式，令Sxgxi

3、

4、ij()0,1,2,m;hxj()0,1,2,l,称S为可行域，S中的点为可行点，上述约束非线性规划问题（2.33-2.34）等价于minfx()st..xS(2-36)而无约束非线性规划问题等价于nminfxx(),(2-37)n是n维欧氏空间。2非线性规划的基本性质非线性规划问题的求解一般通过两种途径来实现，一种是基于目标函数和约束条件的函数分析性质直接加以求解的解析解法，多适用于具有良好函数解析性质的少数非线性规划问题；另一种是基于循环迭代算法的数值求解法，适用于大部分非

5、线性规划问题。在进一步讨论解析解法之前，先引入非线性规划问题全局最优解和局部最优解的定义。定义2-1全局最优解设fx()为目标函数，S为可行域，xS。若对每一个xS都有**fxfx()(),则称x为极小化问题（2.3.6）的全局最优解（最小）。定义2-2局部最优解*设fx()为目标函数，S为可行域，xS。若存在x的一个邻S，使得对每一个**域xS都有fxfx()(),则称x为极小化问题（2-36）的局部最优解（最小）。凸规划是非线性规划中一种重要的特殊情况，具有许多良好的解析性质，

6、可以用解析解法求解。n定义2-3设S为中的一个集合，若对S中任意两点，连接它们的线段仍属于S，即对S中任意两点xx12,及每个实数]1,0[，都有xx12(1)S则称S为凸集，xx12(1)称为x1和x2的凸组合n定义2-4设S为中的非空凸集，f是定义在S上的实函数。如果对任意的xx12,S及每个数λ（0，1），都有fx((1))()(xfx1)()fx，则称f为S上凸函1212数。如果对任意相异的xx12,S及每个数λ（0，1），都有fx((

7、1))()(xfx1)()fx，则称f为S上的严格凸函1212数。如果f为S上的凸函数，则称f为S上的凹函数。定义2-5若式（2-33）的fx()是凸函数，式（2-34）的gxi()是凹函数，hxj()是线性函数，则求凸函数在凸集上的极小点问题称为凸规划。凸规划的解析解具有以下性质。n引理2-1设S是中的凸集，f是定义在S上的凸函数，则f在S的内部连续。n引理2-2设f是一个凸函数，x,在x处fx()取有限值，则f在x处沿任何方向都存在右侧导数和左侧导数（包括±∞）。为方便非线性规划的

8、求解，还要引入函数梯度和Hesse矩阵概念。n定义2-6设函数fxx(),存在一阶偏导数，则称向量Tffffx(),,xx12xnT为fx()在点xxxx12,,n处的梯度。定义2-7设函数fx()存在二阶偏导数，则称矩阵222fff2xxxxx1121n22ff2f2Hx()xxxxx2122n222fff2xxxxxnn12nTxx

9、xx,,处的Hesse矩阵。为fx()在点12n由梯度和Hesse矩阵的上述定义，无约束非线性规划问题（2.37）的局部极小点的解析解可由以下定理求出。3非线性规划的解析求解引理2-3局部极小点的一阶必要条件**设函数fx()在点x处可微，若x是局部极小点，则梯度f(x)0。引理2-4局部极小点的二阶必要条件**设函数fx()在点x处二次可微，若x是局部极小点，则梯度*f(x)0，并且Hesse矩阵Hx()是半正定的。上