Detailansicht
Conic approaches to mixed-integer QPs with complementarity constraints and applications to sparse machine learning models
Bo Peng
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doctor of Philosophy-Doktoratsstudium Wirtschaftswissenschaften: Business Analytics, Logistics and Operations Research
Betreuer*in
Immanuel Bomze
DOI
10.25365/thesis.77650
URN
urn:nbn:at:at-ubw:1-27318.50457.619675-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die Dissertation befasst sich mit gemischt-ganzzahligen (nichtkonvexen) quadratischen Optimierungsproblemen (QPs) mit Komplementaritätsbedingungen (CC), einer wichtigen Unterklasse von quadratischen Optimierungsproblemen unter (linearen und) quadratischen Nebenbedingungen (QCQPs). Diese Probleme dienen als leistungsstarke Modellierungswerkzeuge in verschiedenen Bereichen, darunter interpretierbares maschinelles Lernen, mathematische Finanzen und die Selektion in den Biowissenschaften. Angesichts der Herausforderung, diese Probleme global zu lösen, wird der Fokus nicht auf die direkte Lösung der Probleme gelegt, sondern auf Konvexifizierungstechniken wie lineare konische Relaxationen. Wie in der Dissertation gezeigt wird, liefert eine starke, aber dennoch handhabbare konvexe Relaxation nicht nur eine robuste untere Schranke, sondern ermöglicht auch Heuristiken, die auf der optimalen Lösung der Relaxation basieren, und die einen qualitativ hochwertigen zulässigen Punkt liefern. Diese Relaxationen können zudem in den Branch-and-Bound-Ansatz integriert werden, was einen umfassenden Ansatz zur globalen Lösung der ursprünglichen Probleme bietet. Diese kumulative Dissertation ist in erster Linie als eine Sammlung von (bereits publizierten oder bei international angesehenen Zeitschriften eingereichten) Aufsätzen~\cite{peng2022performance,Bomz23a,bomze2024feature,bomze2024tighter,bomze2023tractable} und einem fast fertiggestellten Artikel organisiert. Die Hauptresultate lassen sich in zwei Teile gliedern. Der erste Teil besteht aus zwei Kapiteln: In Kapitel 2 stelle ich mehrerecompletely positive (CP) Reformulierungen für die QPCCs unter neuen Bedingungen vor, die deutlich weniger restriktiv sind als die in der aktuellen Literatur. Im Wesentlichen codieren die CP-Reformulierungen die Nichtkonvexität mit Hilfe des completely positive cone, eines Matrixkegels, der in der Optimierungsforschung in letzter Zeit zunehmend Beachtung findet. Darüber hinaus werden im Kapitel 3 neuartige und kompakte CP-Reformulierungen für die (nichtkonvexen) QPs mit Kardinalitätsbedingungen vorgeschlagen, basierend auf einer Arbeit, die beinahe zur Einreichung bereit ist. Der zweite Teil (Kapitel 4 und Kapitel 5) konzentriert sich auf handhabbare konvexe Relaxationen, die auf den CP-Reformulierungen basieren, was besonders relevant in realen Anwendungen ist. Für Standard-Quadratische-Optimierungsprobleme (StQPs) unter Kardinalit\"atsbedingungen wird ein analytischer Vergleich dieser handhabbaren Relaxationen vorgenommen, was zu kompakteren hybriden Relaxationen führt. Des Weiteren werden neuartige und rechnerisch skalierbare Relaxationen für die Merkmalsauswahl in Support-Vektor-Maschinen (SVMs) vorgeschlagen, ein weit verbreitetes Werkzeug im überwachten maschinellen Lernen. In diesem Zusammenhang verbessert die Kardinalitätsbedingung die Interpretierbarkeit der resultierenden KI-Modelle. Umfangreiche numerische Experimente belegen die Effektivität und Effizienz dieser innovativen Relaxationen.
Abstract
(Englisch)
The thesis addresses mixed-integer (nonconvex) quadratic optimization problems (QPs) with complementarity constraints (CC), a crucial subclass of quadratically constrained quadratic optimization problems (QCQPs). These problems serve as powerful modeling tools in various fields, including interpretable machine learning, mathematical finance, and selection in biosciences. Given the challenge of solving these problems globally, rather than solving the problems directly, the focus is placed on convexification techniques, such as linear conic relaxations. As demonstrated in the thesis, a tight yet tractable convex relaxation not only provides a robust lower bound but also yields a high-quality feasible point through heuristics based on the optimal solution of the relaxation. These relaxations can be further integrated into the branch-and-bound framework, offering a comprehensive approach for globally solving the original problems. This cumulative thesis is primarily organized as a collection of papers already published or submitted to internationally renowned journals~\cite{peng2022performance,Bomz23a,bomze2024feature,bomze2024tighter,bomze2023tractable} and a nearly complete work, and the main results can be divided into two parts. The first part consists of two chapters: In Chapter 2, I establish several completely positive (CP) reformulations for the QPCCs under new conditions that are significantly less restrictive than those in the current literature. Essentially, CP reformulations package the nonconvexity into the completely positive cone, a matrix cone that has received increasing attention in the optimization domain recently. Additionally, novel and compact CP reformulations are proposed for the (nonconvex) QPs involving a cardinality term in Chapter 3, which is based on a work nearing completion to be ready for submission. The second part (Chapters 4 and 5) focuses on tractable convex relaxations based on the CP reformulations, which are of particular interest in real-world applications. For sparse standard quadratic optimization problems (StQPs), an analytical comparison is made among these tractable relaxations, resulting in more compact hybrid relaxations. Furthermore, novel and computationally scalable relaxations are proposed for feature selection in support vector machines (SVMs), a widely used tool in supervised machine learning. In this context, the cardinality constraint enhances the interpretability of the resulting AI models. Extensive numerical experiments demonstrate the effectiveness and efficiency of these innovative relaxations.
Schlagwörter
Schlagwörter
(Deutsch)
Quadratische Optimierung Completely Positive Reformulierung Maschinelles Lernen Komplementaritätsbedingung
Autor*innen
Bo Peng 
Haupttitel (Englisch)
Conic approaches to mixed-integer QPs with complementarity constraints and applications to sparse machine learning models
Publikationsjahr
2024
Umfangsangabe
xi, 109 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Kurt Anstreicher ,
Veronica Piccialli
Klassifikation
31 Mathematik > 31.99 Mathematik. Sonstiges
AC Nummer
AC17429175
Utheses ID
73351
Studienkennzahl
UA | 794 | 370 | 403 |