Need to relax – but perhaps later? Reflections on modeling sparsity and mixed-binary nonconvex optimization problems

November 12, 2024 3:30PM Singapore (Registration starts at 3:20 PM)

Abstract

In some ML communities, researchers claim that obtaining local solutions of optimality criteria is often sufficient to provide a meaningful and accurate data model in real-world analytics. However, this is simply incorrect and sometimes dangerously misleading, particularly when it comes to highly structured problems involving non-convexity such as discrete decisions (binary variables). This talk will advocate the necessity of research efforts in the quest for global solutions and strong rigorous bounds for quality guarantees, showcased on one of the nowadays most popular domains – cardinality-constrained models. These models try to achieve fairness, transparency and explainability in AI applications, ranging from Math.Finance /Economics to social and life sciences.

From a computational viewpoint, it may be tempting to replace the zero-norm (number of nonzero variables) with surrogates, for the benefit of tractability. We argue that these relaxations come too early. Instead, we propose to incorporate the true zero-norm into the base model and treat this either by MILP relaxations or else by lifting to tractable conic optimization models. Both in practice and in theory, these have proved to achieve much stronger bounds than the usual LP-based ones, and therefore they may, more reliably and based upon exact arguments, assess the quality of proposals coming from other techniques in a more precise way. With some effort invested in the theory (aka later relaxations), the resulting models are still scalable and would guarantee computational performance closer to reality and/or optimality.

joint work with F.d’Onofrio, L.Palagi, B.Peng, Y.Qiu, E.A.Yildirim

About the Speaker

Until his retirement 2023, Immanuel M. Bomze held a chair (full professor) of Applied Mathematics and Statistics at the University of Vienna (THE rank 110 in 2025) and is now active as a Senior Research Associate at various institutions of this university. He has edited one and published four books, as well as over 130 peer-reviewed articles in scientific journals and monographs. He enjoyed cooperation with ninety coauthors from more than a dozen countries in four continents. He was elected Fellow of EurOpt, and later became elected EURO president.

Bomze is an Associate Editor for five international journals. For many international science foundations and councils and for almost 50 scientific journals he acted as a reporting referee. He served as an Editor (Co-EiC) of the European Journal of Operational Research, and since 2021 he serves as sole EiC of the EURO Journal of Computational Optimization.