最优化方法刘二永第一章基 本 概 念
§ 1.1 最优化问题简介最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为 最优方案,搜索最优方案的方法，称为 最优化方法 。这种方法的数学理论，称为 最优化理论 。
实际上最优化方法已广泛应用于空间技术、
军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。
最优化方法包括的内容很广泛，如线性规划、
非线性规划、整数规划、动态规划、多目标规划、
组合优化等等。本教程重点介绍 非线性规划 。
最优化问题的数学模型一般形式为：
1.1m in xf
2.1,,2,1,0.,mixcts i
（ 目标函数 ）
（ 等式 约束）
（ 不等式 约束）
其中
3.1,,,1,0 pmixc i
nTn Rxxxx,,21
相关定义定义１,1 可行解 满足约束条 (1.2)和 (1.3)
的 x称为可行解，也称为可行点或容许点。
定义１,2 可行域 全体可行解构成的集合称为可行域，也称为容许集，记为 D,即：
nii RxpmixcmixcxD,,,1,0,,2,1,0
定义１,3 整体最优解 若：
Dx?
,* Dx? 对于一切则称,* xfxf?恒有 *x 为最优化问题的整体最优解。
若：,,*xxDx 恒有,* xfxf?
则称 *x 为最优化 问题的严格整体最优解。
定义１,4 局部最优解 若：,* Dx? 存在 *x
的某邻域,*xN? 使得对于一切*xNDx
恒有xfxf?* 则称 *x 为最优化问题的局部最优解。 其中 。0,**
xxxxN
同样有：严格局部最优解。
而局部最优解不一定是整体最优解。
显然，整体最优解一定是局部最优解，
注意：
求解最优化问题，实际上是求可行域
D上的整体最优解。 但是,在一般情况下，
整体最优解是很难求出的，往往只能求出局部最优解。
定义１,5 范数,在 n 维向量空间 nR 中，
定义实函数,x 使其满足以下三个条件：
（１）对任意 nRx? 有,0?x
在当且仅当
0?x 时 ；0?x
（２）对任意 nRx? 及实数? 有 ；xx
（３）对任意
x
有 yxyx
则称函数
nRyx?,
为 nR 上的向量范数。
两类比较常见的范数：
P-范数,
pxx
pn
i
p
ip 1
/1
1
其中最常用的是 2-范数，即：
2/1
1
2
2
n
i
ixx
范数,i
ni xx 1m a x
最优化问题的分类根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题。
根据目标函数和约束函数的函数类型分类：线性最优化问题、非线性最优化问题、
二次规划、多目标规划、动态规划、整数规划、０－１规划。
§ 1.2 最优化方法概述迭代算法：选取一个初始可行点,
0 Dx?
由这个初始可行点出发，依次产生一个可行点列：
,,,,21 kxxx 记为,kx
使得 kx 恰好是问题的一个最优解，
或者该点列kx 收敛到问题的一个最优解。
下降算法：在迭代算法中一般要求：
kk xfxf 1
可行点列的产生在
kx 处求得一个方向 kp处求得一个方向 （可行下降方向）
在射线0
kk px
上求一点：
kkkk pxx 1
使得
kk xfxf 1
其中
k?
称为步长。
下降方向（ P16-17）
定义 1.6 下降方向,在点 kx 处,对于方向
,0?kp 若存在实数,0 使得任意的
,0? 有：
kkk xfpxf
成立,则称 kp 为函数xf 在点 kx 处的一个下降方向。
当xf 具有连续的一阶偏导数，令,kk xfg
由 Taylor公式：
kTkkkk pgxfpxf
当 0?kTk pg 时，有,
kkk xfpxf
所以（? 充分小时） kp 是xf 在 kx 处的一个下降方向。
通常称满足,0?kTk pg 的方向 kp 为xf 在 kx
处的下降方向。
可行方向（ P17）
定义 1.7 可行方向,已知区域,,DxRD
kn
对于向量,0?kp 若存在实数,0 使得任意的
,0? 有：
Dpx kk
则称 kp 为 kx 点处 关于区域 D 的可行方向。
下降方向关于区域 D 可行，则称为可行下降方向。
最优化问题的算法的一般迭代格式给定初始点,
0x 令 。0?k
（１）确定
kx
处的可行下降方向 ;kp
（２）确定步长,0?
k?
使得：
kkkk xfpxf
（３）令
kkkk pxx 1
（４）若 1?kx 满足某种终止准则，则停止；
否则令,1 kk 转（１）
收敛性如果一个算法只有当初始点充分接近最优解时，产生的点列才收敛，则称该算法为具有 局部收敛 的算法。
如果对任意的初始点，由算法产生的点列都收敛，则称该算法为具有 全局收敛 的算法。
具有全局收敛性的算法才有实用意义。
但对算法的局部收敛性分析，在理论上是重要的，因为它是全局收敛性分析的基础。
收敛速度定义 1.8 设序列 收敛于 而且：kx *,x
*
*
1lim
xx
xx
k
k
k
若,10 则称序列kx 为线性收敛的，称
为收敛比；
若,0 则称序列kx 为超线性收敛的。
收敛速度定义 1.9 设序列 收敛于 若对kx *,x
0,lim
*
*
1
p
k
k
k xx
xx
则称序列
kx 为
,1?p 有：
p 阶收敛的。
特别当,2?p 时称为二阶收敛的。
终止准则对于一种算法，应该有某种终止准则，当某 次迭代
kk xx 1
满足终止准则时，就停止迭代。常用的 终止准则有：
（１） 或
k
kk
x
xx 1
（２）
kk xfxf 1 或
k
kk
xf
xfxf 1
（３）
kk gxf
其中 0 是预先给定的。
§ 1.1 最优化问题简介最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为 最优方案,搜索最优方案的方法，称为 最优化方法 。这种方法的数学理论，称为 最优化理论 。
实际上最优化方法已广泛应用于空间技术、
军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。
最优化方法包括的内容很广泛，如线性规划、
非线性规划、整数规划、动态规划、多目标规划、
组合优化等等。本教程重点介绍 非线性规划 。
最优化问题的数学模型一般形式为：
1.1m in xf
2.1,,2,1,0.,mixcts i
（ 目标函数 ）
（ 等式 约束）
（ 不等式 约束）
其中
3.1,,,1,0 pmixc i
nTn Rxxxx,,21
相关定义定义１,1 可行解 满足约束条 (1.2)和 (1.3)
的 x称为可行解，也称为可行点或容许点。
定义１,2 可行域 全体可行解构成的集合称为可行域，也称为容许集，记为 D,即：
nii RxpmixcmixcxD,,,1,0,,2,1,0
定义１,3 整体最优解 若：
Dx?
,* Dx? 对于一切则称,* xfxf?恒有 *x 为最优化问题的整体最优解。
若：,,*xxDx 恒有,* xfxf?
则称 *x 为最优化 问题的严格整体最优解。
定义１,4 局部最优解 若：,* Dx? 存在 *x
的某邻域,*xN? 使得对于一切*xNDx
恒有xfxf?* 则称 *x 为最优化问题的局部最优解。 其中 。0,**
xxxxN
同样有：严格局部最优解。
而局部最优解不一定是整体最优解。
显然，整体最优解一定是局部最优解，
注意：
求解最优化问题，实际上是求可行域
D上的整体最优解。 但是,在一般情况下，
整体最优解是很难求出的，往往只能求出局部最优解。
定义１,5 范数,在 n 维向量空间 nR 中，
定义实函数,x 使其满足以下三个条件：
（１）对任意 nRx? 有,0?x
在当且仅当
0?x 时 ；0?x
（２）对任意 nRx? 及实数? 有 ；xx
（３）对任意
x
有 yxyx
则称函数
nRyx?,
为 nR 上的向量范数。
两类比较常见的范数：
P-范数,
pxx
pn
i
p
ip 1
/1
1
其中最常用的是 2-范数，即：
2/1
1
2
2
n
i
ixx
范数,i
ni xx 1m a x
最优化问题的分类根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题。
根据目标函数和约束函数的函数类型分类：线性最优化问题、非线性最优化问题、
二次规划、多目标规划、动态规划、整数规划、０－１规划。
§ 1.2 最优化方法概述迭代算法：选取一个初始可行点,
0 Dx?
由这个初始可行点出发，依次产生一个可行点列：
,,,,21 kxxx 记为,kx
使得 kx 恰好是问题的一个最优解，
或者该点列kx 收敛到问题的一个最优解。
下降算法：在迭代算法中一般要求：
kk xfxf 1
可行点列的产生在
kx 处求得一个方向 kp处求得一个方向 （可行下降方向）
在射线0
kk px
上求一点：
kkkk pxx 1
使得
kk xfxf 1
其中
k?
称为步长。
下降方向（ P16-17）
定义 1.6 下降方向,在点 kx 处,对于方向
,0?kp 若存在实数,0 使得任意的
,0? 有：
kkk xfpxf
成立,则称 kp 为函数xf 在点 kx 处的一个下降方向。
当xf 具有连续的一阶偏导数，令,kk xfg
由 Taylor公式：
kTkkkk pgxfpxf
当 0?kTk pg 时，有,
kkk xfpxf
所以（? 充分小时） kp 是xf 在 kx 处的一个下降方向。
通常称满足,0?kTk pg 的方向 kp 为xf 在 kx
处的下降方向。
可行方向（ P17）
定义 1.7 可行方向,已知区域,,DxRD
kn
对于向量,0?kp 若存在实数,0 使得任意的
,0? 有：
Dpx kk
则称 kp 为 kx 点处 关于区域 D 的可行方向。
下降方向关于区域 D 可行，则称为可行下降方向。
最优化问题的算法的一般迭代格式给定初始点,
0x 令 。0?k
（１）确定
kx
处的可行下降方向 ;kp
（２）确定步长,0?
k?
使得：
kkkk xfpxf
（３）令
kkkk pxx 1
（４）若 1?kx 满足某种终止准则，则停止；
否则令,1 kk 转（１）
收敛性如果一个算法只有当初始点充分接近最优解时，产生的点列才收敛，则称该算法为具有 局部收敛 的算法。
如果对任意的初始点，由算法产生的点列都收敛，则称该算法为具有 全局收敛 的算法。
具有全局收敛性的算法才有实用意义。
但对算法的局部收敛性分析，在理论上是重要的，因为它是全局收敛性分析的基础。
收敛速度定义 1.8 设序列 收敛于 而且：kx *,x
*
*
1lim
xx
xx
k
k
k
若,10 则称序列kx 为线性收敛的，称
为收敛比；
若,0 则称序列kx 为超线性收敛的。
收敛速度定义 1.9 设序列 收敛于 若对kx *,x
0,lim
*
*
1
p
k
k
k xx
xx
则称序列
kx 为
,1?p 有：
p 阶收敛的。
特别当,2?p 时称为二阶收敛的。
终止准则对于一种算法，应该有某种终止准则，当某 次迭代
kk xx 1
满足终止准则时，就停止迭代。常用的 终止准则有：
（１） 或
k
kk
x
xx 1
（２）
kk xfxf 1 或
k
kk
xf
xfxf 1
（３）
kk gxf
其中 0 是预先给定的。
