Gaining or losing perspective

DOI10.1007/S10898-021-01055-6MaRDI QIDQ2124806zbMATH OpenOpenAlexFDO

Authors Jon Lee, Daphne Skipper, Emily Speakman

Publication date 11 April 2022

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.01435

zbMATH Keywords

volumeintegerpolytoperelaxationmixed-integer nonlinear optimizationperspectiveexponential conehigher-dimensional power cone

Mathematics Subject Classification ID

Nonlinear programming (90C30) Mixed integer programming (90C11)

Abstract: We study MINLO (mixed-integer nonlinear optimization) formulations of the disjunction $xin0cup[l,u]$, where $z$ is a binary indicatorof $xin[l,u]$ ($u>ell>0$), and $y$ "captures" $f(x)$, which is assumed to be convex on its domain $[l,u]$, but otherwise $y=0$ when $x=0$. This model is useful when activities have operating ranges, we pay a fixed cost for carrying out each activity, and costs on the levels of activities are convex. Using volume as a measure to compare convex bodies, we investigate a variety of continuous relaxations of this model, one of which is the convex-hull, achieved via the "perspective reformulation" inequality $ygeqzf(x/z)$. We compare this to various weaker relaxations, studying when they may be considered as viable alternatives. In the important special case when $f(x):=x^p$, for $p>1$, relaxations utilizing the inequality $y{z}^{q}geq{x}^p$, for $qin[0,p-1]$, are higher-dimensional power-cone representable, and hence tractable in theory. One well-known concrete application (with $f(x):=x^2$) is mean-variance optimization (in the style of Markowitz), and we carry out some experiments to illustrate our theory on this application.

Recommendations

• A Different Angle on Perspective
• A new perspective on finding the viewpoint
• scientific article; zbMATH DE number 1368683
• Putting objects in perspective

Cites work

• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• A decomposition of 2-weak vertex-packing polytopes
• A strong conic quadratic reformulation for machine-job assignment with controllable processing times
• Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes
• Experimental validation of volume-based comparison for double-McCormick relaxations
• Geometric comparison of combinatorial polytopes
• More Virtuous Smoothing
• Nonlinear programming
• On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
• Optimal cutting planes from the group relaxations
• Perspective cuts for a class of convex 0-1 mixed integer programs
• Perspective reformulations of mixed integer nonlinear programs with indicator variables
• Quantifying double McCormick
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• The volume of relaxed Boolean-quadric and cut polytopes
• Theoretical challenges towards cutting-plane selection
• Virtuous smoothing for global optimization
• Volume computation for sparse Boolean quadric relaxations

Cited in

(5)

• A new dual-based cutting plane algorithm for nonlinear adjustable robust optimization
• Gaining or Losing Perspective for Convex Multivariate Functions on a Simplex
• Perspective cuts for a class of convex 0-1 mixed integer programs
• Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions
• Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions

Describes a project that uses

Uses Software

• CVX
• SDPT3

This page was built for publication: Gaining or losing perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2124806)