Abstract
In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.
Similar content being viewed by others
References
Alizadeh, F. (1995) Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM Journal of Optimization 5(1), 13–51.
Audet, C., Hansen, P. Jaumard, B. and Savard, G. (2000) Branch and Cut Algorithm for Nonconvex Quadratically Constrained Quadratic Programming. Mathematical Programming 87(1), 131–152.
Bazaraa, M. S., Sherali, H. D. and Shetty, C. M., (1993) Nonlinear Programming Theory and Applications, Wiley, New York, NY, second edition.
Bertsimas, D. and Ye, Y. (1998) Semidefinite Relaxations,Multivariate Normal Distributions and Order Statistics. In: D.-Z. Du and P. M. Pardalos (eds.): Handbook of Combinatorial Optimization, Vol. 3. Kluwer Academic Publishers, pp. 1–19.
Burer, S. and Monteiro, R. (1998) A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization. Presented at the ISMP Conference, Atlanta, GA.
Goemans, M. and Williamson, D. (1995), Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming Journal of the Association for Computational Machinery 42(6), 1115–1145.
Nowak, I. (1998) A Global Optimality Criterion for Non-Convex Quadratic Programming Over a Simplex. Pre-Print 98–17, Humboldt University, Berlin. Available online at http://wwwiam. mathematik.hu-berlin.de/ivo/ivopages/work.html.
Paige, C.C. (1972) Computational Variants of the Lanczos Method for the Eigen-problems. Journal of the Institute of Mathematics and Its Applications 10, 373–381.
Ramana, M. and Goldman, A. J. (1995), Some Geometric Results in Semidefinite Programming. Journal of Global Optimization 7, 33–50.
Ramana, M. and Pardalos, P. M. (1996) Semidefinite Programming. In: T. Terlaky (ed.): Interior Point Methods of Mathematical Programming. Kluwer Academic Publishers, Dordrecht, pp. 369–398.
Sherali, H. D. and Adams, W. P. (1999), A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Boston, MA: Kluwer Academic Publishing.
Sherali, H. D. and Tuncbilek, C. H. (1992), A Global Optimization Algorithm for Polynomial Programming PRoblems Using a Reformulation-Linearization Technique. Journal of Global Optimization 2, 101–112.
Sherali, H. D. and Tuncbilek, C. H. (1997), Reformulation-Linearization/Convexification Relaxations for Univariate and Multivariate Polynomial Programming Problems. Operations Research Letters 21(1), 1–10.
Sherali, H. D. and Wang, H. (2001), Global Optimization of Nonconvex Factorable Programming Problems. Mathematical Programming 89(3), 459–478.
Shor, N. Z. (1998), Nondifferentiable Optimization and Polynomial Problems. Boston, MA: Kluwer Academic Publishing.
Todd, M. J. (1998), Semidefinite Programming Applications, Duality, and Interior-Point Methods. Presented at the Fall INFORMS meeting, Seattle,WA. Also available on the WorldWide Web at http://www.orie.cornell.edu/mike-todd/todd.html.
Vandenbergh, L. and Boyd, S. (1996), Semidefinite Programming. SIAM Review 38(1), 49–95.
Vanderbei, R.J. and Benson, H. Y. (2000), On Formulating Semidefinite Programming Problems as Smooth Convex Nonlinear Optimization Problems. Working paper, Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ.
Wolkowicz, H., Saigal, R. and Vandenbergh, L. 2000, Handbook of Semidefinite Progamming: Theory and Algorithms, and Applications. Boston, MA: Kluwer Academic Publishers.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sherali, H.D., Fraticelli, B.M.P. Enhancing RLT relaxations via a new class of semidefinite cuts. Journal of Global Optimization 22, 233–261 (2002). https://doi.org/10.1023/A:1013819515732
Issue Date:
DOI: https://doi.org/10.1023/A:1013819515732