Dissertations / Theses on the topic 'Convex duality theory'

The goal of this work is to present a conjugate duality treatment of composed programming as well as to give an overview of some recent developments in both scalar and multiobjective optimization. In order to do this, first we study a single-objective optimization problem, in which the objective function as well as the constraints are given by composed functions. By means of the conjugacy approach based on the perturbation theory, we provide different kinds of dual problems to it and examine the relations between the optimal objective values of the duals. Given some additional assumptions, we verify the equality between the optimal objective values of the duals and strong duality between the primal and the dual problems, respectively. Having proved the strong duality, we derive the optimality conditions for each of these duals. As special cases of the original problem, we study the duality for the classical optimization problem with inequality constraints and the optimization problem without constraints. The second part of this work is devoted to location analysis. Considering first the location model with monotonic gauges, it turns out that the same conjugate duality principle can be used also for solving this kind of problems. Taking in the objective function instead of the monotonic gauges several norms, investigations concerning duality for different location problems are made. We finish our investigations with the study of composed multiobjective optimization problems. In doing like this, first we scalarize this problem and study the scalarized one by using the conjugacy approach developed before. The optimality conditions which we obtain in this case allow us to construct a multiobjective dual problem to the primal one. Additionally the weak and strong duality are proved. In conclusion, some special cases of the composed multiobjective optimization problem are considered. Once the general problem has been treated, particularizing the results, we construct a multiobjective dual for each of them and verify the weak and strong dualities
In dieser Arbeit wird, anhand der sogenannten konjugierten Dualitätstheorie, ein allgemeines Dualitätsverfahren für die Untersuchung verschiedener Optimierungsaufgaben dargestellt. Um dieses Ziel zu erreichen wird zuerst eine allgemeine Optimierungsaufgabe betrachtet, wobei sowohl die Zielfunktion als auch die Nebenbedingungen zusammengesetzte Funktionen sind. Mit Hilfe der konjugierten Dualitätstheorie, die auf der sogenannten Störungstheorie basiert, werden für die primale Aufgabe drei verschiedene duale Aufgaben konstruiert und weiterhin die Beziehungen zwischen deren optimalen Zielfunktionswerten untersucht. Unter geeigneten Konvexitäts- und Monotonievoraussetzungen wird die Gleichheit dieser optimalen Zielfunktionswerte und zusätzlich die Existenz der starken Dualität zwischen der primalen und den entsprechenden dualen Aufgaben bewiesen. In Zusammenhang mit der starken Dualität werden Optimalitätsbedingungen hergeleitet. Die Ergebnisse werden abgerundet durch die Betrachtung zweier Spezialfälle, nämlich die klassische restringierte bzw. unrestringierte Optimierungsaufgabe, für welche sich die aus der Literatur bekannten Dualitätsergebnisse ergeben. Der zweite Teil der Arbeit ist der Dualität bei Standortproblemen gewidmet. Dazu wird ein sehr allgemeines Standortproblem mit konvexer zusammengesetzter Zielfunktion in Form eines Gauges formuliert, für das die entsprechenden Dualitätsaussagen abgeleitet werden. Als Spezialfälle werden Optimierungsaufgaben mit monotonen Normen betrachtet. Insbesondere lassen sich Dualitätsaussagen und Optimalitätsbedingungen für das klassische Weber und Minmax Standortproblem mit Gauges als Zielfunktion herleiten. Das letzte Kapitel verallgemeinert die Dualitätsaussagen, die im zweiten Kapitel erhalten wurden, auf multikriterielle Optimierungsprobleme. Mit Hilfe geeigneter Skalarisierungen betrachten wir zuerst ein zu der multikriteriellen Optimierungsaufgabe zugeordnetes skalares Problem. Anhand der in diesem Fall erhaltenen Optimalitätsbedingungen formulieren wir das multikriterielle Dualproblem. Weiterhin beweisen wir die schwache und, unter bestimmten Annahmen, die starke Dualität. Durch Spezialisierung der Zielfunktionen bzw. Nebenbedingungen resultieren die klassischen konvexen Mehrzielprobleme mit Ungleichungs- und Mengenrestriktionen. Als weitere Anwendungen werden vektorielle Standortprobleme betrachtet, zu denen wir entsprechende duale Aufgaben formulieren

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.

A norm ||⋅|| on a Banach space X is Fréchet differentiable at x ∈ X if there is a functional ∫∈ X* such that [Formula Omitted] This concept reflects the smoothness characteristics of X. A dual Banach space X* has the Radon-Nikodym Property (RNP) if whenever C ⊂ X* is weak*-compact and convex, and ∈ > 0, there is an x ∈ X and an ⍺ > 0 such that diameter [Formula Omitted] this property reflects the convexity characteristics of X*. Culminating several years of work by many researchers, the following theorem established a strong connection between the smoothness of X and the convexity of X*: Every equivalent norm on X is Fréchet differentiable on a dense set if and only if X* has the RNP. A more general measure of convexity has been recently receiving a great deal of attention: A dual Banach space X* has the weak* Convex Point-of-Continuity Property (C*PCP) if whenever ɸ ≠ C ⊂ X* is weak*-compact and convex, and ∈ > 0, there is a weak*-open set V such that V ⋂ C ≠ ɸ and diam V ⋂ C < ∈. In this thesis, we develop the corresponding smoothness properties of X which are dual to C*PCP. For this, a new type of differentiability, called cofinite Fréchet differentiability, is introduced, and we establish the following theorem: Every equivalent norm on X is cofinitely Fréchet differentiable everywhere if and only if X* has the C*PCP. Representing joint work with R. Deville, G. Godefroy and V. Zizler, an alternate approach is developed in the case when X is separable. We show that if X is separable, then every equivalent norm on X which has a strictly convex dual is Fréchet differentiable on a dense set if and only if X* has the C*PCP, if and only if every equivalent norm on X which is Gâteaux differentiable (everywhere) is Fréchet differentiable on a dense set. This result is used to show that if X* does not have the C*PCP, then there is a subspace Y of X such that neither Y* nor (X/Y)* have the C*PCP, yet both Y and X/Y have finite dimensional Schauder decompositions. The corresponding result for spaces X* failing the RNP remains open.
Science, Faculty of
Mathematics, Department of
Graduate

The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: z* := minz ctx s.t. Ax - b Cy C Cx , to the more general non-conic format: z* := minx ctx (GPd) s.t. Ax-b E Cy X P, where P is any closed convex set, not necessarily a cone, which we call the groundset. Although any convex problem can be transformed to conic form, such transformations are neither unique nor natural given the natural description of many problems, thereby diminishing the relevance of data-based condition number theory. Herein we extend the modern theory of condition numbers to the problem format (GPd). As a byproduct, we are able to state and prove natural extensions of many theorems from the conic-based theory of condition numbers to this broader problem format.

This thesis represents a theoretical and numerical investigation of the canonical duality theory, which has been recently proposed as an alternative to the classic and direct methods for non-convex variational problems. These non-convex variational problems arise in a wide range of scientific and engineering applications, such as phase transitions, post-buckling of large deformed beam models, nonlinear field theory, and superconductivity. The numerical discretization of these non-convex variational problems leads to global minimization problems in a finite dimensional space. The primary goal of this thesis is to apply the newly developed canonical duality theory to two non-convex variational problems: a modified version of Ericksen's bar and a problem of Landau-Ginzburg type. The canonical duality theory is investigated numerically and compared with classic methods of numerical nature. Both advantages and shortcomings of the canonical duality theory are discussed. A major component of this critical numerical investigation is a careful sensitivity study of the various approaches with respect to changes in parameters, boundary conditions and initial conditions.
Ph. D.

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.

L'obbiettivo di questa tesi è la definizione del calcolo differenziale e dell'operatore di Laplace in spazi metrici di misura. Nel primo capitolo vengono introdotte le definizioni e proprietà principali degli spazi metrici di misura mentre nel secondo quelle riguardanti le funzioni lipschitziane e la derivata metrica di curve assolutamente continue. Nel terzo capitolo quindi viene definito il concetto di p-supergradiente debole e di conseguenza la classe di Sobolev S^p. Nel quarto capitolo viene poi studiata la generalizzazione del concetto di differenziale di f applicato al gradiente di g che da luogo a due funzioni che in generale risultano diverse, ma se coincidono lo spazio verrà detto q-infinitesimamente strettamente convesso. Vengono quindi dimostrate alcune regole della catena per per queste due funzioni attraverso la dualità fra lo spazio S^p e un opportuno spazio di misure dette q-piani test. In particolare mediante l'introduzione del funzionale energia di Cheeger e il suo flusso-gradiente sarà possibile associare un piano di trasporto al gradiente di una funzione in S^p. Nel quinto capitolo viene definito il p-laplaciano e le regole di calcolo provate precedentemente saranno usate per provare quelle per il laplaciano. Verranno poi definiti gli spazi infitesimamente di Hilbert: in questo caso il laplaciano assume un solo valore e risulta linearmente dipendente da g e si dimostra un'identificazione tra differenziali e gradienti. Nell'ultima parte del quinto capitolo infine viene mostrata un'applicazione del calcolo differenziale in spazi metrici di misura al gruppo di Heisenberg, considerandolo uno spazio metrico di misura munito della metrica di Korany e la misura di Lebesgue. Nella prima parte si mostra che il laplaciano metrico coincide con quello subriemanniano. Viene poi considerata nella seconda parte la sottovarietà {x=0} e si dimostra come il laplaciano metrico sia diverso da quello differenziale.

Lau, Fu Man.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2009.
Includes bibliographical references (leaves 94-97).
Abstract also in Chinese.
Abstract --- p.i
Acknowledgements --- p.iii
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Notations and Preliminaries --- p.4
Chapter 2.1 --- Introduction --- p.4
Chapter 2.2 --- Basic notations --- p.4
Chapter 2.3 --- On the properties of subdifferentials --- p.8
Chapter 2.4 --- On the properties of normal cones --- p.9
Chapter 2.5 --- Some computation rules for conjugate functions --- p.13
Chapter 2.6 --- On the properties of epigraphs --- p.15
Chapter 2.7 --- Set-valued analysis --- p.19
Chapter 2.8 --- Weakly* sum of sets in dual spaces --- p.21
Chapter 3 --- Sum of Epigraph Constraint Qualification (SECQ) --- p.31
Chapter 3.1 --- Introduction --- p.31
Chapter 3.2 --- Definition of the SECQ and its basic properties --- p.33
Chapter 3.3 --- Relationship between the SECQ and other constraint qualifications --- p.39
Chapter 3.3.1 --- The SECQ and the strong CHIP --- p.39
Chapter 3.3.2 --- The SECQ and the linear regularity --- p.46
Chapter 3.4 --- Interior-point conditions for the SECQ --- p.58
Chapter 3.4.1 --- I is finite --- p.59
Chapter 3.4.2 --- I is infinite --- p.61
Chapter 4 --- Duality theory of semi-infinite optimization via weakly* sum of epigraph of conjugate functions --- p.70
Chapter 4.1 --- Introduction --- p.70
Chapter 4.2 --- Fenchel duality in semi-infinite convex optimization --- p.73
Chapter 4.3 --- Sufficient conditions for Fenchel duality in semi-infinite convex optimization --- p.79
Chapter 4.3.1 --- Continuous real-valued functions --- p.80
Chapter 4.3.2 --- Nonnegative-valued functions --- p.84
Bibliography --- p.94

Thesis (Ph. D.)--Florida State University, 2004.
Advisor: Dr. Daniel M. Oberlin, Florida State University, College of Arts and Sciences, Dept. of Mathematics. Title and description from dissertation home page (June 18, 2004). Includes bibliographical references.

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.

碩士
國立成功大學
數學系應用數學碩博士班
97
In this thesis, we study the global optimality conditions for non-convex minimization problems. With the extended concept of gradient, lower bound function, and Farkas’ lemma, we have the extended KKT conditions for characterizing the non-convex, non-differentiable function. The extension is based on the concept of L-subdifferential, S-property, and solvability property, introduced by Jeyakumar, Rubinov, and Wu, but we have focused on the geometrical connections and interpretation of those abstract properties. The concepts are particularly applied for non-convex quadratic minimization problems and we have made comparisons with the canonical duality theory, introduced by Fang, Gao, Sheu, and Wu, by figures.