Spelling suggestions: "subject:"konvexität"" "subject:"konvexitäts""
1 |
Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operatorsCsetnek, 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.
|
2 |
Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operatorsCsetnek, 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.
|
3 |
New insights into conjugate dualityGrad, 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.
|
4 |
Geometry of Minkowski Planes and Spaces -- Selected TopicsWu, Senlin 03 February 2009 (has links) (PDF)
The results presented in this dissertation refer to the geometry of Minkowski
spaces, i.e., of real finite-dimensional Banach spaces.
First we study geometric properties of radial projections of
bisectors in Minkowski spaces, especially the relation between the
geometric structure of radial projections and Birkhoff
orthogonality. As an application of our results it is shown that for
any Minkowski space there exists a number, which plays somehow the
role that $\sqrt2$ plays in Euclidean space. This number is referred
to as the critical number of any Minkowski space. Lower and upper
bounds on the critical number are given, and the cases when these
bounds are attained are characterized. Moreover, with the help of
the properties of bisectors we show that a linear map from a normed
linear space $X$ to another normed linear space $Y$ preserves
isosceles orthogonality if and only if it is a scalar multiple of a
linear isometry.
Further on, we examine the two tangent segments from any exterior
point to the unit circle, the relation between the length of a chord
of the unit circle and the length of the arc corresponding to it,
the distances from the normalization of the sum of two unit vectors
to those two vectors, and the extension of the notions of
orthocentric systems and orthocenters in Euclidean plane into
Minkowski spaces. Also we prove theorems referring to chords of
Minkowski circles and balls which are either concurrent or parallel.
All these discussions yield many interesting characterizations of
the Euclidean spaces among all (strictly convex) Minkowski spaces.
In the final chapter we investigate the relation between the length
of a closed curve and the length of its midpoint curve as well as
the length of its image under the so-called halving pair
transformation. We show that the image curve under the halving pair
transformation is convex provided the original curve is convex.
Moreover, we obtain several inequalities to show the relation
between the halving distance and other quantities well known in
convex geometry. It is known that the lower bound for the geometric
dilation of rectifiable simple closed curves in the Euclidean plane
is $\pi/2$, which can be attained only by circles. We extend this
result to Minkowski planes by proving that the lower bound for the
geometric dilation of rectifiable simple closed curves in a
Minkowski plane $X$ is analogously a quarter of the circumference of
the unit circle $S_X$ of $X$, but can also be attained by curves
that are not Minkowskian circles. In addition we show that the lower
bound is attained only by Minkowskian circles if the respective norm
is strictly convex. Also we give a sufficient condition for the
geometric dilation of a closed convex curve to be larger than a
quarter of the perimeter of the unit circle.
|
5 |
An Algebraic View on p-Admissible Concrete Domains for Lightweight Description Logics: Extended VersionBaader, Franz, Rydval, Jakub 20 June 2022 (has links)
Concrete domains have been introduced in Description Logics (DLs) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. To retain decidability when integrating a concrete domain into a decidable DL, the domain must satisfy quite strong restrictions. In previous work, we have analyzed the most prominent such condition, called w-admissibility, from an algebraic point of view. This provided us with useful algebraic tools for proving w-admissibility, which allowed us to find new examples for concrete domains whose integration leaves the prototypical expressive DL ALC decidable. When integrating concrete domains into lightweight DLs of the EL family, achieving decidability is not enough. One wants reasoning in the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. In the present paper, we investigate p-admissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical padmissible concrete domain based on the rational numbers. Although w-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into ALC yields decidable DLs.
|
6 |
Singular control of optional random measuresBank, Peter 14 December 2000 (has links)
In dieser Arbeit untersuchen wir das Problem der Maximierung bestimmter konkaver Funktionale auf dem Raum der optionalen, zufälligen Maße. Deartige Funktionale treten in der mikroökonomischen Literatur auf, wo ihre Maximierung auf die Bestimmung des optimalen Konsumplans eines ökomischen Agenten hinausläuft. Als Alternative zu den wohlbekannten Methoden der dynamischen Programmierung wird ein neuer Zugang vorgestellt, der es erlaubt, die Struktur der maximierenden Maße in einem über den üblicherweise angenommenen Markovschen Rahmen hinausgehenden, allgemeinen Semimartingalrahmen zu klären. Unser Zugang basiert auf einer unendlichdimensionalen Version des Kuhn-Tucker-Theorems. Die implizierten Bedingungen erster Ordnung erlauben es uns, das Maximierungsproblem auf ein neuartiges Darstellungsproblem für optionale Prozesse zu reduzieren, das damit als ein nicht-Markovsches Substitut für die Hamilton-Jacobi-Bellman Gleichung der dynamischen Programmierung dient. Um dieses Darstellungsproblem im deterministischen Fall zu lösen, führen wir eine zeitinhomogene Verallgemeinerung des Konvexitätsbegriffs ein. Die Lösung im allgemeinen stochastischen Fall ergibt sich über eine enge Beziehung zur Theorie des Gittins-Index der optimalen dynamischen Planung. Unter geeigneten Annahmen gelingt ihre Darstellung in geschlossener Form. Es zeigt sich dabei, daß die maximierenden Maße absolutstetig, diskret und auch singulär sein können, je nach Struktur der dem Problem zugrundeliegenden Stochastik. Im mikroökonomischen Kontext ist es natürlich, daß Problem in einen Gleichgewichtsrahmen einzubetten. Der letzte Teil der Arbeit liefert hierzu ein allgemeines Existenzresultat für ein solches Gleichgewicht. / In this thesis, we study the problem of maximizing certain concave functionals on the space of optional random measures. Such functionals arise in microeconomic theory where their maximization corresponds to finding the optimal consumption plan of some economic agent. As an alternative to the well-known methods of Dynamic Programming, we develop a new approach which allows us to clarify the structure of maximizing measures in a general stochastic setting extending beyond the usually required Markovian framework. Our approach is based on an infinite-dimensional version of the Kuhn-Tucker Theorem. The implied first-order conditions allow us to reduce the maximization problem to a new type of representation problem for optional processes which serves as a non-Markovian substitute for the Hamilton-Jacobi-Bellman equation of Dynamic Programming. In order to solve this representation problem in the deterministic case, we introduce a time-inhomogeneous generalization of convexity. The stochastic case is solved by using an intimate relation to the theory of Gittins-indices in optimal dynamic scheduling. Closed-form solutions are derived under appropriate conditions. Depending on the underlying stochastics, maximizing random measures can be absolutely continuous, discrete, and also singular. In the microeconomic context, it is natural to embed the above maximization problem in an equilibrium framework. In the last part of this thesis, we give a general existence result for such an equilibrium.
|
7 |
New insights into conjugate dualityGrad, 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.
|
8 |
Geometry of Minkowski Planes and Spaces -- Selected TopicsWu, Senlin 13 November 2008 (has links)
The results presented in this dissertation refer to the geometry of Minkowski
spaces, i.e., of real finite-dimensional Banach spaces.
First we study geometric properties of radial projections of
bisectors in Minkowski spaces, especially the relation between the
geometric structure of radial projections and Birkhoff
orthogonality. As an application of our results it is shown that for
any Minkowski space there exists a number, which plays somehow the
role that $\sqrt2$ plays in Euclidean space. This number is referred
to as the critical number of any Minkowski space. Lower and upper
bounds on the critical number are given, and the cases when these
bounds are attained are characterized. Moreover, with the help of
the properties of bisectors we show that a linear map from a normed
linear space $X$ to another normed linear space $Y$ preserves
isosceles orthogonality if and only if it is a scalar multiple of a
linear isometry.
Further on, we examine the two tangent segments from any exterior
point to the unit circle, the relation between the length of a chord
of the unit circle and the length of the arc corresponding to it,
the distances from the normalization of the sum of two unit vectors
to those two vectors, and the extension of the notions of
orthocentric systems and orthocenters in Euclidean plane into
Minkowski spaces. Also we prove theorems referring to chords of
Minkowski circles and balls which are either concurrent or parallel.
All these discussions yield many interesting characterizations of
the Euclidean spaces among all (strictly convex) Minkowski spaces.
In the final chapter we investigate the relation between the length
of a closed curve and the length of its midpoint curve as well as
the length of its image under the so-called halving pair
transformation. We show that the image curve under the halving pair
transformation is convex provided the original curve is convex.
Moreover, we obtain several inequalities to show the relation
between the halving distance and other quantities well known in
convex geometry. It is known that the lower bound for the geometric
dilation of rectifiable simple closed curves in the Euclidean plane
is $\pi/2$, which can be attained only by circles. We extend this
result to Minkowski planes by proving that the lower bound for the
geometric dilation of rectifiable simple closed curves in a
Minkowski plane $X$ is analogously a quarter of the circumference of
the unit circle $S_X$ of $X$, but can also be attained by curves
that are not Minkowskian circles. In addition we show that the lower
bound is attained only by Minkowskian circles if the respective norm
is strictly convex. Also we give a sufficient condition for the
geometric dilation of a closed convex curve to be larger than a
quarter of the perimeter of the unit circle.
|
Page generated in 0.0275 seconds