Gaining or losing perspective

DOI10.1007/S10898-021-01055-6zbMATH Open1490.90199arXiv2001.01435OpenAlexW4206289127MaRDI QIDQ2124806FDOQ2124806

Authors: Jon Lee, Daphne Skipper, Emily Speakman 

Publication date: 11 April 2022

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

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.

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

Recommendations

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

zbMATH Keywords

volumeintegerpolytoperelaxationmixed-integer nonlinear optimizationperspectiveexponential conehigher-dimensional power cone

Mathematics Subject Classification ID

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

Cites Work

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

Uses Software

• SDPT3
• CVX

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)