- Author:
- Mahdi Namazifar,
- Adviser:
- Jeffrey T. Linderoth
In this thesis we study convex relaxations for global optimization problems involving multilinear functions. Multilinear functions appear frequently in global optimization problems and finding strong convex relaxations for these functions is crucial for algorithms in global optimization, especially spatial branch-and-bound. We study different linear relaxations for multilinear functions and analyze their comparative strength.
We also, present a novel method to build linear relaxations for problems containing multilinear functions. The new relaxation is often close to the strength of the convex envelopes of multilinear functions, but prohibits the relaxation from becoming unmanageably large. Numerical results show that this relaxation can be quite effective for finding strong linear relaxations for problems involving multilinear functions.
Finally, we study the convex hull of a set defined by a simple monomial constraint, and we present linear inequalities valid for the convex hull of the set. There are infinitely many of inequalities, so we also present a separation algorithm for these inequalities. We conjecture that these inequalities, along with some other known inequalities, give the convex hull of this important set.
Cited By
- Del Pia A and Khajavirad A (2018). On decomposability of Multilinear sets, Mathematical Programming: Series A and B, 170:2, (387-415), Online publication date: 1-Aug-2018.
- Luedtke J, Namazifar M and Linderoth J (2012). Some results on the strength of relaxations of multilinear functions, Mathematical Programming: Series A and B, 136:2, (325-351), Online publication date: 1-Dec-2012.
Recommendations
Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation
We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme ...
Relaxations of multilinear convex envelopes: dual is better than primal
SEA'12: Proceedings of the 11th international conference on Experimental AlgorithmsBilinear, trilinear, quadrilinear and general multilinear terms arise naturally in several important applications and yield nonconvex mathematical programs, which are customarily solved using the spatial Branch-and-Bound algorithm. This requires a ...