×

zbMATH — the first resource for mathematics

Extending Mehrotra and Gondzio higher order methods to mixed semidefinite-quadratic-linear programming. (English) Zbl 0957.90102
Summary: We discuss extensions of S. Mehrotra’s higher order corrections scheme [Higher order methods and their performance, Tech. Report 90-16R1, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Ill. (1991)] and J. Gondzio’s multiple centrality corrections scheme [Computational Optimization and Applications 6, 137-156 (1996; Zbl 0860.90084)] 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.

MSC:
90C22 Semidefinite programming
90C20 Quadratic programming
90C05 Linear programming
Software:
LAPACK; HOPDM; SDPpack
PDF BibTeX Cite
Full Text: DOI
References:
[1] Adler, I. and Alizadeh, F. December 1995.Primal–dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems, December, 46–95. Piscataway, NJ: RUTCOR. Rutgers University. Tech. Report RRR
[2] DOI: 10.1137/0805002 · Zbl 0833.90087
[3] Alizadeh F., SDP pack User Guide (Version 0.9 Beta) (1997)
[4] DOI: 10.1137/S1052623496304700 · Zbl 0911.65047
[5] Alizadeh F., Optimization with semidefinite, quadratic and linear constraints (1997)
[6] Anderson E., LAPACK User’s Guide
[7] DOI: 10.1137/0803036 · Zbl 0794.90043
[8] Czyzyk J., PCx User Guide (Version 1.1)
[9] Duff I. S., User’s guide for the Harwell–Boeing sparse matrix collection (release 1) (1992)
[10] Gondzio J., Computational Optimization and Applications 6 pp 137– (1996)
[11] Gondzio J., HOPDM modular solver for LP problems, User’s guide to version 2.12
[12] Horn R. A., Topics in matrix analysis (1994) · Zbl 0801.15001
[13] Mehrotra S., Higher order methods and their performance 3 (1991)
[14] DOI: 10.1137/0802028 · Zbl 0773.90047
[15] Nesterov Yu. E., Interior–point polynomial algorithms in convex programming (1994) · Zbl 0824.90112
[16] Vandenberghe, L., Boyd, S. and El Gamal, A. 1997. Optimal wire and transistor sizing for circuits with non-tree topology. Proceedings of the IEEE International Conference on Computer–Aided Design. 1997, San Jose, CA.
[17] Wright S. J., Primal-dual interior-point methods (1997) · Zbl 0863.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.