×

A polynomial time constraint-reduced algorithm for semidefinite optimization problems. (English) Zbl 1329.90104

Summary: 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 F. A. Potra and R. Sheng [SIAM J. Optim. 8, No. 4, 1007–1028 (1998; Zbl 0917.65058)] 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.

MSC:

90C22 Semidefinite programming
65K05 Numerical mathematical programming methods
90C51 Interior-point methods

Citations:

Zbl 0917.65058
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Potra, F.A., Sheng, R.: A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8(4), 1007-1028 (1998) · Zbl 0917.65058 · doi:10.1137/S1052623495294955
[2] Dantzig, G.B., Ye, Y.: A Build-Up Interior-Point Method for Linear Programming: Affine Scaling Form. Tech. Rep. Stanford University, Stanford (1991)
[3] Tone, K.: An active-set strategy in an interior point method for linear programming. Math. Progr. 59(3), 345-360 (1993) · Zbl 0804.90093 · doi:10.1007/BF01581252
[4] Kaliski, J.A., Ye, Y.: A decomposition variant of the potential reduction algorithm for linear programming. Manag. Sci. 39, 757-776 (1993) · Zbl 0783.90073 · doi:10.1287/mnsc.39.6.757
[5] Hertog, D.D., Roos, C., Terlaky, T.: Adding and deleting constraints in the path-following method for LP. In: Advances in Optimization and Approximation, vol. 1, pp. 166-185. Springer, New York (1994) · Zbl 0828.90084
[6] Tits, A.L., Absil, P.A., Woessner, W.P.: Constraint reduction for linear programs with many inequality constraints. SIAM J. Optim. 17(1), 119-146 (2006) · Zbl 1112.90049 · doi:10.1137/050633421
[7] Winternitz, L.B., Nicholls, S.O., Tits, A.L., O’Leary, D.P.: A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm. Comput. Optim. Appl. 51(3), 1001-1036 (2012) · Zbl 1245.90056 · doi:10.1007/s10589-010-9389-4
[8] Jung, J.H., O’Leary, D.P., Tits, A.L.: Adaptive constraint reduction for training support vector machines. Electron. Trans. Numer. Anal. 31, 156-177 (2008) · Zbl 1177.90308
[9] Williams, J.A.: The Use of Preconditioning for Training Support Vector Machines, Master’s Thesis, Applied Mathematics and Scientific Computing Program. University of Maryland, College Park (2008)
[10] Jung, J.H., O’Leary, D.P., Tits, A.L.: Adaptive constraint reduction for convex quadratic programming. Comput. Optim. Appl. 51(1), 125-157 (2012) · Zbl 1245.90082 · doi:10.1007/s10589-010-9324-8
[11] Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342-361 (1996) · Zbl 0853.65066 · doi:10.1137/0806020
[12] Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7(1), 86-125 (1997) · Zbl 0872.90098 · doi:10.1137/S1052623494269035
[13] Monteiro, R.D.C.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7(3), 663-678 (1997) · Zbl 0913.65051 · doi:10.1137/S1052623495293056
[14] Alizadeh, F., Haeberly, J.P.A., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming. Tech. rep., Manuscript presented at the Math. Programming Symposium, Ann Arbor, MI (1994) · Zbl 0819.65098
[15] Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1-42 (1997) · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[16] Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8(2), 324-364 (1998) · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[17] Monteiro, R.D.C., Zhang, Y.: A unified analysis for a class of long-step primal-dual path-following interior point algorithms for semidefinite programming. Math. Progr. 81(3), 281-299 (1998) · Zbl 0919.90109 · doi:10.1007/BF01580085
[18] Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8(2), 365-386 (1998) · Zbl 0913.65050 · doi:10.1137/S1052623495296115
[19] Alizadeh, F., Haeberly, J.P.A., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8(3), 746-768 (1998) · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[20] Monteiro, R.D.C.: Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. SIAM J. Optim. 8(3), 797-812 (1998) · Zbl 0913.65052 · doi:10.1137/S1052623496308618
[21] Kojima, M., Shida, M., Shindoh, S.: Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math. Progr. 80(2), 129-160 (1998) · Zbl 0897.90183 · doi:10.1007/BF01581723
[22] Potra, F.A., Sheng, R.: Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 99(1), 103-119 (1998) · Zbl 0911.90255 · doi:10.1023/A:1021700210959
[23] Kojima, M., Shida, M., Shindoh, S.: A predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction. SIAM J. Optim. 9(2), 444-465 (1999) · Zbl 0997.90086 · doi:10.1137/S1052623496300623
[24] Potra, F.A., Sheng, R.: Superlinear convergence of a predictor-corrector method for semidefinite programming without shrinking central path neighborhood. Tech. Rep. 91, Reports on Computational Mathematics, Department of Mathematics, University of Iowa (1996) · Zbl 0999.90025
[25] Ji, J., Potra, F.A., Sheng, R.: On the local convergence of a predictor-corrector method for semidefinite programming. SIAM J. Optim. 10(1), 195-210 (1999) · Zbl 0959.65076 · doi:10.1137/S1052623497316828
[26] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[27] Schrijver, A.: A comparison of the Delsarte and Loviász bounds. IEEE Trans. Inf. Theory 25(4), 425-429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072
[28] de Klerk, E., Pasechnik, D.V., Sotirov, R.: On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Optim. 19(4), 1559-1573 (2008) · Zbl 1196.90094 · doi:10.1137/070711141
[29] Bachoc, C., Vallentin, F.: New upper bounds for kissing number from semidefinite programming. J. Am. Math. Soc. 21(3), 909-924 (2007) · Zbl 1223.90039 · doi:10.1090/S0894-0347-07-00589-9
[30] Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1), 71-109 (1998) · Zbl 0904.90145 · doi:10.1023/A:1009795911987
[31] Park, S.: Matrix Reduction in Numerical Optimization, Ph.D. Thesis, Computer Science Department, University of Maryland, College Park (2011). http://drum.lib.umd.edu/handle/1903/11751
[32] Toh, KC; Todd, MJ; Tütüncü, RH; Anjos, MF (ed.); Lasserre, JB (ed.), On the implementation and usage of SDPT3 - a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0, No. 166, 715-754 (2012), New York · Zbl 1334.90117 · doi:10.1007/978-1-4614-0769-0_25
[33] Park, S., O’Leary, D.P.: A Polynomial Time Constraint Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs. Tech. rep., University of Maryland, College Park (2015). http://www.optimization-online.org/DB_HTML/2013/08/4011.html · Zbl 1329.90104
[34] de Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Norwell (2002) · Zbl 0991.90098 · doi:10.1007/b105286
[35] Jansen, B.: Interior Point Techniques in Optimization. Kluwer Academic Publishers, Norwell (1997) · Zbl 0886.90098 · doi:10.1007/978-1-4757-5561-9
[36] Fujisawa, K., Kojima, M., Nakata, K.: Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Math. Progr. 79(1), 235-253 (1997) · Zbl 0887.90156
[37] Hager, W.: Condition estimates. SIAM J. Sci. Stat. Comput. 5(2), 311-316 (1984) · Zbl 0542.65023 · doi:10.1137/0905023
[38] Higham, N.: A survey of condition number estimation for triangular matrices. SIAM Rev. 9(4), 575-596 (1987) · Zbl 0635.65049 · doi:10.1137/1029112
[39] O’Leary, D.P.: Estimating matrix condition numbers. SIAM J. Sci. Stat. Comput. 1(2), 205-209 (1980) · Zbl 0445.65024 · doi:10.1137/0901014
[40] Stewart, P.G.W.: Efficient generation of random orthogonal matrices with an application to condition estimators. SIAM J. Numer. Anal. 17(3), 403-409 (1980) · Zbl 0443.65027 · doi:10.1137/0717034
[41] Gill, P.E., Golub, G.H., Murray, W., Saunders, M.A.: Methods for modifying matrix factorizations. Math. Comput. 28(126), 505-535 (1974) · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6
[42] Dongarra, J.J., Moler, C.B., Bunch, J.R., Stewart, G.W.: LINPACK Users’ Guide. SIAM, Philadelphia, PA (1979) · Zbl 0476.68025 · doi:10.1137/1.9781611971811
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.