On verified numerical computations in convex programming. (English) Zbl 1184.90124

Jansson, Christian

Japan J. Ind. Appl. Math. 26, No. 2-3, 337-363 (2009).

Summary: This survey contains recent developments for computing verified results of convex constrained optimization problems, with emphasis on applications. Especially, we consider the computation of verified error bounds for non-smooth convex conic optimization in the framework of functional analysis, for linear programming, and for semidefinite programming. A discussion of important problem transformations to special types of convex problems and convex relaxations is included. The latter are important for handling and for reliability issues in global robust and combinatorial optimization. Some remarks on numerical experiences, including also large-scale and ill-posed problems, and software for verified computations conclude this survey.

MSC:

90C25

Convex programming

Keywords:

linear programming; semidefinite programming; conic programming; convex programming; combinatorial optimization; rounding errors; ill-posed problems; interval arithmetic; branch-bound-and-cut

Software:

INTLAB; Benchmarks for Optimization Software; SDPLR; SDPA; CPLEX; CSDP; VSDP; INTOPT_90; SDPT3; SDPLIB; Cosy; YALMIP; NETLIB LP Test Set; SeDuMi; Lurupa; SBmethod; Numerica

References:

[1]	G. Alefeld and J. Herzberger, Introduction to Interval Computations. Academic Press, New York, 1983. · Zbl 0552.65041
[2]	F. Alizadeh and D. Glodfarb, Second-order cone programming. Math. Program.,95 (2003), 3–51. · Zbl 1153.90522
[3]	E.D. Andersen, C. Roos and T. Terlaky, A primal-dual interior-point method for conic quadratic optimization. Math. Programming,95 (2003), 249–277. · Zbl 1030.90137
[4]	H. Beeck, Linear programming with inexact data. Technical Report 7830, Abteilung Mathematik, TU München, 1978.
[5]	A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust semidefinite programming. Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal and L. Vandenberghe (eds.), Kluwer Academic Publishers, 2000.
[6]	A. Ben-Tal and A. Nemirovski, Robust convex optimization. Math. Operations Res.,23 (1998), 769–805. · Zbl 0977.90052
[7]	A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization, SIAM, Philadelphia, PA, 2001. · Zbl 0986.90032
[8]	S.J. Benson and Y. Ye, DSDP3: Dual scaling algorithm for general positive semidefinite programming. Technical Report Preprint ANL/MCS-P851-1000, Argonne National Labs, 2001.
[9]	M. Berz et al., COSY Infinity. http://www.bt.pa.msu.edu/index_files/cosy.htm.
[10]	G.D. Birkhoff, Lattice Theory, revised edition. Am. Math. Soc. Colloquium Publications, Vol. 25, Am. Math. Soc., New York, 1948. · Zbl 0033.10103
[11]	B. Borchers, CSDP, A C library for semidefinite programming. Optimization Methods and Software,11 (1999), 613–623. · Zbl 0973.90524
[12]	B. Borchers, SDPLIB 1.2, a library of semidefinite programming test problems. Optimization Methods and Software,11 (1999), 683–690. · Zbl 0973.90522
[13]	N. Bourbaki, Éléments de mathématique. XIII. 1 part: Les structures fondamentales de l’analyse, Livre VI: Intégration, Actualités scientifique et industrielles, 1952.
[14]	S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. · Zbl 1058.90049
[15]	S. Burer and R.D.C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming,95 (2003), 329–357. · Zbl 1030.90077
[16]	S. Burer, R.D.C. Monteiro and Y. Zhang, Solving a class of semidefinite programs via nonlinear programming. Math. Programming,93 (2002), 97–122. · Zbl 1007.90045
[17]	D. Chaykin, Verified Semidefinite Programming: Applications and the Software Package verified SDP. Ph.D. thesis, Technische Universität Hamburg-Harburg, 2009.
[18]	E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Dordrecht: Kluwer Academic Publishers, 2002. · Zbl 0991.90098
[19]	L. El Ghaoui, F. Oustry and H. Lebret, Robust Solutions to Uncertain Semidefinite Programs. SIAM J. Optim.,9 (1998), 33–52. · Zbl 0960.93007
[20]	R.M. Freund, F. Ordóñez and K. Toh, Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems. Math. Programming,109 (2007), 445–475. · Zbl 1278.90447
[21]	E.R. Hansen, Global Optimization Using Interval Analysis. Marcel Dekker, New York, 1992. · Zbl 0762.90069
[22]	C. Helmberg, SBmethoda C++ implementation of the spectral bundle method. Technical Report, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000, Manual to Version 1.1, ZIB-Report ZR 00-35, http://www.mathematik.uni-kl.de/helmberg/SBmethod/.
[23]	C. Helmberg, Semidefinite programming for combinatorial optimization (Habilitationsschrift). Technical Report ZIB ZR-00-34, Konrad-Zuse-Zentrum Berlin, TU Berlin, 2000.
[24]	C. Helmberg and K.C. Kiwiel, A spectral bundle method with bounds. Math. Programming,93 (2002), 173–194. · Zbl 1065.90059
[25]	ILOG CPLEX 7.1, User’s Manual. ILOG, France, 2001.
[26]	C. Jansson, A self-validating method for solving linear programming problems with interval input data, Computing Suppl.,6 (1988), 33–45. · Zbl 0661.65056
[27]	C. Jansson, A rigorous lower bound for the optimal value of convex optimization problems. J. Global Optimization,28 (2004), 121–137. · Zbl 1134.90461
[28]	C. Jansson, Rigorous lower and upper bounds in linear programming. SIAM J. Optimization (SIOPT),14 (2004), 914–935. · Zbl 1073.90022
[29]	C. Jansson, VSDP: A MATLAB software package for verified semidefinite programming. NOLTA, 2006, 327–330.
[30]	C. Jansson, VSDP: Verified Semidefinite Programming, User’s Guide. 2006, http://www.BetaVersion0.1. optimization-online.org/DB_HTML/2006/12/1547.html.
[31]	C. Jansson, Guaranteed accuracy for conic programming problems in vector lattices. 2007, arXiv:0707.4366v1, http://arxiv.org/abs/0707.4366v1.
[32]	C. Jansson, D. Chaykin and C. Keil, Rigorous error bounds for the optimal value in semidefinite programming. SIAM Journal on Numerical Analysis,46 (2007), 180–200, http://link.aip.org/link/?SNA/46/180/1. · Zbl 1167.90009
[33]	R.B. Kearfott, GlobSol. http://interval.louisiana.edu.
[34]	R.B. Kearfott, On proving existence of feasible points in equality constrained optimization problems. Math. Program.,83 (1998), 89–100. · Zbl 0949.90089
[35]	R.B. Kearfott, On proving existence of feasible points in equality constrained optimization problems. Preprint, Department of Mathematics, Univ. of Southwestern Louisiana, U.S.L. Box 4-1010, Lafayette, La 70504, 1994.
[36]	R.B. Kearfott, Rigorous Global Search: Continuous Problems. Kluwer Academic Publisher, Dordrecht, 1996. · Zbl 0876.90082
[37]	C. Keil, Verified linear programming – a comparison. Submitted, 2008, http://www.optimization-online.org/DB_HTML/2008/06/2007.html.
[38]	C. Keil, Lurupa – rigorous error bounds in linear programming. Algebraic and Numerical Algorithms and Computer-Assisted Proofs, B. Buchberger, S. Oishi, M. Plum and S.M. Rump (eds.), Dagstuhl Seminar Proceedings, No. 05391. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006, http://drops.dagstuhl.de/opus/volltexte/2006/445.
[39]	C. Keil and C. Jansson, Computational experience with rigorous error bounds for the Netlib linear programming library. Reliable Computing,12 (2006), 303–321. http://www.optimization-online.org/DB_HTML/2004/12/1018.html. · Zbl 1099.65051
[40]	R. Krawczyk, Fehlerabschätzung bei linearer Optimierung, Interval Mathematics, K. Nickel (ed.), Lecture Notes in Computer Science, Vol. 29, Springer-Verlag, Berlin, 1975, 215–222. · Zbl 0301.65034
[41]	M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope. Linear Algebra and Its Applications (LAA),223/224 (1995), 439–461. · Zbl 0835.90078
[42]	J. Löfberg, YALMIP: A toolbox for modeling and optimization in MATLAB. Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
[43]	H.D. Mittelmann, An independent benchmarking of SDP and SOCP solvers. Math. Programming Ser. B,95 (2003), 407–430. · Zbl 1030.90080
[44]	R.E. Moore, Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979. · Zbl 0417.65022
[45]	A. Nemirovskii, Lectures on Modern Convex Optimization. 2003.
[46]	Y. Nesterov, Long-step strategies in interior-point primal-dual methods. Math. Programming,76 (1997), 47–94. · Zbl 0881.90108
[47]	Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, 1994. · Zbl 0824.90112
[48]	Y.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res.,22 (1997), 1–42. · Zbl 0871.90064
[49]	NETLIB Linear Programming Library. http://www.netlib.org/lp.
[50]	A. Neumaier, Interval Methods for Systems of Equations. Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 1990. · Zbl 0715.65030
[51]	A. Neumaier, Introduction to Numerical Analysis. Cambridge University Press, 2001. · Zbl 0980.65001
[52]	A. Neumaier, Complete search in continuous global optimization and constraint satisfaction. Acta Numerica, Vol. 13, A. Iserles (eds.), Cambridge University Press, 2004, 271–369. · Zbl 1113.90124
[53]	A. Neumaier and O. Shcherbina, Safe bounds in linear and mixed-integer programming. Mathematical Programming, Ser. A,99 (2004), 283–296. · Zbl 1098.90043
[54]	J. von Neumann and H.H. Goldstine, Numerical inverting of matrices of high order. Bull. Amer. Math. Soc.,53 (1947), 1021–1099. · Zbl 0031.31402
[55]	S. Oishi and S.M. Rump, Fast verification of solutions of matrix equations. Numer. Math.,90 (2002), 755–773. · Zbl 0999.65015
[56]	S. Oishi, K. Tanabe, T. Ogita and S.M. Rump, Convergence of Rump’s method for inverting arbitrarily ill-conditioned matrices. J. Comput. Appl. Math.,205 (2007), 533–544. · Zbl 1120.65040
[57]	F. Ordóñez and R.M. Freund, Computational experience and the explanatory value of condition measures for linear optimization. SIAM J. Optimization (SIOPT),14 (2003), 307–333. · Zbl 1046.90001
[58]	A.L. Peressini, Ordered Topological Vector Spaces. Harper and Row, 1967. · Zbl 0169.14801
[59]	J. Renegar, Some perturbation theory for linear programming. Mathematical Programming,65 (1994), 79–91. · Zbl 0818.90073
[60]	J. Renegar, Linear programming, complexity theory, and elementary functional analysis. Mathematical Programming,70 (1995), 279–351, citeseer.ist.psu.edu/renegar95linear.html. · Zbl 0855.90085
[61]	S.M. Rump, Solving algebraic problems with high accuracy (Habilitationsschrift), A New Approach to Scientific Computation, U.W. Kulisch and W.L. Miranker (eds.), Academic Press, New York, 1983, 51–120.
[62]	S.M. Rump, Validated solution of large linear systems. Validation Numerics: Theory and Applications, R. Albrecht, G. Alefeld and H.J. Stetter (eds.), Computing Supplementum, Vol. 9, Springer, 1993, 191–212. · Zbl 0837.65013
[63]	S.M. Rump, INTLAB–interval laboratory, a Matlab toolbox for verified computations, Version 5.1, 2005.
[64]	S.M. Rump, Error bounds for extremely ill-conditioned problems. Proceedings of 2006 International Symposium on Nonlinear Theory and Its Applications, Bologna, Italy, September 11–14, 2006.
[65]	S.M. Rump, INTLAB–interval laboratory, the Matlab toolbox for verified computations, Version 5.3, 2006.
[66]	S.M. Rump and T. Ogita, Super-fast validated solution of linear systems. Special issue on scientific computing, computer arithmetic, and validated numerics (SCAN 2004), Journal of Computational and Applied Mathematics (JCAM),199 (2006), 199–206. · Zbl 1108.65020
[67]	H.H. Schaefer, Banach lattices and positive operators. Springer, 1974. · Zbl 0296.47023
[68]	J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software,11 (1999), 625–653. · Zbl 0973.90526
[69]	J.F. Sturm, Central region method. High Performance Optimization, J.B.G. Frenk, C. Roos, T. Terlaky and S. Zhang (eds.), Kluwer Academic Publishers, 2000, 157–194.
[70]	L. Tuncel, Generalization of primaldual interior-point methods to convex optimization problems in conic form. Found. Comput. Math.,1 (2001), 229–254. · Zbl 1017.90126
[71]	A.M. Turing, Rounding-off errors in matrix processes. Quarterly J. of Mechanics & App. Maths.,1 (1948), 287–308. · Zbl 0033.28501
[72]	R.H. Tütüncü, K.C. Toh and M.J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program.,95 (2003), 189–217. · Zbl 1030.90082
[73]	P. Van Hentenryck, P. Michel and Y. Deville, Numerica: A Modelling Language for Global Optimization. MIT Press, Cambridge, 1997.
[74]	H. Wolkowicz, Semidefinite and Cone Programming Bibliography, Comments. http://orion.uwaterloo.ca/\(\sim\)hwolkowi/henry/book/fronthandbk.d/sdpbibliog.pdf.
[75]	H. Wolkowicz, R. Saigal and L. Vandenberghe (eds.), Handbook of Semidefinite Programming. International Series in Operations Research and Management Science, Vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. · Zbl 0951.90001
[76]	M. Yamashita, K. Fujisawa and M. Kojima, Implementation and evaluation of SDPA 6.0. Optimization Methods and Software,18 (2003), 491–505. · Zbl 1106.90366