- 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.
Search results
Showing 1 to 7 of 7 (0.066 seconds)| 1 |
Graph Partitioning and Semi-definite Programming HierarchiesSinop, Ali Kemal 15 May 2012 (has links)
Graph partitioning is a fundamental optimization problem that has been intensively studied. Many graph partitioning formulations are important as building blocks for divide-and-conquer algorithms on graphs as well as to many applications such as VLSI layout, packet routing in distributed networks, clustering and image segmentation. Unfortunately such problems are notorious for the huge gap between known best known approximation algorithms and hardness of approximation results. In this thesis, we study approximation algorithms for graph partitioning problems using a strong hierarchy of relaxations based on semi-definite programming, called Lasserre Hierachy.
Our main contribution in this thesis is a propagation based rounding framework for solutions arising from such relaxations. We present a novel connection between the quality of solutions it outputs and column based matrix reconstruction problem. As part of our work, we derive optimal bounds on the number of columns necessary together with efficient randomized and deterministic algorithms to find such columns. Using this framework, we derive approximation schemes for many graph partitioning problems with running times dependent on how fast the graph spectrum grows.
Our final contribution is a fast SDP solver for this rounding framework: Even though SDP relaxation has nO(r) many variables, we achieve running times of the form 2O(r) poly(n) by only partially solving the relevant part of relaxation. In order to achieve this, we present a new ellipsoid algorithm that returns certificate of infeasibility.
|
| 2 |
Farkas - type results for convex and non - convex inequality systemsHodrea, Ioan Bogdan 22 January 2008 (has links) (PDF)
As the title already suggests the aim of the present work is to present Farkas -
type results for inequality systems involving convex and/or non - convex functions.
To be able to give the desired results, we treat optimization problems which involve
convex and composed convex functions or non - convex functions like DC functions
or fractions.
To be able to use the fruitful Fenchel - Lagrange duality approach, to the primal
problem we attach an equivalent problem which is a convex optimization problem.
After giving a dual problem to the problem we initially treat, we provide weak
necessary conditions which secure strong duality, i.e., the case when the optimal
objective value of the primal problem coincides with the optimal objective value of
the dual problem and, moreover, the dual problem has an optimal solution.
Further, two ideas are followed. Firstly, using the weak and strong duality
between the primal problem and the dual problem, we are able to give necessary
and sufficient optimality conditions for the optimal solutions of the primal problem.
Secondly, provided that no duality gap lies between the primal problem and its
Fenchel - Lagrange - type dual we are able to demonstrate some Farkas - type
results and thus to underline once more the connections between the theorems of
the alternative and the theory of duality. One statement of the above mentioned
Farkas - type results is characterized using only epigraphs of functions.
We conclude our investigations by providing necessary and sufficient optimality
conditions for a multiobjective programming problem involving composed convex
functions. Using the well-known linear scalarization to the primal multiobjective
program a family of scalar optimization problems is attached. Further to each of
these scalar problems the Fenchel - Lagrange dual problem is determined. Making
use of the weak and strong duality between the scalarized problem and its dual the
desired optimality conditions are proved. Moreover, the way the dual problem of
the scalarized problem looks like gives us an idea about how to construct a vector
dual problem to the initial one. Further weak and strong vector duality assertions
are provided.
|
| 3 |
Farkas - type results for convex and non - convex inequality systemsHodrea, Ioan Bogdan 13 December 2007 (has links)
As the title already suggests the aim of the present work is to present Farkas -
type results for inequality systems involving convex and/or non - convex functions.
To be able to give the desired results, we treat optimization problems which involve
convex and composed convex functions or non - convex functions like DC functions
or fractions.
To be able to use the fruitful Fenchel - Lagrange duality approach, to the primal
problem we attach an equivalent problem which is a convex optimization problem.
After giving a dual problem to the problem we initially treat, we provide weak
necessary conditions which secure strong duality, i.e., the case when the optimal
objective value of the primal problem coincides with the optimal objective value of
the dual problem and, moreover, the dual problem has an optimal solution.
Further, two ideas are followed. Firstly, using the weak and strong duality
between the primal problem and the dual problem, we are able to give necessary
and sufficient optimality conditions for the optimal solutions of the primal problem.
Secondly, provided that no duality gap lies between the primal problem and its
Fenchel - Lagrange - type dual we are able to demonstrate some Farkas - type
results and thus to underline once more the connections between the theorems of
the alternative and the theory of duality. One statement of the above mentioned
Farkas - type results is characterized using only epigraphs of functions.
We conclude our investigations by providing necessary and sufficient optimality
conditions for a multiobjective programming problem involving composed convex
functions. Using the well-known linear scalarization to the primal multiobjective
program a family of scalar optimization problems is attached. Further to each of
these scalar problems the Fenchel - Lagrange dual problem is determined. Making
use of the weak and strong duality between the scalarized problem and its dual the
desired optimality conditions are proved. Moreover, the way the dual problem of
the scalarized problem looks like gives us an idea about how to construct a vector
dual problem to the initial one. Further weak and strong vector duality assertions
are provided.
|
| 4 |
Duality investigations for multi-composed optimization problems with applications in location theoryWilfer, 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.
|
| 5 |
Duality investigations for multi-composed optimization problems with applications in location theoryWilfer, Oleg 29 March 2017 (has links)
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.
|
| 6 |
Application of the Duality TheoryLorenz, 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.
|
| 7 |
Application of the Duality Theory: New Possibilities within the Theory of Risk Measures, Portfolio Optimization and Machine LearningLorenz, 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.
|
Page generated in 0.0719 seconds