http://www.ma-xy.com
第一章 最小最大规划
1.1 问题的引入与分析
重新考虑前面的线性回归，在最小二乘回归中，我们要求预测与实际的离差平方和最小，即
min
w
∥y − w
T
x∥
2
2
=
n
∑
i=1
(y
i
− w
T
x
i
)
2
s.t.
∑
w = 1
当然，我们可以将 n 个残差 e
i
= y
i
− w
T
x
i
进行加权处理，设 n 个权重为 η
i
，有
min
w
n
∑
i=1
η
i
(y
i
− w
T
x
i
)
2
s.t.
∑
w = 1
上面的加权模型称为加权最小二乘回归。下面，我们要求残差中最大的那一个最小，有
min
w
max
i
(y
i
− w
T
x
i
)
上述规划问题是一个最小最大规划。求解上面这个 Chekyshev approximation problem 等价
于求解下面的线性规划
min t
s.t. w
T
x
i
− t ⩽ y
i
− w
T
x
i
− t ⩽ −y
i
i = 1, 2, . . . , n
其中：w ∈ R
n
, t ∈ R。
对于最大最小规划 (最小最大规划)，我们再考虑一个示例
min max
x
1
sin(x
2
)
1 − x
1
x
2
(1.1)
s.t. 0 ⩽ x ⩽ 1
注：此外，SVM 也是从离超平面的最小间隔最大化推出来的。
1
http://www.ma-xy.com
1.2 模型规范化及基础理论 第一章 最小最大规划
1.2 模型规范化及基础理论
上述引例中的规划问题称为极小极大规划 (最小最大规划)，是一种常见的不可微优化问题，
其一般形式为
min
y
max
i
f
i
(y) (1.2)
s.t.
l
k
(y) ⩽ 0 k ∈ J
h
j
(y) = 0 j ∈ l
2
其中：i ∈ I = {1, 2, . . . , p}，J = {1, 2, . . . , q}，l
2
= {1, 2, . . . , s},y ∈ R
n
为决策变量。f
i
(y), l
k
(y), h
j
(y) :
R
n
→ R。
假设：f
i
, l
k
, h
j
为连续可微函数。对上述问题引入变量 δ ∈ R，有
min δ (1.3)
s.t.
f
i
(y) ⩽ δ i ∈ I
l
k
(y) ⩽ 0 k ∈ J
h
j
(y) = 0 j ∈ l
2
引理 (1) 如果 (y, δ) 为 (1.3) 可行的，则 y 为 (1.2) 可行的；如果 y 为 (1.2) 可行的，则存
在 δ ∈ R 使得 (y, δ) 为 (1.3) 可行的。
引理 (2) 如果 ¯y 是 (1.2) 的最优解，且对应 (1.2) 的最优值为
¯
δ；当且仅当 (¯y,
¯
δ) 为 (1.3) 的
最优解，对应 (1.3) 的最优解为
¯
δ。
易知，在引理 (1) 和引理 (2) 下，(1.2)(1.3) 是等价的。令 x = (δ, y) ∈ R
1+n
，g
i
(x) =
−δ + f
i
(y), i ∈ I，g
k
(x) = l
k
(y), k ∈ J，δ(x) = δ，p + q = m，则 (1.3) 转化为
min f(x) (1.4)
s.t.
g
i
(x) ⩽ δ i ∈ l
1
h
j
(x) = 0 j ∈ l
2
其中：l
1
= {1, 2, . . . , m}，{1, 2, . . . , s}。记 L = l
1
∪ l
2
，Q = {x ∈ R
1+n
, g
i
(x) ⩽ 0, i ∈ l
1
; h
j
(x) =
0, j ∈ l
2
}。
原问题的 Lagrange 对偶问题为
max I(µ, λ ) = inf
x
L(x|µ, λ) (1.5)
其中：µ ∈ R
m
+
, λ ∈ R
n
为 Lagrange 乘子；L(x, µ, λ) 为拉格朗日函数，L(x, µ, λ) = f(x)+µ
T
g(x)+
λ
T
h(x)。
令 Z = {z|z = (µ
T
, λ
T
)
T
, µ ∈ R
m
+
, λ ∈ R
n
}。对固定 z，记 D(z) 是 L(x; z) 的全体极小点集。
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 最小最大规划 1.2 模型规范化及基础理论
定义 称 z
∗
∈ Z 是 (1.4) 的 Lagrange 乘子，若 inf
x∈R
1+n
L(x; z
∗
) = f(x
∗
)。
假设 (1) 问题 (1.4) 的最优解集以及 Lagrange 乘子的集合是非空的。
假设 (2) 对问题 (1.4) 的每个 Lagrange 乘子 z
∗
，D(z
∗
) 含有唯一全局最小点。
在假设 1 和假设 2 的条件下，我们有以下定理：
定理 在假设 1 下，f(∗) = sup
z∈Z
I(z)，z
∗
是 (1.4) 的一个 Lagrange 乘子的充分必要条件是 z
∗
是 (1.5) 的最优解。
定理 在假设 1,2 下 z
∗
∈ Z，z
∗
是 (1.5) 的最优解的充分必要条件是：对任意 x
∗
∈ D(z
∗
)，
有 ((x
∗
, z
∗
) = f(x
∗
)), g(x
∗
) ∈ 0, h(x
∗
) = 0，且 (x
∗
, z
∗
) 为 (1.4) 的 KKT 点。
定理 设 I(z) 如前定义，则 I(z) 是 z ∈ Z 的凹函数。
我们将问题 (1.5) 转化为标准形式
min −I(z) (1.6)
s.t. Az ⩽ b
其中：z ∈ R
m+s
，A = [−I
m
, 0]
m
×
(
m
+
s
)
，b = 0。易知，问题 (1.2) 是一个线性约束的凸规划问题，
从全局优化理论来看，已有较为有效的求解方法，下面，我们给出此问题的信赖域方法：
设第 k 次迭代已有当前迭代点 z
k
，且 z
k
是可行的，对应的信赖域子问题为
min
d
g
T
k
d +
1
2
d
T
B
k
d = φ
k
(d) (1.7)
s.t.
A(z
k
+ d) ⩽ b
∥d∥ ⩽ ∆
k
记 d
k
为 (1.7) 的解。定义比值
r
k
=
−I(z
k
) − (−I(z
k
+ d
k
))
φ
k
(0) − φ
k
(d
k
)
(1.8)
由 d
k
的定义，显然 d
k
= 0，当且仅当 z
k
是 (1.6) 的 KKT 点。
信赖域算法步骤：
step1. 初始化。
给出 z
1
满足 Az
1
⩽ b, B
1
∈ R
(m+s)×(m+s)
，∆
1
⩾ 0, ε ⩾ 0, k := 1。
step2. 求解问题 (1.7)，给出 d
k
(方向)，如果 ∥d
k
∥ ⩽ ε，则停止；否则，根据公式 (1.8) 计算 r
k
：
如果 r
k
> 0，则 z
k+1
:= z
k
+ d
k
；否则 z
k+1
:= z
k
。
step3. 如果 r
k
⩾ 0.25，则转到 step4，∆
k
= ∆
k
/2，转到 step5。
step4. 如果 r
k
⩾ 0.75，或者 ∥d
k
∥
∞
⩽ ∆
k
则转到 step5；否则 ∆
k
= 2∆
k
。
step5.∆
k+1
= 2∆
k
，计算矩阵 B
k+1
；置 k := k + 1 转到 step2。其中：B
k+1
可由拟牛顿公式给
出。
下面，给出算法的一些性质：假设 {B
k
} 一致有界，即 ∃M > 0，使得 ∥B
k
∥ ⩽ M。
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.3 MATLAB 应用实例 第一章 最小最大规划
定理 在上述假设下，算法所产生的点列 {z
k
} 有聚点，则必有一个聚点是问题 (1.6) 的 K-T
点。
推论 算法产生的点列为 {z
k
}，设 {x
k
} ∈ D{z
k
}, k = 1, 2, . . .，则 {x
k
} 的每一个聚点都是
(1.4) 的最优解
1.3 MATLAB 应用实例
MATLAB 采用 fminimax 求解极小极大规划问题，fminimax 可以解决的极小极大规划问题
的一般形式如下
min
x
max
i
f
i
(x)
s.t.
c(x) ⩽ 0
ceq(x) = 0
Ax ⩽ b
Aeq · x = beq
lb ⩽ x ⩽ ub
fminimax 的调用格式为
[x,fval,maxfval,exitag,output,lambda]=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
其中：输入可以变为结构体，例：problem,objective 等；maxfval 为目标函数在解 x 处的最大值。
应用 fminimax 求解前面的引例 2(1.1)，求解程序如下
1 func = @(x)[x(1)*sin(x(2));1−x(1)*x(2)];
2 x0 = [0.5,0.3];
3 A=[];b=[];
4 Aeq=[];beq=[];
5 lb = [0,0];
6 ub = [0,0];
7 x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub);
8
http://www.ma-xy.com 4 http://www.ma-xy.com
