A long-step primal-dual path-following method for semidefinite programming

被引：3

作者：

Jiang, JM ^{[1
]}

机构：

[1] Tsing Hua Univ, Dept Appl Math, Beijing 100084, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 1998年 / 23卷 / 1-2期

关键词：

semidefinite programming; primal-dual interior point methods; proximity measure; logarithmic barrier function;

D O I：

10.1016/S0167-6377(98)00018-2

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 [运筹学与控制论]; 12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];

摘要：

In this paper, the long-step primal-dual path-following method of Jansen et al. is extended from linear programming to semidefinite programming. By generalizing the proximity measure and using the Nesterov-Todd direction as the search direction, we construct an algorithm which finds an E-optimal solution in at most O(n\In epsilon\) iterations. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：53 / 61

页数：9

共 27 条

[1]

INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].

ALIZADEH, F .

SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51

[2]

ALIZADEH F, 1995, COMPLEMENTARITY NOND

[3]

A LONG-STEP BARRIER METHOD FOR CONVEX QUADRATIC-PROGRAMMING [J].

ANSTREICHER, KM ;

DENHERTOG, D ;

ROOS, C ;

TERLAKY, T .

ALGORITHMICA, 1993, 10 (05) :365-382

[4]

ANSTREICHER KM, 1996, LONG STEP PATH FOLLO

[5]

den Hertog D., 1994, Interior Point Approach to Linear, Quadratic and Convex Programming

[6]

ON A MATRIX GENERALIZATION OF AFFINE-SCALING VECTOR-FIELDS [J].

FAYBUSOVICH, L .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1995, 16 (03) :886-897

[7]

FAYBUSOVICH L, 1995, SEMIDEFINITE PROGRAM

[8]

FAYBUSOVICH L, IN PRESS SIAM J OPTI

[9]

FREUND RM, 1994, 30294 MIT

[10]

HE B, 1996, 9627 DELFT U TECHN F

← 1 2 3 →