Optimization Online


A Method for Convex Black-Box Integer Global Optimization

Jeffrey Larson(jmlarson***at***anl.gov)
Sven Leyffer(leyffer***at***mcs.anl.gov)
Prashant Palkar(prashant.palkar***at***iitb.ac.in)
Stefan Wild(wild***at***mcs.anl.gov)

Abstract: We study the problem of minimizing a convex function on the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective but, rather, uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings are shown to underestimate the objective in disconnected portions of the domain. Therefore, the union of these conditional cuts provides a nonconvex underestimator of the objective. We propose an algorithm that alternates between updating the underestimator and evaluating the objective function. We prove that the algorithm converges to a global minimum of the objective function on the integer lattice. We present two approaches for representing the underestimator and compare their computational effectiveness. We also compare implementations of our algorithm with existing methods for minimizing functions on the integer lattice. We discuss the noticeable difficulty of this problem class and provide insights into why a computational proof of optimality is challenging even for moderate problem sizes.

Keywords: Derivative-Free Optimization, Integer Optimization, Simulation Optimization, Global Optimization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 03/26/2019
Entry Accepted: 03/26/2019
Entry Last Modified: 03/26/2019

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