非线性规划的基本概念和基本原理精要.ppt

* 凸集概念： 设D是n维线性空间En的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。 即：若D中的任意两点x(1),x(2) ∈D，任意0?1 使得 x= ? x(1)+(1- ?)x(2) ∈ D,则称D为凸集 7.3 凸函数与凸规划 * 一、凸函数的定义 几何解释 * f(X) X * f(X) X f(X1) f(X2) X1 X2 * f(X) X ?f( x1 ) +(1- ?) f( x2) f(X1) f(X2) X1 X2 ?x1+(1- ?)x2 f(?x1+(1- ?)x2 ) * f(X) X ?f( x1 ) +(1- ?) f( x2) f(X1) f(X2) X1 X2 ?x1+(1- ?)x2 f(?x1+(1- ?)x2 ) 任意两点的函数值的连线上的点都在曲线的上方 * 线性函数既是凸函数,又是凹函数。 如果 - f(X)为R上的(严格)凸函数,则f(X)为R上的(严格) 凹函数. * 二． 凸函数的性质 性质1 设 都是定义在凸集R上的凸函数， 那么 仍是在凸集R上的凸函数。 性质2 设 是定义在凸集S上的凸函数，那么对任意实数 ，集合 是S的凸子集。 性质3 f(x)是凸集R上凸函数，则f(x)在R上局部极小点就是全局极小点，且极小点的集合是凸集。 * 三、凸函数的判别 * 例 * 作业： P200 4.6（1）（2） * 定理6（充要条件）： 若 是二阶连续可微的凸函数， 则 是全局极小点 。 类似地，若 二阶连续可微的严格凸函数， 则 是惟一全局极小点。 四、凸函数极值点的充要条件 * 解无约束问题的算法： 求f(X)的驻点X*，若是凸函数，得到最优解。否则，转下一步。 在驻点X*处，计算H(x)。 根据H(x)来判断该驻点X*是否是极值点。 * 例 求极值 f(X)= x1 + 2x3 +x2x3 -x12-x22-x32 X ? E3 解：?f(X) = (1-2x1,x3 -2x2, 2+x2 - 2x3 ) = 0 驻点x*=(1/2,2/3,4/3) H(X) =?xxf(X)= -2 0 0 0 -2 1 0 1 -2 * H(X) =?xxf(X)= 各阶主子式：-20, =40 -2 0 0 -2 = - 60 -2 0 0 0 -2 1 0 1 -2 -2 0 0 0 -2 1 0 1 -2 H(X)负定， f(X) 是凹函数 X*=(1/2,2/3,4/3)为极大值点。 f(X*)= f(1/2,2/3,4/3)=19/12 * 五、凸规划 下述问题为凸规划. 求凸函数f(x)在凸集R上的极小点的问题， 称为凸规划。 * 性质： 1、凸规划的局部极小点就是全局极小点。 2、极小点的集合是凸集。 3、若目标函数为严格凸函数，若存在极小点， 则极小点必定唯一。 凸规划是一类比较简单而又具有重要理论意义 的非线性规划。 * 例 如下非线性规划是否为凸规划： * 的海赛矩阵： 所以，该问题为凸规划。 * 如图所示，该问题 最优解在C点取得。 * 算法概述 一个算法（Algorithm)就是一种求解方法，它可看作为一个循环过程，按照一组指令和规定的停算准则，产生近似解序列，它应该收敛到整体最优解，但由于某些原因（不连续性、无凸性、规模大、实现方面困难等）常使得计算难以符合以上条件，往往是一个无限的过程，因而给出停算准则，如果在第k次循环时，满