McCormick envelopes

Introduction

Optimization of a nonconvex function f(x) is challenging since it may have multiple locally optimal points and it can take a significant amount of time or effort to determine if the problem has no solution or if the solution is global. Gradient based solvers are unable to certify optimality1. Different techniques are used to address this challenge depending on the characteristics of the problem. One technique used is convex envelopes2:

Given a nonconvex function f(x), g(x) is a convex envelope of f(x) for X $\in$ S if:

·      g(x) is convex underestimator of f(x)

·      g(x)>=h(x) for all convex underestimators h(x)

McCormick Envelopes

In particular, for bilinear (e.g., x*y, x²) Non-Linear Programming (NLP) problems3, the McCormick Envelope is a type of convex relaxation used for optimization.  

In case of an NLP, an LP relaxation is derived by replacing each bilinear term with a new variable and adding four sets of constraints. In the case of an MINLP, an MILP relaxation is derived. This strategy is known as McCormick relaxation.

The LP solution gives a lower bound and any feasible solution gives an upper bound.

As noted by Scott et al4, McCormick envelopes are attractive due to their recursive nature of their definition, which affords wide applicability and easy implementation computationally.  Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures.

Derivation of McCormick Envelopes

Example: Convex Relaxation

Example: Numerical

Application

Conclusion

References

1. Castro, Pedro. "A Tighter Piecewise McCormick Relaxation for Bilinear Problems." (n.d.): n. pag. 3 June 2014. Web. 6 June 2015. <http://minlp.cheme.cmu.edu/2014/papers/castro.pdf
2. You, F (2021). Notes for a lecture on Mixed Integer Non-Linear Programming (MINLP). Archives for SYSEN 5800 Computational Optimization (2021FA), Cornell University, Ithaca, NY.
3. Dombrowski, J. (2015, June 7). Northwestern University Open Text Book on Process Optimization, McCormick Envelopes Retrieved from https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes
4.  Scott, J. K. Stuber, M. D. & Barton, P. I. (2011). Generalized McCormick Relaxations. Journal of Global Optimization, Vol. 51, Issue 4, 569-606 doi: 10.1007/s10898-011-9664-7