Convex optimization and monotonic variational inequalities (Q6113387)

The book, written in French, presents the main elements of convex optimization, mainly focusing on the geometry and duality points of view. It is divided into 6 chapters. Chapter 1 gathers the main elements of convex sets and functions. The authors recall the definitions of convex set and of convex envelope, together with their properties, especially in finite dimension. They recall Caratheodory's theorem concerning the convex combination of points and the topological properties of convex sets. They define the notion of almost convex set and prove properties of such sets. They recall the definition of a recession cone, of the projection on a convex set and of separation between two convex sets. They recall the notion of extremal points and Minkowski's theorem. Moving to convex functions, they recall the semi-continuity definitions and the links with the topological properties of the epigraph. For a function of a real variable, they recall the links between convexity, continuity, left and right derivatives, and also with the sign of the second derivative. The authors recall the main properties of a convex function with multiple variables and the links with semi-continuity, also in the cases of a differentiable function or of a twice differentiable function. They consider the case of vectorial norms and they define the recession function of a convex, lower semicontinuous and proper function. In the last part of Chapter 1, the authors consider the optimization problem \( \inf[f(x):x\in C]\), especially in the case of a convex function \(f:\mathbb{R} ^{n}\rightarrow \overline{\mathbb{R}}\). They prove the uniqueness of a solution assuming that \(f\) is strictly convex and they recall properties of such strictly convex functions. For the existence of a solution, the authors introduce the notions of inf-compact and of strongly convex function. They finally recall Ekeland's variational principle. Chapter 2 deals with duality and subdifferentiability. The authors recall the notions of polar set, of dual cone, of positive or negative dual cones, and of polyhedral dual cone. They recall Minkowsky-Weil theorems. They recall the definition of the subdifferential of a convex function and its properties (more generally of set-valued applications). They prove that if \( f \) is a convex, lower-semicontinuous and proper function on \(\mathbb{R}^{n}\) , its subdifferential \(\partial f\) is cyclic monotone at every order \(p\), that it satisfies: \(0\geq \sum_{i=0}^{p}\left\langle x_{i}^{\ast },x_{i+1}-x_{i}\right\rangle \), for every \((x_{i},x_{i}^{\ast })\in G\), the graph of \(\partial f\), such that \((x_{p+1},x_{p+1}^{\ast })=(x_{0},x_{0}^{\ast })\). Chapter 3 starts with the primal minimization problem \(\alpha =\inf_{x}f(x)\), where \(f:\mathbb{R}^{n}\rightarrow \mathbb{R}\) is a convex, lower semi-continuous and proper function. The authors introduce a perturbation function \(\varphi :\mathbb{R}^{n}\times \mathbb{R}^{p}\rightarrow \mathbb{R}\) such that:.\(\varphi (x,0)=f(x)\), for every \(x\in \mathbb{R}^{n}\), which is convex, lower-semi-continuous and proper, and the function \(h:\mathbb{R} ^{p}\rightarrow \mathbb{R}\) defined as: \(h(u)=\inf_{x}\varphi (x,u)\). The function \(h\) is convex but not necessarily lower semi-continuous. The dual problem associated to the perturbation is defined as: \(\beta =\inf_{u^{\ast }}h^{\ast }(u^{\ast })=\inf_{u^{\ast }}\varphi ^{\ast }(0,u^{\ast })=-h^{\ast \ast }(0)\). The Lagrangian associated with \(\varphi \) is defined as \( l(x,u^{\ast })=\inf_{u}[\varphi (x,u)-\left\langle u^{\ast },u\right\rangle ]\), if \(x\in \mathrm{dom}(f)\), \(l(x,u^{\ast })=+\infty \), otherwise. It is concave with respect to \(u^{\ast }\) and convex with respect to \(x\). The authors prove that if \((\overline{x},\overline{u^{\ast }})\) is a saddle point of the Lagrangian \(l\), then \(\overline{x}\) is a solution of the primal minimization problem, \(\overline{u^{\ast }}\) is a solution to the dual minimization problem and \(\alpha +\beta =0\). They then consider the minimization problem with constraints \(\alpha =\inf_{x\in C}f(x)\), with \(C=\{x\in \mathbb{R} ^{n}:g_{i}(x)\leq 0\), \(i=1,\ldots ,p\}\), where the functions \(f,g_{i}: \mathbb{R}^{n}\rightarrow \mathbb{R}\) are convex, lower semi-continuous, proper, and satisfy Slater's condition: there exists \(\widetilde{x}\in \mathrm{int}(\mathrm{dom}(f))\) such that \(g_{i}(\widetilde{x})<0\), \(i=1,\ldots ,p\). They characterize a solution of the minimization problem with constraints in terms of the subdifferentials of \(f\) and \(g_{i}\). They then consider the case where the constraints also involve equalities \(Ax=a\), where \(A\) is a \( q\times n\) matrix of rank \(q\),\ and \(a\in \mathbb{R}^{q}\). They extend this last problem to the minimization problem \(\inf_{x}f(x)\) on the set \(C=\{x\in \mathbb{R}^{n}:Ax=a\), \(g_{i}(x)\leq 0\), \(i=1,\ldots ,p\}\) where the functions \(g_{i}:\mathbb{R}^{n}\rightarrow \mathbb{R}\) are convex, lower semi-continuous and proper, \(a\in \mathbb{R}^{q}\), \(A\) is a \(q\times n\) matrix of rank \(q\), and \(f\) is a differentiable function not necessarily convex. They prove the existence of a solution to this last minimization problem under an hypothesis on the data. They propose tools for linear programming based on duality. They prove that if \(X\subset \mathbb{R}^n\) and \(Y\subset \mathbb{R}^p\) are convex, compact and non empty, and if the function \(L:X\times Y\rightarrow \mathbb{R}\) is convex, lower semi-continuous with respect to the first variable, concave and upper semi-continuous with respect to the second variable, it has a saddle point. They discuss examples of situations where these tools may be applied. They then consider the sum \(s=f_{1}+f_{2}\) of two convex, lower semi-continuous and proper functions, which is also convex, lower semi-continuous and proper, together with its conjugate \( s^{\ast }\). The inf-convolution \(f_{1}^{\ast }\square f_{2}^{\ast }\) de \( f_{1}^{\ast }\) and \(f_{2}^{\ast }\) is the marginal function defined on \( \mathbb{R}^{n}\) by: \(f_{1}^{\ast }\square f_{2}^{\ast }(z^{\ast })=\inf_{x_{1}^{\ast }}[f_{1}^{\ast }(x_{1}^{\ast })+f_{2}^{\ast }(z^{\ast }-x_{1}^{\ast })]\). \(f_{1}^{\ast }\square f_{2}^{\ast }\) is proved to be convex, \(\overline{f_{1}^{\ast }\square f_{2}^{\ast }}\) is convex, lower semi-continuous and \(s(x)=sup_{z^{\ast }}[\left\langle z^{\ast },x\right\rangle -f_{1}^{\ast }\square f_{2}^{\ast }(z^{\ast })]=sup_{z^{\ast }}[\left\langle z^{\ast },x\right\rangle -\overline{ f_{1}^{\ast }\square f_{2}^{\ast }}(z^{\ast })]\). This leads to the definition of a proximal application and of a proximal algorithm. The chapter ends with the description of the simplex and Karmarkar's algorithms, that the authors illustrate with examples. Chapter 4 describes the monotonicity and maximal monotonicity properties of set-valued applications. \(E\) being a topological vector space and \(E^{\ast }\) its dual, to \(G\subset E\times E^{\ast }\), the authors associate the set-valued applications \(\Gamma :E\rightrightarrows E^{\ast }\) and \(\Gamma ^{\ast }:E^{\ast }\rightrightarrows E\) defined through \(\Gamma (x)=\{x^{\ast }\in E^{\ast }:(x,x^{\ast })\in G\}\) and \(\Gamma ^{\ast }(x^{\ast })=\{x\in E:(x,x^{\ast })\in G\}\). The graph \(G\subset E\times E^{\ast }\) is monotone if \(\left\langle x^{\ast }-y^{\ast },x-y\right\rangle \geq 0\) for all \( (x,x^{\ast }),(y,y^{\ast })\in G\). The authors prove some properties of this notion of monotonicity. \(G\subset E\times E^{\ast }\) is maximal monotone if it is monotone and if \(S\supset G\) with \(S\) monotone implies \(S=G\). The authors prove properties of this maximal monotonicity property. A monotone set-valued application \(\Gamma :\mathbb{R}^{n}\rightrightarrows \mathbb{R} ^{n}\), whose domain \(D\) has a non empty interior, is maximal monotone on \( V\subset \mathbb{R}^{n}\) if \(\Gamma \) coincides on \(V\) with every monotone set-valued application which contains \(\Gamma \). The authors prove that if \(V \) is a convex, open and non empty subset of \(D\), \(\Gamma \) is maximal monotone on \(V\) is and only if \(\Gamma \) is monotone and upper semi-continuous on \(V\) and if for all \(x\in V\) the set \(\Gamma (x)\) is convex, compact and non empty. The authors prove properties of such local maximal monotonicity. They prove that if \(f\) is a convex, lower semi-continuous and proper function on \(\mathbb{R}^{n}\), its subdifferential \(\partial f:\mathbb{R}^{n}\rightrightarrows \mathbb{R}^{n}\) is a maximal monotone application and that the set-valued application \(\Gamma :\mathbb{R} ^{n}\rightrightarrows \mathbb{R}^{n}\) with non-empty domain is the sub-differential of a convex function \(f\) if and only if it is cyclic maximal monotone. The function \(f\) is unique up to a constant. The authors discuss the properties of the proximal algorithm in the case of a maximal monotone set-valued application. They prove that the sum of two maximal monotone set-valued applications is maximal monotone under hypotheses concerning their domains and that if \(\Gamma \) is a maximal monotone set-valued application and \(A\) a \(n\times p\) matrix, \(A^{t}\Gamma A\) is maximal monotone if \(0\in \mathrm{int}(\mathrm{dom}(\Gamma ))\). The chapter ends with the presentation of cyclic monotone and maximal monotone set-valued applications and their properties. Chapter 5 deals with the presentation and the resolution of a general variational inequality written as: Find \(\overline{x}\in C\) such that \( \left\langle F(\overline{x}),x-\overline{x}\right\rangle \geq 0\), for every \(x\in C\), where \(C\subset \mathbb{R}^{n}\) is a closed convex set and \( F:C\rightarrow \mathbb{R}^{n}\) is continuous. In the case of a set-valued application \(F:\mathbb{R}^{n}\rightrightarrows \mathbb{R}^{n}\), which is maximal monotone on an open set \(\Omega \) containing \(C\), the authors propose four equivalent formulations of such variational inequalities. They prove the existence of solutions to such variational inequalities in the case of a set-valued application \(F:\mathbb{R}^{n}\rightrightarrows \mathbb{R }^{n}\) which is maximal monotone and assuming that \(C\subset \mathrm{int}(\mathrm{dom}(F))\) is a convex, non empty and compact set. The set of solutions is proved to be also convex, non empty and compact. The authors prove existence results if \( C\subset \mathrm{int}(\mathrm{dom}(F))\) is only convex and non empty, but satisfies further hypotheses. They finally analyze the uniqueness of such solutions. In the last Chapter 6, the authors analyze the link between duality and the resolution of variational inequalities.\ They consider a monotone set-valued application \(\Gamma _{0}:\mathbb{R}^{n}\rightrightarrows \mathbb{R}^{n}\), with non empty domain and with graph \(G_{0}\subset \mathbb{R}^{n}\times \mathbb{R}^{n}\), and the variational inequality: Find \(\overline{x}\in \mathbb{R}^{n}\) such that \(0\in \Gamma _{0}(\overline{x})\). In the case of a set-valued and monotone application \(\Gamma _{0}:\mathbb{R}^{n}\times \mathbb{R}^{p}\rightrightarrows \mathbb{R}^{n}\times \mathbb{R}^{p}\) whose graph \(G=\{(x,u,x^{\ast },u^{\ast }):(x^{\ast },u^{\ast })\in \Gamma (x,u)\}\) is such that.\((x,x^{\ast })\in G_{0}\Leftrightarrow \exists u^{\ast }\in \mathbb{R}^{p}\) such that \((x,0,x^{\ast },u^{\ast })\in G\), the preceding problem may be written as: Find \(\overline{x}\in \mathbb{R}^{n}\) such that there exists \(\overline{u}^{\ast }\in \mathbb{R}^{p}\) with \((\overline{x} ,0,0,\overline{u}^{\ast })\in G\). \(u\) is considered as a perturbative variable. The set \(D\subset (\mathbb{R}^{p}\times \mathbb{R}^{n})\times ( \mathbb{R}^{p}\times \mathbb{R}^{n})\) obtained from \(G\) when permuting the variables:.\((u^{\ast },x^{\ast },u,x)\in D\Leftrightarrow (x,u,x^{\ast },u^{\ast })\in G\) is monotone and may be associated to the set-valued application \(\Delta \) defined as: \(\Delta (u^{\ast },x^{\ast })=\{(u,x):(u^{\ast },x^{\ast },u,x)\in D\}\). The dual set-valued applications \(\Delta _{x^{\ast }}\) are defined through: \(\Delta _{x^{\ast }}(u^{\ast })=\{u:\exists x\in \mathbb{R}^{n}\) such that \((u^{\ast },x^{\ast },u,x)\in D\}\), and the dual variational inequality is: Find \(u^{\ast }\in \Delta _{x^{\ast }}^{-1}(0)=\{u^{\ast }\in \mathbb{R}^{p}:\) there exists \(x\) such that \((u^{\ast },x^{\ast },u,x)\in D\}\). The Lagrangian variational inequality is finally written as: Find \((x,u^{\ast })\in \Lambda ^{-1}(0,0)=\{(x,u^{\ast })\in \mathbb{R}^{n+p}:(x,u^{\ast },0,0)\in D\}\), where the set-valued application \(\Lambda \) is associated to the set \(L\) defined through \((x,u^{\ast },x^{\ast },u)\in L\Leftrightarrow (x,u,x^{\ast },u^{\ast })\in G\) as: \(\Lambda (x,u^{\ast })=\{(x^{\ast },u):(x,u^{\ast },x^{\ast },u)\in L\}\). The authors analyze the maximal monotone properties of these set-valued applications. They prove that the sum of two maximal monotone set-valued applications may be maximal monotone. They finally show how to deal with constraints and they illustrate their results with different examples. The book thus presents a complete analysis of convex optimization with a focus on the resolution of variational inequalities. As explained in the introduction, the authors do not present the associated numerical tools. Nevertheless, the book will be useful to readers involved in this important topic which has many applications in different sciences. Throughout the book, the authors illustrate their definitions with figures. They introduce different interesting examples.