SeDuMi详细教程

1、SeDuMi User Guide线性规划(LP 问题：Lin ear Programmi ng )将需要解决的问题表述成原始问题:minimi2e rTJrsuch that Ax = bz, 0 fnr t - 113t. K K ,或者对偶问题:mxiniizesuch that G - 0 for i = 1 f 2,. 1 n例子:minimize T| -such that 10 xi 7x2 2 5xi + rj/2 0, r； 0.为了解决该LP问题，我们必须添加一些松弛变量，比如x3和x4,我们即可在MATLAB中输入b和c向量以及A矩阵: c 二 ti； -1； o； o；

2、 A = 10. -了了. -1, 0, lt 1/21 0, 1; b - B; 3;现在我们就可以通过sedumi指令来求解这个问题sedumi(A,b,c)eqs m = 2, order n = 5, dim = 5, blocks = 1nn z(A) = 6 + 0, nn z(ADA) = 4, nn z(L) = 3feas1.7E-016, |x|= 2.9e+000, |y|=Post4.680E-002it :b*y gap delta rate t/tP* t/tD*cg cgprec0 :6.02E+000 0.0001 : -1.20E+000 1.84E+000

3、0.000 0.3055 0.9000 0.9000 1.86 1 1 2.1E+0002 : -6.94E-002 5.15E-001 0.000 0.2803 0.9000 0.90002.14118.6E-0013 : -1.21E-001 2.72E-002 0.000 0.0528 0.9900 0.99001.16114.2E-0024 : -1.25E-001 8.69E-006 0.000 0.0003 0.9999 0.99991.0211itersecondsdigits c*x b*y4 0.3 Inf-1.2500000000e-001-1.2500000000e-00

4、1|Ax-b| =0.0e+000, Ay-c_+ =2.8e-001Detailed timing (sec)Pre IPM1.404E-001 2.964E-001Max-norms: |b|=5, |c| = 1,Cholesky |add|=0, |skip| = 0, |L.L| = 1.ans =(1,1)1.9583(2,1)2.0833表明最优值为 -1.2500000000e-001=-0.125 ，对应 c*x 以下的值，同时返回最 优解：x1=1.9583,x2=2.0833, 发现 x 确实有解，因为其每一个元素都是非负的，而 且Ax=b,可以用命令min(x)和nor

5、m(Ax-b)来检验。当然，也会出现一些舍入误 差，如下：norm(A*x-b)ans =1.7764e-015norm(A*(24*x)-24*b)ans = 0二次型和半定限制( Quadratic and semi definite constraint)在 sedumi 中,有可能强制加入二次型或者半定限制条件,即通过限制变量进 入一个二次型和核或者半正定矩阵的核,这样一个限制条件代替了线性规划中的非 负性条件，需要x属于K, 一个对称核中，它是一个非负象限，二次型核和半正定 矩阵核的笛卡儿积。最优化问题的标准形式为：minimizesuch that At-b（ （5） ）对偶形式为

6、：maximizeTFsuch （hat c A y XI.二次型核二次型核由以下形式来确定：QconefUhXiJe J? X 胪“讪 归讪,考虑以下问题：min * Vi +鮒血I L P曲 启Y1 *如卩，其中P为给定矩阵，q为给定向量，以上是鲁棒最小均方问题。其中决策变 量为标量y1和y2，还有向量y3.这个问题有两个二次型限制：如、q - Pgm） ） E Qcone.（略 ）电 0门就给定P和q，以下MATLA函数（rls.m ）将该问题表述成标准对偶问题。 阵被表述为转置方向，即表述为 At。Rls.m% At,b,c,KI = rls（P,q）% Creates dual st

7、a ndard form for robust least squares problem Pu=q.function At ,b,c,K= rls(P,q)m, n = size(P) ;% -minimize y-1 + y-2 -b = -sparse(1; 1; zeros(n,1);% - (y_1, q - p y_3) in Qcone -At = sparse (-1, zeros(1,1+n); . zeros(m, 2), P);c = 0;q ;K.q=1+m;% - (y_2, (1, y_3) in Qcone -At = At; 0, -1, zeros(1,n);

8、 .zeros(1,2+n); . zeros(n,2),-eye(n);c = sparse(c;0;1;zeros(n,1);K.q= K.q, 2+n; 我们可以注意到以上的方程中运用的是系数数据存储形式，为的是节省内存。此外，还定义了一个结构体 K,其中K.q列出了二次型核的维数。K结构体将 被运用于告知 SeDuM：i c-ATy 的元素并不被限制为非负当他们都被用于线性规划it : b*y cg cgprec中。反而言之，第一个行 K.q(1) 被限制在一个二次型核中，最后一行 K.q(2) 被限 制在另外一个二次型核中，这就是我们在之前建立对称核的方法，而且建立了两个 二次型限制

9、。作为数值仿真的例子，我们来来解决一个鲁棒最小平方值的问题，其依靠 P 中的列 P = 3 1 4;0 1 1;-2 5 3; 1 4 5; q = 0; 2;1;3; At,b,c,K = rls(P,q); x,y,info = sedumi(At,b,c,K);运行后出现的结果是SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500eqs m = 5, order n =

10、 5, dim = 11, blocks = 3nnz(A) = 16 + 0, nnz(ADA) = 23, nnz(L) = 14gap delta rate t/tP* t/tD* feas4.00E+000 0.0001: -3.10E+000 3.01E-001 0.000 0.0751 0.9900 0.9900 1.55 1 1 3.4E-0012 : -3.33E+000 6.02E-003 0.000 0.0200 0.99000.9900 1.03 1 1 6.2E-0033 : -3.33E+000 1.31E-005 0.000 0.0022 0.99900.9990

11、1.00 1 1 1.3E-0054 : -3.33E+000 1.26E-006 0.367 0.0958 0.99000.9900 1.00 1 1 1.3E-0065 : -3.33E+000 3.81E-008 0.000 0.0303 0.99000.9900 1.00 1 1 3.8E-0086 : -3.33E+000 2.24E-009 0.425 0.0587 0.99020.9900 1.00 1 1 2.3E-009iter seconds digits c*x b*y6 0.0 9.4 -3.3329085951e+000 -3.3329085963e+000|Ax-b

12、| =9.5e-010, Ay-c_+ =2.1E-009, |x|= 2.0e+000, |y|=2.5e+000Detailed timing (sec)Pre IPM Post3.120E-002 3.120E-002 0.000E+000Max-norms: |b|=1, |c| = 3,Cholesky |add|=0, |skip| = 0, |L.L| = 1.在以上这些SeDuMi的语句中，我们发现了一个新的输入量 viz.K，这个量使 得SeDuMi能够解决一个（5）和（6）形式的最优化问题，其中对称核 K被描述为 结构体K。没有K的话，SeDuMi只能解决（1）和（2）的问

13、题。我们可以通过验证（ 7）中的不等式来确定结果 y 是否能够满足条件（ 9）。 然而，SeDuM提供了一种更简单的方法eigK，这个函数返回相对应于对称核的矩 阵的特征值。一个对称形核包括哪些仅有非负特征值的向量，其中参见 Faraut and Koranyi9 。如下，我们能因此检验可行性和最优性：eigK（x,K）,eigK（c-At*y,K）ans =0.0000 -0.00001.41423.23070.0000 -0.00001.41421.4827x*（c-At*y）ans =3.4744e-009对于对称核K来说，总是有xTz=0,对所有属于K的z和x成立，因此，x 提供里一种

14、在线性规划中对y最优化的认证。Farkas的对偶方案的分解也是采用 同样的思想。具体参见15的方法。然而，一个奇怪的现象出现了，x和y几乎是 可解得，然而cTx-bTy大多是负的(|x|和或者|y|然后肯定会是非常大的)， 根据原理，SeDuM将会返回一个无穷大的精确的 digits。这个现象在14和23 中也有解释。我们需要让这个最优化模型有着非负的和二次型的核限制，而这一点是可行 的。比如，我们可以以上例子中的限制y31 ；血：巧+X is psd从几何学上来说，Rcone仅仅是Qcone的转置。Rcone的这种特殊形式对于建 立凸面体二次型方程十分方便。也就是说，将现行等式限制“x1=1

15、”加入到模型中，我们得到限制：通过该模型，我们能用x2作为的紧上界。分数同样也是由Rcone方便作为限制。举例说明，我们可以最小化 1/x1对于x10来解决模型 J. Ji + J； 0.注意到该问题是无解的：1/x1下确界是0，对x1趋近与无穷大来说：clear K;c= 0,1,0；b = sqrt(2); A = 0, 0, 1; K.r = 3;x,y,i nfo=sedumi(A,b,c,K);x(2),x(1)*x (2)ans =6.5278e-005ans =1.0695你可能会发现x2根本没有足够趋近于0,而且x1也不是等于无穷大。然 而，这个原始解是可解的，对偶解几乎是可解

16、的，而且对偶gap几乎是负的。这就解释了一个误差范围困难，而且对这种不规则的问题是很常见的。在Section 5中，我们可以看看到底如何获得一个更精确的解决方案，通过设计一个选项参数，pars.eps上述例子可以解释，K.r来列出Rcone限制的维数，类似于 Qcone限制中K.q 的定义，设定了 K.l，K.q，K.r也就引出了以下形式的对称核。fC -胖x (Qcone x x Qcone) x (Rcone x - * x Reone).举例说明，我们可以添加界 x1X=vec(1,5,-3;5,2,-9;-3,-9,4)X =15-352-9-3-94Vec的逆运算就是mat。因此，如

17、果x是一个n2长度的向量，而mat (x) 就创建了一个nXn的矩阵，然后依次填入x向量的元素，比如：mat(X)ans =15-352-9-3-94以下MATLA函数产生了一个问题(11)的标准的原始形式:% At,b,c,K =specfac(b)% Creates primal standard form for minimal phase spectral factorization.function At,b,c,K =specfac(b)m = length(b) ;% - minimize sum (m-i)*X(i,i) -c = vec(spdiags(m-1:-l:0),0

18、,m,m);% - Let e be all-1, and allocate space for the A-matrix -e = ones(m,1);At = sparse( , ,mA2,m,m*(m+l)/2);% -sum(diag():k)= b(k) -for k= 1:mAt(:,k) = vec(spdiags(e,k-l,m,m);endK.s = m;字段K.s=m告诉SeDuM我们需要一个mXm的矩阵mat (x)，而且满足对称 正定的。我们能解决如下的问题：b = 2; 0.2; -0.3;At, b, c ,K = specfac(b) ;iter seconds

19、digitsc*xb*yfeasx,y,info = sedumi(At,b,c,K);得到的结果为：it : b*y gap delta rate t/tP* t/tD* cg cgprec0 : 1.69E+001 0.0001 : -2.44E-001 3.91E+000 0.000 0.2312 0.90000.9000 1.39 1 1 2.0E+0002 : 1.86E-001 3.22E-001 0.000 0.0824 0.99000.9900 1.31 1 1 4.0E-0013 : 1.23E-001 1.12E-004 0.000 0.0003 0.99990.9999

20、0.99 1 1 2.6E-0044 : 1.23E-001 5.18E-006 0.000 0.0463 0.99000.9900 1.00 1 1 1.2E-0055 : 1.23E-001 2.36E-007 0.000 0.0455 0.99000.9900 1.00 1 1 6.8E-0076 : 1.23E-001 1.90E-008 0.327 0.0806 0.99000.9900 1.00 2 2 5.5E-0087 : 1.23E-001 8.16E-010 0.000 0.0429 0.99060.9900 0.99 2 2 2.2E-0091.4E-010, |x|=

21、2.0e+000, |y|=Post3.120E-0020.2 8.5 1.2273256559e-001 1.2273256524e-001|Ax-b| = 1.1e-010, Ay-c_+ = 7.6e-001Detailed timing (sec)Pre IPM3.120E-002 2.028E-001Max-norms: |b|=2, |c| = 2,Cholesky |add|=0, |skip| = 0, |L.L| = 1.为检验正定性，可以采用 MATLAB的eig或者SeDuMi中的eigK: eig(mat(x),eigK(x,K)ans =0.00000.00000.00000.00002.00002.0000其中 eigK 更加方便，特别是当有多个正定条件限制的时候，或者也有非负和二次型核限制。SeDuM将总是产生对称决策变量，比如 mat (x)就是对称的。女口 果不明确地加入对称性限制，比如 xij -xji=0 。最多，这些限制将会被 SeDuMi 在 A 矩阵中