Safe Bounds in Semidefinite Programming by Using Interval Arithmetic
Affiliation(s)
1 Computer Science Department, University Dr Moulay Tahar of Saida, Saida, Algeria. 2 Computer Science Department, University Djillali Liabes of SidiBel Abbes, SidiBel Abbes, Algeria.
1 Computer Science Department, University Dr Moulay Tahar of Saida, Saida, Algeria. 2 Computer Science Department, University Djillali Liabes of SidiBel Abbes, SidiBel Abbes, Algeria.
ABSTRACT
Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.
Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.
KEYWORDS
Semidefinite Programming, Interval Arithmetic, Rigorous Error, Bounds, SDPA Solver, Branch and Bound Algorithm
Semidefinite Programming, Interval Arithmetic, Rigorous Error, Bounds, SDPA Solver, Branch and Bound Algorithm
Cite this paper
Derkaoui, O. and Lehireche, A. (2014) Safe Bounds in Semidefinite Programming by Using Interval Arithmetic. American Journal of Operations Research, 4, 293-300. doi: 10.4236/ajor.2014.45028.
Derkaoui, O. and Lehireche, A. (2014) Safe Bounds in Semidefinite Programming by Using Interval Arithmetic. American Journal of Operations Research, 4, 293-300. doi: 10.4236/ajor.2014.45028.
References
[1] Nemirovski, A. (2003) Lectures on Modern Convex Optimization. [2] Ramana, M.V., Tun?el, L. and Wolkowicz, H. (1997) Strong Dality for Semidefinite Programming. SIAM Journal on Optimization, 7, 641-662.
http://dx.doi.org/10.1137/S1052623495288350 [3] Vandenberghe, L. and Boyd, S. (1996) Semidefinite Programming. SIAM Review, 38, 49-95.
http://dx.doi.org/10.1137/1038003 [4] Fujisawa, K. and Kojima, M. (1995) SDPA (Semidefinite Programming Algorithm) Users Manual. Technical Report b-308, Tokyo Institute of Technology. [5] Helmberg, C., Rendl, F., Vanderbei, R. and Wolkowicz, H. (1996) An Interior-Point Method for Semidefinite Programming. SIAM Journal on Optimization, 6, 342-361.
http://dx.doi.org/10.1137/0806020 [6] Vandenberghe, L. and Boyd, S. (1995) Primal-Dual Potential Reduction Method for Problems Involving Matrix Inequalities. Mathematical Programming, Series B, 69, 205-236.
http://dx.doi.org/10.1007/BF01585558 [7] Boyd, S. and Vandenberghe, L. (2004) Convex Optimization. Cambridge University Press, Cambridge.
http://dx.doi.org/10.1017/CBO9780511804441 [8] Krislock, N., Malick, J. and Roupin, F. (2012) Nonstandard Semidefinite Bounds for Solving Exactly 0-1 Quadratic Problems. EURO XXV, Vilnius. [9] Lebbah, Y., Michel, C., Rueher, M., Merlet, J. and Daney, D. (2005) Efficient and Safe Global Constraints for Handling Numerical Constraint Systems. SIAM Journal on Numerical Analysis, 42, 2076-2097.
http://dx.doi.org/10.1137/S0036142903436174 [10] Neumaier, A. (2003) Complete Search in Continuous Global Optimization and Constraint Satisfaction. Acta Numerica. [11] Alefeld, G. and Herzberger, J. (1983) Introduction to Interval Computations. Academic Press, New York. [12] Moore, R.E. (1979) Methods and Applications of Interval Analysis. SIAM, Philadelphia.
http://dx.doi.org/10.1137/1.9781611970906 [13] Neumaier, A. (2001) Introduction to Numerical Analysis. Cambridge University Press, Cambridge.
http://dx.doi.org/10.1017/CBO9780511612916 [14] Jansson, C. (2004) Rigorous Lower and Upper Bounds in Linear Programming. SIAM Journal on Optimization (SIOPT), 14, 914-935.
http://dx.doi.org/10.1137/S1052623402416839 [15] Neumaier, A. and Shcherbina, O. (2004) Safe Bounds in Linear and Mixed-Integer Programming. Mathematical Programming, 99, 283-296. [16] Davis, E. (1987) Constraint Propagation with Interval Labels. Artificial Intelligence, 32, 281-331. [17] Krawczyk, R. (1995) Fehlerabschatzung bei Linearer Optimierung. In: Nickel, K., Ed., Interval Mathematics, Lecture Notes in Computer Science, Vol. 29, Springer, Berlin, 215-222. [18] Jansson, C. (1985) Zur linearen Optimierung mit unscharfen Daten. Dissertation, Fachbereich Mathematik, Universitat Kaiserslautern, Kaiserslautern. [19] Jansson, C. and Rump, S.M. (1991) Rigorous Solution of Linear Programming Problems with Uncertain Data. Zeitschrift für Operations Research, 35, 87-111. [20] Benhamou, F. and Older, W. (1997) Applying Interval Arithmetlc to Real, Integer and Boolean Constraints. Journal of Logic Programming, 32, 1-24. [21] Berkelaar, M. (2005) Lpsolve 5.5, Free Solver, lpsolve.sourceforge.net. Technical Report, Eindhoven University of Technology, Eindhoven. [22] Kearfott, R.B. (1996) Rigorous Global Search: Continuons Problems. [23] Fujisawa, K., Fukuda, M., Kobayashi, K., Kojima, M., Nakata, K., Nakata, M. and Yamashita, M. (2008) SDPA (Semidefinite Programming Algorithm) and SDPA-GMP User’s Manual—Version 7.1.1. [24] Audet, C. (1997) Optimisation globale structurée: Propriétés, équivalences et résolution. Ph.D. Thesis, école Polythecnique de Montréal, Montréal.
[1] Nemirovski, A. (2003) Lectures on Modern Convex Optimization. [2] Ramana, M.V., Tun?el, L. and Wolkowicz, H. (1997) Strong Dality for Semidefinite Programming. SIAM Journal on Optimization, 7, 641-662.
http://dx.doi.org/10.1137/S1052623495288350 [3] Vandenberghe, L. and Boyd, S. (1996) Semidefinite Programming. SIAM Review, 38, 49-95.
http://dx.doi.org/10.1137/1038003 [4] Fujisawa, K. and Kojima, M. (1995) SDPA (Semidefinite Programming Algorithm) Users Manual. Technical Report b-308, Tokyo Institute of Technology. [5] Helmberg, C., Rendl, F., Vanderbei, R. and Wolkowicz, H. (1996) An Interior-Point Method for Semidefinite Programming. SIAM Journal on Optimization, 6, 342-361.
http://dx.doi.org/10.1137/0806020 [6] Vandenberghe, L. and Boyd, S. (1995) Primal-Dual Potential Reduction Method for Problems Involving Matrix Inequalities. Mathematical Programming, Series B, 69, 205-236.
http://dx.doi.org/10.1007/BF01585558 [7] Boyd, S. and Vandenberghe, L. (2004) Convex Optimization. Cambridge University Press, Cambridge.
http://dx.doi.org/10.1017/CBO9780511804441 [8] Krislock, N., Malick, J. and Roupin, F. (2012) Nonstandard Semidefinite Bounds for Solving Exactly 0-1 Quadratic Problems. EURO XXV, Vilnius. [9] Lebbah, Y., Michel, C., Rueher, M., Merlet, J. and Daney, D. (2005) Efficient and Safe Global Constraints for Handling Numerical Constraint Systems. SIAM Journal on Numerical Analysis, 42, 2076-2097.
http://dx.doi.org/10.1137/S0036142903436174 [10] Neumaier, A. (2003) Complete Search in Continuous Global Optimization and Constraint Satisfaction. Acta Numerica. [11] Alefeld, G. and Herzberger, J. (1983) Introduction to Interval Computations. Academic Press, New York. [12] Moore, R.E. (1979) Methods and Applications of Interval Analysis. SIAM, Philadelphia.
http://dx.doi.org/10.1137/1.9781611970906 [13] Neumaier, A. (2001) Introduction to Numerical Analysis. Cambridge University Press, Cambridge.
http://dx.doi.org/10.1017/CBO9780511612916 [14] Jansson, C. (2004) Rigorous Lower and Upper Bounds in Linear Programming. SIAM Journal on Optimization (SIOPT), 14, 914-935.
http://dx.doi.org/10.1137/S1052623402416839 [15] Neumaier, A. and Shcherbina, O. (2004) Safe Bounds in Linear and Mixed-Integer Programming. Mathematical Programming, 99, 283-296. [16] Davis, E. (1987) Constraint Propagation with Interval Labels. Artificial Intelligence, 32, 281-331. [17] Krawczyk, R. (1995) Fehlerabschatzung bei Linearer Optimierung. In: Nickel, K., Ed., Interval Mathematics, Lecture Notes in Computer Science, Vol. 29, Springer, Berlin, 215-222. [18] Jansson, C. (1985) Zur linearen Optimierung mit unscharfen Daten. Dissertation, Fachbereich Mathematik, Universitat Kaiserslautern, Kaiserslautern. [19] Jansson, C. and Rump, S.M. (1991) Rigorous Solution of Linear Programming Problems with Uncertain Data. Zeitschrift für Operations Research, 35, 87-111. [20] Benhamou, F. and Older, W. (1997) Applying Interval Arithmetlc to Real, Integer and Boolean Constraints. Journal of Logic Programming, 32, 1-24. [21] Berkelaar, M. (2005) Lpsolve 5.5, Free Solver, lpsolve.sourceforge.net. Technical Report, Eindhoven University of Technology, Eindhoven. [22] Kearfott, R.B. (1996) Rigorous Global Search: Continuons Problems. [23] Fujisawa, K., Fukuda, M., Kobayashi, K., Kojima, M., Nakata, K., Nakata, M. and Yamashita, M. (2008) SDPA (Semidefinite Programming Algorithm) and SDPA-GMP User’s Manual—Version 7.1.1. [24] Audet, C. (1997) Optimisation globale structurée: Propriétés, équivalences et résolution. Ph.D. Thesis, école Polythecnique de Montréal, Montréal.