Optimization Online


A multiplicative weights update algorithm for MINLP

Luca Mencarelli(mencarelli***at***lix.polytechnique.fr)
Youcef Sahraoui(sahraoui***at***lix.polytechnique.fr)
Leo Liberti(liberti***at***lix.polytechnique.fr)

Abstract: 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.

Keywords: Multiplicative Weights Update, MINLP, Distance Geometry Problem, Hydro Unit Commitment, Portfolio Selection

Category 1: Global Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Working paper, Ecole Polytechnique, September 2015

Download: [PDF]

Entry Submitted: 09/16/2015
Entry Accepted: 10/01/2015
Entry Last Modified: 09/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society