Optimization Online


Convex Maximization via Adjustable Robust Optimization

Aras Selvi (a.selvi19***at***imperial.ac.uk)
Aharon Ben-Tal (abental***at***technion.ac.il)
Ruud Brekelmans (r.c.m.brekelmans***at***uvt.nl)
Dick den Hertog (d.denhertog***at***uvt.nl)

Abstract: Maximizing a convex function over convex constraints is an NP-hard problem in general. We prove that such a problem can be reformulated as an adjustable robust optimization (ARO) problem where each adjustable variable corresponds to a unique constraint of the original problem. We use ARO techniques to obtain approximate solutions to the convex maximization problem. In order to demonstrate the complete approximation scheme, we distinguish the case where we have just one nonlinear constraint and the case where we have multiple linear constraints. Concerning the first case, we give three examples where one can analytically eliminate the adjustable variable and approximately solve the resulting static robust optimization problem efficiently. More specifically, we show that the norm constrained log-sum-exp (geometric) maximization problem can be approximated by (convex) exponential cone optimization techniques. Concerning the second case of multiple linear constraints, the equivalent ARO problem can be represented as an adjustable robust linear optimization (ARLO) problem. Using linear decision rules then returns a safe approximation of the constraints. The resulting problem is a convex optimization problem, and solving this problem gives an upper bound on the global optimum value of the original problem. By using the optimal linear decision rule, we obtain a lower bound solution as well. We derive the approximation problems explicitly for quadratic maximization, geometric maximization, and sum-of-max-linear-terms maximization problems with multiple linear constraints. Numerical experiments show that, contrary to the state-of-the-art solvers, we can approximate large-scale problems swiftly with tight bounds. In several cases, we have equal upper and lower bounds, which concludes that we have global optimality guarantees in these cases.

Keywords: nonlinear optimization, convex maximization, adjustable robust optimization

Category 1: Robust Optimization

Category 2: Nonlinear Optimization

Category 3: Global Optimization

Citation: Selvi A, Ben-Tal A, Brekelmans R, Den Hertog D (July 2020) Convex maximization via adjustable robust optimization. Corresponding author: a.selvi19@imperial.ac.uk

Download: [PDF]

Entry Submitted: 07/02/2020
Entry Accepted: 07/02/2020
Entry Last Modified: 09/01/2021

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