Minimizing a sum of clipped convex functions

DOI10.1007/S11590-020-01565-4MaRDI QIDQ2228412zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 17 February 2021

Published in Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationmixed-integer programmingrobust statistics

Mathematics Subject Classification ID

Mixed integer programming (90C11) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We consider the problem of minimizing a sum of clipped convex functions; applications include clipped empirical risk minimization and clipped control. While the problem of minimizing the sum of clipped convex functions is NP-hard, we present some heuristics for approximately solving instances of these problems. These heuristics can be used to find good, if not global, solutions and appear to work well in practice. We also describe an alternative formulation, based on the perspective transformation, which makes the problem amenable to mixed-integer convex programming and yields computationally tractable lower bounds. We illustrate one of our heuristic methods by applying it to various examples and use the perspective transformation to certify that the solutions are relatively close to the global optimum. This paper is accompanied by an open-source implementation.

Recommendations

• Minimization of the sum of minima of convex functions and its application to clustering
• Application of the clipping procedure to the binary minimization of a quadratic functional
• A general system for heuristic minimization of convex functions over non-convex sets
• scientific article; zbMATH DE number 4010217
• Solution methodologies for minimizing a sum of pointwise minima of two functions

Cites work

• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A perspective-based convex relaxation for switched-affine optimal control
• An e-E-insensitive support vector regression machine
• Analysis of multi-stage convex relaxation for sparse regularization
• Convex Analysis
• Convex analysis approach to d. c. programming: Theory, algorithms and applications
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Efficient and Robust Image Restoration Using Multiple-Feature L2-Relaxed Sparse Analysis Priors
• Graph implementations for nonsmooth convex programs
• scientific article; zbMATH DE number 3574917 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Learning sparse classifiers with difference of convex functions algorithms
• Minimizing Sum of Truncated Convex Functions and Its Applications
• On the limited memory BFGS method for large scale optimization
• Outlier detection using nonconvex penalized regression
• Perspective reformulation and applications
• Perspective reformulations of mixed integer nonlinear programs with indicator variables
• Reducibility among combinatorial problems
• Robust regression: Asymptotics, conjectures and Monte Carlo
• Robust Statistics
• The Concave-Convex Procedure
• Variations and extension of the convex-concave procedure

Cited in

(5)

• Solution methodologies for minimizing a sum of pointwise minima of two functions
• sccf
• Simultaneous feature selection and outlier detection with optimality guarantees
• The ABC of DC programming
• Application of the clipping procedure to the binary minimization of a quadratic functional

Describes a project that uses

Uses Software

• L-BFGS

This page was built for publication: Minimizing a sum of clipped convex functions

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