Conjugate Duality in Convex Optimization

verfasst von: Radu Ioan Bot

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Economics and Mathematical Systems

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The results presented in this book originate from the last decade research work of the author in the ?eld of duality theory in convex optimization. The reputation of duality in the optimization theory comes mainly from the major role that it plays in formulating necessary and suf?cient optimality conditions and, consequently, in generatingdifferent algorithmic approachesfor solving mathematical programming problems. The investigations made in this work prove the importance of the duality theory beyond these aspects and emphasize its strong connections with different topics in convex analysis, nonlinear analysis, functional analysis and in the theory of monotone operators. The ?rst part of the book brings to the attention of the reader the perturbation approach as a fundamental tool for developing the so-called conjugate duality t- ory. The classical Lagrange and Fenchel duality approaches are particular instances of this general concept. More than that, the generalized interior point regularity conditions stated in the past for the two mentioned situations turn out to be p- ticularizations of the ones given in this general setting. In our investigations, the perturbationapproachrepresentsthestartingpointforderivingnewdualityconcepts for several classes of convex optimization problems. Moreover, via this approach, generalized Moreau–Rockafellar formulae are provided and, in connection with them, a new class of regularity conditions, called closedness-type conditions, for both stable strong duality and strong duality is introduced. By stable strong duality we understand the situation in which strong duality still holds whenever perturbing the objective function of the primal problem with a linear continuous functional.

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract

The purpose of this work is to present the state of art but also recent advances and applications in the theory of conjugate duality in the convex analysis and convex optimization and, beyond them, in nonlinear analysis, functional analysis and the theory of monotone operators. Unless otherwise specified, the content of this manuscript is represented by the contributions of the author (along with his coauthors) to this field. The diversity of the topics considered here constitutes an evidence for the important role which the duality theory plays in the different areas enumerated above. The work is divided into six chapters with a total of 26 sections.

Radu Ioan Boţ

Chapter I. Perturbation Functions and Dual Problems

Abstract

The starting point of our investigations is a general approach for constructing a dual optimization problem to a primal one based on the theory of conjugate functions. Consider X a separated locally convex space and $F : X \rightarrow \overline{\mathbb{R}} = \mathbb{R} \cup \{\pm \infty \}$ a given function. We assume that F is proper, namely that F(x)>−∞ for all x∈X and its domain ${\rm dom}F =\{ x \in X : F(x) < +\infty \}$ is nonempty. To the general optimization problem, called also primal problem,

$$(PG) \inf\limits_{x \in X} F(x)$$

one can assign a conjugate dual problem by making use of the so-called perturbation approach. To this end, we consider Y another separated locally convex space and the function $\Phi : X \times Y \rightarrow \overline{\mathbb{R}}$, called perturbation function, fulfilling $\Phi(x, 0) = F(x)\ {\rm for\ all}\ x \in X$. The initial problem (PG) is nothing else than

$$(PG) \inf\limits_{x \in X} \Phi(x, 0).$$

Radu Ioan Boţ

Chapter II. Moreau–Rockafellar Formulae and Closedness-Type Regularity Conditions

Abstract

Throughout this chapter, we assume that all topological dual spaces of the separated locally convex spaces considered are endowed with the corresponding weak* topologies. In this section, we give generalized Moreau–Rockafellar formulae expressed via the perturbation function Φ considered in Section 1 as well as closedness-type regularity conditions for the general optimization problem (PG). These will be particularized in the following sections to the different classes of convex functions and corresponding convex optimization problems, respectively, introduced in the previous chapter (see also [27]).

Let X and Y be separated locally convex spaces and X ^∗ and Y ^∗ be their topological dual spaces, respectively. Given a function $\Phi : X \times Y \rightarrow \overline{\mathbb{R}}$, we have that Φ^∗ is convex and, consequently, the infimal value function of Φ^∗, ${\rm inf}_{{y^{\ast}\in Y^{\ast}}} \phi^{\ast} (., y^{\ast}) : X^{\ast} \rightarrow \overline{\mathbb{R}}$ is also convex. For a subset of X ^∗ and a function defined on X ^∗ the closure and the lower semicontinuous hull, respectively, in the weak^∗ topology are denoted by ${\rm cl}_{\omega^{\ast}}$, while ${\rm cl}_{\omega^{\ast} \times \mathcal{R}}$ denotes the closure of a subset of $(X^{\ast}, \omega(X^{\ast}, X)) \times \mathbb{R}$. Here, we denote by $\mathcal{R}$ the natural topology on $\mathbb{R}$. The following theorem can be obtained from [110] and plays a determinant role in the investigations we make in this chapter.

Radu Ioan Boţ

Chapter III. Biconjugate Functions

Abstract

As follows from the Fenchel–Moreau Theorem, when the dual of a normed space X is endowed with the weak^∗ topology, the biconjugate of a proper, convex and lower semicontinuous function defined on X coincides with the function itself. This is not necessarily the case when X ^∗ is endowed with the strong topology. Working in the latter setting, we give in this chapter formulae for the biconjugates for some classes of functions, which appear in the convex optimization, that hold provided the validity of some suitable regularity conditions.

Consider X a normed space with the norm $\|\cdot\|$ and X ^∗ its topological dual space, the norm of which being denoted by $\|\cdot\|_{\ast}$. On this space we work with three topologies, namely the strong one induced by $\|\cdot\|_{\ast}$ which attaches X ^∗∗ as dual to X ^∗, the weak^∗ one induced by X on X ^∗, ω(X ^∗, X), which makes X to be the dual of X ^∗ and the weak one induced by X ^∗∗ on X ^∗, ω(X ^∗, X ^∗∗), that is the weakest topology on X ^∗ which attaches X ^∗∗ as dual to X ^∗∗. We specify each time when a weak topology is used, otherwise the strong one is considered. Like in the previous section, for sets and functions the closures and the lower semicontinuous hulls, respectively, in the weak^∗ topologies are denoted by cl_ω*, while the ones in the weak topologies are denoted by cl_ω. A normed space X can be identified with a subspace of X ^∗∗, and we denote by $\widehat{x}$ the canonical image in X ^∗∗ of the element $x \in X,\ {\rm i.e.}\ \langle\widehat{x}, x^{\ast}\rangle = \langle x^{\ast}, x\rangle\ {\rm for\ all}\ x \in X\ {\rm and}\ x^{\ast} \in X^{\ast}$, where by $\langle\cdot,\cdot\rangle$ we denote the duality product in both $X^{\ast} \times X\ {\rm and}\ X^{\ast\ast} \times X^{\ast}.\ {\rm For}\ U \subseteq X\ {\rm denote\ also}\ \widehat{U} = \{\widehat{x} : x \in U\}$. In this setting, when $f : X \rightarrow \overline{\mathbb{R}}$ is a given function, its biconjugate $f^{\ast\ast} : X^{\ast\ast} \rightarrow \overline{\mathbb{R}}$ is defined by $f^{\ast\ast} (x^{\ast\ast}) = {\rm sup}\{\langle x^{\ast\ast}, x^{\ast}\rangle - f^{\ast}(x^{\ast}) : x^{\ast} \in X^{\ast}\}$.

For the beginning we prove the following preliminary result.

Radu Ioan Boţ

Chapter IV. Strong and Total Conjugate Duality

Abstract

In this chapter, we are interested in formulating regularity conditions of closednesstype, which do not necessarily guarantee stable strong duality, but are sufficient for having strong duality. First, we do this for the primal–dual pair (PG)–(DG) and after that we particularize the general result to the different classes of problems investigated in the previous chapters.

Assume that X and Y are separated locally convex spaces, with X ^∗ and Y ^∗ their topological dual spaces, respectively, and $\Phi : X \times Y \rightarrow \overline{\mathbb{R}}$ is a proper and convex function such that $0 \in {\rm Pr}Y ({\rm dom} \Phi)$. Throughout this chapter we assume that the dual spaces are endowed with the weak^∗ topologies. As proved by Theorem 5.1, if Φ is lower semicontinuous, then for all $x^{\ast} \in X^{\ast}$ one has $(\Phi(\cdot,0))^{\ast}(x^{\ast}) = {\rm cl}_{\omega\ast}\ ({\rm inf}_{y\ast\in Y\ast}\Phi^{\ast}(\cdot, y^{\ast}))(x^{\ast})$. Starting from this fact, one can formulate the following regularity condition for (PG) and its conjugate dual (DG

$$(Rc_{5}^{\Phi} \left|\begin{array}{rcl}&&\Phi\ {\rm is\ lower\ semicontinuous\ and\ inf}_{y^{\ast} \in Y^{\ast}} \Phi^{\ast}(\cdot,y^{\ast})\ {\rm is\ lower}\\ &&{\rm semicontinuous\ and\ exact\ at\ 0}.\end{array}\right.$$

We say that ${\inf}_{y^{\ast}\in Y^{\ast}} \Phi^{\ast} (\cdot, y^{\ast})$ is exact at $\overline{x}^{\ast} \in X^{\ast}$ if there exists $\overline{y}^{\ast} \in Y^{\ast}$ such that ${\rm inf}_{y^{\ast} \in Y^{\ast}} \Phi^{\ast}(\overline{x}^{\ast}, y^{\ast}) = \Phi^{\ast}(\overline{x}^{\ast}, \overline{y}^{\ast})$. We have the following general result.

Radu Ioan Boţ

Chapter V. Unconventional Fenchel Duality

Abstract

In the fifth chapter of this work, we give some new insights into the classical Fenchel duality. The first two sections deal with the concept of totally Fenchel unstable functions introduced by Stephen Simons in [120], while in the remaining sections we turn our attention to the study of some “unconventional” regularity conditions for Fenchel duality expressed via the quasi interior and the quasi-relative interior of the domains and epigraphs of the functions involved.

Let X be a separated locally convex space, X ^∗ its topological dual space and $f, g : X \rightarrow \overline{\mathbb{R}}$ two arbitrary proper functions. According to the terminology used in Section 5 (see also Definition 5.4), we say that f and g satisfy stable Fenchel duality if for all $x^{\ast} \in X^{\ast}$, there exists $y^{\ast} \in X^{\ast}$ such that $(f + g)^{\ast}(x^{\ast}) = f^{\ast}(x^{\ast} - y^{\ast}) + g^{\ast}(y^{\ast})$. If this property holds for x ^∗ = 0, then f; g satisfy the classical Fenchel duality. Due to Stephen Simons (see [120]), the pair f; g is said to be totally Fenchel unstable if f and g satisfy Fenchel duality, but

$$y^{\ast}, z^{\ast} \in X^{\ast}\ {\rm and}\ (f + g)^{\ast}(y^{\ast} + z^{\ast}) = f^{\ast}(y^{\ast}) + g^{\ast}(z^{\ast}) \Longrightarrow y^{\ast} + z^{\ast} = 0.$$

Radu Ioan Boţ

Chapter VI. Applications of the Duality to Monotone Operators

Abstract

The theory of monotone operators captured the attention of mathematicians not only because of the fineness of the results but also because of the large number of applications, especially in fields like nonlinear analysis, variational inequalities and partial differential equations (see for instance [88, 130]). Different attempts to establish links to the convex analysis have been made (see [90,91,119]), but the most fruitful ones turned out to be the ones based on the so-called Fitzpatrick function discovered by Simons Fitzpatrick in [70]. Neglected for many years until re-popularized in [7, 8, 52, 98, 104–106, 121], this class of functions along with its extensions have given rise to a great number of publications which rediscovered and extended the important results of the theory of monotone operators by using tools from the convex analysis. The investigations we make in this chapter are to be seen belonging to this class of results, whereby, we concentrate ourselves on results based on the conjugate duality theory.

Radu Ioan Boţ

Backmatter

Titel: Conjugate Duality in Convex Optimization
verfasst von: Radu Ioan Bot
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-04900-2
Print ISBN: 978-3-642-04899-9
DOI: https://doi.org/10.1007/978-3-642-04900-2