摘要:

We discuss several different search directions which can be used in primal-dual interior-point methods for semidefinite programming problems and investigate their theoretical properties, including scale invariance, primal-dual symmetry, and whether they always generate well-defined directions. Among the directions satisfying all but at most two of these desirable properties are the Alizadeh-Haeberly-Overton, Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-HaralMonteiro, Nesterov-Todd, Gu, and Toh directions, as well as directions we will call the MTW and Half directions. The first five of these appear to be the best in our limited computational testing also.

ISSN:1055-6788    

DOI:10.1080/10556789908805745

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

This short note shows that the Nesterov-Todd search direction used in primal-dual interior-point methods for semidefinite programs belongs to the family of search directions proposed by Kojima, Shindoh and Hara.

ISSN:1055-6788    

DOI:10.1080/10556789908805746

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

We present a long-step predictor-corrector interior-point algorithm for the monotone semidefinite linear complementarity problems using the Monteiro-Zhang unified search directions. Our algorithm is based on the long-step predictor-corrector interior-point algorithm proposed by Kojima, Shida and Shindoh using the Alizadeh-Haeberly-Overton search direction, though the AHO search direction does not belong to the MZ unified search directions in general.

ISSN:1055-6788    

DOI:10.1080/10556789908805747

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

We discuss extensions of Mehrotra's higher order corrections scheme and Gondzio's multiple centrality corrections scheme to mixed semidefinite-quadratic-linear programming (SQLP). These extensions have been included in a solver for SQLP written in C and based on LAPACK. The code implements a primal-dual path-following algorithm for solving SQLP problems based on the XZ + ZX search direction and Mehrotra's predictor-corrector method. We present benchmarks showing that the use of the higher order schemes yields substantial reductions in both the number of iterations and the running time of the algorithm, and also improves its robustness.

ISSN:1055-6788    

DOI:10.1080/10556789908805748

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

Monteiro and Tsuchiya have proposed two primal-dual Newton directions for semidefinite programming, referred to as the MT directions, and established polynomial convergence of path-following methods based on them. This paper reports some computational results on the performance of interior-point predictor-corrector methods based on the MT directions and a variant of these directions, called the S-Ch-MT direction. We discuss how to compute these directions efficiently and derive their corresponding computational complexities. A main feature of our analysis is that computational formulae for these directions are derived from a unified point of view which entirely avoids the use of Kronecker product. Using this unified approach, we also present schemes to compute the Alizadeh-Haeberly-Overton (AHO) direction, the Nesterov-Todd direction and the HRVW/KSH/M direction with computational complexities (for dense problems) better than previously reported in the literature. We present some computational results for small dense problems, which are quite promising. We have obtained better performance for the methods based on the AHO, NT and HRVW/KSH/M directions. We have also observed that the method based on the S-Ch-MT direction compares favorably with the new implementation of the methods based on the NT direction and the HRVW/KSH/M direction.

ISSN:1055-6788    

DOI:10.1080/10556789908805749

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

In this paper we study primal-dual path-following algorithms for second-order cone programming problems (SOCP). We extend the standard long-step/semilong-step/short-step primal-dual path-following alogorithms for LP and SDP to SOCP, and prove that the long-step algorithm using the NT direction and the HRVW/KSH/M direction haveO(n log ε-1) iteration-complexity andO(n3/2log ε-1) iteration-complexity, respectively, to reduce the duality gap by a factor of 1/ε, wherenis the number of the second-order cones. We also show that the short and semilong-step algorithms using the NT direction and the HRVW/KSH/M direction haveandO(n log ε-1) iteration-complexities, respectively.

ISSN:1055-6788    

DOI:10.1080/10556789908805750

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

The path following algorithms of predictor corrector type have proved to be very effective for solving linear optimization problems. However, the assumption that the Newton direction (corresponding to a centering or affine step) is computed exactly is unrealistic. Indeed, for large scale problems, one may need to use iterative algorithms for computing the Newton step.

ISSN:1055-6788    

DOI:10.1080/10556789908805751

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

In this paper we present an inexact Interior Point method for solving monotone nonlinear complementarity problems. We show that the theory presented by Kojima, Noma and Yoshise for an exact version of this method can be used to establish global convergence for the inexact form. Then we prove that local superlinear convergence can be achieved under some stronger hypotheses. The complexity of the algorithm is also studied under the assumption that the problem satisfies a scaled Lipschitz condition. It is proved that the feasible version of the algorithm is polynomial, while the infeasible one is globally convergent at a linear rate.

ISSN:1055-6788    

DOI:10.1080/10556789908805752

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

In this paper we consider a homogeneous analytic center cutting plane method in a projective space. We describe a general scheme that uses a homogeneous oracle and computes an approximate analytic center at each iteration. This technique is applied to a convex feasibility problem, to variational inequalities, and to convex constrained minimization. We prove that these problems can be solved with the same order of complexity as in the case of exact analytic centers. For the feasibility and the minimization problems rough approximations suffice, but very high precision is required for the variational inequalities. We give an example of variational inequality where even the first analytic center needs to be computed with a precision matching the precision required for the solution.

ISSN:1055-6788    

DOI:10.1080/10556789908805753

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor

摘要:

This paper presents linear algebra techniques used in the implementation of an interior point method for solving linear programs and convex quadratic programs with linear constraints. New regularization techniques for Newton systems applicable to both symmetric positive definite and symmetric indefinite systems are described. They transform the latter to quasidef-inite systems known to be strongly factorizable to a form of Cholesky-like factorization.Two different regularization techniques,primal;anddual, are very well suited to the (infeasible) primal-dual interior point algorithm. This particular algorithm, with an extension of multiple centrality correctors, is implemented in our solver HOPDM. Computational results are given to illustrate the potential advantages of the approach when applied to the solution of very large linear and convex quadratic programs.

ISSN:1055-6788    

DOI:10.1080/10556789908805754

出版商:Gordon and Breach Science Publishers    

年代:1999

数据来源: Taylor