凸规划问题与二阶锥规划 - 好文

如果对于自变量x1、x2以及参数λ，有

则认为f是凸函数，进一步，如果

则认为f是严格凸函数。

R向量空间中，如果集合 S 中任两点的连线上的点都在 S 内，则称集合 S 为凸集。

在凸集范围内，求凸函数在约束条件下的最小值成为凸规划,即：

s.t



如果C∈R^n向量空间，对于任意x∈C，有ax∈C，则称C为锥集；进一步如果对于任意x∈C、y∈C，有ax + by ∈C
，则称C为凸锥集；进一步的，如果向量 x∈R^n-1 以及数值 t∈R，总满足关系式 ||x|| ≤
t，则称所有（x，t）组成的集合为标准集；如果标准集成立条件中的x范数取为二阶，则称（x,t）为二阶锥集，但是在二阶锥的定义中限定了t≥0。

在二阶锥范范围内求解约束条件下目标凸函数的最小值，就是二阶锥规划。

关于凸优化问题的求解可以借助matlab工具包sedumi进行计算：

sedumi帮助文档中的第一个例子

首先看文档中对公式形式，以及变量的约定，对于原始标准形式：

s.t

或者上者的等价形式：

s.t

有了以上约定，假设我们现在面临这样一个线性规划问题：

min（）

s.t

,

按照文档中的变量约定（约束条件1是≥号，需要在括号左边减去一个或
多个非负松弛变量，使≥转换成标准形式的=；同理约束条件2中，需要添加非负松弛变量，使其变成标准形式中的等号）
c = [1;-1;0;0]; A = [10,-7,-1,0;1,1/2,0,1]; b = [5;3]; sedumi(A,b,c)
计算结果如下
SeDuMi 1.3 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003. Alg = 2:
xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500 eqs m
= 2, order n = 5, dim = 5, blocks = 1 nnz(A) = 6 + 0, nnz(ADA) = 4, nnz(L) = 3
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec 0 : 6.02E+00 0.000 1 :
-1.20E+00 1.84E+00 0.000 0.3055 0.9000 0.9000 1.86 1 1 2.1E+00 2 : -6.94E-02
5.15E-01 0.000 0.2803 0.9000 0.9000 2.14 1 1 8.6E-01 3 : -1.21E-01 2.72E-02
0.000 0.0528 0.9900 0.9900 1.16 1 1 4.2E-02 4 : -1.25E-01 8.69E-06 0.000 0.0003
0.9999 0.9999 1.02 1 1 iter seconds digits c*x b*y 4 0.3 Inf -1.2500000000e-01
-1.2500000000e-01 |Ax-b| = 1.3e-15, [Ay-c]_+ = 0.0E+00, |x|= 2.9e+00, |y|=
2.8e-01 Detailed timing (sec) Pre IPM Post 9.600E-01 5.660E-01 5.899E-02
Max-norms: ||b||=5, ||c|| = 1, Cholesky |add|=0, |skip| = 0, ||L.L|| = 1. ans =
(1,1) 1.958333333333333 (2,1) 2.083333333333333
通过以上结果我们可以发现，c*x的最大值或者b*y的最小值是-1.2500000000e-01，以及对应的x1 = 1.958333333333333
，x2 =2.083333333333333

并且结果中给出了误差|Ax-b| =   1.3e-15

热门工具换一换