运筹学-第七章-非线性规划的基本概念和基本原理.ppt

《运筹学-第七章-非线性规划的基本概念和基本原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章非线性规划的基本概念和基本原理17.1数学模型和基本概念非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂。2一、数学模型例某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？分析：设长为米，宽为米，则有f(x)为非线性函数3例设某物理过程具有如下规律用试验法。现要确定参数使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足非负。4非线性规划：目标函数或（和）约束条件为非线性函数的规划。分析：f(x)为非线性函数，求最小。5主要内容非线性规划理论方

2、面应用方面算法方面互补稳定灵敏对偶问题最优性条件无约束问题直接法有约束问题间接法6一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)（P）gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)为En上的实函数。或7二、基本概念1、全局极值和局部极值为目标函数，为可行域。若存在，，都有，则称为该问题的全局极小点，为全局极小值。为目标函数，为可行域。若有，，都有，则称为该问题的严格全局极小点，为严格全局极小值。8若存在，令，都有，则称为该问题的局部极小点，为局部极小值。若存在，令，都有，则称为该问题的严格局部极小点，为严格局部极小值。相应

3、不等式反号，得到相应极大点，极大值定义。9定义如果X满足（P）的约束条件hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)则称XEn为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。10定义X*称为（P）的一个（整体）最优解，如果X*D，满足f(X)f(X*)，XD。定义X*称为（P）的一个（局部）最优解，如果X*D，且存在一个X*的邻域N(X*,)=XEnX-X*<,>0满足f(X)f(X*)，XDN(X*,)11f(X)局部最优解整体最优解122.梯度向量f(X)=gradf(X)=(

4、f/x1,f/x2,…..,f/xn)T区间内连续的梯度的性质：①在某点的f(X（0）)必与函数过该点的等值面的切平面相垂直。②梯度方向是函数值增加最快的方向（函数变化率最大的方向）负梯度方向是函数值减小最快的方向。13143、海赛(Hesse)矩阵2f(X)=H(X)2f/x122f/x1x2…..2f/x1xn2f/x2x12f/x22…..2f/x2xn……..2f/xnx12f/xnx2…..2f/xn2=152f(X)是对称矩阵。（f(X)二阶偏导数连续时，混合偏导数和取导数的顺序无关）f(X

5、)是二次函数，则可写成f(X)＝1/2XTAX+BTX+C则2f(X)＝A（与X的位置无关）164、正定矩阵、负定、半定、不定正定：特征值>0；各阶主子式>0(Ai>0)半正定：特征值≥0；detA=0,Ai≥0负定：特征值<0；Ai<0(i为奇）,Ai>0(i为偶）半负定：特征值≤0；detA=0，Ai≤0(i为奇）,Ai≥0(i为偶）不定：特征值有>0及<0；除了上述情况外即为不定。17例：判定正定性解：18例：判定正定性解：19作业：P2004.4（1）207.2无约束问题的极值条件例求解如下非线性规划问题o262621分析：非线性规划的最优解可能在可行域的

6、任一点达到。o226622若H(x)为正定，该驻点X*是严格局部极小值点；若H(x)为负定，该驻点X*是严格局部极大值点；若H(x)为半正定（半负定），则进一步观察它在该点某邻域内的情况，可能是可能不是；如果H(x)不定的，该驻点X*就不是f(X)极值点。一、用海赛矩阵判断驻点的性质23二、极值点的必要条件和充分条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？本质上把可行解集合的范围缩小。它是许多算法设计的基础。24无约束问题的最优性条件（P1）Minf(X)XEn定理3（一阶必要条件）设f(X)在X*点可微，则X*为（P1）的一个

7、局部极值点，一定有f(X*)=gradf(X*)=0（X*称为驻点）25无约束问题的最优性条件（P1）Minf(X)XEn定理4（二阶必要条件）设f(X)在X*点二阶可微，如果X*为（P1）的一个局部极小点，则有f(X*)=0和H（X*）为半正定。26无约束问题的最优性条件（P1）Minf(X)XEn定理5（二阶充分条件）设f(X)在X*点二阶可微，如果f(X*)=0和H(X*)为正定，则X*为(P1)的一个严格局部极小点。272829例Minf(X)=2x12+5x22+x32+2x2x3+2x1x3-6x2+3XE3解：f(X)=（4x1+2x