http://www.ma-xy.com
目录
第一章 二次规划 1
1.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 模型的规范化及基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 规范化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 最优化条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 对偶问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3
最优化算法
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Lagrange 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 内点算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 MATLAB 应用实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 组合投资问题的混合整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1
http://www.ma-xy.com
第一章 二次规划
1.1 问题的引入与分析
考虑如下组合投资问题：设有 n 支股票，第 i 支股票的收益率为 r
i
(当然，就时间序列而言，
此需要平稳性前提)。我们假设 [0, T ] 时间内 r
i
(t) 独立同分布于 N(µ
i
, σ
2
i
)，则
µ
i
= E(r
i
)
σ
2
i
= E[(r
i
− µ
i
)
2
]
现在，我们决定将现有资产中的
x
i
比例投资股票
i
。问：如何的组合情况
x
= (
x
1
, x
2
, . . . , x
n
)
T
，
能使投资的收益最大风险最小。
解：目标 1，我们要求股票收益最大。我们将收益定义为
R = x
T
r =
n
i=1
x
i
r
i
目标 2，投资风险最小。风险的度量有许多种，这里，我们选取最常用的方差作为度量。投
资组合 R = x
T
r 的方差为
E(R − E(R))
2
= E
i
x
i
(r
i
− µ
i
)
2
=
i
j
x
i
x
j
σ
ij
= x
T
Qx
其中：Q = (cor(r
i
r
j
))
n×n
= (σ
ij
)
n×n
。
于是，得到的优化模型为
min
x
x
T
Qx
max
x
x
T
r
s.t.
x
T
e = 1
x ⩾ 0
i = 1, 2, . . . , n
1
http://www.ma-xy.com
1.1 问题的引入与分析 第一章 二次规划
上面的模型有 2 个目标，而且这 2 个目标相互冲突：不能同时达到最优。这是一个多目标规
划问题，具体处理方法在多目标章节介绍。下面，我们对其进行一定的处理。
(1) 要求收益在不小于一定值的条件下风险最小，则有
min
x
x
T
Qx
s.t.
x
T
e = 1
0 ⩽ x ⩽ 1
x
T
r > b
其中：x ∈ R
n
，Q ∈ R
n×n
，e ∈ R
n
，b ∈ R，r ∈ R
n
，b 为最低收益常数。
(2) 也可以将多目标合并为单目标，设目标权重为 k，则有
min
x
x
T
Qx − kx
T
r
s.t.
x
T
e = 1
0 ⩽ x
i
⩽ 1
i = 1, 2, . . . , n
用 MATLAB 解组合投资的二次规划问题。MATLAB 采用以下三种算法来求解二次规划：
1. 内点凸包算法：具有任何约束组合的凸包问题；
2. 信赖域反射算法：求解边界约束或线性等式约束问题；
3. 动态序列算法：求解任何约束组合的问题。
设组合投资的二次规划模型如下
min
x∈R
n
f(x) = x
T
Qx
s.t.
n
i=1
x
i
r
i
⩾ r
n
i=1
x
i
= 1
0 ⩽ x
i
⩽ 1
i = 1, 2, . . . , n
并且假设现在有 225 支股票，即 n = 225。其求解程序如下
1 %% 组 合 投 资 二 次 规 划 问 题
2 %加 载 数 据
3 load ( ’ port5 . mat ’ , ’ C orre l a t ion ’ , ’ stdDev_return ’ , ’ mean_return ’ )
4 %计 算 相 关 向 量 矩 阵Q
5 Covariance = Corr e l a tion . * ( stdDev_return * stdDev_return ’ ) ;
6 nAssets = numel ( mean_return ) ;
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二次规划 1.1 问题的引入与分析
7 r = 0 . 0 0 2 ;%获 利 下 限
8 Aeq = ones ( 1 , nAssets ) ;
9 beq = 1 ;
10 Aineq = −mean_return ’ ;
11 bineq = −r ;
12 lb = z e r os ( nAssets , 1 ) ;
13 ub = ones ( nAssets , 1 ) ;
14 c = ze r o s ( nAssets , 1 ) ;
15 opt io ns = optimoptions ( ’ quadprog ’ , ’ Algorithm ’ , ’ i n t e r i o r −point−convex ’ ) ;
16 opt io ns = optimoptions ( options , ’ Display ’ , ’ i t e r ’ , ’TolFun ’ ,1 e−10) ;
17 [ x1 , f v a l 1 ] = quadprog ( Covariance , c , Aineq , bineq , Aeq , beq , lb , ub , [ ] , op tio ns ) ;
18 plotPortfDemoStandardModel ( x1 )
19 % 分 组 投 资 225−Asset Problem with Group Co ns traints
20 % 新 的 投 资 组 合 要 求 ：
21 % sum_1_75 xi >=0.3;sum_76_150 xi >=0.3;sum_151_225 xi >=0.3
22 Groups = blkdiag ( ones ( 1 , nAssets /3) , ones (1 , nAssets /3) , ones (1 , nAssets /3) ) ;
23 Aineq = [ Aineq ; −Groups ] ; % co nve rt to <= c o nst r a i n t
24 bineq = [ bineq ; −0.3* ones (3 ,1) ] ; % by changing s i g n s
25 [ x2 , f v a l 2 ] = quadprog ( Covariance , c , Aineq , bineq , Aeq , beq , lb , ub , [ ] , op tio ns ) ;
26 % Plot r e s u l t s , superimposed to r e s u l t s from previo us problem .
27 plotPortfDemoGroupModel ( x1 , x2 ) ;
28 %% 1000 支 股 票
29 % 为 了 展 示 quadprog 的 内 点 算 法 能 解 决 更 大 的 问 题 , 我 们 使 用 一 个 随 机 生 成 1000 的 数 据 集 。
30 % 我 们 生 成 一 个 随 机 相 关 矩 阵 ( 对 称 半 正 定 , 对 角 线 ) 。
31 % Reset random stream f o r r e p r o d u c i b i l i t y .
32 rng ( 0 , ’ t w i s t e r ’ ) ;
33 nAssets = 1000;
34 % Generate means o f r e turn s between −0.1 and 0 . 4 .
35 a = −0.1;
36 b = 0 . 4 ;
37 mean_return = a + (b−a) . * rand ( nAssets , 1 ) ;
38 % Generate standard d e v i a t i o n s of r e t urns between 0 .0 8 and 0 . 6 .
39 a = 0 . 0 8 ;
40 b = 0 . 6 ;
41 stdDev_return = a + (b−a ) . * rand ( nAssets , 1 ) ;
42 % Corre l a t ion matrix , generated using C orre l a t ion = ga l l e r y ( ’ randcorr ’ , nAssets ) .
43 % ( Generating a c o r r e l a t i o n matrix of t h i s s i z e takes a while , so we load
44 % a pre−generated one i n s tea d . )
45 load ( ’ correlationMatrixDemo . mat ’ , ’ Cor r e lati o n ’ ) ;
46 % C alc ul ate co varia nce matrix from c o r r e l a t i o n matrix .
47 Covariance = C orre l a tion . * ( stdDev_return * stdDev_return ’ ) ;
48 % Define and Solve Randomly Generated 1000−Asset Problem
49 % We now d e f i n e the standard QP problem ( no group co n s t r a i n t s here ) and s o l v e .
50 r = 0 . 1 5 ;
51 Aeq = ones ( 1 , nAssets ) ;
52 beq = 1 ;
53 Aineq = −mean_return ’ ;
54 bineq =
−
r ;
55 lb = z e r os ( nAssets , 1 ) ;
56 ub = ones ( nAssets , 1 ) ;
57 c = ze r o s ( nAssets , 1 ) ;
58 x3 = quadprog ( Covariance , c , Aineq , bineq , Aeq , beq , lb , ub , [ ] , o pt ion s ) ;
59
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.2 模型的规范化及基本理论 第一章 二次规划
1.2 模型的规范化及基本理论
1.2.1 规范化
根据上面的例子，我们写出二次规划的一般形式
min
x∈R
n
f(x) =
1
2
x
T
Qx + c
T
x
s.t.
A
1
x ⩽ b
1
A
2
x = b
2
或者写为
min
x
f(x) =
1
2
i
j
x
i
x
j
Q
ij
+
n
i=1
c
i
x
i
s.t.
a
T
i
x ⩽ b
i
i ∈ I
a
T
j
x = b
j
j ∈ E
其中：Q = Q
T
∈ R
n×n
，x ∈ R
n
，I = {1, 2, . . . , m}，E = {1, 2, . . . , l}，|I| = m，|E| = l，
A
1
∈ R
|I|×n
，A
2
∈ R
|E|×n
。由凸函数判定定理，我们有：如果目标函数 f 的 Hesse 矩阵 Q 是正
定的，则该二次规划称为凸二次规划问题。
1.2.2 最优化条件
必要条件 设 x
∗
为二次规划的一个局部极小点，则存在乘子 λ
∗
∈ R
|I|
+
，µ
∗
∈ R
|E|
，有
Qx
∗
+ c = A
T
1
λ
∗
+ A
T
2
µ
∗
(A
1
x
∗
− b
1
)
T
λ
∗
= 0
λ
∗
⩾ 0
且对一切满足
d
T
a
i
= 0 i ∈ E ∪ I(x
∗
)
的 d (d ∈ R
n
)，有
d
T
Qd ⩾ 0
其中：E = {1, 2, . . . , l}，I(x
∗
) = {i|a
T
i
x
∗
= b
i
, i ∈ I}。
充分条件 设 x
∗
为二次规划的一个 KKT 点，λ
∗
µ
∗
为 Lagrange 乘子。如果对于一切满足
d
T
a
i
= 0 i ∈ E
d
T
a
i
⩾ 0 i ∈ I(x
∗
)
d
T
a
i
= 0 i ∈ I(x
∗
), λ
∗
i
> 0, µ
∗
i
> 0
(1.1)
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二次规划 1.2 模型的规范化及基本理论
的非零向量 d，都有
d
T
Qd > 0
则 x
∗
为二次规划的拒不严格极小点。
充分必要条件 设 x
∗
为二次规划的可行点，则 x
∗
是局部极小点，当且仅当存在 λ
∗
µ
∗
，使得
Qx
∗
+ c = A
T
1
λ
∗
+ A
T
2
µ
∗
(A
1
x
∗
− b
1
)
T
λ
∗
= 0
λ
∗
∈ R
|I|
+
, µ
∗
∈ R
|E|
成立，且对一切满足 (1.1) 式的向量 d 有
d
T
Qd ⩾ 0
注：对凸二次规划而言，x
∗
为全局极小点，当且仅当 x
∗
为局部极小点，x
∗
为 KKT 点。
1.2.3 对偶问题
二次规划的对偶理论最先由 J.B.Dennis 和 W.S.Dorn 等人于 1959 年和 1960 年给出。令
A =
A
1
A
2
b =
b
1
b
2
w =
λ
µ
则二次规划的拉格朗日函数为
L(x, λ, µ) =
1
2
x
T
Qx + c
T
x − λ
T
(A
1
x − b
1
) − µ
T
(A
2
x − b
2
)
=
1
2
x
T
Qx + x
T
(c − A
T
w) + b
T
w
若 Q
T
= Q ≻ 0，则 Lagrange 对偶函数 θ(λ, µ) = inf
x∈R
n
L(x, λ, µ) 存在，并且对应的最小点
x
∗
满足
∇
x
L = Qx + c − A
T
w = 0
于是
x = −Q
−1
(c − A
T
w)
将其代入 Lagrange 函数，有
max
λ⩾0
θ(λ, µ) = −
1
2
(c − A
T
w)
T
Q
−1
(c − A
T
w) + b
T
w
即
max
λ⩾0
θ(λ, µ) = −
1
2
w
T
(AQ
−1
A
T
)w + w
T
(b + AQ
−1
c) −
1
2
c
T
Q
−1
c (1.2)
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二次规划
其中：w = (λ, µ)
T
。
如果令 y = c − A
T
w，则有
max
y,w
θ(λ, µ) = −
1
2
y
T
Q
−1
y + b
T
w (1.3)
s.t.
A
T
w + y = c
w = (λ, µ)
T
λ ⩾ 0
上面的式 (1.2)(1.3) 为二次规划对偶的两种形式。值得一提的是，上面要求二次规划的 Q 为正
定，即原二次规划为凸。为了得到适用性更广泛的对偶形式，令 y = Qz，则有
max
y,w
θ(λ, µ) = −
1
2
z
T
Qz + b
T
w
s.t.
A
T
w + Qz = c
w = (λ, µ)
T
λ ⩾ 0
此时，矩阵 Q 可以是半正定的。
对于原问题和对偶问题，有
f(x) − θ(λ, µ ) = c
T
x − b
T
w +
1
2
x
T
Qx +
1
2
y
T
Q
−1
y
= λ
T
(A
1
x − b
1
) +
1
2
(x
T
Qx + y
T
Q
−1
y + 2x
T
y) ⩾ 0
当且仅当 Aλ
T
(A
1
x − b
1
) = 0, x = −Q
−1
y 时，f(x) − θ(λ, µ) = 0。对于严格凸二次规划，记可行
域为 S，则 x
∗
∈ S 为最优解，当且仅当 ∃λ
∗
⩾ 0, µ
∗
使得 (x
∗
, λ
∗
, µ
∗
) 为 Lagrange 函数 L(x, λ, µ)
的鞍点，即对 ∀x ∈ S, ∀λ ⩾ 0，有
L(x
∗
, λ, µ) ⩽ L(x
∗
, λ
∗
, µ
∗
) ⩽ L(x, λ
∗
, µ
∗
)
1.3 最优化算法
1.3.1 Lagrange 方法
考虑只含等式约束的二次规划问题
min
x
1
2
x
T
Qx + c
T
x
s.t. Ax = b
其中：c, x ∈ R
n
，Q ∈ R
n×n
为对称矩阵，A ∈ R
m×n
，rank(A) = m，b ∈ R
m
。首先，写出
Lagrange 函数
L(x, λ) =
1
2
x
T
Qx + c
T
x − λ
T
(Ax − b)
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二次规划 1.3 最优化算法
令
∇
x
L(x, λ) = 0
∇
λ
L(x, λ) = 0
得到方程组
Qx + c − A
T
λ = 0
− Ax + b = 0
将上述方程写为矩阵形式
Q −A
T
−A 0
x
λ
=
−c
−b
(1.4)
系数矩阵
Q −A
T
−A 0
称为 Lagrange 矩阵。设上述 Lagrange 矩阵可逆，表示为
Q −A
T
−A 0
−1
=
H −R
T
−R S
= I
m+n
由此可以推得
−QH + A
T
R = I
n
−QR
T
− A
T
S = O
m×n
−AH = O
n×m
AR
T
= I
m
假设 Q
−1
存在，则有
H = Q
−1
− Q
−1
A
T
(Q
−1
A
T
)AQ
−1
R = (AQ
−1
A
T
)
−1
AQ
−1
S = (AQ
−1
A
T
)
−1
在方程组 (1.4) 的两边乘上 Lagrange 矩阵的逆，得到问题的解
x
∗
= −Hc + R
T
b
λ
∗
= Rc − Sb
1.3.2 内点算法
Ye.Tse 于 1989 年给出二次规划的内点算法。考虑凸二次规划问题
min
x
f(x) =
1
2
x
T
Qx + c
T
x
s.t.
A
T
x = b
x ⩾ 0
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二次规划
设已有 x
k
是一内点，即
A
T
x
k
= b
x
k
> 0
定义矩阵
D
k
=
(x
k
)
1
· · · 0
.
.
.
.
.
.
.
.
.
0 · · · (x
k
)
n
= diag(x
k
)
作变量代换 ˆx := T
k
x，如下
ˆx
i
=
(n + 1)(D
−1
k
x)
i
e
T
D
−1
k
x + 1
i = 1, 2, . . . , n
ˆx
n+1
= (n + 1)/[e
T
D
−1
k
x + 1]
则将原问题转化为
min
ˆx∈R
n+1
ˆx
n+1
Q(T
−1
k
ˆx) (1.5)
s.t.
A
T
D
k
ˆx[n] − ˆx
n+1
b = 0
e
T
ˆx = n + 1
ˆx[n] ⩾ 0
ˆx
n+1
> 0
(1.6)
其中：e = (1, 1, . . . , 1)
T
，ˆx[n] = (ˆx
1
, ˆx
1
, . . . , ˆx
n
)
T
。并且由上面的变量代换，我们有
x = T
−1
k
ˆx = D
k
ˆx[n]/ˆx
n+1
所以
min
ˆ
C
k
ˆx[n] +
1
2
ˆx[n]
T
ˆ
Q
k
ˆx[n]/ˆx
n+1
s.t.
ˆ
A
T
k
ˆx =
ˆ
b
ˆx[n] ⩾ 0
ˆx
n+1
> 0
其中：
ˆ
Q
k
= D
k
QD
k
,
ˆ
C
k
= D
k
c
ˆ
A
k
=
D
T
k
A
k
e
−b
T
e
,
ˆ
b =
0
.
.
.
0
n + 1
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二次规划 1.4 MATLAB 应用实例
对于所给的已知迭代点 x
k
，有 ˆx = e。所以我们有理由考虑在 ˆx = e 附近求解上述问题。于
是，把 ˆx[n] ⩾ 0, ˆx
n
+1
> 0 加强为 ∥ˆx − e∥
2
⩽ β < 1，β 为与 k 无关的正常数。利用 KKT 条件，
我们知道，求解强化后的问题，等价于求解
ˆ
C
k
+ ˆx
−1
n+1
ˆ
Q
k
ˆx[n] =
ˆ
A
k
[n]λ + µ(ˆx[n] − e) (1.7)
−
1
2
1
ˆx
2
n+1
ˆx[n]
T
ˆ
Q
k
ˆx[n] =
ˆa
(k)
n+1
T
λ + µ(ˆx
n+1
− 1) = 0 (1.8)
ˆ
A
T
k
ˆx =
ˆ
b (1.9)
∥ˆx − e∥
2
⩽ β (1.10)
µ [∥ˆx − e∥
2
− β] = 0, µ ⩽ 0 (1.11)
其中：
ˆ
A
k
[n] 是
ˆ
A
k
的前 n 行组成的矩阵，ˆa
(k)
n+1
是
ˆ
A
k
的第 n + 1 行，将式 (1.7)-(1.11) 写成矩
阵形式
P
k
ˆx[n]
ˆ
λ
= ˆx
n+1
ˆ
b +
¯
b (1.12)
其中：
P
k
=
ˆ
Q
k
+ ˆµI −
ˆ
A
k
[n]
ˆ
A[n] 0
ˆ
b =
ˆ
C
k
b
−1
¯
b =
ˆµ
e
0
n + 1
ˆ
λ = ˆx
n+1
λ, ˆµ = −ˆx
n+1
µ
于是，对任何给定的 ˆµ ⩾ 0，我们可由 (1.12) 求得
ˆ
λ 和 ˆx[n]。然后，将求得的
ˆ
λˆx[n] 代入 (1.8)
即可得到 ˆx
n+1
。于是，对任何 ˆµ ⩾ 0，都可求得 ˆx(ˆµ)。定义函数
h(ˆµ) = ∥ˆx(ˆµ) − e∥
2
− β
如果 h(0) ⩽ 0，则 ˆx(0) 为上面函数的解。之后，x = D
k
ˆx(0)[n]/ˆx(0)
n+1
是原问题的解。如果
h(0) > 0，由于 lim
µ→∞
h(µ) = −β < 0，可用方法求解 ˆµ
k
使得 h(ˆµ
k
) = 0，从而可以得到强化后问
题的解 ˆx(µ
k
)，将其变换回去即可得到 x
k+1
。
x
k+1
= T
−1
k
ˆx(ˆµ
k
) =
D
k
ˆx(ˆµ
k
)[n]
ˆx(ˆµ
k
)
n+1
其中：ˆx(ˆµ
k
)[n] = (ˆx(ˆµ
k
)
1
, . . . , ˆx(ˆµ
k
)
n
)
T
。
1.4 MATLAB 应用实例
MATLAB 中用 quadprog 命令求解二次规划问题。其调用格式为
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.5 组合投资问题的混合整数规划 第一章 二次规划
[x,fval,exitag,output,lambda]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
其中：H 为 Hesse 矩阵；f 为 c，c
T
x；lambda：目标函数在极点 x 处的 Lagrange 乘子。
用 quadprog 求解如下二次规划问题
min
x
f = 3x
2
1
+ 2x
2
2
+ 3x
1
− 4x
2
s.t.
2x
1
+ x
2
⩽ 4
− 2x
1
+ 2x
2
⩽ 4
x
1
⩾ 0, x
2
⩾ 0
求解程序如下
1 H = [6 , −4; −4 ,4];
2 f = [ 3 , −4] ;
3 A = [ 2 , 1 ; − 1 , 2 ] ;
4 b = [ 4 ; 4 ] ;
5 lb = [ 0 , 0 ] ;
6 ub = [ ] ;
7 [ x , f v a l ] = quadprog (H, f ,A, b , [ ] , [ ] , lb , ub )
8
1.5 组合投资问题的混合整数规划
前面的引例 (1.1) 中，我们介绍了最基本的组合投资模型。下面，我们将进一步引申到混合
二次整数规划。对于普通二次规划
min
x
λx
T
Qx − r
T
x
s.t.
i
x
i
= 1
0 ⩽ x
i
⩽ 1
i = 1, 2, . . . , n
增设变量 v
i
，使
v
i
=
0 x
i
= 0
1 x
i
> 0
并且要求
m ⩽
i
v
i
⩽ M
其中：m, M 为常量。
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二次规划 1.5 组合投资问题的混合整数规划
然后，我们要求 x
i
的取值在 f
min
i 和 f
max
i 之间。重写组合投资问题为
min
x
λx
T
Qx − r
T
x
s.t.
i
x
i
= 1
v
i
= 0/1
m ⩽
v
i
⩽ M
v
i
f
min
i ⩽ x
i
⩽ v
i
f
max
i
上述问题是以 0-1 变量 v 的二次规划问题。对于混合规划问题，MATLAB 目前为止只能求
解混合线性整数规划。所以，我们要想办法将二次规划转化为线性规划。设置一个 z 变量，让 z
来逼近 x
T
Qx。
min
x,z
λz − r
T
x
s.t.
x
T
Qx − z ⩽ 0
z ⩾ 0
x
T
e = 1
v = 0/1
m ⩽ v
T
e ⩽ M
v
i
f
min
i ⩽ x
i
⩽ v
i
f
max
i
虽然现在已经将目标函数变为线性，但其约束中仍有二次函数。下面，我们来处理 x
T
Qx−z。
将 x
T
Qx − z 在 x
0
处一阶泰勒展开，有
x
T
Qx − z = x
T
0
Qx
0
+ 2x
T
0
Qδ − z + O(||δ||
2
)
用 x − x
0
来代替 δ，有
x
T
Qx − z = −x
T
0
Qx
0
+ 2x
T
0
Qx − z + O(|x − x
0
|
2
)
现在的 x
T
Qx − z 就变为关于 x 的线性函数。对于 x
k
，有
−x
T
k
Qx
k
+ 2x
T
k
Qx − z ⩽ 0
将上式写成 Ax ⩽ b 的标准形式，有
A = 2x
T
k
Q
b = x
T
k
Qx
k
http://www.ma-xy.com 11 http://www.ma-xy.com
http://www.ma-xy.com
1.5 组合投资问题的混合整数规划 第一章 二次规划
即，在求 x
k+1
时，要利用已知的 x
k
。于是，原混合整数二次规划变为
min
x,z
λz − r
T
x
s.t.
Ax − z ⩽ b
z ⩾ 0
x
T
e = 1
v = 0/1
m ⩽ v
T
e ⩽ M
v
i
· lb ⩽ x
i
⩽ ub · v
i
其中：A, b 如上定义。MATLAB 求解程序如下
1 %% 混 合 整 数 规 划 求 解 组 合 投 资 问 题
2 %加 载 数 据
3 load port5
4 r = mean_return ;
5 Q = C o rrel a t i on . * ( stdDev_return * stdDev_return ’ ) ;
6 N = length ( r ) ;
7 xvars = 1 :N;
8 vvars = N+1:2*N;
9 zvar = 2*N+1;
10 lb = z e r os (2*N+1,1) ;
11 ub = ones (2*N+1,1) ;
12 ub( zvar ) = In f ;
13 M = 1 50 ;
14 m = 1 00;
15 A = z eros (1 ,2 *N+1) ; % Allo c a te A matrix
16 A( vvars ) = 1 ; % A*x re p r e s e n t s the sum o f the v ( i )
17 A = [A;−A ] ;
18 b = z e r o s ( 2 , 1 ) ; % All o cate b v ec t or
19 b (1) = M;
20 b (2) = −m;
21 fmin = 0 . 0 0 1 ;
22 fmax = 0 . 0 5 ;
23 Atemp = eye (N) ;
24 Amax = horzcat (Atemp,−Atemp*fmax , zeros (N, 1 ) ) ;
25 A = [A;Amax] ;
26 b = [ b ; z e r o s (N, 1 ) ] ;
27 Amin = h orzcat(−Atemp , Atemp*fmin , z e r o s (N, 1 ) ) ;
28 A = [A;Amin ] ;
29 b = [ b ; z e r o s (N, 1 ) ] ;
30 Aeq = z eros (1 ,2 *N+1) ; % Allo c ate Aeq matrix
31 Aeq( xvars ) = 1 ;
32 beq = 1 ;
33 lambda = 100 ;
34 f = [−r ; zeros (N, 1 ) ; lambda ] ;
35 opt io ns = optimoptions ( @int linprog , ’ Display ’ , ’ o f f ’ ) ; % Suppress i t e r a t i v e d i s p l a y
36 [ xLinInt , f v a l , e x itFl a gIn t , output ] = i n t l i n p r o g ( f , vvars ,A, b , Aeq , beq , lb , ub , opt ions ) ;
37 t h e d i f f = 1e−4;
http://www.ma-xy.com 12 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二次规划 1.5 组合投资问题的混合整数规划
38 i t e r = 1 ; % i t e r a t i o n counter
39 as s e t s = xLinInt ( xvars ) ; % the x va r i a b l e s
40 t rue quad rat i c = a s s e t s ’ *Q* a s s e t s ;
41 z sla c k = xLinInt ( zvar ) ; % s l a c k va r i a b le value
42 while abs ( ( z s l a c k − true qua d rat i c ) / t rue q uad r ati c ) > t h e d i f f % r e l a t i v e e r r o r
43 newArow = ho rzcat (2* a s s e t s ’ *Q, zeros ( 1 ,N) ,−1) ; % L i nea r ized c on s t r a i n t
44 A = [A; newArow ] ;
45 b = [ b ; tr uequ adra tic ] ;
46 % Solve the problem with the new c o n s t r a i n t s
47 [ xLinInt , f v a l , e x itFl a gIn t , output ] = i n t l i n p r o g ( f , vvars ,A, b , Aeq , beq , lb , ub , opt ions ) ;
48 as s e t s = ( a s s e t s+xLinInt ( xvars ) ) / 2 ; % Midway from the previ ous to the curr ent
49 % a s s e t s = xLinInt ( xvars ) ; % Use the pr ev iou s l i n e or t h i s one
50 tr u equ adra tic = a s s e t s ’ *Q* a s s e t s ;
51 z s l a c k = xLinInt ( zvar ) ;
52 h i s t o ry = [ hi s t o r y ; tr ue quadrat ic , zsl a c k ] ;
53 i t e r = i t e r + 1 ;
54 end
55 p l o t ( h i s t o r y )
56 legend ( ’ Quadratic ’ , ’ Slack ’ )
57 x la b e l ( ’ I t e r a t i o n number ’ )
58 t i t l e ( ’ Quadratic and l i n e a r approximation ( s l a ck ) ’ )
59 di sp ( output . absolutegap )
60 bar ( xLinInt ( xvars ) )
61 g r i d on
62 x la b e l ( ’ Asset index ’ )
63 y la b e l ( ’ Proportion o f investment ’ )
64 t i t l e ( ’ Optimal ass e t a l l o c a t i o n ’ )
65 sum( xLinInt ( vvars ) )
66 f p r i n t f ( ’The expected retur n i s %g , and the r i s k−ad justed ret ur n i s %g . \ n ’ , . . .
67 r ’ * xLinInt ( xvars ) ,− f v a l )
68
http://www.ma-xy.com 13 http://www.ma-xy.com
