如果对于自变量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