  


A Polynomial Time ConstraintReduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs
Sungwoo Park (swpark81gmail.com) Abstract: We present an infeasible primaldual 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 primaldual 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 secondorder cone problem. Keywords: semidefinite programming, semidefinite optimization, interior point methods, constraint reduction, primaldual interior point method, primal dual infeasible, polynomial complexity, linear programming, linear optimization, quadratic programming, quadratic optimization, secondorder cone optimization, second order cone programming. Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: [1] Farid Alizadeh, JeanPierre A. Haeberly, and Michael L. Overton. Primaldual interiorpoint methods for semidefinite programming. Technical report, manuscript presented at the Math. Programming Symposium, Ann Arbor, MI, 1994. [2] Farid Alizadeh, JeanPierre A. Haeberly, and Michael L. Overton. Primaldual interiorpoint methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Opt., 8(3):746768, 1998. [3] Christine Bachoc and Frank Vallentin. New upper bounds for kissing number from semidefinite programming. J. Amer. Math. Soc., 21(3):909924, 2007. [4] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge Univ. Press, New York, NY, 2004. [5] George B. Dantzig and Yinyu Ye. A buildup interiorpoint 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):15591573, 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 primaldual interiorpoint methods for semidefinite programming. Math. Prog., 79(1):235253, 1997. [10] Philip E. Gill, Gene H. Golub, Walter Murray, and Michael A. Saunders. Methods for modifying matrix factorizations. Math. Comp., 28(126):505535, 1974. [11] William Hager. Condition estimates. SIAM J. Sci. Stat. Comput., 5(2):311316, 1984. [12] Christoph Helmberg, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz. An interiorpoint method for semidefinite programming. SIAM J. Opt., 6(2):342361, 1996. [13] Dick Den Hertog, Cornelis Roos, and Tamas Terlaky. Adding and deleting constraints in the pathfollowing method for LP. In Advances in Optimization and Approximation, volume 1, pages 166185. Springer, New York, 1994. [14] Nicholas Higham. A survey of condition number estimation for triangular matrices. SIAM Review, 9(4):575596, 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 predictorcorrector method for semidefinite programming. SIAM J. Opt., 10(1):195210, 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:156177, 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):125157, 2012. [20] John A. Kaliski and Yinyu Ye. A decomposition variant of the potential reduction algorithm for linear programming. Manage. Sci., 39:757776, 1993. [21] Masakazu Kojima, Masayuki Shida, and Susumu Shindoh. Local convergence of predictorcorrector infeasibleinteriorpoint algorithms for SDPs and SDLCPs. Math. Prog., 80(2):129160, 1998. [22] Masakazu Kojima, Masayuki Shida, and Susumu Shindoh. A predictorcorrector interiorpoint algorithm for the semidefinite linear complementarity problem using the AlizadehHaeberlyOverton search direction. SIAM J. Opt., 9(2):444465, 1999. [23] Masakazu Kojima, Susumu Shindoh, and Shinji Hara. Interiorpoint methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Opt., 7(1):86125, 1997. [24] Renato D. C. Monteiro. Primaldual pathfollowing algorithms for semidefinite programming. SIAM J. Opt., 7(3):663678, 1997. [25] Renato D. C. Monteiro. Polynomial convergence of primaldual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. SIAM J. Opt., 8(3):797812, 1998. [26] Renato D. C. Monteiro and Yin Zhang. A unified analysis for a class of long step primaldual pathfollowing interior point algorithms for semidefinite programming. Math. Prog., 81(3):281299, 1998. [27] Yurii E. Nesterov and Michael J. Todd. Selfscaled barriers and interior point methods for convex programming. Math. Op. Res., 22(1):142, 1997. [28] Yurii E. Nesterov and Michael J. Todd. Primaldual interiorpoint methods for selfscaled cones. SIAM J. Opt., 8(2):324364, 1998. [29] Dianne P. O'Leary. Estimating matrix condition numbers. SIAM J. Sci. Stat. Comput., 1(2):205209, 1980. [30] Christopher C. Paige and Michael A. Saunders. Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal., 12(4):617629, 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 predictorcorrector 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 interiorpoint algorithms for semidefinite programming. J. Opt. Theory Appl., 99(1):103119, 1998. [34] Florian A. Potra and Rongqin Sheng. A superlinearly convergent primaldual infeasibleinteriorpoint algorithm for semidefinite programming. SIAM J. Opt., 8(4):10071028, 1998. [35] Alexander Schrijver. A comparison of the Delsarte and Loviasz bounds. IEEE Trans. Inform. Theory, IT25(4):425429, 1979. [36] Pete G. W. Stewart. Efficient generation of random orthogonal matrices with an application to condition estimators. SIAM J. Numer. Anal., 17(3):403409, 1980. [37] Andre L. Tits, PierreAntoine Absil, and William P. Woessner. Constraint reduction for linear programs with many inequality constraints. SIAM J. Opt., 17(1):119146, 2006. [38] KimChuan Toh, Michael J. Todd, and Reha H. Tutuncu. On the implementation and usage of SDPT3  a MATLAB software package for semidefinitequadraticlinear programming, version 4.0. In Miguel F. Anjos and Jean B. Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166, pages 715754. Springer, New York, 2012. [39] Kaoru Tone. An activeset strategy in an interior point method for linear programming. Math. Prog., 59(3):345360, 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 constraintreduced variant of Mehrotra's predictorcorrector algorithm. Comput. Optim. Appl., 51(3):10011036, 2012. [42] Yin Zhang. On extending some primaldual interiorpoint algorithms from linear programming to semidefinite programming. SIAM J. Opt., 8(2):365386, 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):71109, 1998. Download: [PDF] Entry Submitted: 08/26/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  