-
第
4
章
最优性条件
§
4.1
最优性条件的预备知识
1
．极小点的定义
无约束问题：
1
(1)
定义
1
（全
局极小点）若存在
x
?
R
使得
n
f
(
x
)
?
f
(
x
),
?
x
?
R
n
则称
x
为问题
(1)
的全局极小点
。如果有
f
(
x
)
?
f
(
x
),
?
x
?
R
n
,
x
?
x
则称
x
为
问题
(1)
的严格全局极小点。
n
定义
2
（
局部极小点）设
x
?
R
，如果存在
?
?
0
使得
f
(
x
)
?
f
< br>(
x
),
?
x
?
N
?
(
x
)
则称
x
为问题
(1)
的局部极小点。如果有
f
(
x
)
?
f
(
x
),
?
x
< br>?
N
?
(
x
)
/{
x
}
则称
x
为
问题
(1)
的严格局部极小点。
约束问题：
min
< br>f
(
x
)
(2)
s.t.
g
i
(
x
)
?
0
,
i
?
1
,
?
,
m
h
j
(
x
)
?
< br>0
,
j
?
1
,
?
,
l
其中
f
(<
/p>
x
),
g<
/p>
i
(
x
),
h
j
(
x
)
都是定义在
R<
/p>
上的实值连续函数，且至少有一个是非线性的。
称
f
(
x
)
为目标函数，
g
i<
/p>
(
x
)
为不等式
约束函数
,
h
j
(
x
)
为等式约束函数。
(i)
如果
m
?
0
，称
(2)
为等式约束优化问题；
(ii)
如果
l
?
0
，称
(2)
为不等式约束优化问题；
(iii)
如果
g
< br>i
(
x
)(
i
?
1
,
?
,
m
),
h
j
(
x
)(
j
?
1
,
?
,
l
)
都为线性函数，
f
(<
/p>
x
)
是二次函数，
则称
(2)
为二次规划问题。
若
x
?
R
满足
(2)
的所有约束条件，称
x
为
(2)
的可行点
(
或可行解
)
。
可行集（可行域）
：
S
?
?
x
n
n
?
?
?
?
g
i
(
x
)
?
0
,
i
?
1
,
?
,
m
,
?
?
< br>?
。
h
j
(
x
)
?
0
,
j
?
1
,
?
,
l
.
?
?
f
(
x
)
< br>?
f
(
x
),
?
x
?
S
定义
3 (
全局极小点
)
设
x
?
S
使得
成立，则称
x
为问题
(2)
的全局极小
点。如果有
f
(
x
)
?
f
(
x
),
?
x
?
S
< br>,
x
?
x
45
成立，则称
x
为问题
(2)
的严格全局
极小点。
定义
4
(
局部极小点
)
设
x
?
S
，如果存在
?
?
0
使得
< br>
f
(
x
)
?
f
(
x
),
?
x
?
N
?
(
x
)
?
S
成立，则称
x
为问题
(2)
的局部极小点。如果有
f
(
x
)
?
f
(
x
),
?
x
?
N
?
(
x
)
?
S<
/p>
,
x
?
x
成立，则称
x
为问
题
(2)
的严格局部极小点。
2.
内容安排
■
求全局极小点一般来说相当困难。
实际上可行的只是求一个局部
(
或严格局部
)
极小
点。故本课程后面所指极小点，通常指求局部极小点
。
■
仅当
问题为凸规划
(
即目标函数
f
(
x
)
为凸函数，
不等式约束函数
?
g
i
(
x
),
i
?
1
,
?
,
m
为凸函数，
等式约束函数
h
j
(
< br>x
),
j
< br>?
1
,
?
,
l
为线性函数
)
< br>时，局部极小点才是全局极小点。
■
按定义验证最优解是不可能的。因
此有必要给出只依赖于在
x
处目标函数和约束函
数信息的、且与定义等价的条件。
这样的条件称其为
最优性条件，它们是各种基于梯度算法的理论基础。
§
4.2
无约束问题的最优性条件
考虑无约束
问题
(1)
，回忆当
x
?
R
时，即单变量函数极值问题的最优性条件：
必要条件：若
x
?
R
且
f
(
x
)
在
x<
/p>
处取到极值，如果
f
(
< br>x
)
在
x
可微，则
x
为
f
(
x
)
的驻
点，即满足
f
'
(
< br>x
)
?
0
。
充分条件：若
x
?
R
且
f
(
x
)
在
x<
/p>
处可微，如果
f
'
(
x
)
?
0
且
f
'
'
(
x
)
?
0
，则
f
(
x
)
在
x
处取到极小值；如果
f
'
(<
/p>
x
)
?
0
且
f
'
'
(
x
)
?
0
，则
f
(
< br>x
)
在
x
处取到极大值。
Min
单变量优化问题
一阶条件
必要
充分
*
1
必要
二阶条件
充分
*
2
<
/p>
f
'
(
x
)
?
0
?
f
(
x
)
?
0
f
'
(
x
)
?
0
f<
/p>
(
x
)
凸
?
f
(
x
)
?
0
f
(
x
)
凸
f
'
(
x
)
?<
/p>
0
f
'
'
(
x
)
?
0
?
f
(
x
)
?
0
f
'
(
x
)
?<
/p>
0
f
'
'
(
x
)
?
0
?
f
(
x
)
?
0
多变量优化问题
< br>?
2
f
(
x
)
半正定
?
2
f
(
x
)
正定
*<
/p>
1
：
x
为全局极
小点；
*
2
：
x
为严格局部极小点。
Max
单变量优化问题
一阶条件
必要
充分
*
3
必要
二阶条件
充分
*
4
<
/p>
f
'
(
x
)
?
0
?
f
(
x
)
?
0
f
'
(
x
)
?
0
f<
/p>
(
x
)
凹
?
f
(
x
)
?
0
f
(
x
)
凹
f
'
(
x
)
?<
/p>
0
f
'
'
(
x
)
?
0
?
f
(
x
)
?
0
f
'
(
x
)
?<
/p>
0
f
'
'
(
x
)
?
0
?
f
(
x
)
?
0
多变量优化问题
?
< br>2
f
(
x
)
半负定
?
2
f
(
x
)
负定
46
*
3
：
x
为全局极大点；
*4<
/p>
：
x
为严格局部极大点。
定理
1 (
一阶必要条件
)
：
设
< br>x
?
R
为函数
< br>f
(
x
)
在
R
的局部极小点，
且
f
(
x
)
< br>在
x
可微，
则
< br>?
f
(
x
)
?
0
。
证明
利用
§
4.0
中的定理
1
可证。
几何解释：
若
x
为局部极小点，
则
f
(
x
)
< br>在
x
处不能有下降方向。
从而，
当
?
f
(
x
)
?
0
时，
n
n
－
?
f
(
x
)
为
f
(
x
)
在
x
处的一个下降方向，故若
x
?
R
n
为函数
f
(
x
)
在
R
n
的极值点，必有
?
f<
/p>
(
x
)
?
0
。
定理
2 (
二阶必要条件
)
：设
x
?
R
为函数
f
(
x
)
在
R
的局部极小点，且
f
(
x
)
在
x
二阶
可微，则有
n
n
?
f
(
x
)
?
0
，且
?
2
f
(
< br>x
)
半正定
证明：利用
f
(
x
)
在
x
的二阶
Taylor
展开及局部极小点的定义可得。
< br>
几何解释：由
x
为局部极小点及
?
f
(
x
)
?
0
所确定。
定理
3 (
二阶充分条件
)
：设
f
(
x
)
是定义在
R
上的二次可微函数，如果
?
f
(
x
)
?
0
，且
n
?
2<
/p>
f
(
x
)
正定，则
x
为函数
f
(
x
)
在
R
n
的严格局部极小点。
< br>
证明
利用
f
(
x
)
在
x
的二阶
Tay
lor
展开及正定矩阵的定义可得。
注：满
足
?
f
(
x<
/p>
)
?
0
的点称为
f
(
x
)
的平稳点或驻点。驻点可能是极大值点，也可能是
极小值点，
也可能不是极值点。
但若目标函数为凸函数，
则驻点就是全局极小值点；若目标
函数为凹函数，则驻点就是全局极大值点。
定理
4 (
凸充分性定理
)
：设
f
(
x
)
是定义在
R
上的凸函数，如果
?
f<
/p>
(
x
)
?
0
，则
x
为函
数
f
(
x
)
在
R
上的全局极小点。
(
一阶必要条件＋凸性
)
证明
利用可微凸函数的一阶判别条件
和
?
f
(
x<
/p>
)
?
0
易证。<
/p>
例：利用极值条件求解
n
n
min
f
(
x
)
?
2
x
?
R
1
3
1
3
2
x
1
?
x<
/p>
2
?
x
2
?
x
1
3
3
解：
?
f
?
f
2
2
?
x
1
?
1
，
?
x
2
< br>?
2
x
2
?
x
1
?
x
2
2
2
令
?
f
(
x
)
?
0
，即
x
1
?
1
?
0
，
x
2
?
2
x
2
?
0
。<
/p>
得到驻点：
?
1
?
?
1<
/p>
?
?
?
1
?
?
?
1
?
x
(
1
)
?
?
?
，
x
(
2
)
?
?
?
，<
/p>
x
(
3
)
?
?
?
，
x
(
4
)
?
?
?
?
0
?
?
2
?
?
0
?<
/p>
?
2
?
Hesse
矩阵：
< br>?
f
(
x
)
?
?
在点
x
,
x
,
x<
/p>
,
x
(
1
)
(
2
)
(
3
)
(
4
)
2
?
2
x
1
?
0
?
2
x<
/p>
2
?
2
?
?
0
处
Hesse<
/p>
矩阵：
47
?
2
0
?
?
2
0
?
2
(
2
)
，
?
2
< br>f
(
x
(
1
)
)
?
?
?
f
(
x
)
?
?
?
?
?
0
?
2
?
?
0
< br>2
?
?
?
2
0
?
?
?
2
0
?
2
(
4
)
，
?
2
f
(
x
(
3
< br>)
)
?
?
?
f
(
x
)
?
?
?
?
?
0
?
2
?
?
0
2
?
?
2
f
< br>(
x
(
1
)
)
和
?
2
f
(
x
(
4
)
)
不定，根据
定理
2
，
x
(
1
)
,
x
(
4
)
不是极小点
；
?
2
f
(<
/p>
x
(
3
)
)
负定，
x
(
3
)
是
极大点；
?
2
f
(
x
(
2
)
)
正定，根据定理
3
，
x
(
2
)
是局部极小点。
§
4.3
约束问题的极值条件
4.3.1
一阶最优性条件
引入记号：
E
?
{
1
,
?
,
l
}
――等
式约束指标集
I
?
< br>{
1
,
?
,
m
}
――不等式约束指标集
x
?
S
，若
g
(
~
x
处是
定义
1:
对
(2)
的任何可行解
~
x
)
?
0
,
i
?
I
，称第
i
个不等式约束在
~
i
紧的，称集合
I
(
~
x
)
?
{
i
|
g
i
(
< br>~
x
)
?
0
,
i
?
I
}
x
处的紧约束指标集。称
为不等式约束中在
~
A
(
~
x
)
?
E
?
I
(
~
x
)
x
处的积极集合
(
有效约束
指标集，或紧约束指标集
)
。
是在
~
可行集上一点是否为局部极小点
,
取决于目标函数在该点以及附近其它可行
点上的值。可行方向在推导最优性条件中起十分重要的作用。
各种可行方向的定义
:
n
定义
2:
设
x
?
S
，<
/p>
0
?
d
?
R
，如果存在
?
?<
/p>
0
，使得
x<
/p>
?
?
d
?
S
，
?
?
?
(
0
,
?
)
< br>则称
d
是集合
S
在
x
处的可行方向。
S
在
x
处的可行方向的集合记为
FD
(
x
,
< br>S
)
。
问题：问
FD
(
x
,
R
n
)
？
(
FD
(
x
,
R
n
)
?
R
n
/{
0
}
)
例
1:
考虑集合
S
1
?
{
x
?<
/p>
R
2
|
x
2
?
x
1
}
，
S
2
?
{
x
?
R
2
|
x
2
?
x
1
}<
/p>
在点
x
?
(
0
,
0
)
处的可行方向集，则
T
2
2
F
D
(
x
,
S<
/p>
1
)
?
?
FD
(
x
,
S
2
)
?
{(
d
1
,
d
2
)
|
d
1
?
R
,
d
2
?<
/p>
0
}
定义
3:
设
x
?
S
，
d<
/p>
?
R
，如果
<
/p>
n
d
T
?
h
j
(
x
)
?
0
,
j
?
E
; <
/p>
d
T
?
g
i
(
x
)
?
0
,
i
?
I
(
x
)
则称
d
是集合
S
在
x
处的线性化可行方向。
S
在
x
处的线性化可行方向的集合记为
LF
D
(
x
,
S<
/p>
)
。
48
定义
4:
设
x
?
S
，<
/p>
d
?
R
，如果存
在序列
{
d
k
}
和
{
?
k<
/p>
}
，其中
?
k<
/p>
?
0
，使得
<
/p>
n
x
?
?
k
d
k
?
S
，
?
k
且有
d<
/p>
?
d
和
?
k
?
0
，则称
d
是集合
S
在
x
处的序列可行方向。
S
在
x
处的所有序列可
行方向的集合
记为
SFD
(
x
,
S
)
。
k
d
?
lim
k
?
?
x
k
?
x
x
?
x
k
注：
可行方向为几何概念，
线性化可行方向
为代数概念，
序列可行方向是基于极限定义
的几何概念。
例
2
S<
/p>
?
{
x
?
R
2
|
x
2
?
x
1
}
，取
x
?
< br>(
0
,
0
)
T
，则
2
FD
(
x<
/p>
,
S
)
?
?
LFD
(
x
,
S
)
?
{(
d
1
,
0
)
|
< br>d
1
?
R
}
SFD
(
x
,
S
)
?
{(
d
1
,<
/p>
0
)
|
d
1
?
R
}
上述定义的三个可行方向集有如下关系：
引
理
1
设<
/p>
x
?
S
，
如
果
所
有
的
约
束
函
数
在
x
处
可
微
，
则
有
FD
(
x
,
S
)
?
SFD
(
x
,
S
)
?
LFD
(
x
,
S
)
。
注：该结论条件可以放宽为
g
i
(
x
)
，
i
?
I
(
x
)
，
h
j
(
x
)
，
j<
/p>
?
1
,
?
,
l
在
x
处可微，其余不
等式约束函数
g
< br>i
(
x
)
，
i
?
I
(
x
)
在
x
处连续。
引理
2
(
几何最优性条件－必要
)
：设
x
?
S
是
(2)
的局部极小点，如果
f
(
x
)
在
x
处可微，
则必有
< br>d
T
?
f
(
x
)
?
0
,
?
d
?
SFD
(
x
,
S
)
证明
利用目标函数
< br>f
(
x
)
在
x
?
?
k
d
k
处的一阶
Taylor
展开，序列可行方向的定义及局
部极小点的定义可
证。
注
：
该
定
理
也
可
表
述
为
：
x
?
S
是
< br>(2)
的
局
部
< br>极
小
点
，
则
{
d
|
d
T
?
f
(
x
)
?
0
}
?
SFD
(
x
,
S
)
?
?
。
< br>第一个集合表示目标函数在
x
处的一个下降方向的子集，
即该下降方向的子集与序列可
行方向无公共元素。
定理
1
：设
x
?
S
是
(2)
的局部极小点，如果目标函数和所有的约束函数在
x
处可微，且
SFD<
/p>
(
x
,
S
)
?
LFD
(
x
,
S
)
(3)
则必存在
w
i
,
i
?
I
和
v
j
,
<
/p>
j
?
E
使得
（
4a
）
<
/p>
?
f
(
x
)
?
?
w
i
?
g
i
(
x
)
?
?
v
j
?
h
j
(
x
)<
/p>
?
0
（
梯
度
条
件
）
i
?
1
j
?
1
m
l
（
4b
）
w
i
?
0
,
w
i<
/p>
g
i
(
x
)
?
0
，
i
?
1
,
?
,
m
（
互
补
松
弛
条
件
）
该定理的另外一种等价表示（基于该等价表示可以看出
K-T
最优性条件的几何意义）
：
定理
1
:
设
x
?
S
是
(2)
的局部极小点，如果目标函数和所
有的约束函数在
x
处可微，且
49
'
S
FD
(
x
,
S
)
?
LFD
(
x
,
S
)
则必存在
w
i<
/p>
?
0
,
i
?
I
(
x
)
和
v
j
,
j
< br>?
E
使得
?
f
(
x
)
?
证明思路：
Farkas
定理
i
?<
/p>
I
(
x
)
?
w
?
g
(
x
)
?
?
v
?
h
(
x
)
?
0
（
5
）
i
i
j
j
j
?
1
l
引理
2
（几何形式
的最优性）
FJ
最优性
条件
约束规格
CQ
K-T
条件
（代数形式
的最优性）
(4a)-(4b)
由
Kuhn
，<
/p>
Tuck
（
1951
）给出，一般称为
K-T
条件，因
Karush
（
1939
）也类似
地考虑了约束优化的最优性条件，所以也称
K-K-T
条件。
几
何
意
义
：
在局部极小
点处，
若某种约束规范成立，
则
目
标
函
数
的
梯
度
向
量
位于不等式
积极约束的
梯
度
向
量
生
成
的
凸
锥
与
等式约束的
梯
度
向
量
生
成
的
线
性
空
间
的
和
集
。即
?
?
g
i
(
x
),
i
?
I
(
x
)
?
?
spa
n
?
?
h
j<
/p>
(
x
),
<
/p>
j
?
E
?
?
f
(
x
)
?
cone
?
?
g
i
(
x
),
i
?
I
(
x
)
?
?
?
cone
?
?
?
w
?
g<
/p>
(
x
)
w
?
0
,
i
?
I
(
x
)
?
i
i
i
?
i
?
?
?
I
(
x<
/p>
)
?
?
?
?
span
?
?
h
j
(
x
),
j
?
E
?
?
?
v
j
?
h
< br>j
(
x
)
v
j
?
R
,
j
?
E
?
?
j
?
E
?
?
?
例
3
考虑问题
min(
x
1
?
2
)
2<
/p>
?
x
2
s.t.
x
1
?
x
2
?
0
?
x
1
?
x
2
?
0
验证点
x
(
1
)
?
(
0
,
0
< br>)
T
,
x
(
2
)
?
(
1
,
1
)
T
是否满足
K-T
条件。
2
2
记
f
(
x
)
?
(
x
1
?
2
)
2
?
< br>x
2
，
g
1
(
x
)
?
x
1
?
x
2
，
g
2
(
x
)
?
?
x
1
?
< br>x
2
梯度：
< br>?
f
(
x
)
?
?
2
2
?
2
(
x
1
?
2
)
?
?
1
?
?
?
1
?
< br>，
，
?
g
(
x
)
?
?
g
(
x
)
?
?
2
1
?
1
?
?
?
2
x
< br>?
2
x
2
?
?
?
?
2
?
?
50
先验证
x
。在此点，
< br>g
1
(
x
)
?
0
和
g
2
(
x
)
?
0
都是起作用约束，目标函数和约束函数
的
梯度为
(
1
)
?
1
?<
/p>
?
?
1
?
?
?
4
?
?
f
(
x
(
1
)
)
?
?
?
，
?
g
1
(
x<
/p>
(
1
)
)
?
?
?
，
?
g
2
(
x
(
1
)
)
?
?
?
?
0
?
?
1
?
?
0
?
?
?
4
?
?
1
?
< br>?
?
1
?
?
0
?
设
?
?
?
w
1
?
?
?
w
2
?
?
?
< br>?
?
?
0
?
?
0
?
?
1
?
?
0
?
得到
w
1
?
?
4
，
w
2
?
0
。由于
w
1
?
0
，故
x
< br>不是
K-T
点。
再验证
x
梯度为
(
2
)
(
1
)
。
在此点，
g
1
(
x
)
?
0
和
g
2
(
x
)
?
0
都是起作用约束，
目标函数和约束函数的
?
?
2
?
?
1
?<
/p>
?
?
1
?
?
f
(
x
(
2
)
)
?
?
?
，
?
g
1
(
x
(
2
)
)<
/p>
?
?
?
，
?
g
2
(
x
(
2
)
)
?
?
?
?
2
?
?
?
2
?
?<
/p>
1
?
?
?
2
?
?
1
?
?
?
1
?
?
0
?
设
?
?
?
w
1
?
?
?
w
2
?
?
?
?
?
< br>?
2
?
?
?
2
?
?
1
?
?
0
?
得到
w
1
?
0
，
w
2
?
2
。故
x
例
4
考虑问题
min
(
x
1
?
1<
/p>
)
2
?
x
2
s.t.
?<
/p>
x
1
?
x
2
?
2
?
0
(
2
)
是
K-T
点。
x
2
?
< br>0
求该问题的
K-T
点。
目标函数和约束函数的梯度：
?
2
(
x
?
1
)
?
?
?
1
?
?
< br>0
?
，
，
?
f
(
x
)
?
?
1
?
g
(
x
)
?
?
g
(
x
)
?
< br>1
2
?
?
?
?
?
?
1
?
?
?
1
?
?
1
?
?
f
(
x
)
?
?
w
i
?
g
i
(
x
)
< br>?
0
i
?
1
2
K-T
条件：
< br>
w
i
g
i
(
x
)
?
0
,
i
?
1
,
2
w
i
?
0
,
i
?
1
,
2
2
(
x
1
?
1
)
?
w
1
?
0
1
?
< br>w
1
?
w
2
?
0
即：
w
1
(
?
x
1
?
x
2
?
2
)
?
< br>0
w
2
x
2
?
0
w
1
,
w
2
?
0
可得上述方程组的一组解：
x
1
?
1
,
x
2
< br>?
0
,
w
1
?
0
,
w
2
?
1
由于
w<
/p>
1
,
w
2
非负，因此得到
K-T
点
x
?
(
1
,
0
)
T
。
例
5
考虑问题
min(
< br>x
1
?
2
)
2
?
(
x
2
?
1
)
2
51
s.t.
?
x
1
?
x
2
?
0
,
?
x
1
?
x
2
?
2
?
0
.
求该问题的
K-T
点。<
/p>
2
目标函数和约束函数的梯度：
?
2
(
x
?
2
)
?
?
?
2
x
1
< br>?
?
?
1
?
?
f
(
x
)
?
?
1
，
，
?
g
(
x
)
?
?
g
(
x
< br>)
?
?
1
2
?
1
?
?
?
1
?
2
(
x
?
1
)
?
2
?
?
?
?
< br>?
K-T
条件：
2
(
x
1
?
2
)
?
2
w
1
x
1
?
w
2
?
0
2
(
x
< br>2
?
1
)
?
w
1
?
w
2
?
0
w
1
(
?
x
1
2
?
x
2
)
?
0
< br>w
2
(
?
x
1
?
x
2
?
2
)
?
0
?
x
1
2
?
x
2
?
0
?
x
< br>1
?
x
2
?
2
?
0
w
1
,
w
2
?
0
解得：
x
1
?
1
,
x
2
?
1
,
w
1
?
2
/
< br>3
,
w
2
?
2
/
3
。
故
x<
/p>
?
(
1
,
1
)
T
为
K-T
点，也是全局最优点（？）
。
注
1
：
此定理中目标函数和所有的约束函数在
x
处
可微，
可放宽为
g
i
< br>(
x
),
i
?
I
(
x
)
在
x
连
续
，
f
(<
/p>
x
),
g<
/p>
i
(
x
),
i
?
I
(
x
)
；
h
j
(
x
),
j
?
1
,
?
< br>,
l
在
x
可
微
。
注
2
：
(3)
式所给
条件称为约束规范
(
约束规格－
Con
straint
Qualification)
。若约束规范
不
成立，则
(2)
的局部极小点不一定
是
K-T
点。
x
1
例
6 (Flether,1987)
min
2
x
?
R
s.t.
x
1
?
x
2
?
0
,
<
/p>
x
2
?
0
则
x
?
(
0
,
0
)
为局部极小点，且
T
3
?
1
?
?
0
?
?
0
?
?
f
< br>(
x
)
?
?
?
,
?
g
1
(
x
)
?
?
?
,
?
< br>g
2
(
x
)
?
?
?
?
0
?
?
?
1
?
?
1
?
易验证：
SFD
(
x
,
S
)
?
{(
d
1
,
0
)
|
d
1
?
0
}
LFD
(
x
,
S
)
?
{(
d
1
,
0
)
|
d
1
?
R
}
52
-
-
-
-
-
-
-
-
-
上一篇：防护功能平战转换设计专篇各专业
下一篇：空调设计通风设计说明书