EUROPT 2024
Abstract Submission

335. Minimization of a sum of pointwise minimum of finite collections of convex functions.

Invited abstract in session TB-2: Solver-based optimization algorithms, stream Conic optimization: theory, algorithms and applications.

Thursday, 10:05 - 11:20
Room: M:O

Authors (first author is the speaker)

1. Guillaume Van Dessel
Mathematical Engineering, UCLouvain
2. François Glineur
ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain)

Abstract

Recently, a few papers tackled the problem of minimizing the sum of a number N of so-called truncated convex functions, i.e. each term of the sum stems as the pointwise minimum between a constant and a convex function. The resulting objective can be expressed as the difference between two convex functions (DC). Hence, celebrated DC algorithms and their variants can be applied. Thanks to a straightforward bi-convex reformulation of the problem, an alternating-minimization (AM) scheme can also provide, hopefully good, local solutions.

In this work, we extend this framework by allowing each term of the sum to be a minimum of a finite number of convex conic representable functions, called components. Accordingly, we propose a family of local methods, dubbed as relaxed alternating minimization (RAM). We provide new lemmas, tailored for the problem at hand, about the inherent concepts of criticality and local optimality and we show, without requiring the strict convexity of the components, that every accumulation point of (RAM) is critical. We show the empirical superiority of (RAM), compared to (AM) and (DC) approaches, on piecewise-linear regression but also multifacility and restricted location problems.

If time allows, we will present our new mixed-integer reformulation for the studied class. In practice, based on the aforementioned lemmas, it can help to produce local optimality certificates or exit directions from neighbourhoods of critical points when using (RAM).

Keywords

Status: accepted

Back to the list of papers