We discuss an application of the well-known Multiplicative Weights Update (MWU) algorithm to non-convex and mixed-integer nonlinear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of Markowitz' portfolio selection problems. It turns out that, on top of giving a relative approximation guarantee, the MWU is competitive with a simple Multi-Start algorithm, specially on problems exhibiting many nonconvex terms.
Citation
Working paper, Ecole Polytechnique, September 2015