Top

Published in:

2013 | OriginalPaper | Chapter

12. Preprocessing and Regularization for Degenerate Semidefinite Programs

Authors : Yuen-Lam Cheung, Simon Schurr, Henry Wolkowicz

Published in: Computational and Analytical Mathematics

Publisher: Springer New York

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper presents a backward stable preprocessing technique for (nearly) ill-posed semidefinite programming, SDP, problems, i.e., programs for which the Slater constraint qualification (SCQ), the existence of strictly feasible points, (nearly) fails. Current popular algorithms for semidefinite programming rely on primal-dual interior-point, p-d i-p, methods. These algorithms require the SCQ for both the primal and dual problems. This assumption guarantees the existence of Lagrange multipliers, well-posedness of the problem, and stability of algorithms. However, there are many instances of SDPs where the SCQ fails or nearly fails. Our backward stable preprocessing technique is based on applying the Borwein–Wolkowicz facial reduction process to find a finite number, k, of rank-revealing orthogonal rotations of the problem. After an appropriate truncation, this results in a smaller, well-posed, nearby problem that satisfies the Robinson constraint qualification, and one that can be solved by standard SDP solvers. The case k = 1 is of particular interest and is characterized by strict complementarity of an auxiliary problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Logarithmic and Complex Constant Term Identities

next chapter The Largest Roots of the Mandelbrot Polynomials

Note that for numerical stability and well-posedness, it is essential that there exists Lagrange multipliers and that intF ≠ ∅. Regularization involves finding both a minimal face and a minimal subspace; see [66].

orion.math.uwaterloo.ca/^~hwolkowi/henry/reports/ABSTRACTS.html.

Alfakih, A., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Computational optimization–a tribute to Olvi Mangasarian, Part I. Comput. Optim. Appl. 12(1–3), 13–30 (1999)

Alipanahi, B., Krislock, N., Ghodsi, A.: Manifold learning by semidefinite facial reduction. Technical Report Submitted to Machine Learning Journal, University of Waterloo, Waterloo, Ontario (2010)

Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77, 111–128 (1997)MathSciNetMATH

Anjos, A.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science. Springer, New York (2011)

Anjos, M.F., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem. Foundations of heuristics in combinatorial optimization. Discrete Appl. Math. 119(1–2), 79–106 (2002)MathSciNetMATH

Ben-Israel, A., Ben-Tal, A., Zlobec, S.: Optimality in Nonlinear Programming: A Feasible Directions Approach. A Wiley-Interscience Publication, New York (1981)MATH

Ben-Israel, A., Charnes, A., Kortanek, K.: Duality and asymptotic solvability over cones. Bull. Amer. Math. Soc. 75(2), 318–324 (1969)MathSciNetCrossRefMATH

Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer, New York (2000)MATH

Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods Soft. 11/12(1–4), 613–623 (1999). projects.coin-or.org/Csdp

10.

Borwein, J.M., Wolkowicz, H.: Characterization of optimality for the abstract convex program with finite-dimensional range. J. Austral. Math. Soc. Ser. A 30(4), 390–411 (1980/1981)

11.

Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Austral. Math. Soc. Ser. A 30(3), 369–380 (1980/1981)

12.

Borwein, J.M., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495–530 (1981)MathSciNetCrossRefMATH

13.

Boyd, S., Balakrishnan, V., Feron, E., El Ghaoui, L.: Control system analysis and synthesis via linear matrix inequalities. In: Proceedings of the American Control Conference, pp. 2147–2154 (1993)

14.

Burkowski, F., Cheung, Y-L., Wolkowicz, H.: Efficient use of semidefinite programming for selection of rotamers in protein conformations. Technical Report, p. 30, University of Waterloo, Waterloo, Ontario (2012)

15.

Caron, R.J., Boneh, A., Boneh, S.: Redundancy. In: Advances in Sensitivity Analysis and Parametric Programming. International Series in Operations Research & Management Science, vol. 6, pp. 13.1–13.41. Kluwer Academic Publishers, Boston (1997)

16.

De Klerk, E.: Interior point methods for semidefinite programming. Ph.D. Thesis, Delft University (1997)

17.

De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Applied Optimization Series. Kluwer Academic, Boston (2002)

18.

Demmel, J., Kågström, B.: The generalized Schur decomposition of an arbitrary pencil A − λ B; robust software with error bounds and applications II: software and applications. ACM Trans. Math. Soft. 19(2), 175–201 (1993)CrossRefMATH

19.

Doan, X.V., Kruk, S., Wolkowicz, H.: A robust algorithm for semidefinite programming. Optim. Methods Soft. 27(4–5), 667–693 (2012)MathSciNetCrossRefMATH

20.

Fourer, R., Gay, D.M.: Experience with a primal presolve algorithm. In: Large Scale Optimization (Gainesville, FL, 1993), pp. 135–154. Kluwer Academic Publishers, Dordrecht (1994)

21.

Freund, R.M.: Complexity of an algorithm for finding an approximate solution of a semi-definite program with no regularity assumption. Technical Report OR 302-94, MIT, Cambridge (1994)

22.

Freund, R.M.: Complexity of convex optimization using geometry-based measures and a reference point. Math. Program. Ser. A 99(2), 197–221 (2004)MathSciNetCrossRefMATH

23.

Freund, R.M., Vera, J.R.: Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system. Technical report, MIT, Cambridge (1997)

24.

Freund, R.M., Ordóñez, F., Toh, K.C.: Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems. USC-ISE Working Paper #2005-02, MIT (2005). www-rcf.usc.edu/~fordon/

25.

Goldman, A.J., Tucker, A.W.: Theory of linear programming. In: Linear Inequalities and Related Systems. Annals of Mathematics Studies, vol. 38, pp. 53–97. Princeton University Press, Princeton (1956)

26.

Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)MATH

27.

Gondzio, J.: Presolve analysis of linear programs prior to applying an interior point method. Informs J. Comput. 9(1), 73–91 (1997)MathSciNetCrossRefMATH

28.

Gould, N.I.M., Toint, Ph.L.: Preprocessing for quadratic programming. Math. Program. Ser. B 100(1), 95–132 (2004)MathSciNetMATH

29.

Gourion, D., Seeger, A.: Critical angles in polyhedral convex cones: numerical and statistical considerations. Math. Program. 123(1), 173–198 (2010)MathSciNetCrossRefMATH

30.

Gruber, G., Rendl, F.: Computational experience with ill-posed problems in semidefinite programming. Comput. Optim. Appl. 21(2), 201–212 (2002)MathSciNetCrossRefMATH

31.

Hiriart-Urruty, J-B., Malick, J.: A fresh variational-analysis look at the positive semidefinite matrices world. Technical Report, University of Tolouse, Toulouse, France (2010)

32.

Horn, R.A., Johnson, C.R.: Matrix Analysis (Corrected reprint of the 1985 original). Cambridge University Press, Cambridge (1990)

33.

Iusem, A., Seeger, A.: Searching for critical angles in a convex cone. Math. Program. Ser. B 120(1), 3–25 (2009)MathSciNetCrossRefMATH

34.

Jibrin, S.: Redundancy in semidefinite programming. Ph.D. Thesis. Carleton University, Ottawa, Ontario, Canada (1997)

35.

Karwan, M.H., Lotfi, V., Telgen, J., Zionts, S.: Redundancy in Mathematical Programming. Springer, New York (1983)CrossRefMATH

36.

Krislock, N., Wolkowicz, H.: Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20(5), 2679–2708 (2010)MathSciNetCrossRefMATH

37.

Lamoureux, M., Wolkowicz, H.: Numerical decomposition of a convex function. J. Optim. Theory Appl. 47(1), 51–64 (1985)MathSciNetCrossRefMATH

38.

Luo, Z-Q., Sturm, J.F., Zhang, S.: Conic convex programming and self-dual embedding. Optim. Methods Soft. 14(3), 169–218 (2000)MathSciNetCrossRefMATH

39.

Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20(1), 336–356 (2009)MathSciNetCrossRefMATH

40.

Mangasarian, O.L., Fromovitz, S.: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17, 37–47 (1967)MathSciNetCrossRefMATH

41.

Mészáros, C., Suhl, U.H.: Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum 25, 575–595 (2003). doi: 10.1007/s00291-003-0130-xCrossRefMATH

42.

Monteiro, R.D.C., Todd, M.J.: Path-following methods. In: Handbook of Semidefinite Programming, pp. 267–306. Kluwer Academic Publishers, Boston (2000)

43.

Nesterov, Y.E., Todd, M.J., Ye, Y.: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems. Math. Program. Ser. A 84(2), 227–267 (1999)MathSciNetMATH

44.

Pataki, G.: On the closedness of the linear image of a closed convex cone. Math. Oper. Res. 32(2), 395–412 (2007)MathSciNetCrossRefMATH

45.

Pataki, G.: Bad semidefinite programs: they all look the same. Technical Report, Department of Operations Research, University of North Carolina, Chapel Hill (2011)

46.

Peña, J., Renegar, J.: Computing approximate solutions for convex conic systems of constraints. Math. Program. Ser. A 87(3), 351–383 (2000)CrossRefMATH

47.

Pólik, I., Terlaky, T.: New stopping criteria for detecting infeasibility in conic optimization. Optim. Lett. 3(2), 187–198 (2009)MathSciNetCrossRefMATH

48.

Ramana, M.V.: An algorithmic analysis of multiquadratic and semidefinite programming problems. Ph.D. Thesis, Johns Hopkins University, Baltimore (1993)

49.

Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77(2), 129–162 (1997)MathSciNetMATH

50.

Ramana, M.V., Tunçel, L., Wolkowicz, H.: Strong duality for semidefinite programming. SIAM J. Optim. 7(3), 641–662 (1997)MathSciNetCrossRefMATH

51.

Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2001)CrossRefMATH

52.

Robinson, S.M.: Stability theory for systems of inequalities I: Linear systems. SIAM J. Numer. Anal. 12, 754–769 (1975)MathSciNetCrossRefMATH

53.

Robinson, S.M.: First order conditions for general nonlinear optimization. SIAM J. Appl. Math. 30(4), 597–607 (1976)MathSciNetCrossRefMATH

54.

Rockafellar, R.T: Some convex programs whose duals are linearly constrained. In: Nonlinear Programming (Proceedings of a Symposium, University of Wisconsin, Madison, Wisconsin, 1970), pp. 293–322. Academic, New York (1970)

55.

Rockafellar, R.T.: Convex Analysis (Reprint of the 1970 original) Princeton Landmarks in Mathematics, Princeton Paperbacks. Princeton University Press, Princeton (1997)

56.

Shapiro, A.: On duality theory of conic linear problems. In: Semi-Infinite Programming (Alicante, 1999). Nonconvex Optim. Appl. vol. 57, pp. 135–165. Kluwer Academic Publishers, Dordrecht (2001)

57.

Shapiro, A., Nemirovskii, A.: Duality of linear conic problems. Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia (2003)

58.

Stewart, G.W.: Rank degeneracy. SIAM J. Sci. Stat. Comput. 5(2), 403–413 (1984)CrossRefMATH

59.

Stewart, G.W.: Determining rank in the presence of error. In: Linear Algebra for Large Scale and Real-Time Applications (Leuven, 1992). NATO Advanced Science Institute Series E: Applied Sciences, vol. 232, pp. 275–291. Kluwer Academic Publishers, Dordrecht (1993)

60.

Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Soft. 11/12(1–4), 625–653 (1999). sedumi.ie.lehigh.edu.

61.

Sun, D.: The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31(4), 761–776 (2006)MathSciNetCrossRefMATH

62.

Todd, M.J., Ye, Y.: Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming. Math. Program. Ser. A 81(1), 1–21 (1998)MathSciNetCrossRefMATH

63.

Todd, M.J.: Semidefinite programming. Acta Numerica 10, 515–560 (2001)MathSciNetMATH

64.

Tunçel, L.: On the Slater condition for the SDP relaxations of nonconvex sets. Oper. Res. Lett. 29(4), 181–186 (2001)MathSciNetCrossRefMATH

65.

Tunçel, L.: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization. Fields Institute Monographs, vol. 27. American Mathematical Society, Providence (2010)

66.

Tunçel, L., Wolkowicz, H.: Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53(2),619–648 (2012)MathSciNetCrossRefMATH

67.

Tütüncü, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. Ser. B 95(2), 189–217 (2003). www.math.nus.edu.sg/~mattohkc/sdpt3.html.

68.

Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49–95 (1996)MathSciNetCrossRefMATH

69.

Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218–242 (2006)MathSciNetCrossRefMATH

70.

Wei, H., Wolkowicz, H.: Generating and solving hard instances in semidefinite programming. Math. Program. 125(1), 31–45 (2010)MathSciNetCrossRefMATH

71.

Wolkowicz, H.: Calculating the cone of directions of constancy. J. Optim. Theory Appl. 25(3), 451–457 (1978)MathSciNetCrossRefMATH

72.

Wolkowicz, H.: Some applications of optimization in matrix theory. Linear Algebra Appl. 40, 101–118 (1981)MathSciNetCrossRefMATH

73.

Wolkowicz, H.: Solving semidefinite programs using preconditioned conjugate gradients. Optim. Methods Soft. 19(6), 653–672 (2004)MathSciNetCrossRefMATH

74.

Wolkowicz, H., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96/97, 461–479 (1999) (Selected for the special Editors’ Choice, Edition 1999)

75.

Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. International Series in Operations Research & Management Science, vol. 27. Kluwer Academic Publishers, Boston (2000)

76.

Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0). Optim. Methods Soft. 18(4), 491–505 (2003). sdpa.indsys.chuo-u.ac.jp/sdpa/

77.

Yamashita, M., Fujisawa, K., Nakata, K., Nakata, M., Fukuda, M., Kobayashi, K., Goto, K.: A high-performance software package for semidefinite programs: Sdpa7. Technical Report, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan (2010)

78.

Zălinescu, C: On zero duality gap and the Farkas lemma for conic programming. Math. Oper. Res. 33(4), 991–1001 (2008)MathSciNetCrossRefMATH

79.

Zălinescu, C.: On duality gap in linear conic problems. Technical Report, University of Alexandru Ioan Cusa, Iasi, Romania (2010)

80.

Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. Semidefinite programming and interior-point approaches for combinatorial optimization problems (Fields Institute, Toronto, ON, 1996). J. Comb. Optim. 2(1), 71–109 (1998)

Title: Preprocessing and Regularization for Degenerate Semidefinite Programs
Authors: Yuen-Lam Cheung
Simon Schurr
Henry Wolkowicz
Publisher: Springer New York
Book: Computational and Analytical Mathematics
Print ISBN: 978-1-4614-7620-7

Electronic ISBN: 978-1-4614-7621-4

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-1-4614-7621-4_12

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner