Global ETD Search

1	Fenchel duality-based algorithms for convex optimization problems with applications in machine learning and image restoration Heinrich, André 27 March 2013 (has links) (PDF) The main contribution of this thesis is the concept of Fenchel duality with a focus on its application in the field of machine learning problems and image restoration tasks. We formulate a general optimization problem for modeling support vector machine tasks and assign a Fenchel dual problem to it, prove weak and strong duality statements as well as necessary and sufficient optimality conditions for that primal-dual pair. In addition, several special instances of the general optimization problem are derived for different choices of loss functions for both the regression and the classifification task. The convenience of these approaches is demonstrated by numerically solving several problems. We formulate a general nonsmooth optimization problem and assign a Fenchel dual problem to it. It is shown that the optimal objective values of the primal and the dual one coincide and that the primal problem has an optimal solution under certain assumptions. The dual problem turns out to be nonsmooth in general and therefore a regularization is performed twice to obtain an approximate dual problem that can be solved efficiently via a fast gradient algorithm. We show how an approximate optimal and feasible primal solution can be constructed by means of some sequences of proximal points closely related to the dual iterates. Furthermore, we show that the solution will indeed converge to the optimal solution of the primal for arbitrarily small accuracy. Finally, the support vector regression task is obtained to arise as a particular case of the general optimization problem and the theory is specialized to this problem. We calculate several proximal points occurring when using difffferent loss functions as well as for some regularization problems applied in image restoration tasks. Numerical experiments illustrate the applicability of our approach for these types of problems. Konjugierte Dualität Glättungsverfahren Maschinelles Lernen schwache und starke Dualität conjugate duality constraint qualification double smoothing fast gradient algorithm Fenchel duality image deblurring image denoising machine learning regularization support vector machines ddc:510 Konjugierte Dualität Maschinelles Lernen Regularisierung
2	New insights into conjugate duality Grad, Sorin - Mihai 19 July 2006 (has links) (PDF) With this thesis we bring some new results and improve some existing ones in conjugate duality and some of the areas it is applied in. First we recall the way Lagrange, Fenchel and Fenchel - Lagrange dual problems to a given primal optimization problem can be obtained via perturbations and we present some connections between them. For the Fenchel - Lagrange dual problem we prove strong duality under more general conditions than known so far, while for the Fenchel duality we show that the convexity assumptions on the functions involved can be weakened without altering the conclusion. In order to prove the latter we prove also that some formulae concerning conjugate functions given so far only for convex functions hold also for almost convex, respectively nearly convex functions. After proving that the generalized geometric dual problem can be obtained via perturbations, we show that the geometric duality is a special case of the Fenchel - Lagrange duality and the strong duality can be obtained under weaker conditions than stated in the existing literature. For various problems treated in the literature via geometric duality we show that Fenchel - Lagrange duality is easier to apply, bringing moreover strong duality and optimality conditions under weaker assumptions. The results presented so far are applied also in convex composite optimization and entropy optimization. For the composed convex cone - constrained optimization problem we give strong duality and the related optimality conditions, then we apply these when showing that the formula of the conjugate of the precomposition with a proper convex K - increasing function of a K - convex function on some n - dimensional non - empty convex set X, where K is a k - dimensional non - empty closed convex cone, holds under weaker conditions than known so far. Another field were we apply these results is vector optimization, where we provide a general duality framework based on a more general scalarization that includes as special cases and improves some previous results in the literature. Concerning entropy optimization, we treat first via duality a problem having an entropy - like objective function, from which arise as special cases some problems found in the literature on entropy optimization. Finally, an application of entropy optimization into text classification is presented. Composed convex optimization Fenchel - Lagrange Dualität Geometric programming generalized convex optimization ddc:510 Dualitätstheorie Entropie <Informationstheorie> Fenchel Konvexität <Kapitalanlage> Lagrange-Dualität Optimierungsproblem
3	Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators Csetnek, Ernö Robert 14 December 2009 (has links) (PDF) The aim of this work is to present several new results concerning duality in scalar convex optimization, the formulation of sequential optimality conditions and some applications of the duality to the theory of maximal monotone operators. After recalling some properties of the classical generalized interiority notions which exist in the literature, we give some properties of the quasi interior and quasi-relative interior, respectively. By means of these notions we introduce several generalized interior-point regularity conditions which guarantee Fenchel duality. By using an approach due to Magnanti, we derive corresponding regularity conditions expressed via the quasi interior and quasi-relative interior which ensure Lagrange duality. These conditions have the advantage to be applicable in situations when other classical regularity conditions fail. Moreover, we notice that several duality results given in the literature on this topic have either superfluous or contradictory assumptions, the investigations we make offering in this sense an alternative. Necessary and sufficient sequential optimality conditions for a general convex optimization problem are established via perturbation theory. These results are applicable even in the absence of regularity conditions. In particular, we show that several results from the literature dealing with sequential optimality conditions are rediscovered and even improved. The second part of the thesis is devoted to applications of the duality theory to enlargements of maximal monotone operators in Banach spaces. After establishing a necessary and sufficient condition for a bivariate infimal convolution formula, by employing it we equivalently characterize the $\varepsilon$-enlargement of the sum of two maximal monotone operators. We generalize in this way a classical result concerning the formula for the $\varepsilon$-subdifferential of the sum of two proper, convex and lower semicontinuous functions. A characterization of fully enlargeable monotone operators is also provided, offering an answer to an open problem stated in the literature. Further, we give a regularity condition for the weak$^*$-closedness of the sum of the images of enlargements of two maximal monotone operators. The last part of this work deals with enlargements of positive sets in SSD spaces. It is shown that many results from the literature concerning enlargements of maximal monotone operators can be generalized to the setting of Banach SSD spaces. Fenchel-Lagrange Dualität ddc:510 Dualitätstheorie Konvexität Monotoner Operator
4	Über die F-Modul-Struktur von Matlis-Dualen lokaler Kohomologiemoduln Tobisch, Danny 20 November 2017 (has links) In der algebraischen Geometrie und kommutativen Algebra sind die lokalen Kohomologiemoduln seit ihrer Einführung vor gut 50 Jahren von großem Interesse. Dabei handelt es sich um eine mathematische Konstruktion, die Anfang der 60er Jahre von Grothendieck in [Gro67] gemacht wurde, um geometrische Fragen zu beantworten. Mittlerweile ist die Theorie der lokalen Kohomologie ein fester Bestandteil für die Untersuchung von kommutativen noetherschen Ringen. Betrachtet man Ringe als Funktionen auf Räumen, so lassen sich auch geometrische und topologische Inhalte untersuchen. info:eu-repo/classification/ddc/000 ddc:000
5	New insights into conjugate duality Grad, Sorin - Mihai 13 July 2006 (has links) With this thesis we bring some new results and improve some existing ones in conjugate duality and some of the areas it is applied in. First we recall the way Lagrange, Fenchel and Fenchel - Lagrange dual problems to a given primal optimization problem can be obtained via perturbations and we present some connections between them. For the Fenchel - Lagrange dual problem we prove strong duality under more general conditions than known so far, while for the Fenchel duality we show that the convexity assumptions on the functions involved can be weakened without altering the conclusion. In order to prove the latter we prove also that some formulae concerning conjugate functions given so far only for convex functions hold also for almost convex, respectively nearly convex functions. After proving that the generalized geometric dual problem can be obtained via perturbations, we show that the geometric duality is a special case of the Fenchel - Lagrange duality and the strong duality can be obtained under weaker conditions than stated in the existing literature. For various problems treated in the literature via geometric duality we show that Fenchel - Lagrange duality is easier to apply, bringing moreover strong duality and optimality conditions under weaker assumptions. The results presented so far are applied also in convex composite optimization and entropy optimization. For the composed convex cone - constrained optimization problem we give strong duality and the related optimality conditions, then we apply these when showing that the formula of the conjugate of the precomposition with a proper convex K - increasing function of a K - convex function on some n - dimensional non - empty convex set X, where K is a k - dimensional non - empty closed convex cone, holds under weaker conditions than known so far. Another field were we apply these results is vector optimization, where we provide a general duality framework based on a more general scalarization that includes as special cases and improves some previous results in the literature. Concerning entropy optimization, we treat first via duality a problem having an entropy - like objective function, from which arise as special cases some problems found in the literature on entropy optimization. Finally, an application of entropy optimization into text classification is presented. info:eu-repo/classification/ddc/510 ddc:510 Dualitätstheorie Entropie <Informationstheorie> Fenchel Konvexität <Kapitalanlage> Lagrange-Dualität Optimierungsproblem Composed convex optimization Fenchel - Lagrange Dualität Geometric programming generalized convex optimization
6	Sattelpunkte und Optimalitätsbedingungen bei restringierten Optimierungsproblemen Grunert, Sandro 10 June 2009 (has links) (PDF) Sattelpunkte und Optimalitätsbedingungen bei restringierten Optimierungsproblemen Ausarbeitung im Rahmen des Seminars "Optimierung", WS 2008/2009 Die Dualitätstheorie für restringierte Optimierungsaufgaben findet in der Spieltheorie und in der Ökonomik eine interessante Anwendung. Mit Hilfe von Sattelpunkteigenschaften werden diverse Interpretationsmöglichkeiten der Lagrange-Dualität vorgestellt. Anschließend gilt das Augenmerk den Optimalitätsbedingungen solcher Probleme. Grundlage für die Ausarbeitung ist das Buch "Convex Optimization" von Stephen Boyd und Lieven Vandenberghe. Mathematik Sattelpunkte Wirtschaftsmathematik ddc:500 ddc:510 Dualitätstheorie Gleichgewichtspunkt <Spieltheorie> Karush-Kuhn-Tucker-Bedingungen Lagrange-Dualität Optimierung
7	Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators Csetnek, Ernö Robert 08 December 2009 (has links) The aim of this work is to present several new results concerning duality in scalar convex optimization, the formulation of sequential optimality conditions and some applications of the duality to the theory of maximal monotone operators. After recalling some properties of the classical generalized interiority notions which exist in the literature, we give some properties of the quasi interior and quasi-relative interior, respectively. By means of these notions we introduce several generalized interior-point regularity conditions which guarantee Fenchel duality. By using an approach due to Magnanti, we derive corresponding regularity conditions expressed via the quasi interior and quasi-relative interior which ensure Lagrange duality. These conditions have the advantage to be applicable in situations when other classical regularity conditions fail. Moreover, we notice that several duality results given in the literature on this topic have either superfluous or contradictory assumptions, the investigations we make offering in this sense an alternative. Necessary and sufficient sequential optimality conditions for a general convex optimization problem are established via perturbation theory. These results are applicable even in the absence of regularity conditions. In particular, we show that several results from the literature dealing with sequential optimality conditions are rediscovered and even improved. The second part of the thesis is devoted to applications of the duality theory to enlargements of maximal monotone operators in Banach spaces. After establishing a necessary and sufficient condition for a bivariate infimal convolution formula, by employing it we equivalently characterize the $\varepsilon$-enlargement of the sum of two maximal monotone operators. We generalize in this way a classical result concerning the formula for the $\varepsilon$-subdifferential of the sum of two proper, convex and lower semicontinuous functions. A characterization of fully enlargeable monotone operators is also provided, offering an answer to an open problem stated in the literature. Further, we give a regularity condition for the weak$^*$-closedness of the sum of the images of enlargements of two maximal monotone operators. The last part of this work deals with enlargements of positive sets in SSD spaces. It is shown that many results from the literature concerning enlargements of maximal monotone operators can be generalized to the setting of Banach SSD spaces. info:eu-repo/classification/ddc/510 ddc:510 Dualitätstheorie Konvexität Monotoner Operator Fenchel-Lagrange Dualität
8	Perturbative quantization of superstring theory in Anti de-Sitter spaces / integrability in gauge / string dualities Sundin, Per 19 April 2011 (has links) Um das mikroskopische Verhalten der Gravitation zu beschreiben, ist es nötig, Quantenfeldtheorie und allgemeine Relativitätstheorie in einer vereinheitlichten Sprache zu formulieren. Eine Möglichkeit dieses Problem anzugehen ist es, die Punktteilchen der Quantenfeldtheorie durch fadenförmige Strings zu ersetzen. Allerdings erfordert die mathematische Konsistenz, dass sich die String in höherdimensionalen Raum-Zeiten bewegen; dies macht es jedoch sehr schwer, physikalische Konsequenzen zu extrahieren. Eine mögliche Lösung dieses Problems ist die Verwendung von String-Dualitäten, welche die Stringtheorie mittels holographischer Beschreibungen mit Eichtheorien auf dem Rand der Raum-Zeit verbinden. Die Dualitäten sind begründete Vermutungen, die die String- und Eichtheorie bei unterschiedlichen Werten der Kopplung gleichsetzen. Nicht zuletzt deshalb ist eine direkte Überprüfung der Dualitäten schwierig durchführbar. Hier hilft jedoch die sehr bemerkenswerte Tatsache, dass eine verborgene Eigenschaft der Vermutungen Integrabilität zu sein scheint, welche eine Extrapolation zwischen starker und schwacher Kopplung ermöglicht. Desweiteren kann das gesamte Spektrum, in gewissen vereinfachenden Grenzfällen, durch einen kompakten Satz von Bethe-Gleichungen ausgedrückt werden. Die Bethe-Gleichungen, welche aus Eichtheorierechnungen hergeleitet und geraten werden, bieten ein exzellentes Hilfsmittel, die vermuteten Dualitäten zu prüfen. Durch das Vergleichen der Vorhersagen der Gleichungen und expliziten Berechnungen in der Stringtheorie erhält man starke Argumente für die Gültigkeit der Vermutung und der angenommenen Integrabilität. / In this thesis we study superstring theory on AdS$_5\, \times\,$S$^5$, AdS$_3\,\times\,$S$^3$ and $\adsfour$. A shared feature of each theory is that their corresponding symmetry algebras allows for a decomposition under a $\mathbb{Z}_4$ grading. The grading can be realized through an automorphism which allows for a convenient construction of the string Lagrangians directly in terms of graded components. We adopt a uniform light-cone gauge and expand in a near plane wave limit, or equivalently, an expansion in transverse string coordinates. With a main focus on the two critical string theories, we perform a perturbative quantization up to quartic order in the number of fields. Each string theory is, through holographic descriptions, conjectured to be dual to lower dimensional gauge theories. The conjectures imply that the conformal dimensions of single trace operators in gauge theory should be equal to the energy of string states. What is more, through the use of integrable methods, one can write down a set of Bethe equations whose solutions encode the full spectral problem. One main theme of this thesis is to match the predictions of these equations, written in a language suitable for the light-cone gauge we employ, against explicit string theory calculations. We do this for a large class of string states and the perfect agreement we find lends strong support for the validity of the conjectures. Integrabilität String theorie Dualität Gauge theory Integrability String theory Duality Guage theory 530 Physik 29 Physik, Astronomie ddc:530
9	Fenchel duality-based algorithms for convex optimization problems with applications in machine learning and image restoration Heinrich, André 21 March 2013 (has links) The main contribution of this thesis is the concept of Fenchel duality with a focus on its application in the field of machine learning problems and image restoration tasks. We formulate a general optimization problem for modeling support vector machine tasks and assign a Fenchel dual problem to it, prove weak and strong duality statements as well as necessary and sufficient optimality conditions for that primal-dual pair. In addition, several special instances of the general optimization problem are derived for different choices of loss functions for both the regression and the classifification task. The convenience of these approaches is demonstrated by numerically solving several problems. We formulate a general nonsmooth optimization problem and assign a Fenchel dual problem to it. It is shown that the optimal objective values of the primal and the dual one coincide and that the primal problem has an optimal solution under certain assumptions. The dual problem turns out to be nonsmooth in general and therefore a regularization is performed twice to obtain an approximate dual problem that can be solved efficiently via a fast gradient algorithm. We show how an approximate optimal and feasible primal solution can be constructed by means of some sequences of proximal points closely related to the dual iterates. Furthermore, we show that the solution will indeed converge to the optimal solution of the primal for arbitrarily small accuracy. Finally, the support vector regression task is obtained to arise as a particular case of the general optimization problem and the theory is specialized to this problem. We calculate several proximal points occurring when using difffferent loss functions as well as for some regularization problems applied in image restoration tasks. Numerical experiments illustrate the applicability of our approach for these types of problems. info:eu-repo/classification/ddc/510 ddc:510
10	Application of the Duality Theory Lorenz, Nicole 15 August 2012 (has links) (PDF) The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning. First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature. In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above. The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization. We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem. Konjugierte Dualität konvexe Analysis Fencheldualität Lagrangedualität Regularitätsbedingungen schwache Dualität starke Dualität Portfoliooptimierung innere Punktbedingungen Regularitätsbedingungen Risikomaße Support Vektor Regression Suport Vektor Klassifikation Machinelles Lernen Conjugate duality convex duality theory Fenchel duality Lagrange duality Fenchel-Lagrange duality regularity conditions perturbation functions composed convex optimization problems geometric constraints cone constraints weak and strong duality scalar optimization interior point regularity condition conjugate functions convex risk measures convex deviation measures portfolio optimization optimality conditions stochastic programming chance constraints machine learning Tikhonov regularization loss functions Support Vector Regression Support Vector Classification concrete compressive strength ddc:515 Maschinelles Lernen Konjugierte Dualität konvexe Analysis

Search results