清华大学运筹学5非线性规划.pptx

第六章 非线性规划/110第一节 基本概念第三节 无约束极值问题第四节 约束极值问题第一节 基本概念一、非线性规划数学模型/110非线性规划数学模型一般形式： Min f(X) s.t. hi(X)=0(i=1, 2, …, m) gj(X)≥0， (j=1, 2, …, l)X=(x1, x2, … , xn )T 是n维欧式空间En中的点，目标函数f(X)，约束函数hi(X)和gj(X) 是X实函数。有时，非线性规划数学模型写成： Min f(X) s.t. gj(X)≥0， (j=1, 2, …, l)若某gj(X) =0，可以gj(X)≥0和 -gj(X)≥0代替之。/110还常写成 Min f(X)，X?En ={X| gj(X)≥0，(j=1, 2, …, l)} 二、二维问题图解 Min f(X)=(x1-2)2+(x2-1)2 s.t. x1+x22-5x2=0 x1+x2-5≥0 x1≥0 x2≥0?/110A(0,5)BCD(4,1)1x1O41235/110x2上图中B是f(X)部分可行域极小点，称为局部极小点， f(B)是部分可行域极小值，称为局部极小值， D是f(X)整个可行域上极小点，称为全局极小点， f(D)是整个可行域上极小值，称为全局极小值。全局极小点是局部极小点，局部极小点不应当是全局极小点。三、几个定义设f(X)是定义在n维欧式空间En中某一区域R上的n元实函数（可记为f(X)：?En→ E1），对于X* ，如果存在某个ε0，使所有距离X*小于ε 的X ， (即X 即且||X- X*||ε)，都有?/110f(X)≥f(X*)，则称X*为f(X)在上的局部极小点， f(X*)为局部极小值。若X≠X*，X ，||X- X*||ε，都有f(X)f(X*)，则称X*为f(X)在上的严格局部极小点， f(X*)为严格局部极小值。设f(X)是定义在En某一区域R上的n元实函数，若存在X* ，X ，都有f(X)≥f(X*)，则称X*为f(X)在上的全局极小点， f(X*)为全局极小值。若存在X* ，X ≠X* ，都有f(X)f(X*)，则称X*为f(X)在上的严格全局极小点， f(X*)为严格全局极小值。若颠倒上述定义中的不等号方向，可得相应极大点和极大值的定义。?/110四、多元函数极值点存在条件1. 必要条件定理1 设R为n维欧式空间En上的某一开集，f(X)在R上有连续一阶偏导数，且在点X* 取得局部极值，则必有==…==0, 或=0= (, , … ,)T 是在处的梯度。满足上述条件的点叫做“驻点”。?/110多元函数f(X)有如下性质：(1)某点 (0)处的与过此点的等值面正交（设非零）。(2)的方向是在该点处增加最快的方向；-的方向是在该点处减少最快的方向。2. 二次型 a11 a12 … a1n x1f(X)=XTAX =(x1, x2, … , xn )a21 a22 … a2n x2 .... .... .... an1 an2 … ann xn= ?/110AT=A，即 aji =aij 。若aij均为实数，则称f(X)=XTAX为实二次型。A与二次型一一对应。(1)若对于非零X ，实二次型总有XTAX0，则称为正定的；(2)若对于非零X ，实二次型总有XTAX0，则称为负定的；(3)若对于某些非零X ，XTAX0，而对另一些非零X， XTAX0，则称为不定的；(4)若对任意非零X ，XTAX≥0 ，则称为半正定的。若对任意非零X ，XTAX≤0 ，则称为半负定的。(5)A相应地称正定、负定、不定、半定。/110实二次型f(X)=XTAX为正定的充要条件是：0a110，|a11 a12 ||a11 a12 a13| |a21 a22 |0 |a21 a22 a23|0 … |a31 a32 a33| |a11 a12 … a1n | |a21 a22 … a2n | |... |0 |... | |... | |an1 an2 … ann|/110实二次型f(X)=XTAX为负定的充要条件是：a110，|a11 a12 ||a11 a12 a13| |a21 a22 |0 |a21 a22 a23|0 … |a31 a32 a33| |a11 a12 … a1n | |a21 a22 … a2n |(-1)n |... |0 |... | |... | |an1 an2 … ann|/110 [例1]判定如下二次型的性质。 -522011A= 2 -60B= 10-3 2 0-41-30 矩阵A： -50， | -5 2 | =26 0 |-5 2 2| | 2 -6 || 2 -