二阶锥规划两个新的预估-校正算法

被引：2

作者：

曾友芳 ^{[1
,2
]}

白延琴 ^{[1
]}

简金宝 ^{[2
]}

唐春明 ^{[2
]}

机构：

[1] 上海大学数学系

[2] 广西大学数学与信息科学学院

来源：

应用数学和力学 | 2011年 / 32卷 / 04期

关键词：

二阶锥规划; 不可行内点算法; 预估-校正算法; 全局收敛性; 复杂性分析;

D O I：

暂无

中图分类号：

O221.2 [非线性规划];

学科分类号：

070105 ; 1201 ;

摘要：

基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法.其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴.算法对于迭代点可行或不可行的情形都适用.主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键.在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数.数值实验结果表明提出的两个算法是有效的.

引用

页码：497 / 508

页数：12

共 7 条

[1]

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM[J]. 迟晓妮,刘三阳.Acta Mathematica Scientia. 2008(03)

[2] A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions [J].

Pan, Shaohua ;

Chen, Jein-Shan .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2010, 45 (01) :59-88

[3] Second-order cone programming [J].

Alizadeh, F ;

Goldfarb, D .

MATHEMATICAL PROGRAMMING, 2003, 95 (01) :3-51

[4] Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions [J].

Monteiro, RDC ;

Tsuchiya, T .

MATHEMATICAL PROGRAMMING, 2000, 88 (01) :61-83

[5]

Applications of second-order cone programming[J] . Miguel Sousa Lobo,Lieven Vandenberghe,Stephen Boyd,Hervé Lebret.Linear Algebra and Its Applications . 1998 (1)

[6]

Basic lemmas in polynomial-time infeasible-interiorpoint methods for linear programs[J] . Masakazu Kojima.Annals of Operations Research . 1996 (1)

[7] Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems [J].

Nemirovskii, A ;

Scheinberg, K .

MATHEMATICAL PROGRAMMING, 1996, 72 (03) :273-289

← 1 →