第四章 非线性规划教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降 法，约束最优化问题的最优性条件及简约梯度法教学难点：约束最优化问题的最优性条件教学课时：24 学时主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生 以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题第一节 基本概念教学重点：非线性规划问题的引入，非线性方法概述 教学难点：无教学课时：2 学时 主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非 线性规划方法的求解难题1、非线性规划问题举例例 1 曲线最优拟合问题已知某物体的温度9 与时间t之间有如下形式的经验函数关系：0 = c + ct + 幺钻 (*)12其中c ,c ,c是待定参数现通过测试获得n组9与t之间的实验数据(t ,9 )，1 2 3 i ii=l, 2,…,n试确定参数c，1c， c，使理论曲线(*)尽可能地与n个测试点23(t ,9 )拟合iimm £ [9 一 (c + c t + e^c^i )]2i 1 2 ii=1例 2 构件容积问题设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积为 圆锥部分的高和圆柱部分的高之 比为a。
确定构件尺寸，使其容积最 大通过分析我们可以得到如下的规划模型：max V = (1 + a / 3)兀x2x 1 2< s.t.兀x Jx2 + a2x2 + 2兀x x +Kx2 = S1 ® 1 2 1 2 1x > 0, x > 0I 1 2基本概念 设 x = (x ,・・・,x )T G Rn，f (x);g (x),i = 1,・・・,p;h (x),j = 1,・・・,q: Rn — R,1 n i j如下的数学模型称为数学规划(Mathematical Programming, MP):min f (x)< s,t・ g (x) < 0,i = 1,・・・,pih (x) = 0,j = 1，«««,q约束集或可行域V x G X MP的可行解或可行点MP中目标函数和约束函数中至少有一个不是x的线性函数，称(MP)为非线性规划令 g(x)= (g (x),・・・,g (x))T1ph(x)=(h (x),・・・,h (x))T，1p其中，g : Rn — Rp , h : Rn — Rq，那么(MP)可简记为'min f (x)< s-t・ g(x) < 0 或者 min f (x)h( x) < 0 心、当 p=0,q=0 时，称为无约束非线性规划或者无约束最优化问题。
否则，称为约束非线性规划或者约束最优化问题定义4.1.1 对于非线性规划(MP)，若x* g X，并且有f (x*) < f (x), V xG X 则称x*是(MP)的整体最优解或整体极小点，称f (x*)是(MP) 的整体最优值或整体极小值如果有f (x*) V f (x), V x G X, x 丰 x*则称x*是(MP)的严格整体最优解或严格整体极小点，称f (x*)是(MP)的严格整体最优值或严格整体极小值定义4.1.2 对于非线性规划(MP),若x * g X，并且存在x *的一个领域Ng(x*)= ( g R^ ||x-x*卜6 R > 0,S g R)，使f (x*) < f (x), V x G N (x*)A X，o则称x*是(MP)的局部最优解或局部极小点，称f (x*)是(MP)的局部 最优值或局部极小点如果有f (x*) V f (x), V x g N (x*)AX, x 工 x*，o则称x*是(MP)的严格局部最优解或严格局部极小点，称f (x*)是(MP) 的严格局部最优值或严格局部极小点定义 4.1.3 设 f : Rn — R, x G Rn , p G Rn , p 丰 0，若存在 0 > 0，使f (x + tp) V f (x), Vt G (0,0 )则称向量p是函数f(x)在点x处的下降方向定义 4.1.4 设 X u Rn,x g X,p G Rn,p 丰 0，若存在 t > 0，使x + tp G X则称向量p是函数f(x)在点x处关于X的可行方向 一般解非线性规划问题的迭代方法的步骤：第一步：选取初始点 x0,k :=0；第二步：构造搜索方向 pk ；第三步：根据pk，确定步长t ；k第四步：令xk+1 =xk +1 pk若xk+1已满足某种终止条件，停止迭代，输出近k似最优解xk+1，否则令k := k + 1，转回第二步。
常用规则：1、 相邻两次迭代点的绝对差小于给定误差，即||xk+l-xk||<£ ；Xk+1 — Xk2、 相邻两次迭代点的相对差小于给定误差，即——y <£；3、 阿(Xk )| <8 ；4、 f (Xk+1)- f (Xk ) <8第二节 凸函数和凸规划教学重点：凸函数的概念及性质，凸规划的概念、性质及判定 教学难点：凸规划的概念及性质教学课时：4 学时主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划 的性质凸函数的定义及性质：定义4.2.1 设S u Rn是非空凸集，f : S 一 R，如果对任意的ae (0,1)有f (ax 1 + (1 -a)x2) < af (xi) + (1 -a)f (x2), Vx 1,x2 e S则称f是S上的凸函数，或f在S上是凸的如果对于任意的ae (0,1)有 f (ax 1 + (1 -a)x2) v af (x 1) + (1 -a)f (x2)， x 1 工 x2则称f是S上的严格凸函数，或f在S上是严格凸的若-f是S上的(严格)凸函数，则称f是S上的(严格)凹函数 或f在S上是(严格)凹的心) af(x[) + (1 — &)/(/)(b)凹函数(a) 凸函数凸函数的性质：定理4.2.1设S u Rn是非空凸集。
1)若f : Rn 一 R是S上的凸函数，a > 0，贝y af是S上的凸函数;(2)若f , f : Rn - R都是S上的凸函数，则f + f是S上的凸函数1 2 1 2定理4.2.2设S u Rn是非空凸集，f : Rn 一 R是凸函数，c e R，则集合HS(f,c) = e Sf (x) < c}是凸集注：一般来说上述定理的逆是不成立的定理 4.2.3 设S u Rn是非空开凸集，f : S R可微，则(1) f 是 S 上的凸函数的充要条件是Vf(X1)T (x2 - x 1)< f (x2)- f (x 1), V x 1,x2 G S其中Vf (x 1)=(空凹,・・・・,堂列)t是函数f在点x 1处的一阶 ox1 oxn导数或梯度2) f 是 S 上的严格凸函数的充要条件是Vf (x 1)T (x 2 - x 1)V f (x 2)一 f (x 1)， V x 1, x 2 G S , x 1 丰 x 2证明(1)・必要性•设f是S上的凸函数，对Va G (0,1)有：f (ax2 + (1-a)xi)
当V2f (x)在S上是正定矩阵时，f是S上的严格凸函数注意：该逆命题不成立)a 2f( x)a 2f( x)a 2f( x)dx 2dx ax••••ax axa 2f (x)a 2f( x)a 2f( x)dx axax 2•••ax ax21・22n•・a 2f( x)a 2f( x)•a 2f( x)dx dxn1ax axn2ax 2nV 2f (x)=凸规划及其性质(MP)约束集min f (x)< s.t. g (x) < 0, i = 1,..., pih (x) = 0, j = 1,...qj=< X G Rn如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性 凸规划，或简称为凸规划凸规划的性质 定理4.2.5对于非线性规划(MP)，若g (x),i = 1,.・・,pi皆为Rn上的凸函数，hj(x),j = 1,・・・,q皆为线性函数，j并且f是X上的凸函数，则(MP)是凸规划定理 4.2.6 凸规划的任一局部最优解都是它的整体最优解证明：设x*是凸规划(MP)的一个局部解，存在则x*的临域N (x*)使得0f (x*) < f (x),V x g XpjNJx*)若x*不是(MP)的整数最优解，则存在x g X，使f (x) < f (x*)又因为 f 是凸函数，有f (ax + (l—a)x*)
例4.2.3验证下列(MP)是凸规划解答：将二次目标函数改写为：—11—12010 x + (1,2,0)2x3丿I x3由例 4.2.2 知 f 的 Hesse 矩阵为：'4 -11、V 2 f = —12 0「04 ‘V2f 的一、二、三阶顺序主子式分别为：4—114—1二 7 > 0,—120=26—12 -1044 > 0,V2f 正定， f 为凸函数厂2 0 0、而v2g (x) = 0 2 0半正定，g (x)是凸函数其他约束条件均为线性故改 1 [0 0 0丿 1(MP )为凸规划第三节 一维搜索教学重。