第四章 非线性规划
教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。
教学难点：约束最优化问题的最优性条件。 教学课时：24学时
主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。
第一节 基本概念
教学重点：非线性规划问题的引入，非线性方法概述。 教学难点：无。 教学课时：2学时
主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。
1、非线性规划问题举例 例1 曲线最优拟合问题 已知某物体的温度ϕ
与时间t 之间有如下形式的经验函数关系：
3
12c t c c t e φ=++ （*）
其中1c ，2c ，3c 是待定参数。现通过测试获得n 组ϕ与t 之间的实验数据),(i i t ϕ，
i=1，2，…,n 。试确定参数1c ，2c ，3c ，使理论曲线(*)尽可能地与n 个测试点
),(i i t ϕ拟合。
∑=++-n
1i 221)]([ min 3i t c i i e t c c ϕ
例 2 构件容积问题
通过分析我们可以得到如下的规划模型：
⎪⎪⎩
⎪⎪⎨⎧≥≥=++++=0
,0 2 ..)3/1( max 212
121222211221x x S x x x x a x x t s x x a V ππππ 基本概念
设n T n R x x x ∈=),...,(1，R R q j x h p i x g x f n j i α:,...,1),(;,...,1),();(==, 如下的数学模型称为数学规划(Mathematical Programming, MP)：
⎪⎩
⎪
⎨⎧===≤q j x h p i x g t s x f j i ,...,1,0)( ,...,1,0)( ..)
( min 约束集或可行域
X x ∈∀ MP 的可行解或可行点
MP 中目标函数和约束函数中至少有一个不是x 的线性函数，称(MP)为非线性规划
令 T p x g x g x g ))(),...,(()(1=
T p x h x h x h ))(),...,(()(1=，
其中，q n p n
R R h R R
g αα:,:，那么(MP )可简记为
⎪⎩
⎪
⎨⎧≤≤ 0)( 0 ..)( min x h g(x)t s x f 或者 )(min x f X
x ∈ 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。
否则，称为约束非线性规划或者约束最优化问题。 定义4.1.1 对于非线性规划(MP )，若X x ∈*，并且有
X ),()(*∈∀≤x x f x f
设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S ， 圆锥部分的高h 和圆柱部分的高x 2之 比为a 。确定构件尺寸，使其容积最 大。
则称*x 是(MP )的整体最优解或整体极小点，称)(*x f 是 (MP )的整体最优值或整体极小值。如果有
** ),()(x x X,x x f x f ≠∈∀<
则称*x 是(MP )的严格整体最优解或严格整体极小点，称
)(*x f 是(MP )的严格整体最优值或严格整体极小值。
定义 4.1.2 对于非线性规划(MP )，若X x ∈*，并且存在*x 的一个 领域}
{),0( )(**R x x R x x N n ∈><-∈=δδδδ，使
I X x N x x f x f )( ),()(**δ∈∀≤，
则称*x 是(MP )的局部最优解或局部极小点，称)(*x f 是(MP )的局部 最优值或局部极小点。如果有
I *** ,)( ),()(x x X x N x x f x f ≠∈∀<δ，
则称*x 是(MP )的严格局部最优解或严格局部极小点，称)(*x f 是(MP ) 的严格局部最优值或严格局部极小点。
定义 4.1.3 设0,,,:≠∈∈p R p R x R R f n n n α，若存在0>δ ，使
),0( ),()(δ∈∀<+t x f tp x f
则称向量p 是函数f(x)在点x 处的下降方向。
定义 4.1.4 设0,,,≠∈∈⊂p R p X x R X n n ，若存在0>t ，使
X tp x ∈+
则称向量p 是函数f(x)在点x 处关于X 的可行方向。 一般解非线性规划问题的迭代方法的步骤：
第一步：选取初始点0,:0x k =； 第二步：构造搜索方向k p ； 第三步：根据k p ，确定步长k t ；
第四步：令1k k k k x x t p +=+若1k x +已满足某种终止条件，停止迭代，输出近似最优解1k x +，否则令:1k k =+，转回第二步。
常用规则：
1、相邻两次迭代点的绝对差小于给定误差，即1k k x x ε+-<；
2、相邻两次迭代点的相对差小于给定误差，即
1k k
k
x x x ε+-<；
3、()k f x ε∇<；
4、1()()k k f x f x ε+-<
第二节 凸函数和凸规划
教学重点：凸函数的概念及性质，凸规划的概念、性质及判定。 教学难点：凸规划的概念及性质。 教学课时：4学时
主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。
凸函数的定义及性质：
定义 4.2.1 设n R S ⊂是非空凸集，R S f α:，如果对任意的)1,0(∈α有
)()1()())1((2121x f x f x x f αααα-+≤-+，S x x ∈∀21,
则称f 是S 上的凸函数，或f 在S 上是凸的。如果对于任意的)1,0(∈α有
)()1()())1((2121x f x f x x f αααα-+<-+，21x x ≠
则称f 是S 上的严格凸函数，或f 在S 上是严格凸的。
若-f 是S 上的（严格）凸函数，则称f 是S 上的（严格）凹函数， 或f 在S 上是（严格）凹的。
凸函数的性质：
定理 4.2.1 设n R S ⊂是非空凸集。
（1）若R R f n α:是S 上的凸函数，0≥α，则 f α是S 上的凸函数； （2）若R R f f n α:,21都是S 上的凸函数，则21f f +是S 上的凸函数。 定理 4.2.2 设n R S ⊂是非空凸集，R R f n α:是凸函数，R c ∈，则集合
}{c x f
S x c f H S ≤∈=)(),(
是凸集。
注：一般来说上述定理的逆是不成立的。
(a) 凸函数 (b)凹函数
