http://www.ma-xy.com
目录
第一章 全局优化 1
1.1 全局优化简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 凸集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 凸函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 函数的连续性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4 凸包络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.5 lipschitz
函数
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.6 D.C. 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 常见的全局优化模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 凹极小化问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 D.C. 规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Lipschitz 规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 最优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1
http://www.ma-xy.com
第一章 全局优化
1.1 全局优化简介
在最优化刚开始的时候，我们提到过有局部极小点和全局极小点。因为全局极小点不易求解，
所以我们前面都是在求局部极小点。并且提到过，如果一个问题是凸规划，则局部极小点就是全
局极小点。下面，我们将来介绍非凸规划中的全局优化。全局最优化研究的是非线性目标函数在
某个特征区域上全局最优点的特征和计算方法。由于目标函数通常是非凸函数，特定区域也可能
不是凸集 (即非凸区域)，所以全局优化也称非凸优化。
1.1.1 凸集
定义 (凸集) 一个集合 S ⊂ R
n
是凸集，即 ∀x
1
, x
2
∈ S，∂ ∈ [0, 1]，有 ∂x
1
+ (1 − ∂)x
2
∈ S.
定义 (凸组合) 给定 m 个向量 x
1
, x
2
, . . . , x
m
∈ R
n
以及
m
i=1
∂
i
= 1, (∂
i
⩾ 0)，称向量
m
i=1
α
i
x
i
为 x
1
, x
2
, . . . , x
m
的凸组合.
定理 集合 S ⊂ R
n
是凸集，当且仅当它包含了具有有限个元素的所有凸组合，即对 ∀m ∈
N
+
≜ {1, 2, · · · } 以及 ∀x
i
(i = 1, 2, · · · , m) ∈ S，有
m
i=1
∂
i
x
i
∈ S，其中：
m
i=1
∂
i
= 1, (∂
i
⩾ 0)。
性质：凸集关于加法、数乘、和交运算是封闭的，即 S
1
+ S
2
, βS
1
, S
1
∩ S
2
为凸集。
定义 (凸包) 集合 T ⊂ R
n
的凸包是指所有包含 T 的凸集的交集，记为 convT =
C⊇T
C，其
中：C 为凸集。
命题：若集合 S ⊂ R
n
是凸集，则它的闭包 S 也为凸集。
定义 (凸锥) 设非空集合 C ⊆ R
n
，若 ∀x ∈ C, λ > 0, λx ∈ C，则称 C 为一个锥。此外，若
C 为凸集，该锥为凸锥。
性质：锥关于正的数乘的运算封闭，凸锥关于加法和正的数乘运算是封闭的。一般地对于凸
集 S，集合 K (S) = {λx|λ > 0, x ∈ S} 是包含 S 的最小凸锥。
定义 (尖锥) 对于锥 C，若 O ∈ C，则 C 为一尖锥。
1
http://www.ma-xy.com
1.1 全局优化简介 第一章 全局优化
约定：非空集合 S ⊂ R
n
生成的凸锥是指 S 中有限个元素非负线性组合的所有点构成的集
合，记为 coneS。特别地，若非空集合 S 是凸的，coneS = K(S) ∪ {0}。
令 ∧(S) 表示由 S 中任何有限个点的所有凸组合的集合。可以证明 cone(S) = ∧(S)。这个
等式反映了从” 外” 和” 内” 两个角度刻画的凸集的特征，通常互称为” 对偶”。并且，如果我们
用 S 内的点来表示 (x ∈ conv(S))。所需要的点数不超过 d(H)。其中，d 是包含 S 的最小仿射
子空间的维数，即集合 S 的维数 dim(S)。
1.1.2 凸函数
定义 (凸函数) 设 S ⊂ R
n
是非空集合，函数 f : S → R，若 ∀x, y ∈ S, ∀λ ∈ (0, 1)，有
f (λx + (1 − λ)y) ⩽ λf (x) + (1 − λ)f (y)
则称 f 是 S 上的凸函数。若不等式对于 x = y 严格成立，则称 f 是 S 上的严格凸函数。
易知：−f 则 S 上的凹函数，若 −f 是 S 上的严格凸，则 f 是 S 上的严格凹函数。
定理 设 f : R
n
→ R 为凸函数，则对 ∀x ∈ R
n
和向量 d ⊂ R
n
/{0}，函数 f 在 x 点处沿方
向 d 的方向导数存在。
性质：¬所有凸函数 f 的集合关于凸锥组合运算是封闭的；函数 f 在开集 ◦
S
内是连续的；
®f 在水平集 (level set)
L(f; α) = {x|x ∈ S, f(x) ⩽ α}
和上镜图 (epigraph)
epi(f) = {(x, y)|x ∈ S, y ∈ R, y ⩾ f (x)} ⊂ R
n+1
均是凸集。
定理 设
S
∈
R
是非空的凸集，
f
:
S
→
R
是凸函数，则
f
在
S
上的局部极小点也是全局极
小点，且极小点的集合是凸集。
定理 (水平集的有界性) 设 S ∈ R 是非空的闭凸集，f : S → R 是二阶连续可微的凸函数。
∀x ∈ S，若 ∃m > 0，使
d
T
∇
2
f(x)d ⩾ m∥d∥
2
, ∀x ∈ L(f; f(x
0
)), d ∈ R
n
则水平集 L(f; f(x
0
)) 是有界的闭凸集。
1.1.3 函数的连续性
定义 (下半连续) 设 S ⊂ R 是非空集合，函数 f : S → R 在 x ∈ S 点下半连续是指，
对于 S 中任意一个收敛到 x 的点列 {x
1
, x
2
, · · · , }，有 f(x) = f ( lim
i→∞
x
i
) ⩽ lim
i→∞
inff(x
i
)，即
f(x) ⩽ lim
y →x
inff(y)。
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 全局优化 1.1 全局优化简介
定义 (上半连续) 同理，f 在 x ∈ S 点上半连续是指，对于 S 中任意一个收敛到 ∆x 的点列
{x
1
, x
2
, · · · , }，有 f( lim
i→∞
x
i
) ⩾ lim
i→∞
supf(x
i
) 即 f(x) ⩾ lim
y →x
supf(y)。
定义 (连续) 如果 f 在 x 点处上半连续又下半连续，则 f 在 x 点处连续。
定理 设 S 是 R
n
中一个非空紧集，如果 f(x) 是 S 上的下半连续函数，那么 f(x) 在 S 上
至少有一个全局极小点；如果 f(x) 是 S 上的上半连续函数，则 f(x) 在 S 上至少有一个全局极
大点。
注：若上述定理中 f 是连续的，则结论称为 Weierstrass 定理。
定义 (函数的下境图) 函数 f 的下境图 (hypograh) 定义为
hyp(f) = {(x, y)|y ⩽ f(x), x ∈ S, y ∈ R} ⊂ R
n+1
定义 (函数的上境图) 函数 f 的上境图 (epigraph) 定义为
epi(f) = {(x, y)|y ⩽ f(x), x ∈ S, y ∈ R} ⊂ R
n+1
定理 f 是 S 下半连续的等价于，∀∂ ∈ R，水平集 L(f, ∂) 是闭的，等价于上镜图 epi(f) 在
R
n+1
中是闭集。
定义 (强制) f : R
n
→ R 是强制的指 lim
∥x∥→∞
f(x) = +∞
定理 若 f(x) 是强制的，并且下半连续，则 lim
x∈R
n
f(x) 至少有一个全局极小点。
定义 (次梯度) 一个向量 p 称为凸函数 f : S → R 在 x ∈ S 的次梯度，指
f(y) ⩾ f(x) + p
T
(y − x) ∀y ∈ S
定义 (次微分) f 在 x 点的所有次梯度的集合称为 f 在 x 点的次微分，记为 ∂f(x)，若
∂f(x) = ϕ，则 f 在 x 点次可微。
性质：f 在 x 点的次微分 ∂f (x) 是一个闭凸集，特别地，若 f 在 x 点是次可微的，则
∂f(x) = {∇f(x)}。在一般情形下，∂f (x) 可能是空集。
给定一个紧凸集 S ⊂ R
n
，和凹函数 f : S → R，则 f 可以在 S 的某个极点取得全局极小
点。并且，若 f 是严格凹函数，它的全局极小值只能出现在 S 的极点处。
1.1.4 凸包络
定义 (凸包络) 设 S ⊆ R
n
是一个非空凸集，f : S → R 是下半连续函数。f 在 S 上的凸包
络是指满足如下性质的函数 F (x):
¬F (x) 在 S 上是凸的
对于所有 x ∈ S，F (x) ⩽ f (x)
®对于任意一个定义在 S 上的凸函数 h(x)，∀x ∈ S, h(x) ⩽ f (x)，则 ∀x ∈ S，有 h(x) ⩽ F (x)。
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.1 全局优化简介 第一章 全局优化
根据凸包络的定义可以看出，凸包络是 f 在 S 上最佳一致的凸下面估计量。凸包络示意图
如图 (1.1) 所示
图 1.1: 凸包络示意图
基于凸函数这一概念，可以证明，每个凸可行域上的非凸规划问题，相伴着一个具有相同最
优值的凸规划问题，即设 f : S → R 是定义在 R
n
中的非空紧凸集 S 上的下半连续函数，考虑
global min
x⊂C
f(x)
令 F (x) 是函数 f (x) 在 S 上的凸包络，则
f
x
= min {f (x)|x ∈ S} = min {F (x)|x ∈ S}
并且
{y ∈ S|f(y) = f
∗
} ⊆ {y ⊂ S|F (y) = f
∗
}
虽然在理论上我们可以解凸包络问题，但在实际中，找一个函数的凸包络，同计算它的全局
极小点一样困难。
1.1.5 lipschitz 函数
定义 (lipschitz 函数) 在 P ⊆ R
n
上的实值函数 f 称为 lipschitz 函数，是指 ∃L = L(f, p) >
0(L 是 lipschitz 常数)，使得 ∀x
1
, x
2
∈ P ，有
∥f(x
2
) − f(x
1
)∥ ⩽ L∥x
2
− x
1
∥
注：连续函数不一定是 lipschitz 函数
定义 (局部 lipschitz 函数) R
n
上的函数 f (x) 称为局部 lipschitz 函数，是指对于每个 x
0
∈
R
n
，存在一个以 x
0
为球心，以 ε > 0 为半径的球 B(x
0
, ε) 和常数 L > 0，使得 ∀x, y ∈ B(x
0
, ε)，
有
∥f(x) − f (y)∥ ⩽ L∥x − y∥
命题 设 P ⊂ R
n
是凸集，若函数 f 在包含 P 的一个开集上连续可微，并且在 P 上具有有
界梯度，则 f 在 P 上 lipschitz 函数，并且具有 lipschitz 常数
L = sup{∇h(x)|x ∈ P }
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 全局优化 1.1 全局优化简介
一般来说，找到上式的上界是一件困难的事情。但是，在许多使用 lipschitz 函数的优化技术
中，集合 P 是逐次加细的矩形或单纯形。对于此类集合，可以使用自适应的方法逼近常数 L。区
间分析方法提供了一种在矩形上估计常数 L 的十分有用的技术。lipschitz 函数是十分广泛的一
类函数，这类函数关于许多常见的运算是封闭的。
命题 设 f, g 是紧集 P ⊂ R
n
上的 lipschitz 函数，则下面的断言 成立：
(1) f, g 的每个线性组合在 P 上是 lipschitz 函数；
(2) max{f, g} 和 min{f, g} 在 P 上是 lipschitz 函数；
(3) 乘积 f · g 在 P 上是 lipschitz 函数；
(4) ∀p ∈ [1, +∞), (|f|
p
+ |g|
p
)
1/p
在 P 上是 lipschitz 函数。
1.1.6 D.C. 函数
根据二次函数 Hesse 矩阵的正负特征根，可以将二次函数表示成对应正特征根的凸部分和
对应负特征根的凹部分之和。事实上，许多优化问题涉及的函数都可以表示成每个凸函数之差
(dierences of two concexfunctions, 简记为 D.C.)。
定义 (D.C. 函数) 给定凸集 x ⊆ R
n
，函数 f : x → R 称为集合 x 上的 D.C. 函数是指，f
在 x 上可以表示为如下形式
f(x) = p(x) − q(x)
其中：
p, q
均是
x
上的凸函数。
D.C. 函数类十分丰富，并且其许多运算是封闭的。
定理 设 f, g 是凸集 x ⊂ R
n
上的 D.C. 函数，则下面的函数都是 x 上的 D.C. 函数：
(1) λf + µg，∀λ, µ ∈ R；
(2) max{f, g} 和 min{f, g} 在 P 上是 lipschitz 函数；
(3) |f(x)|, f
−1
(x) = max{0, f(x)}，f
−1
(x) = min{0, f(x)}；
(4) 乘积 f · g。
定义 (局部 D.C. 函数) 一个函数 f : R
n
→ R 称为局部 D.C. 函数 (locally D.C) 是指，对
于每个 x
0
∈ R
n
，存在一个以 x
0
为球心，以 ε 为半径的球 B(x
0
, ε)，使得 f 是 B(x
0
, ε) 上的
D.C. 函数。
定理 每个局部 D.C. 函数是 D.C. 函数。
定理 若函数 f : R
n
→ R 的二阶偏导数处处连续，则它是 D.C. 函数。
定理 在紧凸集 C ⊂ R
n
上的每个实值连续函数都是 C 上一致收敛的 D.C. 函数序列的极限。
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.2 常见的全局优化模型 第一章 全局优化
1.2 常见的全局优化模型
1.2.1 二次规划
二次规划
min f(x) =
1
2
x
T
Qx + c
T
x
s.t. x ∈ D
其中：Q ∈ R
n×n
是一个实对称矩阵，c ∈ R
n
，D 是 R
n
中的一个多面体。若 Q 是负半定的，则
f
(
x
)
是凹函数；若
Q
至少有一个正的和一个负的特征值
(
即
Q
为不定矩阵
)
，则相应的
QP
为
不定二次规划问题。下面，给出一些可以用凹的或者不定的二次规划模型描述的优化问题。
¬线性 0-1 规划
min c
T
x
s.t. Ax ⩽ b
x
i
∈ {0, 1}
令 e = (1, . . . , 1)
T
∈ R
n
，则上述问题等价于如下的凹二次规划
min f(x) = c
T
x + µx
−1
(e − x)
s.t. Ax ⩽ b
0 ⩽ x ⩽ e
其中：µ 是一个充分大的正数。
二次 0-1 规划
min f(x) = c
T
x + x
T
Qx
s.t. x
i
∈ {0, 1}
i = 1, 2, · · · , n
对于任意给定的实数 µ，令
¯c = c − µe
¯
Q = Q + µI
注意到，对 ∀i ∈ {1, 2, · · · , n}，当 x
i
∈ {0, 1} 时，x
2
i
= x
i
，所以转化为
min
¯
f(x) = ¯c
T
x + x
T
¯
Qx
s.t. x
i
∈ {0, 1}
其中：
¯
f(x) = f (x)。特别地，如果选择 µ，使
¯
Q = Q + µI 为负半定，则
¯
f(x) 是凹的。于是约
束条件可替换为 0 ⩽ x ⩽ e。
®二次指派问题 (QAP)
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 全局优化 1.2 常见的全局优化模型
给定正整数 n 以及两个元素非负的 n×n 矩阵 A = (a
ij
) 和 B = (b
ij
)，寻找集合 {1, 2, . . . , n}
的一个置换 p = (p(1), · · · , p(n))，使之极小化
C(p) =
n
i=1
n
j=1
a
ij
b
p(i)p(j)
上述问题等价于下面的二次 0-1 规划
min
n
i=1
n
j=1
n
k=1
n
l=1
a
ij
b
kl
x
ik
x
jl
s.t.
n
i=1
x
ij
= 1, j = 1, 2, · · · , n
n
j=1
x
ij
= 1, i = 1, 2, · · · , n
x
ij
∈ {0, 1}, i, j = 1, 2, · · · , n
易看出，未知元可以表示成 n
2
维向量的形式，记为 x。
min x
T
Sx
s.t. x ∈ D
其中：S ∈ R
n
2
×n
2
。现在，考虑如下凹二次规划
min x
T
Qx
s.t. x ∈ Ω
其中：S ∈ αI，α ⩾ ∥S∥
∞
，Ω 是满足下面条件的所有 x ∈ R
n
2
的集合
n
i=1
x
ij
= 1
n
j=1
x
ij
= 1
x
ij
⩽ 0
1.2.2 凹极小化问题
min
x
f(x)
s.t. g(x) ⩾ 0
x ∈ X ⊂ R
n
其中：f, g 为非空凸开集 X 上的凹函数。
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.2 常见的全局优化模型 第一章 全局优化
假设该问题的可行域是一个紧的凸集，记为 D。整数规划、双线性规划、互补性问题等都可
以变换为凹极小化问题。
¬双线性规划
min f(x, y) = p
T
x + x
T
Qy + q
T
y
s.t. x ∈ X, y ∈ Y
其中：X, Y 分别是 R
n
, R
m
上的多胞体，p ∈ R
n
, q ∈ R
m
, Q ∈ R
n×m
。令 V (X) 和 V (Y ) 分别表
示 X 和 Y 的顶点集。我们知道，对每一个 x ∈ X，min{f (x, y)|y ∈ Y } 的解可以在 Y 的一个顶
点取得。于是，上述问题可表示为
min
x∈X,y∈Y
f(xy) = min
x∈X
{min
y ∈Y
f(x, y)}
= min
x∈X
{ min
y∈V (Y )
f(x, y)} = min
x∈X
g(x)
其中：g(x) = min
y ∈V (Y )
f(x, y) = p
T
x + min{(q + Q
T
x)
T
y|y ∈ V (Y )}。
因为 V (Y ) 是有限的，并且对每个 y ∈ V (Y )，f(x, y) 是 x 的仿射函数，所以 min{(q +
Q
T
x)
T
y|y ∈ V (Y )} 是有限个仿射函数的逐点最小值。因此 g(x) 是分段线性的凹函数。
互补性问题
一般地，给定一个集合 D ⊂ R
n
和函数 g, h : R
n
→ R
m
，如何寻找 x ∈ D，满足
g(x) ⩾ 0, h(x) ⩾ 0, (g(x))
T
h(x) = 0
的问题称为互补性问题。
命题 若上式中的函数 h 和 g 是凸集 D 上的凹函数，则上述问题有解，当且仅当下面的凹
极小化问题的全局极小值为零
min f(x) =
n
i=1
min{g
i
(x), h
i
(x)}
s.t. g(x) ⩾ 0, h(x) ⩾ 0
1.2.3 D.C. 规划
D.C.
规划指如下规划问题
min f
0
(x)
s.t. f
i
(x) ⩽ 0, i = 1, 2, · · · , m
x ∈ X
其中：X 是 R
n
的闭凸子集，并且所有的函数 f
i
都是 D.C. 函数。
典范 D.C. 规划形式如下
min c
T
x
s.t. x ∈ D, g(x) ⩾ 0
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 全局优化 1.2 常见的全局优化模型
其中：D 是 R
n
的闭凸子集，向量 c ∈ R
n
，g : R
n
→ R 是凸函数。
¬双层线性规划
min c
T
1
x + d
T
1
y
s.t. A
1
x + B
1
y ⩾ b
1
x ⩾ 0
y ∈ arg min d
T
2
y
s.t. A
2
x + B
2
y ⩾ b
2
y ⩾ 0
双层线性规划等价于如下典范 D.C. 规划
min c
T
1
x + d
T
1
y
s.t. A
1
x + B
1
y ⩾ b
1
A
2
x + B
2
y ⩾ b
2
ϕ(A
2
x) − d
T
2
y ⩾ 0
x ⩾ 0, y ⩾ 0
其中在多面体 E = {u|u + B
2
y ⩾ b
2
, y ⩾ 0} 上，函数
ϕ(u) = sup{(b
2
− u)
T
λ|B
T
2
λ ⩽ d
2
, λ ⩾ 0}
是下半连续的凸函数，并且
∀
u
1
⩾
u
2
，有
ϕ
(
u
1
)
⩽
ϕ
(
u
2
)
.
双凸规划。考虑非线性规划问题
min
x,y
f(x, y)
s.t. h(x, y) = 0
g(x, y) ⩽ 0
x ∈ X ⊂ R
n
y ∈ Y ⊂ R
m
其中：X, Y 是紧的凸集，h(x, y), g(x, y) 分别是定义等式约束和不等式约束的向量值函数。假设
所有函数 f, h, g 是连续可微的，并且满足下面的双凸条件：
(1) 对于每一个固定的 y, f(x, y) 是关于 x 的凸函数；对于每个固定的 x, f(x, y) 是关于 y 的
凸函数。
(2) 对于每一个固定的 y, h(x, y) 是关于 x 的仿射函数；对于每个固定的 x, h(x, y) 是关于 y
的仿射函数。
(3) 对于每一个固定的 y, g(x, y) 是关于 x 的凸函数；对于每个固定的 x, g(x, y) 是关于 y 的
凸函数。
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.2 常见的全局优化模型 第一章 全局优化
(4) 对于每一个固定的 y，一阶约束规格 (比如 Slater 约束规格) 成立。
我们将原问题首先投影到 y 的空间，可以表示成双层规划形式
min f(x, y)
s.t. y ∈ Y
x ∈
¯
X(y) ⊂ X
¯
X(y) = arg min
x∈X
f(x, y)
s.t. h(x, y) ⩾ 0
g(x, y) ⩽ 0
因为外层 f 是关于 x, y 的双凸函数，所以又称为双凸规划。
1.2.4 Lipschitz 规划
给定一个紧集 D ⊂ R
n
和实值 lipschitz 函数 f : P → R，其中开集 P ⊃ D
min f(x)
s.t. x ∈ D
称为 lipschitz 规划。一般地，D 可以取为下列类型的集合：
¬n− 矩形 {x ∈ R
n
|a ⩽ x ⩽ b}, a ⩽ b ∈ R
n
；
具有顶点 v
0
, · · · , v
n
的 n-单纯形 [v
0
, · · · , v
n
]；
®n− 矩形 {x ∈ R
n
|Ax ⩽ b}, a ∈ R
n×m
, b ∈ R
m
；
¯{x|g
i
(x) ⩽ 0, i = 1, 2, · · · , m} 的集合，其中 g
i
是 lipschitz 函数。
下面以非线性系统来说明
h
j
(x) = 0 j ∈ E
g
i
(x) ⩽ 0 i ∈ I
x
l
⩽ x ⩽ x
u
在上述非线性系统中，变量的个数与等式约束的个数可以不同。上述非线性系统可以变换为如下
极小极大问题
min
x
max
j∈E
|h
j
(x)|
s.t. g
i
(x) ⩽ 0 i ∈ I
x
l
⩽ x ⩽ x
u
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 全局优化 1.3 最优化算法
如果引进非负变量 s = max
j∈E
|h
j
(x)|。那么，极小极大问题等价于
min
x,s
s
s.t. h
j
(x) − s ⩽ 0 j ∈ E
− h
j
(x) − s ⩽ 0 j ∈ E
g
i
(x) ⩽ 0 i ∈ I
x
l
⩽ x ⩽ x
u
s ⩾ 0
若 g
i
, h
j
都是 lipschitz 函数，则上述问题就是 lipschitz 优化问题。当问题的全局极小值为
零时，它的全局极小点 (x
∗
, s
∗
= 0) 与非线性系统的解之间存在一一对应关系。除非函数 h
j
是
线性的，并且函数 g
i
是凸的，上述问题通常是非凸的约束优化问题。对此，如果使用局部优化方
法求解，就可能丢失问题的某些解，甚至得到非线性系统没有解的错误结论。因此，就需要正确
地辨识出问题的全局最优解 (x
∗
, s
∗
) 的存在性。
1.3 最优化算法
求解全局优化的常用算法有：¬外逼近与割平面算法；凹性割方法；®分支定界法等。
http://www.ma-xy.com 11 http://www.ma-xy.com
