• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 37
  • 8
  • 2
  • Tagged with
  • 47
  • 31
  • 23
  • 20
  • 18
  • 14
  • 13
  • 13
  • 13
  • 10
  • 10
  • 9
  • 8
  • 8
  • 7
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Proximal Splitting Methods in Nonsmooth Convex Optimization

Hendrich, Christopher 17 July 2014 (has links)
This thesis is concerned with the development of novel numerical methods for solving nondifferentiable convex optimization problems in real Hilbert spaces and with the investigation of their asymptotic behavior. To this end, we are also making use of monotone operator theory as some of the provided algorithms are originally designed to solve monotone inclusion problems. After introducing basic notations and preliminary results in convex analysis, we derive two numerical methods based on different smoothing strategies for solving nondifferentiable convex optimization problems. The first approach, known as the double smoothing technique, solves the optimization problem with some given a priori accuracy by applying two regularizations to its conjugate dual problem. A special fast gradient method then solves the regularized dual problem such that an approximate primal solution can be reconstructed from it. The second approach affects the primal optimization problem directly by applying a single regularization to it and is capable of using variable smoothing parameters which lead to a more accurate approximation of the original problem as the iteration counter increases. We then derive and investigate different primal-dual methods in real Hilbert spaces. In general, one considerable advantage of primal-dual algorithms is that they are providing a complete splitting philosophy in that the resolvents, which arise in the iterative process, are only taken separately from each maximally monotone operator occurring in the problem description. We firstly analyze the forward-backward-forward algorithm of Combettes and Pesquet in terms of its convergence rate for the objective of a nondifferentiable convex optimization problem. Additionally, we propose accelerations of this method under the additional assumption that certain monotone operators occurring in the problem formulation are strongly monotone. Subsequently, we derive two Douglas–Rachford type primal-dual methods for solving monotone inclusion problems involving finite sums of linearly composed parallel sum type monotone operators. To prove their asymptotic convergence, we use a common product Hilbert space strategy by reformulating the corresponding inclusion problem reasonably such that the Douglas–Rachford algorithm can be applied to it. Finally, we propose two primal-dual algorithms relying on forward-backward and forward-backward-forward approaches for solving monotone inclusion problems involving parallel sums of linearly composed monotone operators. The last part of this thesis deals with different numerical experiments where we intend to compare our methods against algorithms from the literature. The problems which arise in this part are manifold and they reflect the importance of this field of research as convex optimization problems appear in lots of applications of interest.
32

Dynamic convex risk measures

Penner, Irina 17 March 2008 (has links)
In dieser Arbeit werden verschiedene Eigenschaften von dynamischen konvexen Risikomaßen für beschränkte Zufallsvariablen untersucht. Dabei gehen wir vor allem der Frage nach, wie die Risikobewertungen in verschiedenen Zeitpunkten von einander abhängen, und wie sich solche Zeitkonsistenzeigenschaften in der Dynamik der Penalty-Funktionen und Risikoprozesse widerspiegeln. Im Kapitel 2 widmen wir uns zunächst der starken Zeitkonsistenz und charakterisieren diese mithilfe von Akzeptanzmengen, Penalty-Funktionen und einer gemeinsamen Supermartingaleigenschaft des Risikoprozesses und seiner Penalty-Funktion. Die Charakterisierung durch Penalty-Funktionen liefert eine explizite Form der Doob- und der Riesz-Zerlegung des Prozesses der Penalty-Funktionen. Anschließend führen wir einen schwächeren Begriff der Zeitkonsistenz ein, den wir Besonnenheit nennen. In Analogie zu dem zeitkonsistenten Fall charakterisieren wir Besonnenheit durch Akzeptanzmengen, Penalty-Funktionen und eine bestimmte Supermartingaleigenschaft. Diese Supermartingaleigenschaft gilt allgemeiner für alle beschränkten adaptierten Prozesse, die sich ohne zusätzliches Risiko aufrechterhalten lassen. Wir nennen solche Prozesse nachhaltig und beschreiben Nachhaltigkeit durch eine gemeinsame Supermartingaleigenschaft des Prozesses und der schrittweisen Penalty-Funktionen. Dieses Resultat kann als eine verallgemeinerte optionale Zerlegung unter konvexen Restriktionen gesehen werden. Mithilfe der Supermartingaleigenschaft identifizieren wir das stark zeitkonsistente dynamische Risikomaß, das aus jedem beliebigen Risikomaß rekursiv konstruiert werden kann, als den kleinsten Prozeß, der nachhaltig ist und den Endverlust minimiert. Diese Beschreibung liefert ein neues Argument für den Einsatz von zeitkonsistenten Risikomaßen. Im Kapitel 3 diskutieren wir das asymptotische Verhalten von zeitkonsistenten und von besonnenen Risikomaßen hinsichtlich der asymptotischen Sicherheit und der asymptotischen Präzision. Im Kapitel 4 werden die allgemeinen Ergebnisse aus den Kapiteln 2 und 3 anhand des entropischen Risikomaßes und des Superhedging-Preisprozesses veranschaulicht. / In this thesis we study various properties of a dynamic convex risk measure for bounded random variables. The main subject is to investigate possible interdependence of conditional risk assessments at different times and the manifestation of these time consistency properties in the dynamics of corresponding penalty functions and risk processes. In Chapter 2 we focus first on the strong notion of time consistency and characterize it in terms of penalty functions, acceptance sets and a joint supermartingale property of the risk measure and its penalty function. The characterization in terms of penalty functions provides the explicit form of the Doob and of the Riesz decomposition of the penalty function process for a time consistent risk measure. Then we introduce and study a weaker notion of time consistency, that we call prudence. Similar to the time consistent case, we characterize prudent dynamic risk measures in terms of acceptance sets, of penalty functions and by a certain supermartingale property. This supermartingale property holds more generally for any bounded adapted process that can be upheld without any additional risk. We call such processes sustainable, and we give an equivalent characterization of sustainability in terms of a combined supermartingale property of a process and one-step penalty functions. This result can be viewed as a generalized optimal decomposition under convex constraints. The supermartingale property allows us to characterize the strongly time consistent risk measure arising from any dynamic risk measure via recursive construction as the smallest process that is sustainable and covers the final loss. Thus our discussion provides a new reason for using strongly time consistent risk measures. In Chapter 3 we discuss the limit behavior of time consistent and of prudent risk measures in terms of asymptotic safety and of asymptotic precision. In the final Chapter 4 we illustrate the general results of Chapter 2 and Chapter 3 by examples. In particular we study the entropic dynamic risk measure and the superhedging price process under convex constraints.
33

Duality for convex composed programming problems

Vargyas, Emese Tünde 25 November 2004 (has links)
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.
34

A duality approach to gap functions for variational inequalities and equilibrium problems

Lkhamsuren, Altangerel 25 July 2006 (has links)
This work aims to investigate some applications of the conjugate duality for scalar and vector optimization problems to the construction of gap functions for variational inequalities and equilibrium problems. The basic idea of the approach is to reformulate variational inequalities and equilibrium problems into optimization problems depending on a fixed variable, which allows us to apply duality results from optimization problems. Based on some perturbations, first we consider the conjugate duality for scalar optimization. As applications, duality investigations for the convex partially separable optimization problem are discussed. Afterwards, we concentrate our attention on some applications of conjugate duality for convex optimization problems in finite and infinite-dimensional spaces to the construction of a gap function for variational inequalities and equilibrium problems. To verify the properties in the definition of a gap function weak and strong duality are used. The remainder of this thesis deals with the extension of this approach to vector variational inequalities and vector equilibrium problems. By using the perturbation functions in analogy to the scalar case, different dual problems for vector optimization and duality assertions for these problems are derived. This study allows us to propose some set-valued gap functions for the vector variational inequality. Finally, by applying the Fenchel duality on the basis of weak orderings, some variational principles for vector equilibrium problems are investigated.
35

An Invitation to Generalized Minkowski Geometry

Jahn, Thomas 11 March 2019 (has links)
The present thesis contributes to the theory of generalized Minkowski spaces as a continuation of Minkowski geometry, i.e., the geometry of finite-dimensional normed spaces over the field of real numbers. In a generalized Minkowski space, distance and length measurement is provided by a gauge, whose definition mimics the definition of a norm but lacks the symmetry requirement. This seemingly minor change in the definition is deliberately chosen. On the one hand, many techniques from Minkowski spaces can be adapted to generalized Minkowski spaces because several phenomena in Minkowski geometry simply do not depend on the symmetry of distance measurement. On the other hand, the possible asymmetry of the distance measurement set up by gauges is nonetheless meaningful and interesting for applications, e.g., in location science. In this spirit, the presentation of this thesis is led mainly by minimization problems from convex optimization and location science which are appealing to convex geometers, too. In addition, we study metrically defined objects, which may receive a new interpretation when we measure distances asymmetrically. To this end, we use a combination of methods from convex analysis and convex geometry to relate the properties of these objects to the shape of the unit ball of the generalized Minkowski space under consideration.
36

Oscillatory Solutions to Hyperbolic Conservation Laws and Active Scalar Equations

Knott, Gereon 09 September 2013 (has links)
In dieser Arbeit werden zwei Klassen von Evolutionsgleichungen in einem Matrixraum-Setting studiert: Hyperbolische Erhaltungsgleichungen und aktive skalare Gleichungen. Für erstere wird untersucht, wann man Oszillationen mit Hilfe polykonvexen Maßen ausschließen kann; für Zweitere wird mit Hilfe von Oszillationen gezeigt, dass es unendlich viele periodische schwache Lösungen gibt.
37

Dynamic Graph Generation and an Asynchronous Parallel Bundle Method Motivated by Train Timetabling

Fischer, Frank 09 July 2013 (has links)
Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems. The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes. The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions. Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.
38

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.
39

Application of the Duality Theory: New Possibilities within the Theory of Risk Measures, Portfolio Optimization and Machine Learning

Lorenz, Nicole 28 June 2012 (has links)
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.
40

Duality investigations for multi-composed optimization problems with applications in location theory

Wilfer, Oleg 30 March 2017 (has links) (PDF)
The goal of this thesis is two-fold. On the one hand, it pursues to provide a contribution to the conjugate duality by proposing a new duality concept, which can be understood as an umbrella for different meaningful perturbation methods. On the other hand, this thesis aims to investigate minimax location problems by means of the duality concept introduced in the first part of this work, followed by a numerical approach using epigraphical splitting methods. After summarizing some elements of the convex analysis as well as introducing important results needed later, we consider an optimization problem with geometric and cone constraints, whose objective function is a composition of n+1 functions. For this problem we propose a conjugate dual problem, where the functions involved in the objective function of the primal problem are decomposed. Furthermore, we formulate generalized interior point regularity conditions for strong duality and give necessary and sufficient optimality conditions. As applications of this approach we determine the formulae of the conjugate as well as the biconjugate of the objective function of the primal problem and analyze an optimization problem having as objective function the sum of reciprocals of concave functions. In the second part of this thesis we discuss in the sense of the introduced duality concept three classes of minimax location problems. The first one consists of nonlinear and linear single minimax location problems with geometric constraints, where the maximum of nonlinear or linear functions composed with gauges between pairs of a new and existing points will be minimized. The version of the nonlinear location problem is additionally considered with set-up costs. The second class of minimax location problems deals with multifacility location problems as suggested by Drezner (1991), where for each given point the sum of weighted distances to all facilities plus set-up costs is determined and the maximal value of these sums is to be minimized. As the last and third class the classical multifacility location problem with geometrical constraints is considered in a generalized form where the maximum of gauges between pairs of new facilities and the maximum of gauges between pairs of new and existing facilities will be minimized. To each of these location problems associated dual problems will be formulated as well as corresponding duality statements and necessary and sufficient optimality conditions. To illustrate the results of the duality approach and to give a more detailed characterization of the relations between the location problems and their corresponding duals, we consider examples in the Euclidean space. This thesis ends with a numerical approach for solving minimax location problems by epigraphical splitting methods. In this framework, we give formulae for the projections onto the epigraphs of several sums of powers of weighted norms as well as formulae for the projection onto the epigraphs of gauges. Numerical experiments document the usefulness of our approach for the discussed location problems.

Page generated in 0.0422 seconds