We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction due to Potra and Sheng (1998) and can be applied whenever the data matrices are block diagonal. It thus solves as special cases any optimization problem that is a linear, convex quadratic, convex quadratically constrained, or second-order cone problem.
Citation
[1] Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton. Primal-dual interior-point methods for semidefinite programming. Technical report, manuscript presented at the Math. Programming Symposium, Ann Arbor, MI, 1994. [2] Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton. Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Opt., 8(3):746-768, 1998. [3] Christine Bachoc and Frank Vallentin. New upper bounds for kissing number from semidefinite programming. J. Amer. Math. Soc., 21(3):909-924, 2007. [4] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge Univ. Press, New York, NY, 2004. [5] George B. Dantzig and Yinyu Ye. A build-up interior-point method for linear programming: Affine scaling form. Technical report, Stanford Univ., 1991. [6] Etienne de Klerk. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Norwell, MA, 2002. [7] Etienne de Klerk, Dmitrii V. Pasechnik, and Renata Sotirov. On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Opt., 19(4):1559-1573, 2008. [8] Jack J. Dongarra, Cleve B. Moler, James R. Bunch, and G. W. Stewart. LINPACK Users' Guide. SIAM, Philadelphia, PA, 1979. [9] Katsuki Fujisawa, Masakazu Kojima, and Kazuhide Nakata. Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Math. Prog., 79(1):235-253, 1997. [10] Philip E. Gill, Gene H. Golub, Walter Murray, and Michael A. Saunders. Methods for modifying matrix factorizations. Math. Comp., 28(126):505-535, 1974. [11] William Hager. Condition estimates. SIAM J. Sci. Stat. Comput., 5(2):311-316, 1984. [12] Christoph Helmberg, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz. An interior-point method for semidefinite programming. SIAM J. Opt., 6(2):342-361, 1996. [13] Dick Den Hertog, Cornelis Roos, and Tamas Terlaky. Adding and deleting constraints in the path-following method for LP. In Advances in Optimization and Approximation, volume 1, pages 166-185. Springer, New York, 1994. [14] Nicholas Higham. A survey of condition number estimation for triangular matrices. SIAM Review, 9(4):575-596, 1987. [15] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge Univ. Press, New York, NY, 1985. [16] Benjamin Jansen. Interior Point Techniques in Optimization. Kluwer Academic Publishers, Norwell, MA, 1997. [17] Jun Ji, Florian A. Potra, and Rongqin Sheng. On the local convergence of a predictor-corrector method for semidefinite programming. SIAM J. Opt., 10(1):195-210, 1999. [18] Jin Hyuk Jung, Dianne P. O'Leary, and Andre L. Tits. Adaptive constraint reduction for training support vector machines. Elec. Trans. Numer. Anal., 31:156-177, 2008. [19] Jin Hyuk Jung, Dianne P. O'Leary, and Andre L. Tits. Adaptive constraint reduction for convex quadratic programming. Comput. Optim. Appl., 51(1):125-157, 2012. [20] John A. Kaliski and Yinyu Ye. A decomposition variant of the potential reduction algorithm for linear programming. Manage. Sci., 39:757-776, 1993. [21] Masakazu Kojima, Masayuki Shida, and Susumu Shindoh. Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math. Prog., 80(2):129-160, 1998. [22] Masakazu Kojima, Masayuki Shida, and Susumu Shindoh. A predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction. SIAM J. Opt., 9(2):444-465, 1999. [23] Masakazu Kojima, Susumu Shindoh, and Shinji Hara. Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Opt., 7(1):86-125, 1997. [24] Renato D. C. Monteiro. Primal-dual path-following algorithms for semidefinite programming. SIAM J. Opt., 7(3):663-678, 1997. [25] Renato D. C. Monteiro. Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. SIAM J. Opt., 8(3):797-812, 1998. [26] Renato D. C. Monteiro and Yin Zhang. A unified analysis for a class of long step primal-dual path-following interior point algorithms for semidefinite programming. Math. Prog., 81(3):281-299, 1998. [27] Yurii E. Nesterov and Michael J. Todd. Self-scaled barriers and interior point methods for convex programming. Math. Op. Res., 22(1):1-42, 1997. [28] Yurii E. Nesterov and Michael J. Todd. Primal-dual interior-point methods for self-scaled cones. SIAM J. Opt., 8(2):324-364, 1998. [29] Dianne P. O'Leary. Estimating matrix condition numbers. SIAM J. Sci. Stat. Comput., 1(2):205-209, 1980. [30] Christopher C. Paige and Michael A. Saunders. Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal., 12(4):617-629, 1975. [31] Sungwoo Park. Matrix Reduction in Numerical Optimization. PhD thesis, Computer Science Department, Univ. of Maryland, College Park, MD, 2011. [32] Florian A. Potra and Rongqin Sheng. Superlinear convergence of a predictor-corrector method for semidefinite programming without shrinking central path neighborhood. Technical Report 91, Reports on Computational Mathematics, Department of Mathematics, Univ. of Iowa, 1996. [33] Florian A. Potra and Rongqin Sheng. Superlinear convergence of interior-point algorithms for semidefinite programming. J. Opt. Theory Appl., 99(1):103-119, 1998. [34] Florian A. Potra and Rongqin Sheng. A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Opt., 8(4):1007-1028, 1998. [35] Alexander Schrijver. A comparison of the Delsarte and Loviasz bounds. IEEE Trans. Inform. Theory, IT-25(4):425-429, 1979. [36] Pete G. W. Stewart. Efficient generation of random orthogonal matrices with an application to condition estimators. SIAM J. Numer. Anal., 17(3):403-409, 1980. [37] Andre L. Tits, Pierre-Antoine Absil, and William P. Woessner. Constraint reduction for linear programs with many inequality constraints. SIAM J. Opt., 17(1):119-146, 2006. [38] Kim-Chuan Toh, Michael J. Todd, and Reha H. Tutuncu. On the implementation and usage of SDPT3 - a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0. In Miguel F. Anjos and Jean B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166, pages 715-754. Springer, New York, 2012. [39] Kaoru Tone. An active-set strategy in an interior point method for linear programming. Math. Prog., 59(3):345-360, 1993. [40] Jhacova Ashira Williams. The use of preconditioning for training support vector machines. Master's thesis, Applied Mathematics and Scientific Computing Program, Univ. of Maryland, College Park, MD, 2008. [41] Luke B. Winternitz, Stacey O. Nicholls, Andre L. Tits, and Dianne P. O'Leary. A constraint-reduced variant of Mehrotra's predictor-corrector algorithm. Comput. Optim. Appl., 51(3):1001-1036, 2012. [42] Yin Zhang. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Opt., 8(2):365-386, 1998. [43] Qing Zhao, Stefan E. Karisch, Franz Rendl, and Henry Wolkowicz. Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Opt., 2(1):71-109, 1998.