TU Darmstadt / ULB / TUprints

Optimality Conditions and Numerical Methods for a Continuous Reformulation of Cardinality Constrained Optimization Problems

Bucher, Max (2018)
Optimality Conditions and Numerical Methods for a Continuous Reformulation of Cardinality Constrained Optimization Problems.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
Text
mbucher_cardinality_reformulation180919.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Optimality Conditions and Numerical Methods for a Continuous Reformulation of Cardinality Constrained Optimization Problems
Language: English
Referees: Schwartz, Prof. Dr. Alexandra ; Kanzow, Prof. Dr. Christian
Date: 5 April 2018
Place of Publication: Darmstadt
Date of oral examination: 1 June 2018
Abstract:

Nonlinear constrained optimization problems can be used to model practical and theoretical questions from a vast range of areas in science and industry. In this thesis, we consider a certain class of these problems: cardinality constrained optimization problems. The goal is to minimise a, possibly nonlinear, objective function subject to given constraints, which we also allow to be nonlinear. The cardinality constraint is of our particular interest. It restricts the maximum number of nonzero components of a feasible vector. Cardinality constraints play an important role in a range of applications such as portfolio optimization, compressed sensing as well as in logistics.

Since the cardinality constraint is given by a discontinuous function, theoretical results and methods from nonlinear optimization cannot be readily applied. In this thesis, we consider an approach by Burdakov et al. (2016): a reformulation of the cardinality constraint with a continuous auxiliary variable. This reformulation bears strong similarities to a mathematical program with complementarity constraints (MPCC). Similarly, it violates common constraint qualifications which ensure that first order optimality conditions hold at a local minimum. For this reason custom constraint qualifications and first order optimality condition were introduced by Burdakov et al. (2016) and Červinka et al. (2016).

In this thesis we follow the approach by Burdakov et. al. (2016). We introduce new second order optimality conditions for the reformulation which hold under custom constraint qualifications. These include a necessary second order optimality condition, a sufficient second order optimality condition and a result on the local uniqueness of stationary points. Additionally, we deduce counterparts of those results for the original cardinality constrained problem. Moreover, the existence of a local error bound for the reformulation is shown. These optimality conditions as well as the result on the existence of a local error bound are subsequently used for the convergence theories of numerical methods.

In this thesis, we furthermore place emphasis on numerical methods. We proof exactness of a penalty term using the existence of a local error bound. For the case that non negativity constraints are additionally present, we consider an $\ell^1$-penalty term. This special case occurs, for instance, in portfolio optimization. For this approach, we show that Karush-Kuhn-Tucker points of a penalised problem, for increasing penalty parameters, fulfil a necessary optimality condition for the reformulation in the limit.

Furthermore, we consider the application of a sequential quadratic programming (SQP) method to the reformulation by using a piecewise decomposition of the feasible set. Our theoretical results yield an explanation for the results delivered by a (standard) SQP solver applied to the reformulation.

Moreover, we consider regularisation methods for the reformulation. We prove convergence of a Scholtes-type regularisation and an exponential regularisation. The former already proved to perform well numerically for MPCCs. Using the second order optimality conditions, we expand the convergence theory for this method. We then show how the approach can be used to expand the convergence theory of a whole class of regularisation methods.

Subsequently we present and discuss computational results. We use the reformulation as a model for sparse portfolios, which we construct using historical market data. For various time spans these portfolios yield a better Sharpe-ratio than an equal-weight portfolio.

Additionally, we present computational results of the numerical methods for the reformulation. We test the methods for portfolio optimization problems using different risk measures and a range of test cases. The application of the regularisation methods yields better results than a commercial solver for nonlinear optimization problems. Among the penalty methods, the $\ell^1$-penalty method yields the best results. If the objective is to compute a good solution in a short amount of time, the Scholtes-type regularisation compares favourably against a commercial global solver, as further numerical results indicate.

Alternative Abstract:
Alternative AbstractLanguage

In einer Vielzahl von Anwendungen spielen nichtlineare restringierte Optimierungsprobleme eine Rolle. Gegenstand dieser Arbeit sind nichtlineare Optimierungsprobleme mit einer Kardinalitätsrestriktion. Durch diese Nebenbedingung wird die Anzahl der Komponenten eines zulässigen Vektors, die ungleich Null sind, beschränkt. Zu den Anwendungen von Kardinalitätsrestriktionen zählen unter anderem Portfolio-Optimierung, Compressed Sensing, sowie logistische Problemstellungen.

Da die Kardinalitätsrestriktion durch eine unstetige Funktion beschrieben wird, ist die Anwendung von herkömmlichen Verfahren aus der nichtlinearen Optimierung nicht ohne weiteres möglich. Eine Möglichkeit ist die Anwendung von Verfahren aus der diskreten Optimierung auf eine Umformulierung mit Binärvariablen.

In dieser Arbeit befassen wir uns mit einem anderen Ansatz von Burdakov et al. (2016): Mittels kontinuierlicher Hilfsvariablen wird die Kardinalitätsrestriktion umformuliert, wodurch auch nichtlineare Probleme abgedeckt werden. Die Umformulierung weist Ähnlichkeit zu einem Optimierungsproblem mit Komplementaritätsnebenbedingungen (MPCC) auf und verletzt ebenfalls Bedingungen (Constraint Qualifications), unter denen Optimalitätsbedingungen erster Ordnung in einem lokalen Minimum gelten. Aus diesem Grund wurden von Burdakov et al. (2016) und Červinka et al. (2016) angepasste Optimalitätsbedingungen erster Ordnung hergeleitet.

Diese Arbeit knüpft an diese Ergebnisse an und enthält neue Optimalitätsbedingungen zweiter Ordnung für die Umformulierung. Diese gelten ebenfalls unter angepassten Constraint Qualifications, von denen man, im Gegensatz zu herkömmlichen Constraint Qualifications, annehmen kann, dass sie für die Umformulierung erfüllt sind. Wir leiten eine notwendige Optimalitätsbedingung zweiter Ordnung, eine hinreichende Optimalitätsbedingung zweiter Ordnung sowie ein Ergebnis zur Eindeutigkeit stationärer Punkte her. Zusätzlich formulieren wir diese Bedingungen bezüglich des ursprünglichen Problems. Diese Optimalitätsbedingungen können beispielsweise benutzt werden, um zu überprüfen, ob ein stationärer Punkt tatsächlich ein lokales Minimum ist. Für die hinreichende Optimalitätsbedingung zweiter Ordnung verwenden wir eine schwächere Voraussetzung als in der Theorie für herkömmliche nichtlineare Optimierungsprobleme. Ferner wird die Existenz einer lokalen Fehlerschranke für die Umformulierung hergeleitet. Sowohl die Optimalitätsbedingungen zweiter Ordnung als auch das Ergebnis zur Existenz einer lokalen Fehlerschranke werden anschließend für die Konvergenztheorie numerischer Verfahren verwendet.

Diese numerischen Verfahren stellen einen weiteren Schwerpunkt der Arbeit dar. Mit Hilfe des Ergebnisses zur Existenz einer lokalen Fehlerschranke leiten wir einen exakten Strafterm her. Für den Fall, dass Nichtnegativitätsnebenbedingungen vorhanden sind, betrachten wir zudem einen $\ell^1$-Strafterm. Dieser Spezialfall ist zum Beispiel in der Portfolio-Optimierung von Interesse. Wir zeigen, dass Karush-Kuhn-Tucker Punkte eines Hilfsproblems, welches den $\ell^1$-Strafterm verwendet, für wachsende Strafparameter im Grenzübergang eine notwendige Optimalitätsbedingung für die Umformulierung erfüllen.

Zusätzlich untersuchen wir die Anwendung eines Sequential Quadratic Programming (SQP) Verfahrens auf die Umformulierung theoretisch, wofür wir eine Zerlegung des ursprünglichen Optimierungsproblems verwenden. Unsere Ergebnisse liefern eine mögliche Erklärung für das Konvergenzverhalten eines SQP Verfahrens, welches wir im letzten Kapitel der Arbeit beobachten.

Darüber hinaus übertragen wir Regularisierungsverfahren auf die Umformulierung. Wir zeigen die Konvergenz einer Scholtes-artigen Regularisierung und einer Exponential Regularisierung. Erstere lieferte bereits für MPCCs gute numerische Ergebnisse. Mit Hilfe der Optimalitätsbedingungen zweiter Ordnung bauen wir die Konvergenztheorie für diese Regularisierung weiter aus und zeigen, wie man dieses Vorgehen auf weitere Regularisierungsverfahren übertragen kann.

Anschließend präsentieren wir numerische Ergebnisse. Wir verwenden die Umformulierung als Modell für dünnbesetzte Portfolios, die wir mit Hilfe historischer Kursentwicklungen konstruieren. Diese Portfolios weisen für verschiedene Zeiträume ein höheres Sharpe-Ratio als ein gleichverteiltes Portfolio auf. Die Ergebnisse sprechen für die Umformulierung als Modell für dünnbesetzte Portfolios.

Zusätzlich werden numerische Ergebnisse der Verfahren für die Umformulierung präsentiert und diskutiert. Wir testen die Verfahren an Portfolio-Optimierungsproblemen mit verschiedenen Zielfunktionen und für eine Reihe von Testfällen. Die Anwendung von Regularisierungsverfahren liefert im Großteil der Fälle bessere Ergebnisse als ein kommerzieller Löser für nichtlineare Optimierungsprobleme. Unter den Strafkostenansätzen ist der $\ell^1$-Strafterm vielversprechend, welcher sich für bestimmte Zielfunktionen ebenfalls gegen den kommerziellen Löser durchsetzen kann. Gegeben der Zielsetzung eine gute (aber nicht notwendigerweise die globale) Lösung in möglichst kurzer Zeit zu berechnen, vergleichen wir abschließend Ergebnisse der Scholtes-artigen Regularisierung mit Ergebnissen eines Lösers für gemischt-ganzzahlige Probleme.

German
URN: urn:nbn:de:tuda-tuprints-77402
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics
04 Department of Mathematics > Optimization
04 Department of Mathematics > Optimization > Nonlinear Optimization
Date Deposited: 25 Sep 2018 12:24
Last Modified: 09 Jul 2020 02:14
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/7740
PPN: 437022536
Export:
Actions (login required)
View Item View Item