Optimization Online


A Reformulation-Linearization Technique for Optimization over Simplices

Aras Selvi (a.selvi19***at***imperial.ac.uk)
Dick den Hertog (d.denhertog***at***uva.nl)
Wolfram Wiesemann (ww***at***imperial.ac.uk)

Abstract: We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added to tighten the relaxation, is vacuously satisfied and can thus be omitted, and (ii) the number of decision variables in the RLT relaxation can be reduced from O(n^2) to O(n). Taken together, both observations allow us to reduce computation times by up to several orders of magnitude. Our results can be specialized to indefinite quadratic optimization problems over simplices and extended to non-convex optimization problems over the Cartesian product of two simplices as well as specific classes of polyhedral and non-convex feasible regions. Our numerical experiments illustrate the promising performance of the proposed framework.

Keywords: Reformulation-Linearization Technique, Global Optimization, Semidefinite Optimization

Category 1: Global Optimization

Category 2: Global Optimization (Theory )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Selvi A, Den Hertog D, Wiesemann W (November 2020) A Reformulation-Linearization Technique for Optimization over Simplices. Corresponding author: a.selvi19@imperial.ac.uk

Download: [PDF]

Entry Submitted: 11/06/2020
Entry Accepted: 11/06/2020
Entry Last Modified: 05/07/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