运筹学课件第六章 非线性规划.ppt

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

1、运筹帷幄之中决胜千里之外运筹学非线性规划Non-linearProgramming第六章非线性规划基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法第一节基本概念非线性规划问题非线性规划方法概述一、非线性规划问题引例例1曲线的最优拟合问题例2构件容积问题设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积为S，圆锥部分的高h和圆柱部分的高x2之比为a。确定构件尺寸，使其容积大。h二、数学模型约束集或可行域其中x=(x1,x2,...,xn)T∈Rn，D中的点称为可行解或可行点三、分类（1）线性规划：目标函数和约束条件皆为x的线性函数。（2）非线性

2、规划：目标函数和约束条件中至少有一个是x的非线性函数。本章讨论非线性规划。（1）当p=0,q=0,即可行域D=Rn时，(P)可写成称为无约束非线性规划或无约束最优化问题。（2）若可行域D≠Rn，(P)称为约束非线性规划或约束最优化问题。定义1对于非线性规划(P)，若并且存在x*的一个领域则x*称为局部最优解或局部极小点，称f(x*)为局部最优值或局部极小值。则称x*为严格局部最优解或严格局部极小点,称f(x*)为严格局部最优值或严格局部极小值。若使得使得四、最优解和最优值四、最优解和最优值全局最优解为x*=(1/2,1/2)T,全局最优值为f(x*)=1/2。1x1x

3、21x*若目标函数改为：其最优解和最优值如何？五、非线性规划方法概述迭代法:按某种方法给出目标函数极小点的一个初始估计，称为初始点。然后按某种特定的迭代规则产生一点列{xk}，使得{xk}为有穷点列时，其最后一个点是最优解；当{xk}是无穷点列时，其极限点是最优解(此时称该方法是收敛的)。定义3则称向量p是函数f(x)在点处的下降方向。定义4则称向量p是函数f(x)在点处的可行方向。图例说明。基本迭代格式第1步选取初始点,k:=0;第2步构造搜索方向第3步根据，确定步长第4步若xk+1已满足某种终止条件，停止迭代，输出近似解.否则令k:=k+1，转回第2步。随机性方法

4、是按照某种规则随机产生迭代点,迭代点列依概率收敛到最优解，包括遗传算法,模拟退火算法,神经网络算法等,这类方法具有对函数性质要求低、容易实现等优点,但效率低、可靠性差、不能保证产生优化问题的最优解.全局优化算法概述全局优化方法可分为随机性方法和确定性方法.全局优化算法概述确定性方法充分利用了问题的解析性质,如函数的凸性、单调性、稠密性等,产生一个确定性的有限或无限点序列,使得该点序列收敛于全局最优解.包括分枝定界算法、区间算法、填充函数法、割平面法、顶点枚举法等,这类算法在理论上有较强的可行性,但对较为复杂的大型优化问题却难于应用.全局优化方法可分为随机性方法和确定性

5、方法.第二节凸函数和凸规划凸函数及其性质凸规划及其性质一、凸函数及其性质定义5设是非空凸集，如果对任意的有则称f是S上的凸函数，或f在S上是凸的。有则称f是S上的严格凸函数，或f在S上是严格凸的。如果对于任意的若–f是S上的（严格）凸函数，则称f是S上的（严格）凹函数或f在S上是（严格）凹的例1线性函数在Rn上既是凸函数又是凹函数。例2函数证证证:(1)定理1(1)若f(x)是S上的凸函数，都是S上的凸函数,是S上的凸函数。是非空凸集。(2)则也是S上的凸函数。凸函数的性质定理1(1)若f(x)是S上的凸函数，是S上的凸函数。是非空凸集。凸函数的性质都是S上的凸函数,

6、(2)则也是S上的凸函数。证:(2)定理2设是非空凸集，是凸函数，，则集合是凸集。证：水平集又因f是S上的凸函数，所以凸函数的性质定理3设是非空开凸集，，是函数f在点处的梯度（1）f是S上的凸函数的充要条件是（2）f是S上的严格凸函数的充要条件是可微，则凸函数的判定证(1)必要性.设f是S上的凸函数，则对代入得由泰勒公式得证（1）（2）对和充分性.设定理4设是非空开凸集，则f是S上的凸函数的充要条件是f的Hesse矩阵在S上是半正定的.注意：该逆命题不成立。f在S上二阶连续可导,在S上正定时，f是S上的严格凸函数.凸函数的判定二次型二次型函数其中x∈Rn,A是一个n阶

7、对称矩阵，所以当且仅当A为半正定矩阵时，f(x)是凸函数。A为正定矩阵时，f(x)是严格凸函数。例二、凸规划及其性质约束集如果(P)的约束集D是凸集，目标函数f是D上的凸函数，则(P)叫做非线性凸规划，或简称为凸规划。非线性规划定理5对于非线性规划(P)，若并且f是D上的凸函数，则(P)是凸规划。皆为Rn上的凸函数，皆为线性函数证：又因f是D上的凸函数，(P)是凸规划定理6凸规划的任一局部最优解都是它的全局最优解。证：又因f是凸函数，所以矛盾例：验证下列规划为凸规划第三节一维搜索方法★非精确一维搜索方法Goldstein法Armijo法★精确一维搜索