二阶锥规划的Lagrange对偶及2维原始对偶单纯形法

目前对二阶锥规划算法的研究是数学规划领域的研究热点之一,在这方面的研究成果初具规模.文中着重研究两方面问题:一是详细推导二阶锥规划的Lagrange对偶问题;二是将2维二阶锥规划(即二阶锥约束都是2维的,但自变量的总维数是2r维的,r表示二阶锥约束的个数)转化成相应的标准形线性规划,给出其原始对偶单纯形法,并举例说明算法的应用,最后进行部分灵敏度分析.这一工作基本完善了2维二阶锥规划的单纯形类方法,即至此,2维二阶锥规划的原始单纯形法、对偶单纯形法和原始对偶单纯形法的理论已较完善.其他拓广的单纯形类方法可在将2维二阶锥规划转化成相应的标准形线性规划之后对应线性规划的拓广单纯形类方法直接得到.

Lagrange dual problem of second-order cone programming and its 2-dimentional primal-dual simplex method

At present, the research on SOCP has been one of the hot spots in the field of math pro-gram. There are many good results. In this paper, we study primarily on two aspects of problems:the first one is to deduce the Lagrange dual problem of SOCP in detail;the other one is to transform2-dimentional SOCP,in which, second-order cone restrictions are all 2-dimentional, into the stand-ard linear programming form and obtain the primal-dual simplex method, then take example to showthe application of the method. Finally, sensitivity analysis is made for the 2-dimentional SOCP. The work is a complement to the class of simplex methods for 2-dimentional SOCP. That is, there are primal simplex method, dual simplex method and primal-dual simplex method for 2-dimentional SOCP now. The others varying simplex methods for it will be obtained directly after 2-dimentional SOCP is transformed into the standard linear programming form.