25
无约束问题的最优性条件
（P1）
Min f(X)
X En
定理4（二阶必要条件） 设f(X)在X*点二阶可微，如果X*为 （P1） 的一个局部极小点，则有 f(X*) =0 和 H（ X* ）为半正定。
26
无约束问题的最优性条件
（P1）
Min f(X)
X En
定理5（二阶充分条件）
17

例：判定正定性
5 A 2 2 2 6 0 2 0 4
5 2 2 6
0 B 1 1
26 0
1 0 3
1 3 0
解： a
11
5 0
5 A 2 2
2 6 0
2 0 4
18
80 0

2
x 2 1 0
x2 2x2
2
求得到4个驻点：
X
4
1 2
2 x1 f (X ) 0
2 x2 2 0

2
2 f (X 1) 0
0 2
0 2

2
2 f (X 2) 0
0 2
7.2 无约束问题的极值条件 例 求解如下非线性规划问题
min f ( x ) ( x 1 2 ) 2 ( x 2 2 ) 2 x1 x 2 6 0 x2 6
, 即 f ( x ) c ( 常数 ), D点,在 D点 3,
*
解
作 f ( x )的等值线
2
x1
3
1 3
2
x 2 x 2 x1 4
3 2
解 因为
f x1
x1 1
，
f
x1 2 令 f (X ) 0 即 x2 2x2 0 1 1 1 X1 X X3 2 0 0 2
11
X En X- X* < , >0
局部最优解
f(X)
整体最优解
12
2.梯度向量 f(X)=grad f(X) =(f/x1 ,f/x2 ,…..,f/xn)T
区间内连续的梯度的性质： ①在某点的f(X（0）)必与函数过该点的等 值面的切平面相垂直。 ②梯度方向是函数值增加最快的方向（函 数变化率最大的方向） 负梯度方向是函数值减小最快的方向。
等值线与直线相切于 得到最优解
* x1
2 o

2

D ( 3 ,3 )

* x2
6
x1
最小值 min f ( x ) f ( x ) 2 .
21
x2 6
min f ( x ) ( x 1 2 ) 2 ( x 2 2 ) 2 x1 x 2 6 0
2 o
非线性规划的最优解可能在可行域的 任一点达到。
22

一、用海赛矩阵判断驻点的性质
o若H(x)为正定，该驻点X*是严格局部极小 值点；
o若H(x)为负定，该驻点X*是严格局部极大 值点； o若H(x)为半正定（半负定），则进一步观 察它在该点某邻域内的情况，可能是可能 不是；
o如果H(x) 不定的，该驻点X*就不是f(X)极 值点。
A 负定

例：判定正定性
5 A 2 2 2 6 0 2 0 4
0 1 1 0
0 B 1 1
1 0
1 0 3
1 3 0
解：
b11 0
B 不定
19
作业： P200 4.4（1）

20
0 2
32

2
2 f (X 3) 0
2 f (X 4) 0
2
X1
，X 3 和
X
4
不是极小点；X 2 是极小点。
7.3 凸函数与凸规划 凸集概念： 设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为凸集
非线性规划
直接法 有约束问题
算法方面
间接法 无约束问题
6
应用方面
一般模型 Min f(X)
s.t. hi(X) = 0
(i=1,2,….m)
（P）
gj(X) 0 (j=1,2….l)
X En f(X) hi(X) gj(X) 为En上的实函数。
或
( 1) min f(x) g j (x) 0 ,j 1 , 2 , , l 目标函数 ( 2) 约束条件
23
二、极值点的必要条件和充分条件
最优性条件的研究是非线性规划理论研究 的一个中心问题。 为什么要研究最优性条件？
o本质上把可行解集合的范围缩小。
o它是许多算法设计的基础。
24
无约束问题的最优性条件 （P1） Min f(X) X En 定理3（一阶必要条件） 设f(X)在X*点可微，则X*为（P1） 的一个局部极值点，一定有 f(X*)=grad f(X*)=0（ X*称为驻点）
T
4 x 1 8 4 x 2 4 0 0
T
T
x 1* 2 4 x1 8 0 * 4 x2 4 0 x2 1
28
例
而
求 m in f ( x ) 2 x 1 8 x 1 2 x 2 4 x 2 2 0
相应不等式反号，得到相应极大点，极大值定义。
9
定义
如果X满足（P）的约束条件
(i=1,2,….m)
hi(X)=0
gj(X) 0 (j=1,2….l)
则称X En 为（P）的一个可行解。 记（P）的所有可行解的集合为D， D称为（P）可行域。
10
定义 X*称为（P）的一个（整体）最优解，如 果X* D，满足 f(X) f(X*)， X D。 定义 X*称为（P）的一个（局部）最优解，如 果X* D，且存在一个X*的邻域 N(X* ,)= 满足 f(X) f(X*)， X D N(X* ,)
7
二、基本概念

1、全局极值和局部极值
f ( X ) 为目标函数，S 为可行域。若存在 X * S ， X S ，都 * 有 f ( X ) f ( X * ) ，则称 X 为该问题的全局极小点，
f (X )
*
为全局极小值。
f ( X ) 为目标函数，S 为可行域。若有X * S , X X * ， X S ， * * 都有 f ( X ) f ( X ) ，则称 X 为该问题的严格全局极小点，
设f(X)在X*点二阶可微，如果f(X*) =0 和 H(X*)为正定，则X*为(P1) 的一个严格局部极小点。
27
例
求 m in f ( x ) 2 x 1 8 x 1 2 x 2 4 x 2 2 0
2 2
解
f f (x) x1
f x 2

16
4、正定矩阵、负定、半定、不定
正定：特征值>0；各阶主子式>0(Ai>0) 半正定：特征值≥0；detA=0, Ai ≥ 0 负定：特征值<0； Ai <0(i为奇）, Ai >0(i为 偶） 半负定：特征值≤0； detA=0，Ai ≤0(i为 奇）, Ai ≥0(i为偶） 不定：特征值有> 0及< 0；除了上述情况外 即为不定。
第七章
非线性规划的基本概念 和基本原理
1
7.1 数学模型和基本概念
非线性规划是运筹学中包含内容最多， 应用最广泛的一个分支，计算远比线性 规划复杂。
2
一、数学模型 例 某单位拟建一排 厂房，厂房建筑平面如图 所示。由于资金及材料的 限制，围墙及隔墙的总长 度不能超过80米。为使建 筑面积最大，应如何选择 长宽尺寸？
x1 x2
max f ( x ) x 1 x 2 2 x 1 5 x 2 80 x1 , x 2 0
分析：设长为 x 1 米， 宽为 x 2 米，则有
f(x)为非线性函数
3
例 设某物理过程具有如下规律
( t ) x1 x 2 e
x3t
用试验法 求得 t i时的 ( t i ) 值 , i 1, 2 , , m 。 现要确定参数 x1 , x 2 , x 3 , 使所得试验点构成的曲线与理论曲线误差平 方和为最小，且满足 x1 x 2 1, x 3 非负。
2 2
2 2 f f 2 x1 x 1 x 2 * H (x ) 2 2 f f 2 x 2x1 x 2

4 0
x x
*
0 4
4 4 0,
4 0
0 4
16 0 , H ( x ) 正定 ,
13
满足 f ( x ) 0 的点 , 称为平稳点或驻点
*
.
在区域内部极值点必为 但驻点不一定是极值点
驻点 , .
14
3、海赛(Hesse)矩阵
2f(X) = H(X)
2f/x12 2f/x1x2 ….. 2f/x1xn 2f/x22 ….. 2f/x2xn
=
*
x 1 2 , x 2 1 为严格局部极小点
* *
极小值 f ( x ) 10
*
29
例 Min f(X)= 2x12+5x22+x32+ 2x2x3 + 2x1x3 - 6x2+3 X E3 解：f(X) = （4x1+ 2x3, 10x2+ 2x3 – 6, 2x1+ 2x2 + 2x3 ）=0 驻点x*=(1,1,-2) 4 0 2