资源描述：
《第3讲 非线性规划 在目标和约束中有非线性成分(非线性规划问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3讲非线性规划在目标和约束中有非线性成分®非线性规划问题§1基本概念一、非线性规划的数学模型1.引例例1某公司经营产品I,II(见下表).第41页共41页I(x1)II(x2)限时服务时间0.52+0.25x2800售价30(元)450(元)求最大营业计划.问题归结为例2产品销售与多因素相关,设已知比值第41页共41页求各权重,使2.一般非线性模型(其余可化作此类型)第41页共41页或较一般的形式R称为问题的可行域若遇,则两边乘第41页共41页若遇max,可换为min{-}二、二维问题图解(高维意义
2、类似)立体上分析例1最优解为演示若第41页共41页则最优解为(注:此时约束无效)平面上分析在平面上作目标函数等值线®.可行域如AB线段;®变小®…第41页共41页®最小例2(含等式和不等式)可行域为ABCD段最小值点(4,1),最小值8.第41页共41页B:是AC段上最小值点D:是ABCD上最小值点三、函数极值概念设(严格)局部极小值:(严格)全局极小值:称为(严格)局部(全局R)极上值.第41页共41页极大值点和极大值的概念类似;四、多元函数极值存在条件对一元(二阶可微)有若,®极小值,若,®极大值
3、,对于n元函数类似有1.定理1(必要)设上有一阶连续偏导,第41页共41页且在处取得极值,则梯度应有极值点+可偏导Þ稳定点(驻点)Þ可能的最值点(1)每点梯度是函数值增长最快(定义域内)的方向.(2)每点梯度与过该点等值线正交2.二次型第41页共41页其中是实对称阵正定有关二次型的正定、半正定、负定、半负定、不定与实对称阵的正定、半正定、负定、半负定、不定的概念,性质∈高等代数3.多元泰勒公式第41页共41页(差量形式)或(带高阶)其中(增量形式)第41页共41页若(增量),则4.充分条件定理2(充分
4、)设上有二阶连续偏导,若正定,则为的严格局部极小点,其中第41页共41页称为在的海赛Hesse阵.例3对,易得第41页共41页®和不定®非极值点.(此点为鞍点)五、凸、凹函数(弦定义法)1．一元凸函数:一元凹函数第41页共41页当上式为严格不等式时,相应函数称为严格凸、凹函数.2凸函数的性质(i)凸域上的凸函数的正线性组合仍为凸函数,即若是凸域上的凸函数,,则函数.第41页共41页凹函数有类似的性质.(ii)设是凸域上的凸函数,则,是凸集.证因为对任意和令由凸函数的性质,得第41页共41页.所以即是凸
5、集.凹函数也有类似的性质.3．凸函数的判定定理3(一阶条件)设则第41页共41页证见右图.(切在曲下)必要性:第41页共41页充分性:由及同样有组合得.证毕.第41页共41页凹函数,严格凸,严格凹都类似可证.(二阶条件)设则证必要性记再任取,因为是开集,任一点均为内点.所以第41页共41页由凸性得由泰勒公式得,故得半正定.充分性第41页共41页其中由R是凸集，得，从而其它类似证.例3证明是凹函数.证负定,所以是严格凹函数.4.凸函数的极值第41页共41页定理5设是凸集R上凸函数,若是R内的极小值,则是
6、R上的最小值,且极小值点集是一个凸集.证设是R内任一极小点，则必有对第41页共41页(注,1的情形)由凸性得因此得,即是R上最小值.另外由前性质,得集是凸集.定理6设是凸集R上的可微凸函数,第41页共41页若则证由凸性及题设即得.:边的点均为增大点.注1若第41页共41页注2若是边界点,则如上图所示®内点上取最优值六、凸规划(凸集上凸函最优化问题)设是凸函数,是凹函数,则称为凸规划,第41页共41页具有:(1)可行解集是凸集;(2)最优解集是凸集(若有);(3)局部最优=>全局最优;(4)若f(X)严
7、格凸,且存在最优解,则最优解唯一.第41页共41页略证(1),则®®是凸集第41页共41页(2)前已叙证;(3)前已叙证;(4)反证法,若不唯一,有取,则,再由在凸集Rc上严格凸,知第41页共41页®说明有更优解®矛盾®故唯一.“非规”与“线规”关系:因z=CX,AX=b视作凹凸均可,故线性规划Ì凸规划.例4试说明以下问题是凸规划第41页共41页解因半负定第41页共41页故原问题是凸规划.最小值点(0.58,1.34);最小值3.8.如图所示.七、下降迭代算法理想--最值求法:若可微第41页共41页现
8、实--(很多)不可微或难微à迭代法;原则--初解,®具体--步骤:(1)选初值(2)选方向;(3)选步长;,能使即可(4)检满停;未达令k=k+1,转(2).第41页共41页注1:各种算法的主要区分点是:搜索方向的选择.注2:大多算法中的步长为第41页共41页实质:对一元函数进行极小;称此过程为:(最优)一维搜索=线搜索;称步长为:最佳步长;(关于该向)重要特点为:搜索方向最佳步长处的梯度定理7设具有一阶连续偏导数,如下得第41页共41页则有证设,令即即
