http://www.ma-xy.com
目录
第一章 优化工具 Yalmip 简介 1
1.1 一些 Yalmip 可解的优化模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Yalmip 应用实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Yalmip 的安装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 解线性规划和二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 解二阶锥规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4
解半定规划
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.5 解行列式规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.6 解一般凸规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.7 整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.8 非凸二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1
http://www.ma-xy.com
第一章 优化工具 Yalmip 简介
1.1 一些 Yalmip 可解的优化模型
下面，我们来介绍一个 MATLAB 优化工具箱 (重量级) - Yalmip。先来列举一些 Yalmip 可
以求解的优化问题：
(1) 线性规划 LP
min
x
c
T
x
s.t.
Ax = b
x
i
⩾ 0
MATLAB 使用单纯形法、内点法和动态序列算法来求解线性规划问题，求解命令为 x=linprog(c,A,b)。
(2) 二次规划 QP
min
x
x
T
Hx + x
T
p
s.t. Ax ⩾ b
MATLAB 使用内点凸包算法、信赖域反射算法和动态序列算法求解二次规划，求解命令为 x=quadprog(
H,c,A,b).
(3) 二阶锥规划 SOCP
min
x
c
T
x
s.t.
Ax = b
A
i
x − b
i
⪯ L
m
i
其中：L
m
i
是 R
m
i
中的二阶锥。
(4) 线性半定规划 SDP
min
x
c · x
s.t.
A
i
x = b
i
x ⪰ 0
1
http://www.ma-xy.com
1.2 YALMIP 应用实例 第一章 优化工具 YALMIP 简介
(5) 非线性半定规划
min
x
c
T
x
s.t. F
0
+
m
i=1
x
i
F
i
⪰ 0, i = 1, 2, . . . , m
其中：b
i
为实数；c, A
i
, F
i
为 n × n 实对称矩阵。
(6) 行列式规划
min
x
c
T
x + log det G(x)
−1
s.t.
G(x) ⩾ 0
F (x) ⩾ 0
其中：x ∈ R
m
，G : R
m
→ R
l×l
，F : R
m
→ R
n×n
，G
i
= G
T
i
，F
i
= F
T
i
，i = 0, 1, . . . , m
G(x) = G
0
+ x
1
G
1
+ . . . , +x
m
G
m
H(x) = H
0
+ x
1
H
1
+ . . . , +x
m
H
m
一个专用于行列式规划的工具箱是“maxdet”，可参考?。
(7) 几何规划
min
x
f
0
(x)
s.t.
f
i
(x) ⩽ 1, i = 1, . . . , m
h
i
(x) = 1, i = 1, . . . , p
其中：f
i
(x) 是正项函数，x ∈ R
n
。一个专用于几何规划的工具箱是“GGPLAB”，可参考?。
Yalmip 还可以求解整数规划、混合整数规划和全局规划等等最优化问题，这里不再详细介
绍。下面，我们来看 Yalmip 的用法。
1.2 Yalmip 应用实例
1.2.1 Yalmip 的安装
1 %% I n s ta l l a t i o n YALMIP
2 folderName = f u l l f i l e ( matlabroot , ’ toolbox ’ , ’ yalmip ’ ) ;%[pwd f i l e s e p ’ yalmip ’ ]
3 mkdir ( folderName )
4 cd ( folderName )
5 u r l w r i t e ( ’ https : / / github . com/yalmip/yalmip/ a r c hive / master . zip ’ , ’ yalmip . z i p ’ ) ;
6 unzip ( ’ yalmip . z i p ’ , ’ yalmip ’ ) ;
7 p = genpath ( folderName ) ;
8 addpath ( p) ;
9 savepath
10
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 优化工具 YALMIP 简介 1.2 YALMIP 应用实例
1.2.2 解线性规划和二次规划
用 Yalmip 求解线性规划和二次规划。以线性回归问题为例，我们设定线性回归模型为
y = xw + ε
ˆy = xw
其中：x 是 n × p 矩阵。现在要求使下面的目标最小的 w
1. min
w
J
1
(w) = ||y − ˆy||
∞
= max
i
{|y
i
− ˆy
i
|}
2. min
w
J
2
(w) = ||y − ˆy||
1
=
n
i=1
|y
i
− ˆy
i
|
3. min
w
J
3
(w) = ||y − ˆy||
2
=
n
i=1
(y
i
− ˆy
i
)
2
= (y − ˆy)
T
(y − ˆy)
更一般的，我们可以设置目标为离差 y − ˆy 的 p 阶范数
min
w
||y − ˆy||
p
对上面的目标 1、2 和 3，目标 2 为线性规划问题，目标 3 为二次规划问题，并且这些优化
问题不存在约束条件。上述 3 个目标的 Yalmip 的程序为
1 %% 线 性 规 划&二 次 规 划−−−−线 性 回 归 示 例
2 w = [ 1 2 3 4 5 6 ] ’ ;
3 n = ( 0 : 0 . 0 2 : 2 * pi ) ’ ;
4 x = [ s i n (n) si n (2*n) si n (3*n) si n (4*n) si n (5*n) si n (6*n) ] ;
5 e = (−4+8*rand ( le ngth (n ) ,1) ) ;
6 e ( 1 00:115 ) = 3 0;
7 y = x*w+e ;
8 pl o t (n , y) ;
9 %第 一 种 方 法
10 what = sdpvar ( 6 , 1 ) ;
11 r e s i d u a l s = y−x*what ;
12 o ptimize ( [ ] , norm( r e s id u a l s , i n f ) ) ;
13 w_Linf = value (what ) ;
14 o ptimize ( [ ] , norm( r e s id u a l s , 1 ) ) ;
15 w_L1 = value (what ) ;
16 o ptimize ( [ ] , norm( r e s id u a l s , 2 ) ) ;
17 w_L2 = value (what ) ;
18 pl o t (n , [ y x*w_L1 x*w_L2 x*w_Linf ] ) ;
19 %第 二 种 方 法
20 bound = sdpvar ( leng th ( r e s i d u a l s ) ,1 ) ;
21 Co nst rai nts = [−bound <= r e s i d u a l s <= bound ] ;
22 o ptimize ( Constraints , sum(bound) ) ;
23 w_L1 = value (what ) ;
24 %
25 o ptimize ( [ ] , r e si d u a l s ’ * r e s i d u a l s ) ;
26 w_L2 = value (what ) ;
27 %
28 bound = sdpvar ( 1 , 1 ) ;
29 Co nst rai nts = [−bound <= r e s i d u a l s <= bound ] ;
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.2 YALMIP 应用实例 第一章 优化工具 YALMIP 简介
30 o ptimize ( Constraints , bound ) ;
31 w_Linf = value (what ) ;
32 %绘 图
33 pl o t (n , [ y x*w_L1 x*w_L2 x*w_Linf ] ) ;
34
1.2.3 解二阶锥规划
我们仍然以回归问题为例，考虑一般形式的岭回归
min
w
||y − xw||
2
+ λ||w||
2
为了方便，这里我们取 λ = 1，于是优化问题变为
min
w
||y − xw||
2
+ ||w||
2
将上面的优化问题变为二阶锥 SOCP 问题，有
min
w
u + v
s.t.
||y − xw||
2
⩽ u
||w||
2
⩽ v
上面问题的程序为
1 %% 二 阶 锥 规 划−−线 性 回 归 示 例
2 sdpvar u v
3 %方 法 1
4 F = [ cone ( y−x*what , u) , cone (what , v) ] ;
5 sol ves dp (F, u + v) ;
6 %方 法 2
7 F = [ norm( y−x*what , 2 ) <= u , norm( what , 2 ) <= v ] ;
8 sol ves dp (F, u + v) ;
9 %方 法 3
10 sol ves dp ( [ ] , norm(y−x*what , 2 ) + norm(what , 2 ) ) ;
11
1.2.4 解半定规划
考虑如下半定规划问题
min
w
c
T
x
s.t.
A
1
x = b
1
A
2
x ⩾ b
2
F
0
+ x
1
F
1
+ · · · + x
p
F
p
⩾ 0
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 优化工具 YALMIP 简介 1.2 YALMIP 应用实例
其中：F
0
+ x
1
F
1
+ · · · + x
p
F
p
⩾ 0 是一个 LMI(Linear Matrix Inequality)。我们将模型中的量设
置为
F
0
=
2 −0.5 −0.6
−0.5 2 0.4
−0.6 0.4 3
, F
1
=
0 1 0
1 0 0
0 0 0
F
2
=
0 0 1
0 0 0
1 0 0
, F
3
=
0 0 0
0 0 1
0 1 0
以及
0.7 ⩽ x
1
⩽ 1
0 ⩽ x
2
⩽ 0.3
0 ⩽ x
3
x
1
+ x
2
+ x
3
= 1
令 t = c
T
x，则有
min
x
t
s.t.
A
1
x = b
1
A
2
x ⩾ b
2
tI − (x
1
F
1
+ x
2
F
2
+ x
3
F
3
) ⩾ 0
其中：x = (x
1
, x
2
, x
3
, t)
T
，A = [1, 1, 1, 0]
T
，b = 1，b
2
= (0.1, −1, 0, −0.3, 0)
T
，A
2
=
1 0 0 0
−1 0 0 0
0 1 0 0
0 −1 0 0
0 0 1 0
。利用 Yalmip 求解上述 NLSDP(非线性半定规划) 的程序为
1 %% 半 定 规 划
2 t = sdpvar ( 1 ) ;
3 x = sdpvar (3 , 1 , ’ f u l l ’ ) ;
4 F0 = [2 , − 0 . 5 , − 0.6 ; − 0. 5 ,2 , 0.4; − 0.6 , 0.4 , 3 ];
5 F1 = [ 0 1 0; 1 0 0 ; 0 0 0 ] ;
6 F2 = [ 0 0 1 ; 0 0 0;1 0 0 ] ;
7 F3 = [ 0 0 0 ; 0 0 1;0 1 0 ] ;
8 a = [sum( x ) == 1 ] ;%等 式 约 束
9 b = [ 0 . 7 <= x( 1 ) <= 1 , 0 <= x ( 2) <=0.3, x ( 3) >=0];%不 等 式 约 束
10 c = [ t * eye (3 )
−
(F0 + x(1) F1 + x ( 2 )F( 2 )+ x(3)F3)>= 0 ]%LMI约 束
11 obj = t ;
12 con s t r ai n t = [ a , b , c ] ;
13 sol ves dp ( c onstrain t , obj ) ;
14 xbest = double ( x ) ;
15
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.2 YALMIP 应用实例 第一章 优化工具 YALMIP 简介
1.2.5 解行列式规划
给定两个椭圆
E
1
= {x|x
T
P
1
x ⩽ 1}
E
2
= {x|x
T
P
2
x ⩽ 1}
找到包含这两个 E
1
, E
2
的最小椭圆 E = x
T
x ⩽ 1。由于椭圆的体积与 det p 成正比，所以我们的
目标是
max
P
det P
s.t.
P ⩽ t
1
P
1
P ⩽ t
2
P
2
0 ⩽ t
1
⩽ 1
0 ⩽ t
2
⩽ 1
目标函数 min
P
− det P 是非凸的，但是单调转换可以使其变为凸问题，例如：min
P
− log det P 。
Yalmip 采用如下变化
min
P
− det(P )
1
m
其中：m 为 P 的维数，这里 m = 2。其求解程序为
1 %% 行 列 式 规 划
2 n = 2 ;
3 P1 = randn (2 ) ; P1 = P1*P1 ’ ;
4 P2 = randn (2 ) ; P2 = P2*P2 ’ ;
5 t = sdpvar ( 2 , 1 ) ;
6 P = sdpvar (n , n) ;
7 F = [1 >= t >=0, t ( 1) *P1 − P >= 0 , t ( 2 ) *P2 >= 0 ] ;
8 obj = −geomean(P) ;
9 s o l = optimize (F, obj ) ;
10 x = sdpvar (2 , 1 ) ;
11 pl o t (x ’ * value (P1) *x , [ ] ) , hold on
12 pl o t (x ’ * value (P2) *x , [ ] )
13 pl o t (x ’ * value (P) *x , [ ] )
14 % 或 者
15 o ptimize (F − l ogdet (P) , s d p s e t t in g ( ’ s o l v e r ’ , ’ sdpt3 ’ ) ) ;
16
1.2.6 解一般凸规划
考虑如下一般的凸规划问题
max
x
−
log(b − Ax)
s.t. Ax ⩽ b
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 优化工具 YALMIP 简介 1.2 YALMIP 应用实例
令 y = log(b − Ax)，则
min
x
−
y
s.t. e
y
<= b − Ax
上述问题的 Yalmip 程序为
1 %% 一 般 凸 规 划
2 n = 5 ;m = 20;
3 A = randn (m, n) ;
4 b = rand (m,1 ) *m;
5 x = sdpvar (n , 1 ) ;
6 y = sdpvar (m,1 ) ;
7 con s t r ai n t = [ exp ( y <= b−Ax) ] ;
8 obj = −sum( y ) ;
9 s o l = optimize ( co n s t r a i nt , obj ) ;
10
1.2.7 整数规划
考虑如下整数规划问题
min
x
c
T
x
s.t.
Ax ⩽ b
Aeqx ⩽ beq
x ⩾ x
m
x为整数
MATLAB 旧版本用 bintprog 命令来求解 0-1 规划，新版本 MATLAB 用 intprog 命令来求
0-1 规划、整数规划和混合整数规划。上述问题的 Yalmip 求解程序为
1 %% 整 数 规 划
2 c = −[2 1 4 3 1 ] ’ ;
3 A = [ 0 2 1 4 2 ; 3 4 5 −1 − 1];
4 b = [ 5 4 ; 6 2 ] ;
5 Aeq = [ ] ; beq = [ ] ;
6 xm = [ 0 , 0 ,3 . 5 2 , 0 . 678 , 2 . 5 7 ] ’ ;
7 x = sdpvar (5 , 1 ) ;
8 obj = c ’ * x ;
9 con s t r ai n t = [ Ax <= b , xm <= x , in t e g e r (x) ] ;
10 s o l = optimize ( c o n s tr a i n t , obj ) ;
11
另外，我们考虑在线性回归中，待求参数 w 是整数的情况
min
w
||y − wx||
2
s.t. w为整数
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.2 YALMIP 应用实例 第一章 优化工具 YALMIP 简介
1 what = i n t v a r ( 6 , 1 ) ;%what = sdpvar ( 6 , 1 ) ;
2 r e s i d u a l s = y−x*what ;
3 o ptimize ( [ ] , norm( r e s id u a l s , 2 ) ) ;
4 w_L2 = value (what ) ;
5 pl o t (n , [ y x*w_L1 x*w_L2 x*w_Linf ] ) ;
6
1.2.8 非凸二次规划
考虑如下非凸二次规划
min
x
x
T
Qx
s.t. − 1 ⩽ x ⩽ 1
其求解程序为
1 %% 非 凸 二 次 规 划
2 Q = magic (5 ) ;
3 x = sdpvar (5 , 1 ) ;
4 ops1 = s dp s e t tin g s ( ’ s o l v e r ’ , ’bmibnb ’ , ’bmibnb . maxiter ’ , 1 0 0 0 , . . .
5 ’bmibnb . u ppe rsol ver ’ , ’ fmincon ’ ) ;
6 ops2 = s dp s e t tin g s ( ’ s o l v e r ’ , ’moment ’ , ’moment. or de r ’ ,3 ) ;
7 ops3 = s dp s e t tin g s ( ’ s o l v e r ’ , ’moment ’ , ’moment. or de r ’ ,2 ) ;
8 ops4 = s dp s e t tin g s ( ’ s o l v e r ’ , ’ kktqp ’ ) ;
9 f o r n = 1 :10
10 Q = magic ( n) ;
11 x = sdpvar (n , x) ;
12 s o l = optimize([
−
1<=x<=1],x ’ *Q*x , ops1 ) ;
13 comptimes (n , 1 ) = s o l . s o l v e r t i n e ;
14 s o l = optimize([−1<=x<=1],x ’ *Q*x , ops2 ) ;
15 comptimes (n , 2 ) = s o l . s o l v e r t i n e ;
16 s o l = optimize([−1<=x<=1,x . * x<=1],x ’*Q*x , ops3 ) ;
17 comptimes (n , 3 ) = s o l . s o l v e r t i n e ;
18 s o l = optimize([−1<=x<=1],x ’ *Q*x , ops4 ) ;
19 comptimes (n , 4 ) = s o l . s o l v e r t i n e ;
20 end
21 semilogy ( 1 : n , comptimes )
22
http://www.ma-xy.com 8 http://www.ma-xy.com
