<figure><img src="image_1.png" /></figure>

HAL
open science

# Selected Topics on Continuous Optimization and Nonsmooth Systems

Jean Charles Gilbert

<figure><img src="image_2.png" /></figure>

## To cite this version:

Jean Charles Gilbert. Selected Topics on Continuous Optimization and Nonsmooth Systems. Master. Palaiseau, France. 2019, pp.184. cel-01249369v3

HAL Id: cel-01249369

https://inria.hal.science/cel-01249369v3

Submitted on 21 Mar 2021

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
Selected Topics on
Continuous Optimization
and Nonsmooth Systems

Jean Charles GILBERT†

Monday 8th March, 2021 (11:00)

<footnote>† INRIA Paris, 2 rue Simone Iff, CS 42112, F-75589 Paris Cedex 12, France; Jean-Charles.Gilbert@inria.fr.</footnote>
<figure><img src="image_3.png" /></figure>
# Preface

This is a preliminary version of the lecture notes of a course given at the University Paris-Saclay in 2015-2021, pompously entitled *Advanced Continuous Optimization*, in *Master classes* simply and adequately named *Optimization*. Despite the use of the qualifier “advanced” in the title of the lectures, their ambition is rather modest, when one looks at the amount of subjects taken up and the level of the research articles, so that we did not keep this qualifier in the title of this document. Naming the course *Intermediate Continuous Optimization* would have been closer to the reality of its contents, but would have attracted less students and less readers! To be more specific, the goal of these lectures is to present and analyze concepts and algorithms in optimization and related domains that are too advanced for being taught in an introductory course, but that should be known by future engineers spending a substantial proportion of their activity in continuous optimization or by students wishing to get involved in the preparation of a PhD thesis in neighboring fields. In a way, these lectures and the present notes can be viewed as an access road to more advanced monographs such as [126, 21, 83, 50, 44, 76], to mention a few of our bookish sources, and a way of filling the gap between basic concepts and research papers in optimization and nonsmooth systems. Rather than being a collection of results, this contribution is meant to be didactic by dedicating a substantial part of its contents to the motivation of concepts and to the presentation of examples and counter-examples. If these lecture notes have awakened the curiosity of the reader or, better still, have deepened his/her knowledge, they will have reached their objective.

This compilation presents both theoretical and numerical subjects, *in a finite dimensional setting*. Whilst many stated results have they counterpart in infinite dimension, we believe that the analysis and algorithmics in finite dimension deserves some interest. First, it is much easier to address than in infinite dimensional spaces, often simpler, and can therefore be taught and learned more rapidly. Furthermore, the knowledge of what is true in finite dimension should allow the reader to make the differences with the infinite dimension corpus and the access to this one should be easier, like linear functional analysis presupposes knowledge in linear algebra. Also, the algorithms, at least those that we shall present in this monograph, find their full usefulness when they are implemented on a computer, which presupposes finite dimension. Readers interested in infinite dimension optimization can pursue the lecture with [21, 23].

The first chapter, entitled *Background*, recalls what should be known to read these lecture notes without difficulty: basic concepts in convex analysis, some less known results in nonsmooth analysis, which is the reason why we devote a little more space on
the generalized differentiability, in theoretical differentiable optimization (optimality conditions and linear optimization duality), and in algorithmics.

Chapter 2, entitled *Optimality Conditions*, starts with more advanced topics and covers the optimality conditions of an optimization problem with constraints expressed by the function inclusion $c(x) \in G$, for some function $c: \mathbb{E} \to \mathbb{F}$ defined between two Euclidean spaces and a closed convex set $G \subseteq \mathbb{F}$. First order optimality conditions are considered in the first place (section 2.1). There, a large part of the analysis is devoted to Robinson's constraint qualification, which generalizes to the present setting the Mangasarian-Fromovitz constraint qualification for sets defined by equality and inequality constraints. Next, the second order optimality conditions of an optimization problem with equality and inequality constraints is considered (section 2.2). This less often taught matter is important for designing, analyzing, and understanding the behavior of algorithms in nonlinear optimization. They can also be viewed as a preliminary step in the presentation of second order optimality conditions for the more general problem described above, which comes next (section ??).

...
# Table of Contents

The chapters and sections marked with the sign “▲” are unfinished, in progress. This does not mean that the unmarked sections are completed; for example, the proof of many results are not provided yet.

This draft of lecture notes is certainly perfectible. Thank you for sending to the author your constructive remarks and suggestions for improvement.

1 Background .................................................................................. 9

1.1 Notation .................................................................................. 9

1.2 Convex Analysis ........................................................................ 10

1.2.1 Convex Set ........................................................................ 10

1.2.2 Hulls .................................................................................. 11

1.2.3 Convex Polyhedron ............................................................ 13

1.2.4 Relative Interior...................................................................... 13

1.2.5 Dual Cone and Farkas Lemma ............................................ 15

1.2.6 Tangent and Normal Cones .................................................. 17

1.2.7 Projection ............................................................................ 19

1.2.8 Asymptotic Cone .................................................................... 20

1.2.9 Convex Function .................................................................... 21

1.2.10 Asymptotic Function ............................................................ 23

1.2.11 Subdifferentiability ............................................................ 25

Notes ................................................................................................. 26

Exercises ............................................................................................ 26

1.3 Nonsmooth Analysis .................................................................... 27

1.3.1 Lower semi-continuity ............................................................ 27

1.3.2 Lipschitz Continuity .............................................................. 28

1.3.3 Differentiability .................................................................... 28

1.3.4 Multifunction ............................................................................ 29

Notes ................................................................................................. 31

Exercises ............................................................................................ 31

1.4 Optimization .................................................................................. 31

1.4.1 Generic Problem .................................................................... 31

1.4.2 Peano-Kantorovich Optimality Condition ................................. 32

1.4.3 Equality Constrained Problem ($P_E$) .................................... 34

1.4.4 Equality and Inequality Constrained Problem ($P_{EI}$) ............ 37

1.4.5 Abstract Duality ...................................................................... 41

1.4.6 Linear Optimization Problem ($P_L$) .................................... 43
<table><tbody><tr><td>1.5 Algorithmics</td><td>45</td></tr><tr><td>1.5.1 Speeds of Convergence</td><td>45</td></tr><tr><td>1.5.2 Newton and Quasi-Newton Algorithms ▲</td><td>46</td></tr><tr><td>1.5.3 Global Convergence in Unconstrained Optimization ▲</td><td>47</td></tr><tr><td>1.5.4 Global Convergence for Nonlinear Equations ▲</td><td>49</td></tr><tr><td><b>2 Optimality Conditions</b></td><td><b>51</b></td></tr><tr><td>2.1 First Order Optimality Conditions for (P<sub>G</sub>)</td><td>51</td></tr><tr><td>2.1.1 Definition of the General Problem</td><td>51</td></tr><tr><td>2.1.2 First Order Optimality Conditions</td><td>53</td></tr><tr><td>2.1.3 Robinson's Condition</td><td>57</td></tr><tr><td>2.1.4 Robinson's Constraint Qualification</td><td>71</td></tr><tr><td>2.1.5 Set of optimal multipliers</td><td>73</td></tr><tr><td>2.1.6 Other problems ▲</td><td>76</td></tr><tr><td>Notes</td><td>79</td></tr><tr><td>Exercises</td><td>80</td></tr><tr><td>2.2 Second Order Optimality Conditions for (P<sub>EI</sub>)</td><td>82</td></tr><tr><td>2.2.1 Critical Cone</td><td>83</td></tr><tr><td>2.2.2 Three Instructive Examples</td><td>85</td></tr><tr><td>2.2.3 Second Order Necessary Optimality Conditions</td><td>86</td></tr><tr><td>2.2.4 Second Order Sufficient Optimality Conditions</td><td>90</td></tr><tr><td>Notes</td><td>92</td></tr><tr><td>Exercises</td><td>92</td></tr><tr><td><b>3 Perturbation Analysis</b></td><td><b>95</b></td></tr><tr><td>3.1 Linear System ▲</td><td>95</td></tr><tr><td>3.2 Nonlinear System ▲</td><td>95</td></tr><tr><td>3.3 Optimization ▲</td><td>95</td></tr><tr><td>Notes</td><td>96</td></tr><tr><td><b>4 A Few Methods for Nonsmooth Systems</b></td><td><b>97</b></td></tr><tr><td>4.1 Josephy-Newton Algorithm for Functional Inclusions</td><td>98</td></tr><tr><td>4.1.1 A Gallery of Problems</td><td>98</td></tr><tr><td>4.1.2 The Josephy-Newton Algorithm</td><td>101</td></tr><tr><td>4.1.3 Regularity</td><td>102</td></tr><tr><td>4.1.4 Speed of Convergence</td><td>108</td></tr><tr><td>4.1.5 Local Convergence</td><td>110</td></tr><tr><td>4.1.6 Globalization by Line-Search ▲</td><td>112</td></tr><tr><td>Notes</td><td>112</td></tr><tr><td>Exercises</td><td>112</td></tr><tr><td>4.2 B-Newton Method for Systems of Equations ▲</td><td>114</td></tr><tr><td>4.3 Linearization method for PC<sup>1</sup> functions ▲</td><td>114</td></tr><tr><td>4.4 Semismooth Newton Method for nonlinear systems</td><td>114</td></tr><tr><td>4.4.1 Motivation, Orientation, Examples</td><td>114</td></tr><tr><td>4.4.2 Generalized Differentiability</td><td>118</td></tr><tr><td>4.4.3 Semismoothness ▲</td><td>122</td></tr><tr><td>4.4.4 The Semismooth Newton Method ▲</td><td>126</td></tr></tbody></table>
<table><tbody><tr><td>4.4.5</td><td>Globalization by linesearch ▲</td><td>127</td></tr><tr><td>4.4.6</td><td>Globalization by trust regions ▲</td><td>128</td></tr><tr><td>4.4.7</td><td>Examples of use ▲</td><td>128</td></tr><tr><td></td><td>Notes</td><td>128</td></tr><tr><td></td><td>Exercises</td><td>128</td></tr><tr><td>4.5</td><td>Reformulation Methods for Complementarity Problems ▲</td><td>128</td></tr><tr><td>4.5.1</td><td>Fischer-Newton Algorithm</td><td>130</td></tr><tr><td>4.5.2</td><td>Newton-Min Algorithm</td><td>131</td></tr><tr><td></td><td>Notes</td><td>131</td></tr><tr><td>5</td><td>A Few Methods for Optimization</td><td>133</td></tr><tr><td>5.1</td><td>SQP Algorithm for (P<sub>EI</sub>)</td><td>133</td></tr><tr><td>5.1.1</td><td>The SQP Algorithm</td><td>134</td></tr><tr><td>5.1.2</td><td>Local Convergence</td><td>138</td></tr><tr><td>5.1.3</td><td>Exact Penalization</td><td>141</td></tr><tr><td>5.1.4</td><td>Globalization by Line-Search for (P<sub>EI</sub>) ▲</td><td>146</td></tr><tr><td>5.1.5</td><td>Globalization by Trust-Region for (P<sub>E</sub>) ▲</td><td>152</td></tr><tr><td></td><td>Notes ▲</td><td>152</td></tr><tr><td></td><td>Exercises</td><td>152</td></tr><tr><td>5.2</td><td>SQP Algorithm for (P<sub>G</sub>) ▲</td><td>153</td></tr><tr><td>5.2.1</td><td>The SQP Algorithm</td><td>153</td></tr><tr><td>5.2.2</td><td>Local Convergence</td><td>154</td></tr><tr><td>6</td><td>Self-dual Conic Optimization</td><td>155</td></tr><tr><td>6.1</td><td>Semidefinite Optimization</td><td>156</td></tr><tr><td>6.1.1</td><td>Primal and Dual Problems</td><td>156</td></tr><tr><td>6.1.2</td><td>Examples of SDO Formulation</td><td>160</td></tr><tr><td>6.1.3</td><td>Existence of Solution, Optimality Conditions</td><td>163</td></tr><tr><td>6.1.4</td><td>Interior Point Algorithms ▲</td><td>167</td></tr><tr><td>6.1.5</td><td>A Nonsmooth Algorithm ▲</td><td>170</td></tr><tr><td></td><td>Notes</td><td>170</td></tr><tr><td></td><td>Exercises</td><td>170</td></tr><tr><td>6.2</td><td>Circular Optimization ▲</td><td>170</td></tr><tr><td>6.3</td><td>Copositive Optimization ▲</td><td>170</td></tr></tbody></table>

Appendices

A References 173

B Index 181
<figure><img src="image_4.png" /></figure>
# 1 Background

In these notes, vector spaces are always assumed to have finite dimension; they are usually denoted by the letters $\mathbb{E}$, $\mathbb{F}$, $\mathbb{G}$, ...

## 1.1 Notation

The set of nonnegative integers is denoted by $\mathbb{N}$ and an interval of integers is denoted by

$$[n_1:n_2] := \{n_1, \dots, n_2\},$$

where we have assumed that the integers $n_1$ and $n_2$ verify $n_1 \le n_2$.

The set of real numbers is denoted by $\mathbb{R}$ and we note

$$\bar{\mathbb{R}} := \mathbb{R} \cup \{-\infty, +\infty\}, \quad \mathbb{R}_+ := \{t \in \mathbb{R} : t \ge 0\}, \quad \mathbb{R}_{++} := \{t \in \mathbb{R} : t > 0\},$$

$\mathbb{R}_- := -\mathbb{R}_+$, and $\mathbb{R}_{--} := -\mathbb{R}_{++}$. For $a \le b$ in $\mathbb{R}$, one defines the *intervals*

$$[a, b] := \{t \in \mathbb{R} : a \le t \le b\},$$

$$[a, b) := \{t \in \mathbb{R} : a \le t < b\},$$

$$(a, b] := \{t \in \mathbb{R} : a < t \le b\},$$

$$(a, b) := \{t \in \mathbb{R} : a < t < b\}.$$

Hence, the last three intervals are empty if $a = b$.

The set of real vectors of integer dimension $n \ge 0$ is denoted by $\mathbb{R}^n$. Inequalities in $\mathbb{R}^n$ must be understood componentwise; hence, for $a$ and $b \in \mathbb{R}^n$, $a \le b$ (resp. $a < b$) means $a_i \le b_i$ (resp. $a_i < b_i$) for all $i \in [1:n]$. We note

$$\mathbb{R}_+^n := \{x \in \mathbb{R}^n : x \ge 0\}, \quad \mathbb{R}_{++}^n := \{x \in \mathbb{R}^n : x > 0\},$$

$$\mathbb{R}_- := -\mathbb{R}_+^n, \text{ and } \mathbb{R}_{--} := -\mathbb{R}_{++}^n.$$

The *Minkowski sum* of two subsets $P$ and $Q$ of a vector space $\mathbb{E}$ is denoted and defined by

$$P + Q := \{x + y : x \in P, y \in Q\}.$$

When $P$ is the singleton $\{x\}$, we simply write $x + Q$ for $\{x\} + Q$. For $\Lambda \subseteq \mathbb{R}$ and $P \subseteq \mathbb{E}$, we note

$$\Lambda P := \{\lambda x : \lambda \in \Lambda, x \in P\}.$$

When $\Lambda$ is the singleton $\{\lambda\}$, we simply note $\lambda P$ for $\{\lambda\}P$. Note that $P - P$ contains 0 but is usually not reduced to $\{0\}$, unless $P$ is a singleton. Similarly, $P + P$ contains $2P$,
but the two sets are usually different, unless $P$ is convex (definition in section 1.2.1 below).

If $\mathbb{E}$ and $\mathbb{F}$ are two vector spaces, the adjoint of a linear map $A : \mathbb{E} \to \mathbb{F}$ is the linear map $A^* : \mathbb{F} \to \mathbb{E}$ uniquely defined by:

$$ \forall (x, y) \in \mathbb{E} \times \mathbb{F} : \langle A^*y, x \rangle = \langle y, Ax \rangle. $$

Because of their finite dimension, there is no restriction in assuming that vector spaces are equipped with a norm, denoted by $\| \cdot \|$, or even with a scalar product, denoted by $\langle \cdot, \cdot \rangle$. It is the topology associated with this norm or scalar product that is assumed to equip the vector space. The open and closed unit balls centered at the origin are then denoted by

$$ B := \{x \in \mathbb{E} : \|x\| < 1\} \quad \text{and} \quad \bar{B} := \{x \in \mathbb{E} : \|x\| \le 1\}. $$

For $x \in \mathbb{E}$ and $r > 0$, we also use the notation $B(x, r) := x + rB$ and $\bar{B}(x, r) := x + r\bar{B}$ for the open and closed balls of radius $r$, centered at $x$. The interior of a set $S \subseteq \mathbb{E}$ is denoted by $\text{int}(S)$, $\text{int} S$, or $S^\circ$, and its closure by $\text{cl}(S)$, $\text{cl} S$, or $\bar{S}$. The set of neighborhoods of a point $x \in \mathbb{E}$ is denoted by $\mathcal{N}(x)$.

In a normed space $(\mathbb{E}, \| \cdot \|)$, the distance to a set, say $S \subseteq \mathbb{E}$, is denoted and defined at $x \in \mathbb{E}$ by

$$ \text{dist}(x, S) := \inf_{x' \in S} \|x' - x\|. \qquad (1.1) $$

By definition of the infimum, this distance is infinite when $S = \emptyset$.

When $\mathbb{E}$ is a Euclidean vector space, the gradient of a function $f : \mathbb{E} \to \mathbb{R}$ at $x$, denoted $\nabla f(x)$, is the unique vector of $\mathbb{E}$ defined from the derivative $f'(x)$ by

$$ \langle \nabla f(x), d \rangle = f'(x) \cdot d, \quad \forall d \in \mathbb{E}. $$

Note that the gradient depends on the chosen scalar product of $\mathbb{E}$, which is not the case for the derivative.

# 1.2 Convex Analysis

## 1.2.1 Convex Set

Let $\mathbb{E}$ be a finite dimensional vector space. With two points $x_0$ and $x_1$ of $\mathbb{E}$, one can form the following segments of $\mathbb{E}$:

$$ [x_0, x_1] := \{(1-t)x_0 + tx_1 : t \in [0, 1]\}, $$

$$ [x_0, x_1) := \{(1-t)x_0 + tx_1 : t \in [0, 1]\}, $$

$$ (x_0, x_1] := \{(1-t)x_0 + tx_1 : t \in (0, 1]\}, $$

$$ (x_0, x_1) := \{(1-t)x_0 + tx_1 : t \in (0, 1]\}. $$

Hence, when $x_0 = x_1$, these four segments are reduced to the single point $\{x_0\}$.

A set $C \subseteq \mathbb{E}$ is convex if

$$ \forall (x_0, x_1) \in C^2 : \ [x_0, x_1] \subseteq C. $$
Convex Sets Calculus

Here are some other convex sets encountered in these notes.

• The Minkowski sum $C_1 + C_2$ of two convex sets $C_1$ and $C_2$ is a convex set.

• The product $\alpha C := \{\alpha x : x \in C\}$ of a scalar $\alpha \in \mathbb{R}$ by a convex set $C$ is a convex set.

• If $\{C_i\}_{i \in I}$ is an arbitrary family of convex sets of a vector space $\mathbb{E}$, then their intersection $\cap_{i \in I} C_i$ is a convex set (but not their union!).

• If $A : \mathbb{E} \to \mathbb{F}$ is a linear map between two vector spaces $\mathbb{E}$ and $\mathbb{F}$, the direct image $A(C) := \{Ax : x \in C\}$ (resp. the inverse image $A^{-1}(C) := \{x \in \mathbb{E} : Ax \in C\}$) of a convex set $C$ of $\mathbb{E}$ (resp. of $\mathbb{F}$) by $A$ is a convex set.

• Let $C_1 \subseteq \mathbb{E}_1$ and $C_2 \subseteq \mathbb{E}_2$. Then, $C_1 \times C_2$ is convex in $\mathbb{E}_1 \times \mathbb{E}_2$ if and only if $C_1$ and $C_2$ are convex.

Examples of Convex Sets

Here are some other convex sets encountered in these notes.

• The unit simplex of $\mathbb{R}^n$ is the set

$$ \Delta_n := \{x \in \mathbb{R}^n : e^T x = 1, x \ge 0\}, $$

where $e = (1, \dots, 1) \in \mathbb{R}^n$.

• The cone (see below) of positive semidefinite symmetric matrices of order $n$ is convex and denoted by $S_+^n$. The notation $M \ge 0$ means that $M \in S_+^n$.

• The cone of positive definite symmetric matrices of order $n$ is convex and denoted by $S_{++}^n$. The notation $M > 0$ means that $M \in S_{++}^n$.

1.2.2 Hulls

Affine and Vector Hulls

The affine hull of an arbitrary set $P \subseteq \mathbb{E}$ is the smallest affine space containing $P$:

$$ \text{aff } P := \bigcap \{A : A \text{ is an affine space containing } P\}. $$

This definition makes sense since the intersection of an arbitrary collection of affine spaces of $\mathbb{E}$ is an affine space of $\mathbb{E}$. It can be shown that

$$ \text{aff } P = \left\{ \sum_{i=1}^{m} \alpha_i x_i : m \in \mathbb{N}, \text{ all } x_i \in P, \alpha_i \in \mathbb{R}^m, e^T \alpha = 1 \right\}, $$

where we have denoted by $e$ the vector of all ones.

The vector hull of an arbitrary set $P \subseteq \mathbb{E}$ is the smallest subspace of $\mathbb{E}$ containing $P$:

$$ \text{vect } P := \bigcap \{E : E \text{ is a subspace containing } P\}. $$

This definition makes sense since the intersection of an arbitrary collection of subspaces of $\mathbb{E}$ is a subspace of $\mathbb{E}$. It is not difficult to see that

$$ \text{vect } P = \text{aff}(P \cup \{0\}) = \left\{ \sum_{i=1}^{m} \alpha_i x_i : m \in \mathbb{N}, \text{ all } x_i \in P, \alpha_i \in \mathbb{R}^m \right\}. $$
### Convex Hull

The convex hull of an arbitrary set $P \subseteq \mathbb{E}$ is the smallest convex set containing $P$:

$$ \co P := \bigcap \{C : C \text{ is a convex set containing } P\}. $$

This definition makes sense since the intersection of an arbitrary collection of convex sets of $\mathbb{E}$ is a convex set of $\mathbb{E}$. It can be shown that

$$ \co P = \left\{ \sum_{i=1}^{m} \alpha_i x_i : m \in \mathbb{N}, \text{ all } x_i \in P, \alpha_i \in \mathbb{R}_+^m, e^T \alpha = 1 \right\}. $$

In finite dimension, one can limit $m$ in the previous sum to $\dim \mathbb{E}+1$ (Carathéodory [29; 1907]) and this observation yields the following important implication:

$$ P \text{ is compact} \quad \Rightarrow \quad \co P \text{ is compact.} \qquad (1.2) $$

But, even if $P$ is closed, $\co P$ may not be closed, which motivates the introduction of the following concept.

### Closed Convex Hull

The closed convex hull of an arbitrary set $P \subseteq \mathbb{E}$ is the smallest closed convex set containing $P$:

$$ \overline{\co} P := \bigcap \{C : C \text{ is a closed convex set containing } P\}. $$

This definition makes sense since the intersection of an arbitrary collection of closed convex sets of $\mathbb{E}$ is a closed convex set of $\mathbb{E}$. It can be shown that

$$ \overline{\co} P = \overline{\co} P. $$

### Conic Hull

Recall that a part $K$ of a vector space $\mathbb{E}$ is a cone if $\mathbb{R}_+^K \subseteq K$, which means that there must hold $tx \in K$ each time $t > 0$ and $x \in K$. Hence a cone may or may not contain zero (this is the reason why $t$ is taken in $\mathbb{R}_+$ above and not in $\mathbb{R}_+$), which allows us to talk about the cone of positive definite symmetric matrices. The conical hull of an arbitrary set $P \subseteq \mathbb{E}$ is the smallest convex cone containing $P^1$:

$$ \text{cone } P := \bigcap \{K : K \text{ is a convex cone containing } P\}. $$

This definition makes sense since the intersection of an arbitrary collection of convex cones of $\mathbb{E}$ is a convex cone of $\mathbb{E}$. It can be shown that

$$ \text{cone } P = \left\{ \sum_{i=1}^{m} \alpha_i x_i : m \in \mathbb{N}, \text{ all } x_i \in P, \alpha_i \in \mathbb{R}_+^m \right\}. $$

<footnote n="1">¹ Rockafellar [125; p. 14] finds it convenient to add the origin to cone $P$, which makes no difference with our definition when $0 \in P$.</footnote>
### 1.2.3 Convex Polyhedron

A convex polyhedron of a vector space $\mathbb{E}$ is a set of the form

$$ P = \{x \in \mathbb{E} : Ax \leq b\}, \qquad (1.3) $$

where $A : \mathbb{E} \to \mathbb{R}^m$ is a linear map and $b \in \mathbb{R}^m$. A convex set that can be written as the set $P$ above is said to be *polyhedral*. A convex polyhedron is therefore an intersection of a finite number of half spaces, namely $\{x \in \mathbb{E} : (Ax - b)_i \leq 0\}$ for $i \in [1:m]$, hence it is closed and convex. For $P$ of the form (1.3) and for $x \in P$, one defines

$$ I(x) := \{i \in [1:m] : (Ax - b)_i = 0\}. \qquad (1.4) $$

It is clear that

$$ (\{x_k\} \to x) \implies I(x_k) \subseteq I(x) \text{ for } k \text{ large.} \qquad (1.5) $$

The representation of a polyhedron by (1.3) is qualified as *dual*, since it involves linear operators (hence elements of the dual space of $\mathbb{E}$). Such a set has also a *primal representation*, which makes use of convex and conic hulls. Indeed, the set $P$ in (1.3) can also be written in the following form

$$ P = \text{co}\{x_1, \dots, x_p\} + \text{cone}\{y_1, \dots, y_q\}, \qquad (1.6) $$

where $\{x_i\}_{i \in [1:p]}$ are points of $\mathbb{E}$ and $\{y_j\}_{j \in [1:q]}$ are “directions” of $\mathbb{E}$ (another name for a point of $\mathbb{E}$, to quote that it is used here to generate a cone). The converse is also true: any set of the form (1.6) can be written in the form (1.3). This equivalence between these representations of a convex polyhedron has been shown by Minkowski.

### Proposition 1.1 (polyhedrality properties)

1) Linear transformation if $P \subseteq \mathbb{E}$ is a convex polyhedron and $T : \mathbb{E} \to \mathbb{F}$ is linear, then $T(P) \subseteq \mathbb{F}$ is a convex polyhedron.

2) Addition: if $P_1$ and $P_2$ are polyhedra, then $P_1 + P_2$ is a polyhedron.

3) Upper semi-continuity of $I$: for $x \in P$, $\exists \delta > 0$ such that $x' \in B(x, \delta) \cap P$ implies that $I(x') \subseteq I(x)$.

### 1.2.4 Relative Interior

The relative interior of $P \subseteq \mathbb{E}$ is its interior in aff $P$ equipped with the relative topology, the one induced from that of $\mathbb{E}$:

$$ \text{ri} P := \{x \in P : \exists r > 0 \text{ such that } [B(x, r) \cap \text{aff } P] \subseteq P\}. $$

Note that $P_1 \subseteq P_2$ does not necessarily imply that $\text{ri} P_1 \subseteq \text{ri} P_2$, but one has

$$ P_1 \subseteq P_1 \quad \text{and} \quad \text{aff } P_1 = \text{aff } P_2 \implies \text{ri } P_1 \subseteq \text{ri } P_2. \qquad (1.7) $$

In finite dimension, the following holds
$$ C \text{ convex and nonempty} \implies \begin{cases} \mathrm{ri} C \neq \emptyset, \\ \mathrm{aff}(\mathrm{ri} C) = \mathrm{aff} C. \end{cases} \qquad (1.8) $$

**Lemma 1.2** Let $C$ be a nonempty convex set and $x \in \mathbb{E}$. Then,

$$ x \in \mathrm{ri} C \text{ and } y \in \bar{C} \implies [x, y) \subseteq \mathrm{ri} C. $$

**Proposition 1.3 (relative interior criterion)** Let $C$ be a nonempty convex set and $x \in \mathbb{E}$. Then,

$$ x \in \mathrm{ri} C \iff \forall x_0 \in C, \exists t > 1 : (1-t)x_0 + tx \in C, \qquad (1.9a) $$

$$ \iff \forall x_0 \in \mathrm{aff} C, \exists t > 1 : (1-t)x_0 + tx \in C. \qquad (1.9b) $$

Let $C$ be a nonempty convex set. Then,

$\mathrm{ri} C$ and $\bar{C}$ are convex,

$$ \mathrm{aff} \bar{C} = \mathrm{aff} C, $$

$$ \overline{\mathrm{ri} C} = \bar{C} \quad \text{and} \quad \mathrm{ri} \bar{C} = \mathrm{ri} C. \qquad (1.10) $$

In short, the last identities tell us that, when the two operators “ri” and “cl” act in sequence on $C$, it is always the last one acting that prevails.

**Proposition 1.4 (relative interior calculus)** Let $\mathbb{E}$, $\mathbb{E}_1$, $\mathbb{E}_2$, and $\mathbb{F}$ be vector spaces and $A : \mathbb{E} \to \mathbb{F}$ be a linear map.

1) (Cartesian product) If $C_1 \subseteq \mathbb{E}_1$ and $C_2 \subseteq \mathbb{E}_2$ are convex sets, then

$$ \mathrm{ri}(C_1 \times C_2) = (\mathrm{ri} C_1) \times (\mathrm{ri} C_2). $$

2) (Intersection) If $(C_i)_{i \in I}$ is a family of convex sets in $\mathbb{E}$ such that $\cap_{i \in I} \mathrm{ri} C_i$ is nonempty, then

$$ \mathrm{ri}(\cap_{i \in I} C_i) \subseteq \cap_{i \in I} \mathrm{ri} C_i. \qquad (1.11) $$

with equality if $I$ is finite.

3) (Linear map) If $C \subseteq \mathbb{E}$ is a convex set, then
$$ \mathrm{ri}(A(C)) = A(\mathrm{ri} C). \qquad (1.12) $$

4) (Linear preimage) If $C \subseteq \mathbb{F}$ is a convex set and if the preimage $A^{-1}(\mathrm{ri} C) \neq \emptyset$, then

$$ \mathrm{ri}(A^{-1}(C)) = A^{-1}(\mathrm{ri} C). $$

5) (Multiplication) If $C \subseteq \mathbb{E}$ is a convex set and $\alpha \in \mathbb{R}$, then

$$ \mathrm{ri}(\alpha C) = \alpha (\mathrm{ri} C). $$

6) (Sum) If $C_1 \subseteq \mathbb{E}$ and $C_2 \subseteq \mathbb{E}$ are convex sets, then

$$ \mathrm{ri}(C_1 + C_2) = (\mathrm{ri} C_1) + (\mathrm{ri} C_2). \qquad (1.13) $$

A point $x$ in a subset $P \subseteq \mathbb{E}$ is said to be *absorbing*<fnref n="2" /> for $P$ if $\forall d \in \mathbb{E}$, $\exists t > 0$ such that $x + td \in P$. In *finite dimension* and for a convex set $C$, one can certify the interiority of a point by looking along all the directions, since the following holds

$$ x \in \mathrm{int} C \iff x \text{ is absorbing for } C. \qquad (1.14) $$

### 1.2.5 Dual Cone and Farkas Lemma

Let $P$ be a subset of a Euclidean vector space $\mathbb{E}$. The (positive) dual cone of $P$ is defined and denoted by

$$ P^+ := \{d \in \mathbb{E} : \langle d, x \rangle \ge 0, \forall x \in P\}. $$

It is a nonempty close convex cone. When $P = E_0$ is a subspace of $\mathbb{E}$, $E_0^+$ is the subspace orthogonal to $E_0$, denoted by $E_0^- := \{d \in \mathbb{E} : \langle d, x \rangle = 0, \forall x \in E_0\}$. A cone is said to be *self-dual* if $K^+ = K$. The *negative dual cone* of a set $P$ is

$$ P^- := -P^+. $$

The *bidual cone* of $P$, denoted $P^{++}$, is the dual cone of the dual cone of $P$:

$$ P^{++} := (P^+)^+. $$

Points in the interior (if any) and relative interior of $P^+$ are characterized in exercise 1.2.10.

The next lemma is of paramount importance for chapter 2. It gives a description of the closure of the linear image of a convex cone, using dual cones. We have denoted by $A^*$ the *adjoint* of the linear map $A$.

<footnote n="2">² The terms *absorbent point* are also used instead of *absorbing point*.</footnote>
**Lemma 1.5 (Farkas, generalized)** Let $\mathbb{E}$ and $\mathbb{F}$ be two Euclidean spaces, $A: \mathbb{E} \to \mathbb{F}$ be a linear map, and $K$ be a nonempty convex cone of $\mathbb{E}$. Then,

$$ \overline{A(K)} = \{y \in \mathbb{F} : A^*y \in K^+\}^+. \qquad (1.15) $$

**Remarks 1.6 1)** In general, one cannot get rid of the closure on $A(K)$ in the left-hand side of (1.15), since the dual cone in the right-hand side is closed, while the linear map of a nonempty (even closed) convex cone is not necessary closed. Here is a counter-example, using the circular cone $K = \mathbb{R}_{\nabla}^3$ (see also section 6.2): the image of

$$ \mathbb{R}_{\nabla}^3 = \{x \in \mathbb{R}^3 : x_3 \ge \|(x_1, x_2)\|_2\} \quad \text{by} \quad A: \mathbb{R}^3 \to \mathbb{R}^2 : x \mapsto (x_1, x_2 + x_3) $$

is the non closed cone $A(\mathbb{R}_{\nabla}^3) = \{x \in \mathbb{R}^2 : x_2 > 0\} \cup \{(0, 0)\}$.

2) If $K$ is polyhedral, then $A(K)$ is polyhedral (a property recalled in section 1.2.3), hence closed, so that the closure in the left-hand side of (1.15) can be discarded (see exercise 1.2.8).

3) For $K = \mathbb{E}$, one recovers the linear algebra identity $\mathcal{R}(A) = \mathcal{N}(A^*)^{\perp}$.

4) The importance of the Farkas lemma lies also on the fact that it is an existence result. This is more easily described when $A(K)$ is closed. Then, the identity (1.15) tells us that, when a vector $d$ has a certain property (i.e., it has a nonnegative scalar product with any vector $y$ such that $A^*y \in K^+$), there exists a vector $x \in K$ such that $d = Ax$. In optimization, one uses this lemma to prove the existence of optimal multipliers (see the proof of theorems 1.40 and 2.6).

5) Assume that $K$ is a nonempty convex cone. Applying the Farkas identity (1.15) with $A = I$, the identity in $\mathbb{E} = \mathbb{F}$, yields

$$ K^{++} = \overline{K}. \qquad (1.16) $$

6) The proof of the Farkas identity (1.15) can be obtained by a separation argument (if the inclusion $\supseteq$ does not hold, one separates $A(\overline{K})$ and a point not belonging to it by a proper hyperplane). Now, it is not difficult to obtain (1.15) as a consequence of (1.16), which has been viewed as a consequence of (1.15)! Actually, (1.16) could also be proved by a separation argument. To deduce (1.15) from (1.16), first observe that

$$ A(K)^+ = \{y \in \mathbb{F} : A^*y \in K^+\}, \qquad (1.17) $$

which is easy to prove. Then, take the dual of both sides of this identity and observe that, since $A(K)$ is a convex cone, its bidual is its closure by (1.16). The identity (1.15) follows. $\square$
**Proposition 1.7 (dual cone calculus)** Let $\mathbb{E}$ be a Euclidean vector space.

1) If $P_1$ and $P_2$ are two nonempty subsets of $\mathbb{E}$, then

$$P_1 \subseteq P_2 \quad \Rightarrow \quad P_1^+ \supseteq P_2^+.$$

2) If $P$ is a nonempty subset of $\mathbb{E}$, then

$$P^+ = (\mathbb{R}_+ P)^+ = (\text{co } P)^+ = (\text{cl } P)^+. \quad (1.18)$$

3) If $P$ is a nonempty subset of $\mathbb{E}$, then

$$P^{++} = \overline{\text{co}}(\mathbb{R}_+ P). \quad (1.19)$$

In particular,

$$P \subseteq P^{++},$$

with equality if and only if $P$ is a nonempty closed convex cone.

4) For nonempty subsets $P_1$ and $P_2$ of $\mathbb{E}$, one has

$$(P_1 + P_2)^+ \supseteq P_1^+ \cap P_2^+,$$

with equality if $0 \in \overline{P_1} \cap \overline{P_2}$. In particular, if $K_1$ and $K_2$ are two nonempty cones, one has

$$(K_1 + K_2)^+ = K_1^+ \cap K_2^+. \quad (1.20)$$

5) If $K_1$ and $K_2$ are two nonempty closed convex cones, then

$$(K_1 \cap K_2)^+ = \overline{K_1^+ + K_2^+}. \quad (1.21)$$

6) If $(P_i)_{i \in I}$ is an arbitrary family of nonempty subsets $P_i$ of $\mathbb{E}$, then

$$(\bigcup_{i \in I} P_i)^+ = \bigcap_{i \in I} P_i^+.$$

7) If $(\mathbb{E}_1, \langle \cdot, \cdot \rangle_1)$ and $(\mathbb{E}_2, \langle \cdot, \cdot \rangle_2)$ are two Euclidean spaces, if $\mathbb{E}_1 \times \mathbb{E}_2$ is equipped with the scalar product $\langle (x_1, x_2), (y_1, y_2) \rangle = \langle x_1, y_1 \rangle_1 + \langle x_2, y_2 \rangle_2$, and if $\emptyset \neq Q_1 \subseteq \mathbb{E}_1$ and $\emptyset \neq Q_2 \subseteq \mathbb{E}_2$, then

$$(Q_1 \times Q_2)^+ \supseteq Q_1^+ \times Q_2^+,$$

with equality when $0 \in \text{cl}(Q_1) \cap \text{cl}(Q_2)$.

### 1.2.6 Tangent and Normal Cones

Let $C$ be a closed convex set of a vector space $\mathbb{E}$. The cone of feasible directions to $C$ at $x \in C$ is defined and denoted by

$$T_x^f C \equiv T_C^f(x) := \mathbb{R}_+(C - x).$$
An element of that cone is called a feasible direction; such a direction $d \in \mathbb{E}$ is therefore characterized by the fact that there is a $t > 0$ such that $x + td \in C$ (or, by the convexity of $C$, $x + td \in C$ for all sufficiently small $t > 0$). Note that, by convexity of $C$, $t(C - x) \subseteq C - x$ when $t \in [0, 1]$, so that one also have $T_C^f(x) := [1, \infty)(C - x)$.

The cone of feasible directions is usually not a closed set. For example, when $C$ is the unit closed ball of $\mathbb{R}^2$, $T_{(0,-1)}C = \{x \in \mathbb{R}^2 : x_2 > 0\} \cup \{(0,0)\}$, which is not closed. The tangent cone to $C$ at $x \in C$ is the closure of the cone of feasible directions. It is denoted by

$$T_x C \equiv T_C(x) = \overline{\mathbb{R}_+(C - x)}. \qquad (1.22)$$

When $x \notin C$, one sets $T_C^f(x) = \emptyset$ and $T_C(x) = \emptyset$. The cone of feasible directions is not necessary the relative interior of the tangent cone. For example, as indicated below, when $C$ is a convex polyhedron, $T_x^f C$ is identical to the tangent cone $T_x C$, which is also a convex polyhedron, hence (relatively) closed.

Now, let $C$ be a closed convex set of a Euclidean vector space $\mathbb{E}$. The normal cone to $C$ at $x \in C$ is defined and denoted by

$$N_x C \equiv N_C(x) = \{d \in \mathbb{E} : \langle x' - x, d \rangle \le 0, \forall x' \in C\}. \qquad (1.23)$$

We also set $N_C(x) = \emptyset$ when $x \notin C$. The following hold

$$N_x C = (T_x C)^- \quad \text{and} \quad T_x C = (N_x C)^-.$$

**Proposition 1.8 (tangent and normal cone calculus)**

1) (Intersection) If $C_1$ and $C_2$ are closed convex sets of a vector space $\mathbb{E}$ and $x \in C_1 \cap C_2$, then

$$T_x(C_1 \cap C_2) \subseteq T_x C_1 \cap T_x C_2, \qquad (1.24a)$$

$$N_x(C_1 \cap C_2) \supseteq N_x C_1 + N_x C_2, \qquad (1.24b)$$

with equalities if $0 \in \text{ri}(C_1 - C_2)$ or $(\text{ri} C_1) \cap (\text{ri} C_2) \neq \emptyset$.

2) (Product) Let $(\mathbb{E}_1, \langle \cdot, \cdot \rangle_1)$ and $(\mathbb{E}_2, \langle \cdot, \cdot \rangle_2)$ be two Euclidean spaces and equip $\mathbb{E}_1 \times \mathbb{E}_2$ with the scalar product $\langle (x_1, x_2), (y_1, y_2) \rangle = \langle x_1, y_1 \rangle_1 + \langle x_2, y_2 \rangle_2$. If $C_1$ (resp. $C_2$) is a closed convex set of $\mathbb{E}_1$ (resp. $\mathbb{E}_2$), then $C_1 \times C_2 := \{(x_1, x_2) : x_1 \in C_1, x_2 \in C_2\}$ is a closed convex set of $\mathbb{E}_1 \times \mathbb{E}_2$ and at $(x_1, x_2) \in C_1 \times C_2$, one has

$$T_{(x_1,x_2)}(C_1 \times C_2) = (T_{x_1} C_1) \times (T_{x_2} C_2), \qquad (1.25a)$$

$$N_{(x_1,x_2)}(C_1 \times C_2) = (N_{x_1} C_1) \times (N_{x_2} C_2). \qquad (1.25b)$$

The tangent and normal cones to the convex polyhedron $P = \{x \in \mathbb{E} : Ax \le b\}$ has the following expressions and properties. Recall the notation (1.4): $I(x) := \{i \in [1:m] : (Ax - b)_i = 0\}$.
• Tangent cones:

$$T_P(x) = T_P^f(x) = \{d \in \mathbb{E} : (Ad)_{I(x)} \le 0\}, \qquad (1.26a)$$

$$I(x_1) \subseteq I(x_2) \implies T_P(x_1) \supseteq T_P(x_2). \qquad (1.26b)$$

• Normal cone:

$$N_P(x) = \mathrm{cone}\{A^*e_i : i \in I(x)\}, \qquad (1.27a)$$

$$I(x_1) \subseteq I(x_2) \implies N_P(x_1) \subseteq N_P(x_2). \qquad (1.27b)$$

We see from (1.26a) and (1.27a) that the tangent and normal cones to a convex polyhedron are polyhedral.

### 1.2.7 Projection

Let $\mathbb{E}$ be a Euclidean space, with a scalar product denoted by $\langle \cdot, \cdot \rangle$ and its associated norm denoted by $\| \cdot \|$. For a nonempty, closed, convex set $C$ in $\mathbb{E}$, the problem

$$\inf_{y \in C} \|y - x\| \qquad (1.28)$$

has a unique solution, called the (orthogonal) projection of $x$ on $C$. This projection is denoted by $P_C(x)$. The function $P_C : \mathbb{E} \to C$ is called the (orthogonal) projector on $C$.

**Proposition 1.9 (characterizations of the projection)** For $x \in \mathbb{E}$ and $\bar{x} \in C$, one has

$$\bar{x} = P_C(x) \iff \langle y - \bar{x}, \bar{x} - x \rangle \ge 0, \quad \forall y \in C \qquad (1.29a)$$

$$\iff \langle y - \bar{x}, y - x \rangle \ge 0, \quad \forall y \in C \qquad (1.29b)$$

$$\iff \langle y - x, \bar{x} - x \rangle \ge \|\bar{x} - x\|^2, \quad \forall y \in C. \qquad (1.29c)$$

**Remarks 1.10** 1) The scalar products in the right-hand sides of the equivalences (1.29) use each time two vectors among the possible three $\bar{x} - x$, $y - \bar{x}$, and $y - x$. To have a characterization of the projection, it suffices to have a nonnegative scalar product of $y - \bar{x}$ with one of the two other vectors, like in (1.29a) and (1.29b). When $y - \bar{x}$ is not present, the inequality must be strengthened, like in (1.29c) to have a characterization, as shown by the counter-example where $C = [0, 1] \subseteq \mathbb{R}$, $x \notin C$, while $y$ and $\bar{x}$ are chosen arbitrarily in $C$ (hence $\bar{x}$ is not necessarily the projection of $x$).

2) The most often used characterization is (1.29a). Maybe that this is because it also expresses the optimality condition "$f'(\bar{x}; y - \bar{x}) \ge 0$, for all $y \in C$" of the optimization problem in (1.28), defining the projection, rewritten $\inf\{f(y) := \frac{1}{2}\|y - x\|^2 : y \in C\}$. $\square$
**Proposition 1.11 (properties of the projection)** *The projection on a nonempty closed convex set C has the following properties:*

1) $\forall (x_1, x_2) \in \mathbb{E}^2, \langle P_C(x_2) - P_C(x_1), x_2 - x_1 \rangle \ge \|P_C(x_2) - P_C(x_1)\|^2,$

2) *monotonicity*: $\forall (x_1, x_2) \in \mathbb{E}^2, \langle P_C(x_2) - P_C(x_1), x_2 - x_1 \rangle \ge 0,$

3) *contraction*: $\forall (x_1, x_2) \in \mathbb{E}^2, \|P_C(x_1) - P_C(x_2)\| \le \|x_1 - x_2\|$.

**Remark 1.12** The projector $P_C$ is a nonsmooth operator. It is even not guaranteed to be directionally differentiable when the convex set $C$ is arbitrary (see Kruskal [86] for a counter-example in $\mathbb{R}^3$ and Shapiro [128] for a counter-example in $\mathbb{R}^2$). However, whatever the convex set $C$ is, $P_C$ has directional derivatives at a point $x$ belonging to $C$ [137]:

$$ \forall x \in C, \forall d \in \mathbb{E}: P'_{C}(x; d) = P_{T_C(x)} d. \qquad (1.30) $$

It is also worth noting that the projector $P_C$ is smoother when the boundary of the convex set $C$ is smooth in a sense that is described in [69]. □

### 1.2.8 Asymptotic Cone

Let $\mathbb{E}$ be a vector space of finite dimension and $C$ be a nonempty closed convex set of $\mathbb{E}$. The asymptotic cone of $C$ is defined and denoted by

$$ C^{\infty} := \{d \in \mathbb{E} : C + \mathbb{R}_{+}d \subseteq C\}. $$

This cone has also the following expressions, whatever $x \in C$ is:

$$ \begin{aligned} C^{\infty} &= \{d \in \mathbb{E} : C + d \subseteq C\} \\ &= \{d \in \mathbb{E} : x + \mathbb{R}_{+}d \subseteq C\} = \bigcap_{t>0} \frac{C-x}{t} \qquad (1.31) \\ &= \{d \in \mathbb{E} : \exists \{x_k\} \subseteq C, \exists \{t_k\} \to \infty \text{ such that } \frac{x_k}{t_k} \to d\}. \end{aligned} $$

The formula (1.31) shows that $C^{\infty}$ is closed.

The asymptotic cone is a nice tool to determine, by calculation, whether a closed convex set is bounded.

**Proposition 1.13 (boundedness by calculation)** Let $C$ be a nonempty closed convex set. Then,

$$ C \text{ is bounded} \iff C^{\infty} = \{0\}. $$
**Proposition 1.14 (asymptotic cone calculus)**

1) If $K \neq \emptyset$, then $K$ is a closed convex cone if and only if $K^{\infty} = K$.

2) For an arbitrary collection $\{C_i\}_{i \in I}$ of closed convex sets $C_i$ with nonempty intersection:

$$ (\cap_{i \in I} C_i)^{\infty} = \cap_{i \in I} C_i^{\infty}. $$

3) Let $A: \mathbb{E} \to \mathbb{F}$ and $B: \mathbb{E} \to \mathbb{G}$ be linear maps, $a \in \mathbb{F}$, $b \in \mathbb{G}$, $K$ be a nonempty closed convex cone of $\mathbb{G}$, and

$$ P := \{x \in \mathbb{E} : Ax = a, Bx \in b + K\} \neq \emptyset. $$

Then,

$$ P^{\infty} = \{d \in \mathbb{E} : Ad = 0, Bd \in K\}. $$

Let $\mathbb{E}$ be a Euclidean space. The sets $S_1$ and $S_2 \subseteq \mathbb{E}$ are said to be strictly separable if there exists a vector $\xi \in \mathbb{E}$ (necessarily nonzero) such that

$$ \sup_{x_1 \in S_1} \langle \xi, x_1 \rangle < \inf_{x_2 \in S_2} \langle \xi, x_2 \rangle. $$

**Proposition 1.15 (strict separation of convex sets)** One can strictly separate two disjoint nonempty closed convex sets $C_1$ and $C_2$ of a Euclidean space $\mathbb{E}$ in any of the following situations

1) $C_1 - C_2$ is closed,

2) $C_1^{\infty} \cap C_2^{\infty} = \{0\}$,

3) $C_1$ or $C_2$ is compact,

4) $C_1$ and $C_2$ are polyhedral.

### 1.2.9 Convex Function

Let $\mathbb{E}$ be a vector space. The domain and the epigraph of an arbitrary (not necessarily convex) function $f: \mathbb{E} \to \mathbb{R}$ are the sets defined and denoted by

$$ \text{dom } f := \{x \in \mathbb{E} : f(x) < +\infty\}, $$

$$ \text{epi } f := \{(x, \alpha) \in \mathbb{E} \times \mathbb{R} : f(x) \leq \alpha\}. $$

The indicator function of an arbitrary (not necessarily convex) set $S \subseteq \mathbb{E}$ is the function $I_S: \mathbb{E} \to \mathbb{R} \cup \{+\infty\}$ defined at $x \in \mathbb{E}$ by

$$ I_S(y) = \begin{cases} 0 & \text{if } y \in S, \\ +\infty & \text{otherwise.} \end{cases} $$

By definition, a function $f: \mathbb{E} \to \mathbb{R}$ is convex if its epigraph is convex; it is closed if its epigraph is closed in $\mathbb{E} \times \mathbb{R}$; it is proper if it does not take the value $-\infty$ and is not identical to $+\infty$. The set of proper convex functions $f: \mathbb{E} \to \mathbb{R}$ is denoted by
Conv($\mathbb{E}$)

and the set of closed proper convex functions $f: \mathbb{E} \to \bar{\mathbb{R}}$ is denoted by

$\overline{\text{Conv}}(\mathbb{E})$.

A function $f: \mathbb{E} \to \bar{\mathbb{R}}$ is said to be *directionally differentiable* in the direction $d \in \mathbb{E}$ at a point $x \in \mathbb{E}$ at which it is finite if the following limit exists in $\bar{\mathbb{R}}$:

$$f'(x; d) = \lim_{t \downarrow 0} \frac{f(x + td) - f(x)}{t}.$$

The value $f'(x; d) \in \bar{\mathbb{R}}$ is then called the *directional derivative* of $f$ at $x$ in the direction $d$. A convex function always has directional derivatives, but these can take infinite values.

**Proposition 1.16 (directional differentiability)** Let $f: \mathbb{E} \to \bar{\mathbb{R}}$ be a convex function, $x \in \mathbb{E}$ be a point at which $f(x)$ is finite, and $d \in \mathbb{E}$. Then,

1) the function

$$t \in \mathbb{R}_{++} \mapsto \frac{f(x + td) - f(x)}{t} \in \bar{\mathbb{R}}$$

est nondecreasing,

2) $f'(x; d)$ exists in $\bar{\mathbb{R}}$ (it can take the values $-\infty$ or $+\infty$),

3) $f'(x; d) = +\infty$ if and only if $x + td \notin \text{dom } f$ for all $t > 0$,

4) there holds

$$f'(x; d) \geq -f'(x; -d), \qquad (1.32)$$

in particular, if one of the two directional derivatives $f'(x; d)$ or $f'(x; -d)$ is $-\infty$ the other is $+\infty$.

**Remarks 1.17** 1) According to point 3, one has $f'(x; d) = +\infty$ if and only if $f(x + td) = +\infty$ for all $t > 0$. but, one can very well have $f'(x; d) = -\infty$, while $f(x+td) > -\infty$ for all $t > 0$. This is the case at $x = 0$ for the convex function $f: \bar{\mathbb{R}} \to \bar{\mathbb{R}}$ defined at $x \in \bar{\mathbb{R}}$ by

$$f(x) = \begin{cases} -\sqrt{x} & \text{if } x \geq 0 \\ +\infty & \text{otherwise} \end{cases} \qquad (1.33)$$

and the direction $d = 1$.

2) Point 4 shows that one can compare $f'(x; d)$ and $f'(x; -d)$ when the function $f$ is convex. If $f$ is not differentiable at $x$, in general $f'(x; d) \neq -f'(x; -d)$. For example, if $f(x) = |x|$, $x \in \bar{\mathbb{R}}$, one has $f'(0; 1) = f'(0; -1) = 1$.

Function (1.33) allows us to see what formula (1.32) yields with infinite directional derivatives: $f'(0; 1) = -\infty$ implies that $f'(0; -1) = +\infty$ must hold.
### 1.2.10 Asymptotic Function

The epigraph of a function $f \in \text{Conv}(\mathbb{E})$ is a nonempty closed convex set. One can therefore consider its asymptotic cone $(\text{epi } f)^{\infty}$. This one has interesting properties.

**Proposition 1.18 (asymptotic function $f^{\infty}$)** If $f \in \text{Conv}(\mathbb{E})$, then

1) $(\text{epi } f)^{\infty}$ is the epigraph of a function $f^{\infty}: \mathbb{E} \to \mathbb{R} \cup \{+\infty\}$,

2) for all $x \in \text{dom } f$ and all $d \in \mathbb{E}$

$$f^{\infty}(d) = \lim_{t \to \infty} \frac{f(x + td) - f(x)}{t} = \lim_{t \to \infty} \frac{f(x + td)}{t}, \quad (1.34)$$

3) $\text{dom } f^{\infty} \subseteq (\text{dom } f)^{\infty}$,

4) $f^{\infty} \in \text{Conv}(\mathbb{E})$.

*Proof.* 0) Let us start by giving a characterization of the membership to $(\text{epi } f)^{\infty}$. For this, take an arbitrary point $(x, f(x))$ in $\text{epi } f$, which is nonempty when $f \in \text{Conv}(\mathbb{E})$. Then,

$$ (d, \delta) \in (\text{epi } f)^{\infty} \iff (x, f(x)) + t(d, \delta) \in \text{epi } f, \quad \forall t > 0 \\ \iff f(x + td) \le f(x) + t\delta, \quad \forall t > 0. \quad (1.35) $$

1) To be an epigraph, $(\text{epi } f)^{\infty}$ must have two properties.

* The first property is that, when $(d, \delta) \in (\text{epi } f)^{\infty}$ and $\delta' \ge \delta$, it must follow that $(d, \delta') \in (\text{epi } f)^{\infty}$. This is actually clear by (1.35).

* The second property is that for any $d \in \mathbb{E}$ such that $\{d\} \times \mathbb{R}$ intersects $(\text{epi } f)^{\infty}$, one must have $(d, \delta_0) \in (\text{epi } f)^{\infty}$ for

$$ \delta_0 := \inf\{\delta : (d, \delta) \in (\text{epi } f)^{\infty}\}. \quad (1.36a) $$

From (1.35), we get

$$ \delta_0 = \sup_{t>0} \frac{f(x + td) - f(x)}{t}. \quad (1.36b) $$

By definition of the supremum, one has then $f(x + td) \le f(x) + t\delta_0$, for all $t > 0$. This and (1.35) now yield that $(d, \delta_0) \in (\text{epi } f)^{\infty}$.

Denote by $f^{\infty}$ the function whose epigraph is $(\text{epi } f)^{\infty}$.

2) Let $x \in \text{dom } f$ and $d \in \mathbb{E}$. It is clear that $(x, f(x)) \in \text{epi } f$.

Let us show that $f^{\infty}(d)$ is the value $\delta_0$ given by (1.36a), hence by (1.36a), which will prove the first equality in (1.34). By the reasoning of the previous point, $f^{\infty}(d)$ is clearly $\delta_0$ when $\{d\} \times \mathbb{R}$ intersects $(\text{epi } f)^{\infty}$. When $\{d\} \times \mathbb{R}$ does not intersect $(\text{epi } f)^{\infty} = \text{epi } f^{\infty}$, both $f^{\infty}(d)$ and $\delta_0$ take the value $= +\infty$ (the first one by definition of the epigraph of $f^{\infty}$, the second one by definition of the infimum in (1.36a) and the fact that there is no $(d, \delta) \in (\text{epi } f)^{\infty}$) hence $f^{\infty}(d) = \delta_0$ in that case also.

For the second equality in (1.34), just observe that $f(x) \in \mathbb{R}$ because $x \in \text{dom } f$ and $f \in \text{Conv}(\mathbb{E})$.

3) If $d \in \text{dom } f^{\infty}$, then $(d, f^{\infty}(d)) \in (\text{epi } f)^{\infty}$ and
$$f(x + td) \leq f(x) + tf^{\infty}(d), \quad \forall t > 0,$$

by (1.35). Since the right-hand side of this inequality is finite for all positive $t$, it results that $d \in (\text{dom } f)^{\infty}$.

4) First, $f^{\infty}$ is a closed convex function, since its epigraph is the closed convex set $(\text{epi } f)^{\infty}$. Secondly, $f^{\infty} \neq +\infty$, since its epigraph $(\text{epi } f)^{\infty}$ is nonempty when $f \in \text{Conv}(\mathbb{E})$. Thirdly, $f > -\infty$ since, by (1.34), for $d \in \text{dom } f^{\infty}$, $f(d)$ is obtained as a limit of an increasing sequence made of finite values. $\square$

**Remarks 1.19** 1) The differential quotient $[f(x + td) - f(x)]/t$ is nondecreasing with $t$. It converges to $f'(x; d)$ when $t \downarrow 0$ and, according to (1.34), it converges to $f^{\infty}(d)$ when $t \to \infty$.

2) the last identity in (1.34) often provides the easiest way of computing $f^{\infty}(d)$. Note however that, unlike the differential quotient, $f(x + td)/t$ is not monotonic with $t$.

3) The inclusion in point 3 may be strict. For the exponential function $\exp \in \text{Conv}(\mathbb{R}) : x \mapsto \exp(x) = e^x$, there holds $\exp^{\infty}(1) = +\infty$, so that $1 \notin \text{dom}(\exp^{\infty})$. But $1 \in (\text{dom } \exp)^{\infty}$, since $\text{dom } \exp = \mathbb{R}$.

4) The inclusion in point 3 expresses in a compact manner the fact that if $f(x + td) = +\infty$ for some $t > 0$, then $f^{\infty}(d) = +\infty$. $\square$

The sublevel set of an arbitrary function $f : \mathbb{E} \to \mathbb{R} \cup \{+\infty\}$ of level $\alpha \in \mathbb{R}$ is the set

$$L_{\alpha}(f) := \{x \in \mathbb{E} : f(x) \leq \alpha\}.$$

Whilst the asymptotic cone is a useful concept to verify the boundedness of a nonempty closed convex set, the asymptotic function is useful to verify the boundedness of the sublevel sets of the corresponding function, in particular the nonemptiness and boundedness of the set of its minimizers.

**Proposition 1.20 (existence of a bounded set of minimizers)** If $f \in \text{Conv}(\mathbb{E})$, then

1) $\forall \alpha \in \mathbb{R}$ such that $L_{\alpha}(f) \neq \emptyset$, the following holds

$$[L_{\alpha}(f)]^{\infty} = \{d \in \mathbb{E} : f^{\infty}(d) \leq 0\}, \quad (1.37)$$

2) the following properties are equivalent:

(i) $\exists \alpha \in \mathbb{R}: L_{\alpha}(f)$ is nonempty and bounded,

(ii) $\forall \alpha \in \mathbb{R}: L_{\alpha}(f)$ is bounded,

(iii) Arg min $f$ is nonempty and bounded,

(iv) $\forall d \in \mathbb{E}\setminus\{0\}: f^{\infty}(d) > 0$.

*Proof.* 1) Let $\alpha \in \mathbb{R}$ and $x \in L_{\alpha}(f)$, which is assumed to be nonempty. Then,

$$d \in (L_{\alpha}(f))^{\infty} \iff f(x + td) \leq \alpha, \quad \forall t \geq 0.$$
Hence, if $d \in (L_\alpha(f))^\infty$, $f^\infty(d) \le 0$ by using the last identity in (1.34). Conversely, if $f^\infty(d) \le 0$, then $f(x+td) \le f(x)$, for all $t > 0$, by the monotonicity of the differential quotient and (1.34). Since $f(x) \le \alpha$, $x \in L_\alpha(f)$, this last inequality yields $f(x+td) \le \alpha$, for all $t > 0$, which shows that $x+td \in L_\alpha(f)$, for all $t > 0$; hence, $d \in (L_\alpha(f))^\infty$.

2) Let us now consider the equivalences.

[(i) ⇒ (ii)] By (i) and proposition 1.13, it results that $[L_\alpha(f)]^\infty = \{0\}$ and therefore $\{d \in \mathbb{E} : f^\infty(d) \le 0\} = \{0\}$ by (1.37). Since $\{d \in \mathbb{E} : f^\infty(d) \le 0\}$ is independent of $\alpha$, it results that $(L_{\alpha'}(f))^\infty = \{0\}$ for all $\alpha'$ such that $L_{\alpha'}(f) \ne \emptyset$. Hence, (ii) holds.

[(ii) ⇒ (iii)] Since $f$ is proper, one can find an $\alpha$ such that $L_\alpha(f) \ne \emptyset$. Then $L_\alpha(f)$ is nonempty and closed (since $f \in \text{Conv}(\mathbb{E})$); it is also compact by (ii). As a result, the function $f$ reaches its minimum at some point $\bar{x} \in L_\alpha(f)$; this point $\bar{x}$ is also a minimum of $f$ on $\mathbb{E}$. Since $\text{Arg min } f = L_\alpha(f)$ with $\alpha = \min f$, $\text{Arg min } f$ is compact by (ii).

[(iii) ⇒ (i)] Clear with $\alpha = \min f$.

[(i) ⇒ (iv)] By (i), it results that $(L_\alpha(f))^\infty = \{0\}$ and therefore that $\{d \in \mathbb{E} : f^\infty(d) \le 0\} = \{0\}$ by (1.37). This implies (iv).

[(iv) ⇒ (ii)] By (iv), $\{d \in \mathbb{E} : f^\infty(d) \le 0\} = \{0\}$ and therefore $(L_\alpha(f))^\infty = \{0\}$ each time $L_\alpha(f) \ne \emptyset$ (by using (1.37)). One deduces (ii). □

The implication (iv) ⇒ (iii) of proposition 1.20 is often a convenient approach to show that a function $f \in \text{Conv}(\mathbb{E})$ has a nonempty and bounded set of minimizers (it is ineffective if the set of minimizers is unbounded). The technique consists, therefore, in calculating the asymptotic function $f^\infty$ and in highlighting its property (iv). Hence, showing the existence a nonempty compact set of minimizers is a task that can be realized by calculation.

### 1.2.11 Subdifferentiability

The notion of subdifferentiability of a function $f \in \text{Conv}(\mathbb{E})$ is based on the following proposition.

**Proposition 1.21 (subdifferentiability)** Suppose that $f \in \text{Conv}(\mathbb{E})$, $x \in \text{dom } f$ and $x^* \in \mathbb{E}$. Then, the following properties are equivalent:

(i) $\forall d \in \mathbb{E} : f'(x; d) \ge \langle x^*, d \rangle$,

(ii) $\forall y \in \mathbb{E} : f(y) \ge f(x) + \langle x^*, y - x \rangle$,

(iii) $x \in \text{Arg min}_{y \in \mathbb{E}} (f(y) - \langle x^*, y \rangle) = \text{Arg max}_{y \in \mathbb{E}} (\langle x^*, y \rangle - f(y))$.

**Definitions 1.22** A function $f \in \text{Conv}(\mathbb{E})$ is said to be *subdifferentiable* at a point $x \in \text{dom } f$ if their exists $x^* \in \mathbb{E}$ verifying the equivalent properties (i)-(iii) of proposition 1.21. Such an element $x^*$ is called a *subgradient* of $f$ at $x$. The set of subgradients of $f$ at $x$ is called the *subdifferential* of $f$ at $x$ and is denoted by $\partial f(x)$. By convention, $\partial f(x) = \emptyset$ if $x \notin \text{dom } f$. □
A subgradient is actually an element of the dual of $\mathbb{E}$, which is identified to $\mathbb{E}$ itself in finite dimension (the distinction between $\mathbb{E}$ and its dual is important in infinite dimension but not in our finite dimension framework). Hence, it is better to see a subgradient as a slope of the function, like for a gradient of a smooth function.

Each of the three equivalent conditions (i)-(iii) of proposition 1.21 reflects a particular aspect of the subgradients, offering also a means to calculate them.

1) Condition (i) tells us that a subgradient is the slope of linear function minorizing $f'(x; \cdot)$. This point of view leads to the following way of computing $\partial f(x)$. First, one computes the directional derivatives of $f$ at $x$ and one determines all the linear function minorizing if; their slopes are the elements of $\partial f(x)$.

2) According to condition (ii), a subgradient is the slope of an affine function minorizing $f$, which has the same value as $f$ at $x$. This definition is often used to verify that a particular $x^* \in \mathbb{E}$ is a subgradient.

3) Condition (iii) tells us that $x^*$ is a subgradient of $f$ at $x$ if $f(\cdot) - \langle x^*, \cdot \rangle$ reaches its minimum at $x$. This point of view leads to the following method to compute $\partial f(x)$. One starts with a slope $x^* \in \mathbb{E}$; then, one computes the minimizers of $x \mapsto f(x) - \langle x^*, x \rangle$; such a minimizer $x$ is such that $x^* \in \partial f(x)$.

A function $f \in \text{Conv}(\mathbb{E})$ is not necessarily subdifferential at all the points in dom $f$. For example, the function (1.33) is not subdifferntiable at 0.

## Notes

Most results given in this section can be found with their proofs in [125, 66, 22, 67]. The notions of asymptotic cone and function have been extended to nonconvex sets and functions, in particular with the goal of providing existence theorems for nonconvex optimization problems and variational inequalities; see the monograph [7].

## Exercises

1.2.1. *Constant subsequence of a sequence of subsets of $[1:n]$.* Let $\{I_k\}_{k \in \mathbb{N}}$ be a sequence of subsets $I_k$ of $[1:n]$. Show that this sequence contains a subsequence $\{I_k\}_{k \in \mathcal{K}}$ (hence $\mathcal{K}$ is an infinite part of $\mathbb{N}$) such that $I_k$ is independent of $k \in \mathcal{K}$.

1.2.2. *Affine hull.* Let $A$ be an affine subspace of a vector space $\mathbb{E}$ and $O \subseteq A$ be relatively open in $A$ (i.e., open for the relative topology of $A$). Then, $\text{aff } O = A$.

1.2.3. *Scaled sum of convex sets.* If $C_1$ and $C_2$ are convex sets of a vector space $\mathbb{E}$, such that $0 \in C_1 \cap C_2$, then $\mathbb{R}_+(C_1 + C_2) = \mathbb{R}_+ C_1 + \mathbb{R}_+ C_2$. Give an example, in which the identity does not hold when $0 \notin C_1 \cap C_2$.

1.2.4. *Dense convex set.* Let $C$ be a convex set in a finite dimensional vector space $\mathbb{E}$. Show that if the closure of $C$ is $\mathbb{E}$, then $C = \mathbb{E}$.

1.2.5. *Relative interior.* Let $C$ be a nonempty convex set of a finite dimensional vector space. Then,

$$2(\text{ri} C) = C + \text{ri} C = \bar{C} + \text{ri} C.$$

1.2.6. *Affine hull and relative interior of a convex polyhedron.* Let $\mathbb{E}$ be a vector space. Consider the convex polyhedron of $\mathbb{E}$ defined by
$$P := \{x \in \mathbb{E} : Ax = a, Bx \le b\},$$

where $A: \mathbb{E} \to \mathbb{R}^m$ and $B: \mathbb{E} \to \mathbb{R}^p$ are linear maps, $a \in \mathbb{R}^m$ and $b \in \mathbb{R}^p$. Define the index set $I \subseteq [1: p]$ by

$$i \in I \iff \{x \in P : B_i x < b_i\} \neq \emptyset.$$

and denote its complementary set by $I^c := [1: p] \setminus I$. Show that

$$\mathrm{aff} P = \{x \in \mathbb{E} : Ax = a, B_{I^c}x = b_{I^c}\}, \quad (1.38)$$

$$\mathrm{ri} P = \{x \in P : B_I x < b_I\}. \quad (1.39)$$

1.2.7. Decomposition of a vector space in the sum of a subspace and a convex cone [129].
Let $E_0$ be a subspace of a vector space $\mathbb{E}$ and $K$ be a convex cone of $\mathbb{E}$. Then,

$$E_0 + K = \mathbb{E} \iff \left\{ \begin{array}{l} E_0 + \mathrm{vect} K = \mathbb{E} \\ E_0 \cap (\mathrm{ri} K) \neq \emptyset. \end{array} \right.$$

1.2.8. Farkas lemma for a polyhedral cone. Let $\mathbb{E}$ be a Euclidean space, and $A_E: \mathbb{E} \to \mathbb{R}^{m_E}$ and $A_J: \mathbb{E} \to \mathbb{R}^{m_J}$ be two linear maps. Then,

$$\{d : A_E d = 0, A_J d \le 0\}^+ = -\{A_E^* \lambda_E + A_J^* \lambda_J : \lambda_E \in \mathbb{R}^{m_E}, \lambda_J \in \mathbb{R}_+^{m_J}\}. \quad (1.40)$$

1.2.9. Bidual of a convex cone. Using Farkas lemma, show that if $K$ is a nonempty convex cone, then $K^{++} = \bar{K}$.

1.2.10. Interior and relative interior of a dual cone. Let $\mathbb{E}$ be a Euclidean (scalar product and associated norm respectively denoted by $\langle \cdot, \cdot \rangle$ and $\| \cdot \|$), $P \subseteq \mathbb{E}$, $P^+ = \mathbb{E} \setminus P$ be the dual cone of $P$, and $P_{\mathrm{aff}(P^+)}$ be the orthogonal projector on $\mathrm{aff}(P^+)$. Show that

$$d \in \mathrm{int}(P^+) \iff \exists \varepsilon > 0, \forall x \in P: \langle d, x \rangle \ge \varepsilon \|x\|, \quad (1.41a)$$

$$d \in \mathrm{ri}(P^+) \iff \exists \varepsilon > 0, \forall x \in P: \langle d, x \rangle \ge \varepsilon \|P_{\mathrm{aff}(P^+)} x\|. \quad (1.41b)$$

1.2.11. Cone of feasible directions to a convex cone [129]. Show that if $K$ is a convex cone and $x \in K$, then $T_x^f K = K + \mathbb{R}\{x\}$.

1.2.12. Tangent cones to $S_+^n$. Show that the tangent cone to $S_+^n$ at $X \in S_+^n$ can be written

$$T_X S_+^n = \{D \in S^n : v^T D v \ge 0, \forall v \in \mathcal{N}(X)\}.$$

1.2.13. Asymptotic cone. Let $\mathbb{E}$, $\mathcal{F}$, and $\mathcal{G}$ be finite dimension vector spaces. Let $A: \mathbb{E} \to \mathcal{F}$ and $B: \mathbb{E} \to \mathcal{G}$ be linear maps, $a \in \mathcal{F}$, $b \in \mathcal{G}$, $K \subseteq \mathcal{G}$ be a closed convex cone, and

$$P = \{x \in \mathbb{E} : Ax = a, Bx \in b + K\}.$$

Then, the asymptotic cone of $P$ is given by

$$P^\infty = \{d \in \mathbb{E} : Ad = 0, Bd \in K\}.$$

# 1.3 Nonsmooth Analysis

## 1.3.1 Lower semi-continuity

Let $\mathbb{E}$ be a finite dimensional vector space and $f: \mathbb{E} \to \overline{\mathbb{R}}$ be a function. The function $f$ is said to be lower semi-continuous (l.s.c. for short) on $\mathbb{E}$ if for all $x \in \mathbb{E}$ there holds
$$f(x) \le \liminf_{x' \to x} f(x').$$

The function $f$ is said to be closed if its epigraph is closed. These two notions are actually equivalent.

**Proposition 1.23 (l.s.c. function)** Let $\mathbb{E}$ be a finite dimensional vector space and $f: \mathbb{E} \to \mathbb{R}$ be a function. Then, the following properties are equivalent.

(i) $f$ is l.s.c. on $\mathbb{E}$,

(ii) $f$ is closed,

(iii) for all $\alpha \in \mathbb{R}$, the sublevel set $L_{\alpha}(f)$ is closed.

### 1.3.2 Lipschitz Continuity

Let $\mathbb{E}$ and $\mathbb{F}$ be two finite dimensional normed spaces and $F: \mathbb{E} \to \mathbb{F}$ be a function. We adopt the following definitions.

* $F$ is Lipschitz (continuous) on a set $V \subseteq \mathbb{E}$ if

$$\exists L \ge 0, \quad \forall (x, x') \in V^2: \quad \|F(x) - F(x')\| \le L\|x - x'\|.$$

In this case, we also say that $F$ is $L$-Lipschitz on $V$.

* $F$ is radially Lipschitz (continuous) at $x \in \mathbb{E}$ if

$$\exists V \in \mathcal{N}(x), \quad \exists L \ge 0, \quad \forall x' \in V: \quad \|F(x) - F(x')\| \le L\|x - x'\|,$$

where $\mathcal{N}(x)$ denotes the family of neighborhoods of $x$.

* $F$ is Lipschitz (continuous) near $x \in \mathbb{E}$ if $F$ is Lipschitz on some neighborhood of $x$.

* $F$ is locally Lipschitz (continuous) on an open set $\Omega \subseteq \mathbb{E}$ if $F$ is Lipschitz near any point of $\Omega$.

### 1.3.3 Differentiability

Let $\mathbb{E}$ and $\mathbb{F}$ be two normed spaces and $\Omega$ be an open set of $\mathbb{E}$. A function $F: \Omega \to \mathbb{F}$ is said to be Fréchet-differentiable [57; 1911] at $x \in \Omega$ if there exists a linear continuous operator $L: \mathbb{E} \to \mathbb{F}$ such that

$$\lim_{\|h\| \downarrow 0} \frac{1}{\|h\|} (F(x+h) - F(x) - Lh) = 0. \quad (1.42)$$

Instead of saying Fréchet-differentiable, one also say $F$-differentiable or simply differentiable. The limit in (1.42) is in $\mathbb{F}$. We have taken care of having the limit for $h \ne 0$ to give a sense to the quotient in (1.42). The operator $L$ is then uniquely determined, is denoted $F'(x)$, and is called the derivative of $F$ at $x$. Condition (1.42) can then also be written

$$F(x+h) = F(x) + F'(x)h + o(h), \quad (1.43)$$
where the small o of h, o(h), denotes a function of h vanishing at zero and verifying the property

$$ \lim_{\|h\|_{E} \downarrow 0} \frac{o(h)}{\|h\|} = 0, $$

where the limit is taken in a normed space depending on the context (here $\mathbb{F}$).

The function $F: \Omega \to \mathbb{F}$ is said to be $F$-differentiable on $\Omega$ if $F$ is $F$-differentiable at each point of $\Omega$.

**Theorem 1.24 (mean value theorem)** Let $\Omega$ be an open set of $\mathbb{E}$, $x \in \Omega$, and $h \in \mathbb{E}\setminus\{0\}$ be such that the closed segment $[x, x+h] \subseteq \Omega$. Suppose that $F: \Omega \to \mathbb{F}$ is continuous on $\Omega$ and differentiable on the open segment $(x, x+h)$. Then

$$ \|F(x+h) - F(x)\| \le \left( \sup_{z \in (x, x+h)} \|F'(z)\| \right) \|h\|. $$

**Corollary 1.25** Under the assumptions of theorem 1.24, if $L: \mathbb{E} \to \mathbb{F}$ is linear continuous, it follows that

$$ \|F(x+h) - F(x) - Lh\| \le \left( \sup_{z \in (x, x+h)} \|F'(z) - L\| \right) \|h\|. $$

Suppose that $F: \Omega \to \mathbb{F}$ is defined on the part $\Omega \subseteq \mathbb{E}$. We denote by $D_F$ the set of points of $\Omega$ at which $F$ is Fréchet-differentiable:

$$ D_F := \{x \in \Omega : F \text{ is Fréchet-differentiable at } x\}. $$

**Theorem 1.26 (Rademacher, 1919)** If $\Omega$ is an open set and $F: \Omega \to \mathbb{F}$ is locally Lipschitz on $\Omega$, then, $F$ is Fréchet-differentiable almost everywhere on $\Omega$, in the sense of Lebesgue. In other words, the Lebesgue measure of $\Omega \setminus D_F$ vanishes.

*Proof.* See [49; 2015, chap. 3] for instance. □

### 1.3.4 Multifunction

A multifunction$^3$ $T$ between two sets $\mathbb{E}$ and $\mathbb{F}$ is a usual function from $\mathbb{E}$ to $\mathcal{P}(\mathbb{F})$, where $\mathcal{P}(\mathbb{F})$ is the power set of $\mathbb{F}$, that is the set of all subsets of $\mathbb{F}$. The adopted notation for a multifunction is

<footnote>$^3$ A multifunction may have many other names, like set-valued mapping or multi-valued function.</footnote>
$$T: \mathbb{E} \to \mathbb{F}: x \in \mathbb{E} \mapsto T(x) \subseteq \mathbb{F}.$$

Several concepts are associated with a multifunction $T: \mathbb{E} \to \mathbb{F}$.

* The graph $\mathcal{G}(T)$, the domain $\mathcal{D}(T)$, and the range $\mathcal{R}(T)$ of $T$ are defined by

$$\mathcal{G}(T) := \{(x, y) \in \mathbb{E} \times \mathbb{F} : y \in T(x)\},$$

$$\mathcal{D}(T) := \{x \in \mathbb{E} : (x, y) \in \mathcal{G}(T) \text{ for some } y \in \mathbb{F}\} = \pi_{\mathbb{E}}\mathcal{G}(T),$$

$$\mathcal{R}(T) := \{y \in \mathbb{F} : (x, y) \in \mathcal{G}(T) \text{ for some } x \in \mathbb{E}\} = \pi_{\mathbb{F}}\mathcal{G}(T),$$

where we have denoted by $\pi_{\mathbb{E}}: (x, y) \in \mathbb{E} \times \mathbb{F} \mapsto x \in \mathbb{E}$ and $\pi_{\mathbb{F}}: (x, y) \in \mathbb{F} \times \mathbb{F} \mapsto y \in \mathbb{F}$, the Cartesian projectors on $\mathbb{E}$ and $\mathbb{F}$ respectively (these are linear maps). Notice that $\mathcal{G}(T)$ is a part of $\mathbb{E} \times \mathbb{F}$, not of $\mathbb{E} \times \mathcal{P}(\mathbb{F})$.

* The concept of multifunction is the same as the one of binary relation, which is defined by the specification of a part $G$ of $\mathbb{E} \times \mathbb{F}$ (the relation, sometimes denoted $x \mathcal{R} y$, is said to be “true” if $(x, y) \in G$ and “false” otherwise). Indeed, one can associate with a part $G$ of $\mathbb{E} \times \mathbb{F}$ the multifunction $T_G: \mathbb{E} \to \mathbb{F}$, defined at $x \in \mathbb{E}$ by

$$T_G(x) = \{y \in \mathbb{F} : (x, y) \in G\}.$$

Then, we have the property that $\mathcal{G}(T_G) = G$.

* The image of a part $P \subseteq \mathbb{E}$ by $T$ is

$$T(P) := \bigcup_{x \in P} T(x) = \pi_{\mathbb{F}}[\mathcal{G}(T) \cap (P \times \mathbb{F})]. \qquad (1.44)$$

* The inverse of $T$ is the multifunction $T^{-1}: \mathbb{F} \to \mathbb{E}$ defined at $y \in \mathbb{F}$ by

$$T^{-1}(y) := \{x \in \mathbb{E} : y \in T(x)\}.$$

The inverse always exists, but it is not true that $T^{-1} \circ T$ is the identity on $\mathbb{E}$ or that $T \circ T^{-1}$ is the identity on $\mathbb{F}$! Note that

$$y \in T(x) \iff x \in T^{-1}(y) \iff (x, y) \in \mathcal{G}(T) \iff (y, x) \in \mathcal{G}(T^{-1}).$$

Here are some commonly encountered properties that a multifunction $T: \mathbb{E} \to \mathbb{F}$ may have.

* When $\mathbb{E}, \mathbb{F}$ are vector spaces, $T$ is said to be convex if $\mathcal{G}(T)$ is convex in $\mathbb{E} \times \mathbb{F}$. This is equivalent to saying that $\forall (x_0, x_1) \in \mathbb{E}^2$ and $\forall t \in [0, 1]$:

$$T((1-t)x_0 + tx_1) \supseteq (1-t)T(x_0) + tT(x_1).$$

Note that

$$\left. \begin{array}{l} T: \mathbb{E} \to \mathbb{F} \text{ convex} \\ C \text{ convex in } \mathbb{E} \end{array} \right\} \implies T(C) \text{ convex in } \mathbb{F}. \qquad (1.45)$$

This is because by (1.44) there holds $T(C) = \pi_{\mathbb{F}}[\mathcal{G}(T) \cap (C \times \mathbb{F})]$ and $\mathcal{G}(T)$ is convex when $T$ is convex.
* When $\mathbb{E}$, $\mathbb{F}$ are topological spaces, $T$ is said to be

- closed at $x \in \mathbb{E}$ if $y \in T(x)$ when $(x_k, y_k) \in \mathcal{G}(T)$ converges to $(x, y)$;

- closed if $\mathcal{G}(T)$ is closed in $\mathbb{E} \times \mathbb{F}$, which amounts to saying that $T$ is closed at any $x \in \mathbb{E}$.

* When $\mathbb{E}$, $\mathbb{F}$ are metric spaces, $T$ is said to be upper semi-continuous at $x \in \mathbb{E}$ if

<figure><img src="image_5.png" /></figure>

In this definition, $B$ may be the open or closed unit ball at any place.

## Notes

A study of Lipschitz continuous functions can be found in [49; 2015, chap. 3], for functions between finite dimensional vector spaces, including a proof of the Rademacher theorem [115; 1919], and in [4; 2004, chap. 3], between metric spaces. The results on the generalized differentiability are taken from [32, 33].

## Exercises

1.3.1. Upper semi-continuity of some multifunctions. Let $\mathbb{E}$ be a Euclidean vector space. Show the upper semi-continuity of the following multifunctions.

1)

2) The subdifferential of a convex function $f: \mathbb{E} \to \mathbb{R}$ at $x \in \mathbb{E}$ is the set $\partial f(x) := \{s \in \mathbb{E} : f(y) \ge f(x) + \langle s, y - x \rangle, \forall y \in \mathbb{E}\}$. Show that the multifunction $\partial f: \mathbb{E} \to \mathbb{E}: x \mapsto \partial f(x)$ is upper semi-continuous at any $x \in \mathbb{E}$.

# 1.4 Optimization

## 1.4.1 Generic Problem

In a rather general setting, an optimization problem consists in minimizing a function $f: \mathbb{E} \to \mathbb{R}$ ($\mathbb{E}$ is a Euclidean vector space, which is the only restriction) on a (possibly nonconvex) subset $X \subseteq \mathbb{E}$. In other words, one looks for a point $x_* \in \mathbb{E}$ such that

$$ \begin{cases} x_* \in X, \\ f(x_*) \le f(x), \quad \forall x \in X. \end{cases} \qquad (1.46) $$

Such a point $x_*$ is called a solution to the optimization problem. This problem, denoted $(P_X)$ is written in one of the following manners

$$ \left\{ \begin{array}{ll} \min_{x \in X} f(x) & \text{or} \\ \inf_{x \in X} f(x) & \text{or} \\ \inf\{f(x) : x \in X\}. & \end{array} \right. \qquad (1.47) $$
The function $f$ is often called the *objective* of the optimization problem, while the set $X$ is called its *feasible set*. A point belonging to $X$ is said to be *feasible*. The “smallest value” of $f$ on $X$, more precisely

$$ \mathrm{val}(P_X) := \inf_{x \in X} f(x) $$

is called the *optimal value* of the optimization problem, while the set of solutions is denoted by

$$ \mathrm{Sol}(P_X) \quad \text{or} \quad \mathrm{Arg\,min}_{x \in X} f(x). $$

One says that the problem $(P_X)$ is *bounded* if $\mathrm{val}(P_X) > -\infty$; otherwise, the problem is said to be *unbounded*, which occurs when there is a sequence $\{x_k\}_{k \ge 1} \subseteq X$ such that $f(x_k) \to -\infty$. We adopt the following convention

$$ \inf_{x \in \emptyset} f(x) = +\infty. \qquad (1.48) $$

A *minimizing sequence* for problem $(P_X)$ is a sequence $\{x_k\}_{k \ge 1} \subseteq X$ such that $f(x_k) \to \mathrm{val}(P_X)$ when $k \to \infty$. By definition of the infimum, such a sequence always exists when $X$ is nonempty.

Maximizing $f$ is “identical” to minimizing $-f$ (i.e., same solutions, opposite optimal value), so that only the minimization problem will be considered. Furthermore, one prefers minimization to maximization, because the notion of “convex set” is meaningful (unlike the one of “concave set”), hence the notion of “convex function” (it is a function whose epigraph is convex), and finally it is more natural to minimize a convex function than to maximize it. From (1.48), one gets

$$ \sup_{x \in \emptyset} f(x) = -\infty. $$

A point $x_*$ satisfying (1.46) is sometimes called a *global minimum*, to stress the distinction with a *local minimum* of $f$ on $X$, which is a point $x_*$ for which there is a neighborhood $V$ of $x_*$, such that

$$ \begin{cases} x_* \in X, \\ f(x_*) \le f(x), \quad \forall x \in X \cap V. \end{cases} \qquad (1.49) $$

One also uses the notion of *strict local/global minimum*, which is a point $x_*$ verifying (1.46)/(1.49) with a strict inequality $f(x_*) < f(x)$ when $x \ne x_*$.

### 1.4.2 Peano-Kantorovich Optimality Condition

Let $\mathbb{E}$ be a Euclidean space. When $x_*$ minimizes a function $f$ on $X = \mathbb{E}$ and when $f$ is differentiable at $x_*$, it is known that

$$ f'(x_*) = 0. $$

Such a property of the minimizer $x_*$ is called a *necessary condition of optimality* (“necessary” since it is implied by the optimality of $x_*$) of the first order (since it only involves the first derivative of $f$); this property is abbreviated in NC1. Use the gradient of $f$, this can also be written
$$\nabla f(x_*) = 0,$$

which is sometimes called the *Fermat optimality condition*.

When $X \neq \mathbb{E}$, some kind of first order approximation of $X$ near $x_*$ is also necessary to get a necessary condition of optimality of the first order. The linearization of $X$ at $x_*$ yields a cone that is called the tangent cone. Note that here $X$ is not necessarily convex like in section 1.2.6.

## Tangent Cone to a Nonconvex Set

Let $X$ be a closed set of $\mathbb{E}$. A direction $d \in \mathbb{E}$ is said to be tangent to $X$ at $x \in X$ (in the sense of Bouligand) if

$$\exists \{x_k\} \subseteq X, \exists \{t_k\} \downarrow 0: \frac{x_k - x}{t_k} \to d.$$

The tangent cone to $X$ at $x$ (in the sense of Bouligand) is the set of tangent directions. It is denoted by

$$T_x X \quad \text{or} \quad T_X(x),$$

with the convention that $T_x X = \emptyset$ when $x \notin X$.

For $x \in X$, one has

$T_x X$ is a closed cone,

$$X \text{ is convex} \implies T_x X \text{ is convex and } T_x X = \overline{\mathbb{R}_+(X-x)}.$$

Therefore, when $X$ is convex, the notions of tangent cones introduced in section 1.2.6 and here coincide, which justifies the similar notation. When $X$ is not convex, one still have $T_x X \subseteq \overline{\mathbb{R}_+(X-x)}$.

The normal cone to $X$ at $x$ is then defined by

$$N_x X := (T_x X)^-, \qquad (1.50)$$

with the convention that $N_x X = \emptyset$ when $x \notin X$.

## Peano-Kantorovich NC1

The following necessary condition of optimality of the first order (NC1) for the generic problem ($P_X$) is so important for chapter 2 that we present its simple proof. The result just expresses compactly and at the first order (i.e., using the first derivative) the fact that $f$ is not decreasing along the tangent directions to $X$ at $x_*$ when it is locally minimized on $X$ at $x_* \in X$.
**Theorem 1.27 (Peano-Kantorovich NC1)** If $x_*$ is a local minimizer of $(P_X)$ and $f$ is differentiable at $x_*$, then

$$ \nabla f(x_*) \in (T_{x_*} X)^+. \qquad (1.51) $$

*Proof.* We have to show that $\langle \nabla f(x_*), d \rangle \ge 0$, for all $d \in T_{x_*} X$. Let $d \in T_{x_*} X \setminus \{0\}$ (the previous inequality is trivially satisfied for $d = 0$). Then, there exist sequences $\{x_k\} \subset X$ and $\{t_k\} \subset \mathbb{R}$ such that $d_k := (x_k - x_*)/t_k \to d$. For large $k$, $x_k = x_* + t_k d_k$ is close to $x_*$, so that, by the local optimality of $x_*$:

$$ f(x_* + t_k d_k) \ge f(x_*), \quad \text{for large } k. $$

Since $f$ is differentiable at $x_*$, $f(x_* + t_k d_k) = f(x_*) + f'(x_*) \cdot (t_k d_k) + o(\|t_k d_k\|)$. Using the previous inequalities yields

$$ 0 \le f'(x_*) \cdot d_k + \frac{o(\|t_k d_k\|)}{t_k} = f'(x_*) \cdot d_k + \frac{o(\|t_k d_k\|)}{\|t_k d_k\|} \|d_k\|, \quad \text{for large } k. $$

Taking the limit when $k \to \infty$ now provides $f'(x_*) \cdot d_k = \langle \nabla f(x_*), d \rangle \ge 0$. $\square$

### NSC1 for Convex Problems

For a convex problem $(P_X)$, one has a necessary and sufficient condition of global optimality of the first order (NSC1). Recall from proposition 1.16 that a convex function $f: \mathbb{E} \to \mathbb{R} \cup \{+\infty\}$ has directional derivatives $f'(x; d) := \lim_{t \downarrow 0} [f(x+td) - f(x)]/t \in \mathbb{R}$ for all $x \in \text{dom } f$ and all $d \in \mathbb{E}$.

**Proposition 1.28 (NSC1 for a convex problem)** Suppose that $X$ is convex, that $f$ is convex on $X$, and that $x_* \in X$. Then, $x_*$ is a global solution to $(P_X)$ if and only if

$$ f'(x_*; x - x_*) \ge 0, \quad \forall x \in X. $$

The proof is straightforward. It uses the convexity inequality

$$ f(x) \ge f(x_*) + f'(x_*; x - x_*), \quad \forall x \in X. $$

### 1.4.3 Equality Constrained Problem ($P_E$)

Let $\mathbb{E}$ and $\mathbb{F}$ be Euclidean vector spaces. The equality constrained problem consists in minimizing a function $f: \mathbb{E} \to \mathbb{R}$ on the set

$$ X_E := \{x \in \mathbb{E} : c(x) = 0\} $$
defined by equality constraints thanks to a function $c: \mathbb{E} \to \mathbb{F}$. The set $X_E$ is said to be the feasible set of $(P_E)$. The problem is written

$$ (P_E) \quad \left\{ \begin{array}{l} \inf_x f(x) \\ c(x) = 0. \end{array} \right. $$

Usually the functions $f$ and $c$ are smooth, possibly nonconvex.

**Definition 1.29** The problem $(P_E)$ is said to be convex if $f$ is convex and $X_E$ is a convex set.

### Lagrange Optimality Conditions

The following NC1 is often attributed to Lagrange (XVIIIth century). It uses the Lagrangian of $(P_E)$, which is the function

$$ \ell: (x, \lambda) \in \mathbb{E} \times \mathbb{F} \mapsto \ell(x, \lambda) = f(x) + \langle \lambda, c(x) \rangle \in \mathbb{R}. $$

We denote by $\nabla_x \ell(x, \lambda)$ the gradient of $\nabla_x \ell(\cdot, \lambda)$ at $x$. It is a particular case of theorem 1.40, whose proof is given explicitly.

**Theorem 1.30 (NC1 for $(P_E)$)** If $x_*$ is a local minimum of $(P_E)$, if $f$ and $c$ are differentiable at $x_*$, and if $c$ is qualified for representing $X_E$ at $x_*$ in the sense (1.53) below, then there exists a multiplier $\lambda_* \in \mathbb{F}$ such that

$$ \nabla_x \ell(x_*, \lambda_*) = 0, \qquad (1.52a) $$

$$ c(x_*) = 0. \qquad (1.52b) $$

**Definitions 1.31** 1) The set $X_E$ can be described by several functions $c$. Some are better than others. The constraint $c$ is said to be qualified for representing $X_E$ at $x \in X_E$ if

$$ T_x X_E = T'_x X_E := \mathcal{N}(c'(x)). \qquad (1.53) $$

There always holds $T_x X_E \subseteq T'_x X_E$, but equality is not necessarily guaranteed. Qualification holds if $c'(x)$ is surjective (hence, this is a sufficient condition of constraint qualification).

2) A vector $\lambda_*$ in (1.52a) is called a *Lagrange multiplier* or *optimal multiplier* associated with $x_*$. The term “multiplier” comes from the fact that it multiplies the constraint in the Lagrangian.

3) A point $x_*$ satisfying (1.52) for some $\lambda_* \in \mathbb{F}$ is said to be a *stationary point*. Sometimes, one says that the pair $(x_*, \lambda_*)$ satisfying (1.52) is *stationary*. $\square$

By definition, the set of optimal multipliers $\lambda_*$ associated with a stationary point $x_*$ of $(P_E)$ is the set defined and denoted by

$$ \Lambda_* := \{ \lambda_* \in \mathbb{F} : \nabla f(x_*) + c'(x_*)^* \lambda_* = 0 \}. $$
It is therefore an affine subspace of $\mathbb{F}$, which is nonempty by definition of the stationarity of $x_*$. Clearly, this set $\Lambda_*$ is reduced to a singleton (uniqueness of the optimal multiplier associated with $x_*$) if and only if $c'(x_*)$ is surjective.

**Proposition 1.32 (SC1 for a convex ($P_E$))** Suppose that problem ($P_E$) is convex in the sense of the definition 1.29 and that $f$ and $c$ are differentiable at a point $x_* \in \mathbb{E}$ that satisfies (1.52) for some $\lambda_* \in \mathbb{F}$. Then, $x_*$ is a global minimum of ($P_E$).

## Second Order Optimality Conditions

First order necessary conditions allows us to select a set of points that are candidates for being solutions to ($P_E$), but these conditions do not even discard a local maximum! With second order necessary conditions (NC2), the selection is more precise and many point that are not local minimums are removed from the list of stationary points.

**Theorem 1.33 (NC2 for ($P_E$))** If $x_*$ is a local minimum of ($P_E$), if $f$ and $c$ are twice differentiable at $x_*$, and if (1.52a) holds for some $\lambda_* \in \mathbb{F}$, then

$$ \forall d \in T_{x_*} X_E : \langle \nabla_{xx}^2 \ell(x_*, \lambda_*) d, d \rangle \ge 0. \quad (1.54) $$

**Remarks 1.34 1) With respect to the second order optimality conditions for the unconstrained problem “inf $f(x)$”, which read**

$$ \nabla f(x_*) = 0 \quad \text{and} \quad \nabla^2 f(x_*) \ge 0, $$

the NC2 for ($P_E$) have two major differences:

* it is the Lagrangian $\ell$ that intervenes in the conditions, not $f$,

* the Hessian of the Lagrangian is not positive semidefinite in the whole space $\mathbb{E}$ but only in the tangent cone $T_{x_*} X_E$, which is the subspace $\mathcal{N}(c'(x_*))$ if the constraint qualification (1.53) holds at $x_*$.

2) The result does not require any constraint qualification, but claims the inequality in (1.54) only for the tangent directions $d \in T_{x_*} X_E$.

3) The inequality in (1.54) is not necessarily true for $d \in \mathcal{N}(c'(x_*)) \setminus T_{x_*} X_E$ (but it holds in the presence of qualification, by the definition (1.53) of the latter). For example, if one minimizes $-x^2$ on $\{x \in \mathbb{R} : x^2 = 0\}$, the unique solution is the origin, $T_0 X_E = \{0\}$, $\mathcal{N}(c'(0)) = \mathbb{R}$, and $\nabla_x \ell(0, 0) = 0$, but $\nabla_{xx}^2 \ell(0, 0) = -2$ is positive negative on $\mathbb{R}$ (while it is positive semidefinite on $\{0\}$).

Of course, if the constraint $c$ is qualified at $x_*$, one has $T_{x_*} X_E = \mathcal{N}(c'(x_*))$ and the inequality in (1.54) is valid for all $d \in \mathcal{N}(c'(x_*))$.

4) As usual, these second order necessary conditions can be used to detect stationary points that are not local minimizers. $\square$
Sufficient optimality conditions of the second order (SC2) for the nonconvex problem ($P_E$) are essentially local; they do not guarantee global optimality (compare with proposition 1.32).

**Theorem 1.35 (SC2 for ($P_E$))** If $f$ and $c$ are twice differentiable at $x_*$, if (1.52) holds for some $\lambda_* \in \mathbb{F}$, and if

$$ \forall d \in T_{x_*} X_E \setminus \{0\} : \quad d^\top \nabla^2_{xx} \ell(x_*, \lambda_*) d > 0, \qquad (1.55) $$

then $x_*$ is a strict local minimum of ($P_E$).

Of course, (1.55) is stronger (hence the conclusion holds) if the inequalities hold for all $d \in \mathcal{N}(c'(x_*)) \setminus \{0\}$.

### 1.4.4 Equality and Inequality Constrained Problem ($P_{EI}$)

Nonlinear optimization deals with the study of the nonlinear optimization problem, which consists in minimizing a function subject to equality and inequality constraints. A generic form of this problem is the following

$$ (P_{EI}) \quad \left\{ \begin{array}{ll} \inf_x f(x) & \\ c_E(x) = 0 & \\ c_I(x) \le 0, & \end{array} \right. $$

where $f: \mathbb{E} \to \mathbb{R}$, $c_E: \mathbb{E} \to \mathbb{R}^{m_E}$, and $c_I: \mathbb{E} \to \mathbb{R}^{m_I}$ are (generally) smooth (possibly nonconvex) functions. Below it is considered that $c_E$ and $c_I$ are the components of a function $c: \mathbb{E} \to \mathbb{R}^m$; hence, $E$ and $I$ form a partition of $[1:m]$, $m_E = |E|$, $m_I = |I|$, and $m_E + m_I = m$. As usual, the inequality "$c_I(x) \le 0$" has to be understood componentwise, meaning that it is equivalent to "$c_I(x) \le 0$ for all $i \in I$". The feasible set of ($P_{EI}$) is denoted by

$$ X_{EI} := \{x \in \mathbb{E} : c_E(x) = 0, c_I(x) \le 0\}. $$

**Definition 1.36** The problem ($P_{EI}$) is said to be convex if $f$ is convex and $X_{EI}$ is a convex set. $\square$

Requiring the convexity of $X_{EI}$ is less demanding than requiring the affinity of $c_E$ and the componentwise convexity of $c_I$.

**Proposition 1.37 (sufficient conditions for $X_{EI}$ convex)** If $c_E$ is affine and $c_I$ is componentwise convex, then $X_{EI}$ is convex.

We say that the inequality constraint $c_i(x) \le 0$, for some $i \in I$, is active at a point $x \in X_{EI}$ if $c_i(x) = 0$. The sets of indices of active and inactive inequality constraints are respectively denoted by

$$ I^0(x) := \{i \in I : c_i(x) = 0\} \quad \text{and} \quad I^\sim(x) := \{i \in I : c_i(x) < 0\}. $$

We alleviate notation by setting $I_*^0 := I^0(x_*)$ and $I_*^\sim := I^\sim(x_*)$ for a given point $x_* \in X_{EI}$.
## Constraint Qualification

The necessary condition of optimality of Peano-Kantorovich (1.51) makes use of the tangent cone to the feasible set. Our goal is to see how this condition reads in the case of the problem ($P_{EI}$), so that an analytic expression of $T_x X_{EI}$ is desirable. As expected, this description of $T_x X_{EI}$ uses the derivatives of the function $c$ defining the feasible set $X_{EI}$.

The tangent cone $T_x X_{EI}$ is always contained in the linearizing cone

$$ T'_{x} X_{EI} := \{d \in \mathbb{E} : c'_{E}(x) \cdot d = 0, c'_{I^{0}(x)}(x) \cdot d \le 0\}, \quad (1.56) $$

that is

$$ T_x X_{EI} \subseteq T'_x X_{EI}. $$

One would like to have equality, since then an explicit expression of the tangent cone is at hand, which makes possible an analytic expression of the optimality (our goal in this section). This is not unusual, but not always true, since $T'_x X_{EI}$ is a convex polyhedron, while the tangent cone $T_x X_{EI}$ may not be convex.

**Definition 1.38 (qualification of c to represent $X_{EI}$)** One says that the constraint $c$ is qualified for representing $X_{EI}$ at $x$ if

$$ T_x X_{EI} = T'_x X_{EI}. \quad (1.57) $$

<figure><img src="image_6.png" /></figure>

It is usually difficult to verify directly whether (1.57) holds. To make this frequent task easier, one has identify a number of sufficient conditions guaranteeing (1.57). Here are the four mostly used (there are many others).

* (CQ-A) [A for Affinity] $c_{E \cup I^0(x)}$ is affine near $x$,

* (CQ-S) [S for Slater [130]] $c_E$ is affine, $c_{I^0(x)}$ is componentwise convex, $\exists \tilde{x} \in X_{EI}$ such that $c_{I^0(x)}(\tilde{x}) < 0$,

* (CQ-LI) [LI for Linear Independence] $\sum_{i \in E \cup I^0(x)} \alpha_i \nabla c_i(x) = 0 \implies \alpha = 0$,

* (CQ-MF) [MF for Mangasarian-Fromovitz [97]] $\sum_{i \in E \cup I^0(x)} \alpha_i \nabla c_i(x) = 0$ and $\alpha_{I^0(x)} \ge 0 \implies \alpha = 0$.

It is clear that (CQ-LI) implies (CQ-MF), so that the latter is more often satisfied than the former.

**Proposition 1.39 (other forms of (CQ-MF))** Suppose that $c_{E \cup I^0(x)}$ is differentiable at $x \in X_{EI}$. Then, the following properties are equivalent:

(i) (CQ-MF) holds at $x$,

(ii) $\forall v \in \mathbb{R}^m, \exists d \in \mathbb{E}: c'_E(x) \cdot d = v_E$ and $c'_{I^0(x)}(x) \cdot d \le v_{I^0(x)}$,

(iii) $c'_E(x)$ is surjective and $\exists d \in \mathbb{E}: c'_E(x) \cdot d = 0$ and $c'_{I^0(x)}(x) \cdot d < 0$.
## KKT Conditions

The following NC1 is often attributed to Karush, Kuhn, and Tucker [82, 87] (XXth century). It uses the Lagrangian of ($P_{EI}$), which is the function

$$ \ell: (x, \lambda) \in \mathbb{E} \times \mathbb{F} \mapsto \ell(x, \lambda) = f(x) + \lambda^T c(x) \in \mathbb{R}. $$

Because of its importance and because we shall follow the same track for determining NC1 for the general problem ($P_G$) in section 2.1.2, we provide a proof of the following result, which is very important in nonlinear optimization.

**Theorem 1.40 (Karush-Kuhn-Tucker (KKT))** If $x_*$ is a local minimum of ($P_{EI}$), if $f$ and $c$ are differentiable at $x_*$, and if $c$ is qualified for representing $X_{EI}$ at $x_*$ in the sense (1.57), then, there exists a $\lambda_* \in \mathbb{R}^m$ such that

$$ \nabla_x \ell(x_*, \lambda_*) = 0, \qquad (1.58a) $$

$$ c_E(x_*) = 0, \qquad (1.58b) $$

$$ 0 \le (\lambda_*)_I \perp c_I(x_*) \le 0. \qquad (1.58c) $$

*Proof.* Let us alleviate notation by setting $J := I^0(x_*)$. We have successively

$$ \begin{aligned} \nabla f(x_*) & \in (T_{x_*} X_{EI})^+ \quad [(1.51)] \\ &= (T'_{x_*} X_{EI})^+ \quad [\text{constraint qualification (1.57) at } x_*] \\ &= -\{c'_E(x_*)^* y + c'_J(x_*)^* z : y \in \mathbb{R}^{m_E}, z \in \mathbb{R}_+^{|J|}\} \quad [(1.2.8)]. \end{aligned} $$

Hence, there exist vectors $y \in \mathbb{R}^{m_E}$ and $z \in \mathbb{R}_+^{|J|}$ such that

$$ \nabla f(x_*) = -c'_E(x_*)^* y - c'_J(x_*)^* z. $$

The conditions in (1.58) are then obtained by introducing

$$ (\lambda_*)_i := \begin{cases} y_i & \text{if } i \in E \\ z_i & \text{if } i \in J \\ 0 & \text{if } i \in I \setminus J. \end{cases} \qquad \square $$

**Definitions 1.41** 1) A vector $\lambda_*$ appearing in (1.58) is called a KKT or optimal multiplier associated with $x_*$, since it multiplies the constraint in the Lagrangian. The term “multiplier” comes from the fact that it multiplies the constraint in the Lagrangian.

2) A point $x_*$ satisfying (1.58) is said to be a stationary point. Sometimes, one says that the pair $(x_*, \lambda_*)$ satisfying (1.58) is stationary.

3) The condition (1.58c) is special and is known as the complementarity conditions of the problem ($P_{EI}$). With their three operators, they mean the three conditions
1. Background

$$ (\lambda_*)I \ge 0, \quad (\lambda_*)^T I c_I(x_*) = 0, \quad \text{and} \quad c_I(x_*) \le 0. $$

Hence “⊥” expresses the orthogonality with respect to the Euclidean product in $\mathbb{R}^{m_I}$. Because of the sign of $\lambda_*$ and $c_I(x_*)$, the second condition above has the following equivalent expressions

$$ (\lambda_*)^T I c_I(x_*) = 0 \iff \forall i \in I: (\lambda_*)_i c_i(x_*) = 0 \\ \iff \forall i \in I: (c_i(x_*) < 0 \implies (\lambda_*)_i = 0). $$

In other words, a multiplier associated with an inactive constraint vanishes.

4) One says that strict complementarity holds for a stationary pair $(x_*, \lambda_*)$ if

$$ \forall i \in I: (c_i(x_*) < 0 \iff (\lambda_*)_i = 0). \qquad (1.59) $$

This is a property of $(x_*, \lambda_*)$, which is not necessary guaranteed by the fact that $x_*$ is a local solution to $(P_{EI})$. $\square$

By definition, the set of optimal multipliers $\lambda_*$ associated with a stationary point $x_*$ of $(P_{EI})$ is the set defined and denoted by

$$ \Lambda_* := \{\lambda_* \in \mathbb{R}^m : \nabla f(x_*) + c'(x_*)^* \lambda_* = 0, (\lambda_*)_{I_*^0} \ge 0, (\lambda_*)_{I_*^c} = 0\}. $$

It is therefore a convex polyhedron of $\mathbb{R}^m$, which is nonempty by definition of the stationarity of $x_*$. The next proposition provides two properties of this set: a characterization of its boundedness [59] and of its uniqueness [89]. For a given multiplier $\lambda_*$, the following notation is adopted:

$$ I_*^{0+} := \{i \in I_*^0 : (\lambda_*)_i > 0\} \quad \text{and} \quad I_*^{00} := \{i \in I_*^0 : (\lambda_*)_i = 0\}. $$

**Proposition 1.42 (set of optimal multipliers)** Suppose that $f$ and $c$ are differentiable at a stationary point $x_*$ of problem $(P_{EI})$ and that the set of associated multipliers $\Lambda_*$ is nonempty. Then,

1) $\Lambda_*$ is bounded if and only if (CQ-MF) holds,

2) for a given $\lambda_* \in \mathbb{R}^m$, the following properties are equivalent:

(i) $\Lambda_* = \{\lambda_*\}$,

(ii) any vector $\alpha \in \mathbb{R}^{|E|+|I_*^0|}$ verifying

$$ \sum_{i \in E \cup I_*^0} \alpha_i \nabla c_i(x_*) = 0 \quad \text{and} \quad \alpha_{I_*^{00}} \ge 0 $$

vanishes,

(iii) $c'_{E \cup I_*^{0+}}(x_*)$ is surjective and there exists a vector $d \in \mathbb{E}$ such that

$$ c'_{E \cup I_*^{0+}}(x_*)d = 0 \quad \text{and} \quad c'_{I_*^{00}}(x_*)d < 0. $$

The boundedness characterization is surprizing, since $\Lambda_*$ is linked to the optimization problem $(P_{EI})$, while (CQ-MF) only depends on the feasible set.
### SC1 for a Convex Problem

Roughly speaking, the KKT conditions at a pair $(x_*, \lambda_*)$ are sufficient to guarantee that $x_*$ is a global minimum of $(P_{EI})$, provided the problem is convex in the sense of the definition 1.36. Note that this CS1 does not require a constraint qualification.

**Proposition 1.43 (SC1 for a convex ($P_{EI}$))** Suppose that problem $(P_{EI})$ is convex in the sense of the definition 1.36 and that $f$ and $c$ are differentiable at a point $x_* \in \mathbb{E}$ that satisfies (1.58) for some $\lambda_* \in \mathbb{F}$. Then, $x_*$ is a global minimum of $(P_{EI})$.

### 1.4.5 Abstract Duality

This section describes various approaches allowing us to make links between two optimization problems, which may seem to have no connection to each other. Sometimes, the optimal multipliers of one problem are the solutions to the other one, and vice versa. The most often used scheme to connect two problems is the min-max duality.

#### Min-max duality

Consider the general optimization problem

$$ (P) \quad \inf_{x \in X} f(x), $$

where $X$ is an arbitrary set and $f: X \to \bar{\mathbb{R}}$ is an arbitrary function. Denote its optimal value and its solution set respectively by

$$ \text{val}(P) \quad \text{and} \quad \text{Sol}(P). $$

In the duality context, $(P)$ is called the *primal problem*, that is the problem that is first present.

Min-max duality comes into play when $f(x)$ can be written as a supremum:

$$ f(x) = \sup_{y \in Y} \varphi(x, y), $$

where $Y$ is some arbitrary set and $\varphi: X \times Y \to \bar{\mathbb{R}}$ is some arbitrary function. The function $\varphi$ is called the *pairing function*. Then problem $(P)$ reads

$$ (P) \quad \inf_{x \in X} \sup_{y \in Y} \varphi(x, y). $$

The *dual problem* is then obtained by inverting the order in which the infimum and the supremum are taken:

$$ (D) \quad \sup_{y \in Y} \inf_{x \in X} \varphi(x, y). $$

Denote its optimal value and its solution set respectively by
$val(D)$ and $Sol(D)$.

Aside from this audacious construction, which allowed us to derive the dual problem from the primal problem, the two problems may have no interesting links with each other. Nevertheless, the following so-called weak duality inequality always holds:

$$ val(D) \leq val(P). \qquad (1.60) $$

*Proof.* Clearly

$$ \forall x' \in X, \forall y' \in Y: \quad \varphi(x', y') \leq \varphi(x', y') $$

and therefore certainly

$$ \forall x' \in X, \forall y' \in Y: \quad \inf_{x \in X} \varphi(x, y') \leq \varphi(x', y'). $$

Fixing $x' \in X$ and taking the supremum in $y' \in Y$ in the two sides, yields

$$ \forall x' \in X: \quad \sup_{y \in Y} \inf_{x \in X} \varphi(x, y) \leq \sup_{y \in Y} \varphi(x', y). $$

Since the left-hand side is independent of $x'$, one can take the infimum in $x' \in X$ in the right-hand side and keep the inequality. This yields (1.60). □

Given the very general context, this inequality is remarkable. When equality occurs in (1.60), one says that there is no dually gap between the primal and dual problems. This fact is not guaranteed. When the inequality (1.60) is strict, the positive value $val(P) - val(D)$ is called the duality gap; it may be infinite.

A stronger link occurs between the primal and dual problems when the pairing function $\varphi$ has a saddle-point, which is a point $(\bar{x}, \bar{y}) \in X \times Y$ such that

$$ \forall (x, y) \in X \times Y: \quad \varphi(\bar{x}, y) \leq \varphi(\bar{x}, \bar{y}) \leq \varphi(x, \bar{y}). $$

In other words, $\varphi(\bar{x}, \cdot)$ must have a maximum at $\bar{y}$ and $\varphi(\cdot, \bar{y})$ must have a minimum at $\bar{x}$; nothing is required outside the vertical cross $(\{\bar{x}\} \times Y) \cup (X \times \{\bar{y}\})$. A saddle-point may be characterized in terms of $val(P)$, $Sol(P)$, $val(D)$, and $Sol(D)$:

$$ (\bar{x}, \bar{y}) \text{ is a saddle-point of } \varphi \iff \left\{ \begin{array}{l} \bar{x} \in \text{Sol}(P) \\ \bar{y} \in \text{Sol}(D) \\ \text{val}(D) = \text{val}(P). \end{array} \right. \qquad (1.61) $$

The set of saddle-points of the function $\varphi$ is a Cartesian product, that is a set of the form $\bar{X} \times \bar{Y}$, where $\bar{X} \subseteq X$ and $\bar{Y} \subseteq Y$. This means that if $(\bar{x}_1, \bar{y}_1)$ and $(\bar{x}_2, \bar{y}_2)$ are saddle-points of $\varphi$, then $(\bar{x}_1, \bar{y}_2)$ and $(\bar{x}_2, \bar{y}_1)$ are also saddle-points of $\varphi$.

The primal and dual problems do not have the same solutions, since these live in different sets, in $X$ for the former and in $Y$ for the latter. Sometimes, the interest of the dual problem is that it may be easier to solve than the primal. Then, the question arises to know how to get a primal solution (what interests the designer of
that problem), when a solution to the dual problem is known. The next propositon
explains how to get such a primal solution in the present very general context.

**Proposition 1.44** Suppose that $\varphi$ has a saddle-point $(\bar{x}, \bar{y})$. Then,

$$
\emptyset \neq \operatorname{Sol}(P) \subseteq \operatorname{Arg\,min}_{x \in X} \varphi(x, \bar{y}) \quad \text{and} \quad \emptyset \neq \operatorname{Sol}(D) \subseteq \operatorname{Arg\,max}_{y \in Y} \varphi(\bar{x}, y).
$$

The first claim of the proposition tells us that, if $\varphi$ has a saddle-point and if $\bar{y}$ is
a solution to the dual problem, the solutions to the primal problem are also the
solutions to the problem $\inf\{\varphi(x, \bar{y}) : x \in X\}$. Therefore, there are some chance
to recover a solution to the primal problem by solving the optimization problem
$\inf\{\varphi(x, \bar{y}) : x \in X\}$. Now, this last problem may also have solutions that are not
solution to $(P)$; we call them *improper solutions*. Analog comments can be made for
the second claim of the proposition.

1.4.6 Linear Optimization Problem ($P_L$)

Let $\mathbb{E}$ be Euclidean vector space, $c \in \mathbb{E}$, $A : \mathbb{E} \to \mathbb{R}^m$ and $B : \mathbb{E} \to \mathbb{R}^p$ be linear maps, $a \in \mathbb{R}^m$, and $b \in \mathbb{R}^p$. A linear optimization problem ($P_L$) and its Lagrangian dual ($D_L$) read

$$
(P_L) \quad \left\{
\begin{array}{ll}
\inf_{x \in \mathbb{E}} \langle c, x \rangle & \text{and} \\
Ax = a & \\
Bx \le b &
\end{array}
\right.
\qquad \text{and} \qquad
(D_L) \quad \left\{
\begin{array}{l}
\sup_{(y,s) \in \mathbb{R}^m \times \mathbb{R}^p} a^T y - b^T s \\
A^T y - B^T s = c \\
s \ge 0.
\end{array}
\right.
\qquad (1.62)
$$

See below to learn how the dual problem is derived from the primal problem using
min-max duality. The optimal value and the solution set of the primal problem are
denoted by val($P_L$) and Sol($P_L$) respectivement. Similarly, the optimal value and the
solution set of the dual problem are denoted by val($D_L$) and Sol($D_L$), respectively.

The existence of a solution to the primal problem ($P_L$) is characterized by the
following equivalence, in which val($P_L$) $\in \mathbb{R}$ means that the problem ($P_L$) is feasible
(i.e., its feasible set is nonempty, or, equivalently val($P_L$) $< \infty$) and bounded (i.e.,
val($P_L$) $> -\infty$).

$$
(P_L) \text{ has a solution} \iff \text{val}(P_L) \in \mathbb{R}. \tag{1.63}
$$

Proof. Since the left-to-right implication is clear, we only have to prove the reciprocal.
Assume that val($P_L$) $\in \mathbb{R}$. Then one can find a minimizing sequence (since the feasible
set is nonempty), i.e., a sequence {$x_k$} such that

$$
Ax_k = a, \quad Bx_k \le b, \quad \text{and} \quad \langle c, x_k \rangle \to \text{val}(P_L).
$$

Furthermore, the set {⟨c, x⟩ : Ax = a, Bx ≤ b} is a closed interval in ℝ (since it is
the image by the linear map x ↦ ⟨c, x⟩ of the convex polyhedron {x ∈ E : Ax = a,
Bx ≤ 0}, hence a convex polyhedron of ℝ; see property 1 of proposition 1.1). Since
$\langle c, x_k \rangle$ is in that interval and converges to $\text{val}(P_L)$, this finite limit belongs to this interval, meaning that there exists a point $\bar{x} \in \mathbb{E}$ such that $\text{val}(P_L) = \langle c, \bar{x} \rangle$, $A\bar{x} = a$, and $B\bar{x} \le b$. This point $\bar{x}$ is therefore a solution to $(P_L)$. $\square$

The dual problem $(D_L)$ is obtained from the primal problem $(P_L)$ using the min-max duality, with the Lagrangian $\ell$ as pairing function (denoted $\varphi$ in section 1.4.5). One can process that way since the primal problem can be written as the following infsup problem:

$$ \inf_{x \in \mathbb{E} \atop y \in \mathbb{R}_+^m} \sup_{s \in \mathbb{R}_+^p} \langle c, x \rangle - y^\mathrm{T}(Ax - a) + s^\mathrm{T}(Bx - b). \quad (1.64) $$

This is because

$$ \sup_{y \in \mathbb{R}_+^m \atop s \in \mathbb{R}_+^p} \langle c, x \rangle - y^\mathrm{T}(Ax - a) + s^\mathrm{T}(Bx - b) = \begin{cases} \langle c, x \rangle & \text{if } Ax = a \text{ and } Bx \le b \\ +\infty & \text{otherwise.} \end{cases} $$

Indeed, first, if $Ax = a$ and $Bx \le b$, $y^\mathrm{T}(Ax - a) = 0$ and $s^\mathrm{T}(Bx - b) \le 0$ (since $s \ge 0$) and the supremum value $\langle c, x \rangle$ can be reached by taking any $y$ and $s = 0$; next, if $Ax \ne a$, the infinite supremum is obtained by taking $y = t(Ax - a)$, $s = 0$, and $t \to \infty$; and finally, if $Bx \le b$, the infinite supremum is obtained by taking $y = 0$, $s = t(Bx - b)^+ = t \max(0, Bx - b)$, and $t \to \infty$. Problem $(D_L)$ is then obtained by inverting the infimum and the supremum in (1.64), to get

$$ \begin{align*} & \sup_{y \in \mathbb{R}_+^m \atop s \in \mathbb{R}_+^p} \inf \langle c, x \rangle - y^\mathrm{T}(Ax - a) + s^\mathrm{T}(Bx - b) \\ &= \sup_{y \in \mathbb{R}_+^m \atop s \in \mathbb{R}_+^p} \inf \langle c - A^*y + B^*s, x \rangle + a^\mathrm{T}y - b^\mathrm{T}s \\ &= \sup_{y \in \mathbb{R}_+^m \atop s \in \mathbb{R}_+^p} \begin{cases} a^\mathrm{T}y - b^\mathrm{T}s & \text{if } A^*y - B^*s = c \\ -\infty & \text{otherwise} \end{cases} \\ &= \sup_{y \in \mathbb{R}_+^m \atop s \in \mathbb{R}_+^p} a^\mathrm{T}y - b^\mathrm{T}s, \\ & \phantom{=} A^*y - B^*s = c \end{align*} $$

which is indeed $(D_L)$.

A consequence of the above dualization process is the weak duality inequality (see (1.60)):

$$ \text{val}(D_L) \le \text{val}(P_L). \quad (1.65) $$

The strong duality result refers to the following equivalences:

$$ (P_L) \text{ and } (D_L) \text{ are feasible} \iff \text{Sol}(P_L) \ne \emptyset \iff \text{Sol}(D_L) \ne \emptyset. \quad (1.66) $$

When the conditions in (1.66) hold, the primal and dual optimal values are identical (there is no duality gap): $\text{val}(D_L) = \text{val}(P_L)$. The implication “$(P_L)$ and $(D_L)$ are feasible $\Rightarrow$ Sol $(P_L) \ne \emptyset$” is often used to show that the primal problem has a solution.
# 1.5 Algorithmics

## 1.5.1 Speeds of Convergence

**Definitions 1.45 (speeds of convergence)** Let $\mathbb{E}$ be a normed space and $\{x_k\} \subseteq \mathbb{E}$ be a sequence converging to $x_* \in \mathbb{E}$, different from $x_*$. Then $\{x_k\}$ is said to converge

* linearly, if there exist a constant $r \in [0, 1)$ and an index $k_0 \in \mathbb{N}$ such that

$$ \forall k \geq k_0 : \quad \|x_{k+1} - x_*\| \leq r\|x_k - x_*\|, $$

* superlinearly, if

$$ x_{k+1} - x_* = o(\|x_k - x_*\|), $$

* quadratically, if

$$ x_{k+1} - x_* = O(\|x_k - x_*\|^2). $$

**Remarks 1.46** 1) The speeds of convergence above are sometimes named *quotient-speeds* since they are based on an estimation of the quotient $\|x_{k+1} - x_*\|/\|x_k - x_*\|$. Such an estimation is usually obtained by taking the development around $x_*$ of the functions involved in the definition of the problem to solve and by using the algorithm definition and properties. Sometimes one uses the terms q-linear, q-superlinear, and q-quadratic convergence, to distinguish them from the r-linear, r-superlinear, and r-quadratic convergence, which are less demanding notions called *root-speeds* of convergence [106].

2) The property of linear convergence depends on the norm chosen on $\mathbb{E}$ (linear convergence may occur for one norm and not for another one), but not those of superlinear and quadratic convergences.

3) Obviously, the superlinear convergence is faster than the linear convergence and the quadratic convergence is faster than the superlinear convergence.

4) Superlinear convergence is typically obtained by the quasi-Newton methods (when everything is going well), while quadratic convergence is typical of Newton's method.

To conclude this section, let us mention a property of superlinear convergence that will be useful in section 4.1.4. We say that two sequences $\{u_k\}_{k \geq 0}$ and $\{v_k\}_{k \geq 0}$ in a normed space $\mathbb{E}$ converge to zero equivalently, a concept that we denote by $\{u_k\} \sim \{v_k\}$, if

$$ \exists C > 0, \forall k \geq 0 : C^{-1}\|u_k\| \leq \|v_k\| \leq C\|u_k\|. $$

**Lemma 1.47 (equivalent vanishing sequences)** If the sequence $\{x_k\}$ converges to $x_*$ superlinearly, then, $\{x_{k+1} - x_k\} \sim \{x_k - x_*\}$.

*Proof.* Just write $x_k - x_{k+1} = (x_k - x_*) - (x_{k+1} - x_*) = (x_k - x_*) + o(\|x_k - x_*\|)$ and conclude. $\square$
### 1.5.2 Newton and Quasi-Newton Algorithms ▲

#### Nonlinear Equation

Consider first the problem of finding a zero of a nonlinear system of equations. A function $F: \mathbb{E} \to \mathbb{F}$ between two vector spaces $\mathbb{E}$ and $\mathbb{F}$ of the same finite dimension is given and the problem consists in finding a zero of $F$, that is a point $x \in \mathbb{E}$ such that

$$F(x) = 0. \tag{1.67}$$

Newton's algorithm computes such a zero approximately (but with high precision) by generating a sequence $\{x_k\} \subseteq \mathbb{E}$, which is expected to converge to a zero of $F$. The procedure is as follows. Given the current iterate $x_k \in \mathbb{E}$, $F$ is first linearized at $x_k$ yielding the affine model of $F$:

$$x \in \mathbb{E} \mapsto F(x_k) + F'(x_k) \cdot (x - x_k),$$

which is a good approximation of $F$ near $x_k$. Then, it makes sense to take as next iterate $x_{k+1}$, a zero of this affine map. Hence $x_{k+1}$ solves (if possible)

$$F(x_k) + F'(x_k) \cdot (x_{k+1} - x_k) = 0. \tag{1.68a}$$

This is a linear system, which is much easier to solve than the original nonlinear system (1.67). If $F$ is $C^1$ and $x_*$ is a regular zero, that is a zero with a nonsingular Jacobian $F'(x_*)$, then when the current iterate $x_k$ is near $x_*$, $F'(x_k)$ is nonsingular and the next iterate $x_{k+1}$ is obtained by

$$x_{k+1} = x_k - F'(x_k)^{-1} F(x_k). \tag{1.68b}$$

These claims are clarified by the local convergence result to theorem 1.48.

Conditions ensuring the local convergence of Newton's method are given in the next result.

**Theorem 1.48 (convergence of the Newton algorithm)** Suppose that $F$ has a zero $x_*$, that $F$ is continuously differentiable around $x_*$, and that $F'(x_*)$ is nonsingular. Then

1) there exists $\varepsilon > 0$ such that, if the first iterate $x_1 \in \bar{B}(x_*, \varepsilon)$, the Newton algorithm (1.68), starting at $x_1$, is well defined and generates a sequence $\{x_k\}$ converging superlinearly to $x_*$,

2) if, furthermore, $F$ is $C^{1,1}$ in a neighborhood of $x_*$, the convergence is quadratic.

A quasi-Newton algorithm operates like the Newton method, except that the Jacobians $F'(x_k)$ are approached by a linear operator $M_k: \mathbb{E} \to \mathbb{F}$, by a very specific technique. This avoids the need of computing the derivatives. Hence, the next iterate $x_{k+1}$ is computed by solving the linear system

$$F(x_k) + M_k(x_{k+1} - x_k) = 0. \tag{1.69}$$
Despite the derivatives are not computed, superlinear convergence of the iterates is usually possible. To prove such speed of convergence, the following Dennis and Moré criterion for superlinear convergence is valuable. This criterion involves the quality of $M_k$ only along the displacement direction $x_{k+1} - x_k$.

**Proposition 1.49 (Dennis & Moré criterion for superlinear convergence)** Suppose $F$ is differentiable at one of its zero $x_*$, that $F'(x_*)$ is nonsingular, and that $\{x_k\}$ generated by (1.69) converges to $x_*$. Then, the following properties are equivalent

(i) the convergence of $\{x_k\}$ to $x_*$ is superlinear,

(ii) $[M_k - F'(x_*)](x_{k+1} - x_k) = o(\|x_{k+1} - x_k\|)$.

*Proof.* Let us start by giving an expression of $[M_k - F'(x_*)](x_{k+1} - x_k)$ that takes into account the form of the algorithm displacement $(x_{k+1} - x_k)$, given by (1.69). There hold

$$ 
\begin{align} 
[M_k - F'(x_*)](x_{k+1} - x_k) & = -F(x_k) - F'(x_*)(x_{k+1} - x_k) \tag{1.69} \\ 
& = -F'(x_*)(x_k - x_*) + o(\|x_k - x_*\|) - F'(x_*)(x_{k+1} - x_k) \nonumber \\ 
& \quad [F(x_*) = 0 \text{ and differentiability of } F \text{ at } x_*] \nonumber \\ 
& = -F'(x_*)(x_{k+1} - x_*) + o(\|x_k - x_*\|). \tag{1.70} 
\end{align} 
$$

[(i) ⇒ (ii)] By (i) and (1.70), we get

$$ [M_k - F'(x_*)](x_{k+1} - x_k) = o(\|x_k - x_*\|). $$

Then (ii) follows by (i) and lemma 1.47.

[(ii) ⇒ (i)] If (ii) holds, (1.70) yield

$$ F'(x_*)(x_{k+1} - x_*) = o(\|x_k - x_*\|). $$

The nonsingularity of $F'(x_*)$ then implies that $x_{k+1} - x_* = o(\|x_k - x_*\|)$, which is the superlinear convergence $\{x_k\}$, yielding (i). □

### Unconstrained Optimization ▲

Consider now the unconstrained optimization problem ...

#### 1.5.3 Global Convergence in Unconstrained Optimization ▲

Consider the problem of minimizing a function $f: \mathbb{E} \to \mathbb{R}$ on a Euclidean vector space $\mathbb{E}$ (no constraint):

$$ \min_{x \in \mathbb{E}} f(x). $$

The global convergence of an algorithm generating a sequence of iterates $\{x_k\}_{k \ge 1}$ means that some kind of convergence result for this sequence $\{x_k\}_{k \ge 1}$ or most often
for some associated quantities (like the gradients $\nabla f(x_k)$) can be obtained, whatever the initial iterate $x_1$ is. This concept has to be compared with that of a local convergence result, which assumes that the initial iterate is close enough to a solution.

The most classical results “only” prove that the sequence of the gradients $\nabla f(x_k)$ converges to zero or, even less, that $\liminf_{k \to \infty} \|\nabla f(x_k)\| = 0$ (meaning that a subsequence of $\{\nabla f(x_k)\}$ converges to zero). It is usually not the case that the sequence of iterates $\{x_k\}_{k \ge 1}$ itself converges to a solution to the problem, unless strong assumption are taken on the function $f$, like its strong convexity. Nevertheless, if $\nabla f(x_k) \to 0$, any adherent point of $\{x_k\}_{k \ge 1}$ is a solution to the problem.

Once a method is able to define a direction of move $d_k \in \mathbb{E}$ at the current iterate $x_k$, a *globalization strategy* can be introduced, which is a technique able to force convergence from any starting point. The most famous globalization strategies are the use of *line-searches* and *trust-regions*.

## Line-search

A line-search algorithm generates a sequence $\{x_k\}$ as follows:

* choice of a descent direction at $x_k$, i.e., $d_k \in \mathbb{E}$ such that $f'(x_k) \cdot d_k < 0$ (standard examples are gradient, conjugate gradient, Newton, quasi-Newton, and Gauss-Newton directions; each of these directions has specific properties and are more or less adapted to a given problem);

* determination of a step-size $\alpha_k > 0$ by a line-search rule to force a sufficient decrease of $f$ along $d_k$ (standard examples are Cauchy, Armijo, Goldstein, and Wolfe rules; each of these rules is adapted to particular situations, directions, and specificities of the problem at hand);

* the next iterate is then obtained by $x_{k+1} := x_k + \alpha_k d_k$.

This is a very simple algorithm, but with powerful properties. Its simplicity makes it more easily adaptable to problems that are more complex than unconstrained minimization.

In the next result, we simplify the notation by abbreviating $g_k := \nabla f(x_k)$.

**Proposition 1.50 (global convergence with line-search)** Let $\{x_k\}$ be a sequence generated by the line-search algorithm described above. If $\{f(x_k)\}$ is bounded below, then

$$ \sum_{k \ge 1} \|g_k\|^2 \cos^2 \theta_k < +\infty, \quad (1.71) $$

where $\theta_k := \arccos(-g_k, d_k) / (\|g_k\| \|d_k\|)$ is the angle between $d_k$ and $-g_k$.

The property claiming that the series in (1.71) is convergent is called the *Zoutendijk condition* [138; 1970]. It provides the contribution of the line-search to the global convergence. The contribution of the directions $d_k$ is also important and one cannot conclude any interesting properties without specifying it. Sometimes the analysis is long and tortuous [61; 1992]. The simplest situation is for the *gradient or steepest descent algorithm*, in which $d_k = -g_k$; in that case, $\cos \theta_k = 1$ and we obtain that the series $\sum_k \|g_k\|^2$ is convergent, implying in turn that $g_k \to 0$. This is the kind of results
that is highly desirable. Without assumption like the strong convexity of $f$, one cannot guarantee that the sequence of iterates $\{x_k\}$ converges to a point minimizing $f$ (see [62; 2000] and the references therein). Hence, one can say that the gradient algorithm with line-search is convergent.

### Trust-Region ▲

A trust-region algorithm generates a sequence $\{x_k\}$ as follows:

* choice of a model $\varphi_k$ of $f$ around $x_k$, usually quadratic: $\varphi_k(s) := \langle g_k, s \rangle + \frac{1}{2}\langle M_k s, s \rangle$ (standard models are the gradient, Newton, quasi-Newton, and Gauss-Newton models);

* determination of a trust-radius $\Delta_k > 0$ such that $f(x_k + s_k)$ is sufficiently smaller than $f(x_k)$, where $s_k \in \operatorname{Arg min}\{\varphi_k(s) : \|s\| \le \Delta_k\}$;

* the next iterate is then obtained by $x_{k+1} := x_k + s_k$.

**Proposition 1.51 (global convergence with trust-region)** If $f$ is $C^1$ in a neighborhood of $V_1 := \{x \in \mathbb{E} : f(x) \le f(x_1)\}$, if $\{f(x_k)\}$ is bounded below, and if $\{M_k\}$ is bounded, then $\liminf_{k \to \infty} \|g_k\| = 0$. If, furthermore, $f$ is $C^{1,1}$, then $g_k \to 0$.

### 1.5.4 Global Convergence for Nonlinear Equations ▲

Let $F: \mathbb{E} \to \mathbb{E}$ and consider the problem of finding $x$ such that

$$F(x) = 0.$$

No algorithm with global convergence (a few exceptions however; e.g., when $F$ is polynomial, but the methods are expensive and restricted to problems with a rather small dimension).

$$\min_{x \in \mathbb{E}} \left( \varphi(x) := \frac{1}{2} \|F(x)\|_2^2 \right).$$

An amazing but misleading fact is the following. If $\nabla\varphi(x_k) \ne 0$, the Gauss-Newton direction

$$d_k^{\mathrm{GN}} \in \operatorname{Arg min}_{d \in \mathbb{E}} \|F(x_k) + F'(x_k)d\|_2^2$$

is a descent direction of $\varphi$ at $x_k$. May yield false convergence. It is better to use the trust-region approach: $x_{k+1} = x_k + s_k$, where

$$s_k \in \operatorname{Arg min}_{\|s\|_2 \le \Delta_k} \|F(x_k) + F'(x_k)s\|_2^2,$$

with well adapted trust-radius $\Delta_k > 0$.
<figure><img src="image_7.png" /></figure>
## 2 Optimality Conditions

There is no more general optimization problem than $(P_X)$ in (1.47), in which an arbitrary function $f$ is minimized on an arbitrary set $X$ (well, there, the set was supposed to belong to a Euclidean space, which is already a major restriction). In this chapter, we consider a problem with a little more structure than $(P_X)$, but not much: an additional function $c$ is used to represent the feasible set, which is now defined by “$c(x) \in G$”, where $c$ is an arbitrary function and $G$ is a nonempty closed convex set. The goal of the analysis of this chapter is to clarify where and how this function $c$ and the set $G$ intervene in the optimality conditions. A remarkable outcome is that the theory presented in section 1.4.4 for the equality and inequality constrained problem $(P_{EI})$ can be nicely extended to this much more general problem. The abstraction brought by the considered model will allow us to better figure out the meaning of the optimality conditions, by highlighting their geometrical structure, and has the technical advantage of not forcing us to work with indices, which makes the proofs easier and more elegant. Furthermore, this generalization is also a means to make a few steps on the way towards the analysis of infinite dimensional problems, which are perfectly well defined with this abstract setting.

### 2.1 First Order Optimality Conditions for $(P_G)$

The first order optimality conditions of an optimization problem are frequently used. Since they express optimality by a mathematical system made of equalities, inequalities, inclusions, etc, which can be solved, they can be used to compute a solution analytically, i.e., on a piece of paper, to design algorithms to compute them, to conceive a stopping criterion for the latter, to have properties on the solutions of the considered problems. For these reasons, their setting is a very important step in the understanding of an optimization problem.

#### 2.1.1 Definition of the General Problem

Let $\mathbb{E}$ and $\mathbb{F}$ be two Euclidean vector spaces. We consider the problem

$$ (P_G) \quad \left\{ \begin{array}{l} \min f(x) \\ c(x) \in G, \end{array} \right. \qquad (2.1) $$

where $f: \mathbb{E} \to \mathbb{R}$ and $c: \mathbb{E} \to \mathbb{F}$ are smooth functions, and $G$ is nonempty closed convex set in $\mathbb{F}$ (not necessarily a cone). The letter $c$ is used to recall that the function intervenes into the constraint and the letter $G$ is introduced to avoid the more
appropriate but too frequent *C* and refers to the rather generality of this set. The feasible set of the problem is denoted by

$$X_G := \{x \in \mathbb{E} : c(x) \in G\} = c^{-1}(G).$$

**Definition 2.1 (convex (P<sub>G</sub>))** The optimization problem (P<sub>G</sub>) is said to be convex if its objective *f* is convex and its feasible set X<sub>G</sub> is convex.

The following implication holds for the multifunction $T: \mathbb{E} \to \mathbb{F}: x \mapsto c(x) - G$.

$$T \text{ is convex} \implies X_G = T^{-1}(0) \text{ is convex.} \qquad (2.2)$$

*Proof.* Note the equivalences

$$x \in X_G \iff c(x) \in G \iff 0 \in T(x) \iff x \in T^{-1}(0).$$

Therefore $X_G = T^{-1}(0)$ and, according to (1.45), $X_G$ is convex by the convexity of $T^{-1}$ (implied by the one of $T$) and the convexity of the singleton $\{0\}$. $\square$

**Examples 2.2** A number of optimization problems can be written in the form (P<sub>G</sub>). Let us mention a few.

1) The nonlinear optimization problem (P<sub>EI</sub>), presented in section 1.4.4, can be written in the form (P<sub>G</sub>), by taking $\mathbb{F} = \mathbb{R}^m$ and $G = \{0_{\mathbb{R}^{m_E}}\} \times \mathbb{R}^{m_I}$. Therefore, problem (P<sub>G</sub>) generalizes problem (P<sub>EI</sub>).

As a problem a little more general than (P<sub>G</sub>), we have

$$(P_{E[l,u]}) \quad \begin{cases} \inf_x f(x) \\ c_E(x) = 0 \\ c_I(x) \in [l, u], \end{cases}$$

where, for some vectors $l$ and $u \in \mathbb{R}^{m_I}$, $[l, u] := \{v \in \mathbb{R}^{m_I} : l \le v \le u\}$. This problem reads like problem (P<sub>G</sub>), with $\mathbb{F} = \mathbb{R}^m$ and $G = \{0_{\mathbb{R}^{m_E}}\} \times [l, u]$.

2) The linear semidefinite optimization problem reads

$$(P_{SDO}) \quad \begin{cases} \inf_{X \in S^n} \langle C, X \rangle \\ A(X) = b \\ X \ge 0, \end{cases}$$

where $C \in S^n$, $A: S^n \to \mathbb{R}^m$ is linear, $b \in \mathbb{R}^m$ and $X \ge 0$ requires that $X \in S^n_+$. This problem can be written in the form (P<sub>G</sub>) by taking $\mathbb{E} = S^n$, $\mathbb{F} = \mathbb{R}^m \times S^n$, $c: X \in S^n \to (A(X) - b, X) \in \mathbb{R}^m \times S^n$ and $G = \{0_{\mathbb{R}^m}\} \times S^n_+$.

The semidefinite optimization problem is analyzed in chapter 6.

3) Let $\mathbb{E}$ and $\mathbb{F}$ be two Euclidean vector spaces. A composite optimization problem is an optimization problem of the form

$$\min_{x \in \mathbb{E}} (g \circ F)(x), \qquad (2.3)$$
where $F: \mathbb{E} \to \mathbb{F}$ is a differentiable function, $g: \mathbb{F} \to \overline{\mathbb{R}}$ is a function that may be nonsmooth and $(g \circ F)$ denotes the composition of $g$ and $F$; hence $(g \circ F)(x) = g(F(x))$.

This problem can also be written [110] $\inf_{(x,\alpha) \in \mathbb{E} \times \mathbb{R}} \{\alpha \in \mathbb{R} : g(F(x)) \le \alpha\}$ or

$$ \left\{ \begin{array}{l} \inf_{(x,\alpha) \in \mathbb{E} \times \mathbb{R}} \alpha \\ (F(x), \alpha) \in \text{epi}(g), \end{array} \right. \qquad (2.4) $$

so that it is of the form ($P_G$) in (2.1) with $\mathbb{E} \leftarrow \tilde{\mathbb{E}} := \mathbb{E} \times \mathbb{R}$, $\mathbb{F} \leftarrow \tilde{\mathbb{F}} := \mathbb{F} \times \mathbb{R}$, $c: (x, \alpha) \in \tilde{\mathbb{E}} \mapsto (F(x), \alpha) \in \tilde{\mathbb{F}}$ and $G = \text{epi}(g) \subseteq \tilde{\mathbb{F}}$. Note that the reformulation (2.4) of (2.3) in terms of ($P_G$) is valid without the need to have $g$ smooth, since this function appears in (2.4) only through its epigraph. The set $G$ will be nonempty closed convex set if $g \in \text{Conv}(\mathbb{F})$.

Conversely, the problem ($P_G$) can also be written as a composite optimization problem [71, 110], since it reads

$$ \inf_{x \in \mathbb{E}} f(x) + \mathcal{I}_G(c(x)), $$

where $\mathcal{I}_G$ is the indicator function of the set $G$. This last optimization problem is of the form (2.3), with a function $F: x \in \mathbb{E} \mapsto (f(x), c(x)) \in \mathbb{R} \times \mathbb{F}$ and $g: (z, y) \in \mathbb{R} \times \mathbb{F} \mapsto z + \mathcal{I}_G(y) \in \overline{\mathbb{R}}$.

Therefore, problems ($P_G$) and (2.3) are equivalent.

See the subsection *Composite optimization* in section 2.1.6 for a short analysis of the composite optimization problem. $\square$

### 2.1.2 First Order Optimality Conditions

Necessary conditions of optimality of the first order (NC1) for problem ($P_G$) can be obtained by using the same approach as for problems with equality and inequality constraints, which starts with the Peano-Kantorovich condition (1.51) and culminates in the proof of theorem 1.40. There are some additional technical difficulties, however, but these can be overcome. This approach requires the computation of the tangent cone $T_x X_G$ to the feasible set $X_G$ at $x$. The first step consists in establishing a link between this tangent cone and the linearizing cone to $X_G$ at $x$, which is the cone defined and denoted by

$$ T_x' X_G := \{d \in \mathbb{E} : c'(x)d \in T_{c(x)} G\}. $$

Since it can also be written $c'(x)^{-1}[T_{c(x)} G]$, the linearizing cone is a nonempty closed convex cone, when $G$ is a nonempty closed convex set.

**Proposition 2.3 (tangent and linearizing cones)** If $c$ is differentiable at $x \in X_G$, then

$$ T_x X_G \subseteq T'_x X_G. \qquad (2.5) $$
Proof. Let $d \in T_x X_G$. One may assume that $d \neq 0$, since $0 \in T'_x X_G$, trivially. Then, there exist a sequence $\{x_k\} \subseteq X_G$ converging to $x$ and a sequence $\{t_k\} \downarrow 0$ such that $(x_k - x)/t_k \to d$. Furthermore, $c$ being differentiable at $x$, one can write $c(x_k) = c(x) + c'(x)(x_k - x) + o(\|x_k - x\|)$, so that

$$ \frac{c(x_k) - c(x)}{t_k} \to c'(x)d. $$

Since $c(x) \in G$ and $c(x_k) \in G$, we deduce from this limit that $c'(x)d \in T_{c(x)} G$. $\square$

Equality does not necessarily hold in (2.5), since $T'_x X_G$ is a convex set (see the remark before the proposition), while $T_x X_G$ is not necessarily convex (we have not required the affinity of the function $c$ defining $X_G$). This is annoying, since it is the tangent cone $T_x X_G$ that intervenes in the generic first order necessary condition of Peano-Kantorovich (1.51), while one would like to take advantage of the analytic expression of the linearizing cone $T'_x X_G$. Like for the problem ($P_{EI}$) (see the subsection *Constraint Qualification* in section 1.4.4), the notion of qualification of the function $c$ to represent $X_G$ is linked to the fact that equality holds in (2.5), but it is not limited to that property. Recall indeed the technique of proof of proposition 1.40 yielding the first order optimality conditions of Karush, Kuhn, and Tucker, a technique that will be also used to prove proposition 2.6 below. The goal is to show that the gradient $\nabla f(x_*)$ belongs to a cone that we want to be explicit. Two ingredients intervene in this approach:

* the equality between the tangent and linearizing cones, which allows us to make good use of the expression of the tangent cone given by the linearizing cone,

* the polyhedrality of the linearizing cone, which allows us to discard the closure operator acting on the set resulting from the use of the Farkas identity (1.15).

In the present case, $T'_x X_G$ is not necessary polyhedral, because we do not want to impose this restrictive polyhedrality property to $G$. In order to select the nonconvex feasible sets for which the proposed approach to establish the first order optimality conditions can be used, we introduce a so-called *constraint qualification assumption*, which precisely ensures the equality between the tangent and linearizing cones (it is (2.6a) below, nothing new there with respect to the definition 1.38), but also the closed character of the image by $c'(x)^*$ of the dual of the tangent cone $T_{c(x)} G$ (it is (2.6b) below).

**Definition 2.4 (qualification of $c$ to represent $X_G$)** The constraint $c$ is said to be qualified for representing $X_G$ at $x \in X_G$ if $c$ is differentiable at $x$ and if the following two conditions are satisfied:

$$ T_x X_G = T'_x X_G, \qquad (2.6a) $$

$$ c'(x)^* [(T_{c(x)} G)^+] \text{ is closed,} \qquad (2.6b) $$

where $c'(x)^*: \mathbb{F} \to \mathbb{E}$ denotes the adjoint linear operator of $c'(x): \mathbb{E} \to \mathbb{F}$. $\square$

The verification of this constraint qualification (2.6) is a difficult task. In order to simplify it, a sufficient condition of qualification is introduced and studied in sections 2.1.3 and 2.1.4.
Constraint qualifications make possible, like for problem ($P_E$) and ($P_{EI}$), the obtention of first order optimality conditions, those of theorem 2.6 below. When $G = K$ is un cone, we shall use the complementarity notation

$$K^+ \ni v \perp u \in K$$

to mean, in a compact manner, that the vectors $u$ and $v$ of $\mathbb{F}$ verify the three properties $u \in K$, $v \in K^+$ and $\langle u, v \rangle = 0$. We shall use the following equivalence.

**Lemma 2.5** Let $K$ be a closed convex cone in a Euclidean space $\mathbb{E}$. Then

$$v + N_u K \ni 0 \iff K^+ \ni v \perp u \in K. \quad (2.7)$$

*Proof.* Since $N_u K = \emptyset$ if $u \notin K$, the condition $v + N_u K \ni 0$ is equivalenet to

$$u \in K \quad \text{and} \quad (\langle -v, u' - u \rangle \le 0, \quad \forall u' \in K).$$

Since $K$ is a cone and $u \in K$, one can take $u' = 2u$ and $u' = \frac{1}{2}u$ (or $u' = 0$, since 0 belongs to the closed cone $K$) in the last condition, which therefore implies that $\langle u, v \rangle = 0$. As a result, the previous conditions are equivalent to

$$u \in K, \quad \langle u, v \rangle = 0, \quad \text{and} \quad (\langle v, u' \rangle \ge 0, \quad \forall u' \in K).$$

It remains to observe that the last condition also reads $v \in K^+$.

<figure><img src="image_8.png" /></figure>

**Theorem 2.6 (NC1 for problem ($P_G$))** Let $x_*$ be a local solution to problem ($P_G$). Suppose that $f$ and $c$ are differentiable at $x_*$ and that $c$ is qualified to represent $X_G$ at $x_*$, in the sense of definition 2.4. Then, there exist $\lambda_* \in \mathbb{F}$ such that

$$\nabla f(x_*) + c'(x_*)^* \lambda_* = 0, \quad (2.8a)$$

$$\lambda_* \in N_{c(x_*)} G. \quad (2.8b)$$

If $G \equiv K$ is also a cone, (2.8b) becomes

$$K^- \ni \lambda_* \perp c(x_*) \in K. \quad (2.8c)$$

*Proof.* Structurally, the proof is similar to the one of theorem 1.40, in a more abstract setting, however. We have sucessively

$$\begin{align*}
\nabla f(x_*) & \in (T_{x_*} X_G)^+ && [\text{Peano-Kantorovich (1.51)}] \\
& = (T'_{x_*} X_G)^+ && [\text{constraint qualification (2.6a) at } x_*] \\
& = \{d \in \mathbb{E} : c'(x_*) d \in T_{c(x_*)} G\}^+ && [\text{formula (2.5) of } T'_{x_*} X_G].
\end{align*}$$
We now apply the Farkas identity (1.15) with $A^* = c'(x_*)$ and $K^+ = T_{c(x_*)} G$. Since the latter is a closed convex cone, the following holds $K = K^{++}$ (see (1.16)). We get

$$ \nabla f(x_*) \in \overline{c'(x_*)^* [(T_{c(x_*)} G)^+]} = c'(x_*)^* [(T_{c(x_*)} G)^+], $$

where we have used the constraint qualification (2.6b) at $x = x_*$. We have shown the existence of a $\lambda_* \in -(T_{c(x_*)} G)^+ = N_{c(x_*)} G$ (it is (2.8b)) such that (2.8a) holds.

The complementarity condition (2.8c) results from (2.8b) and the equivalence (2.7), which can be applied since $G = K$ is a convex cone. $\square$

**Definitions 2.7 (stationary point)** A point $x_*$ satisfying (2.8a)-(2.8b) for some $\lambda_* \in \mathbb{F}$ is said to be a stationary point of problem ($P_G$). Sometimes, one says that the pair $(x_*, \lambda_*)$ satisfying (2.8a)-(2.8b) is stationary for problem ($P_G$). The vectors $\lambda_*$ in (2.8a)-(2.8b) are called the optimal multipliers associated with $x_*$. $\square$

**Remarks 2.8 1)** If $c: \mathbb{E} \to \mathbb{E}$ is the identity, (2.8a)-(2.8b) reads $\nabla f(x_*) \in -N_{x_*} G = (T_{x_*} G)^+$ and one recovers the first order necessary condition of optimality of Peano-Kantorovich (1.51). In other words, the conditions (2.8a)-(2.8b) offer a way of taking into account non simple constraints, in which a function $c$ intervenes.

2) One recognizes in (2.8a) the gradient with respect to $x$ of the Lagrangian of problem ($P_G$), which is the function $\ell: \mathbb{E} \times \mathbb{F} \to \mathbb{R}$ defined at $(x, \lambda) \in \mathbb{E} \times \mathbb{F}$ by

$$ \ell(x, \lambda) = f(x) + \langle \lambda, c(x) \rangle. \qquad (2.9) $$

This Lagrangian makes use of the functional part of the constraint $c(x) \in G$. The set $G$ is taken into account by the second condition (2.8b).

3) The condition (2.8c) is called the complementarity condition of problem ($P_G$), which therefore holds when $G \equiv K$ is a nonempty closed convex cone.

4) Problem ($P_{EI}$) can be written like problem ($P_G$) with the polyhedral cone $G \equiv K = \{0_{\mathbb{R}^{m_E}}\} \times \mathbb{R}_+^{m_I}$. Then, the optimality conditions have the form (2.8a) and (2.8c). Since $K^- = \mathbb{R}^{m_E} \times \mathbb{R}_+^{m_I}$, the complementarity condition (2.8c) only intervenes on the inequality constraints and reads $0 \le (\lambda_*)_I \perp c_I(x_*) \le 0$. One recovers the complementarity conditions of the KKT system (1.58). $\square$

A sibling of the sufficient optimality condition of the first order (SC1) of proposition 1.43 is given below. Like before, this SC1 does not require a constraint qualification. Recall also that the required convexity of $X_G$ is ensured by the convexity of the multifunction $x \mapsto c(x) - G$, see (2.2).

**Proposition 2.9 (SC1 for a convex ($P_G$))** Suppose that problem ($P_G$) is convex in the sense of the definition 2.1, that $f$ and $c$ are differentiable at $x_* \in X_G$, and that there exists a multiplier $\lambda_* \in \mathbb{F}$ such that $(x_*, \lambda_*)$ verifies the first order optimality conditions (2.8a)-(2.8b). Then, $x_*$ is a global solution to ($P_G$).
*Proof.* By proposition 1.28, since $f$ is a convex function and $X_G$ is a convex set, it suffices to show that

$$ \forall x \in X_G: \langle \nabla f(x_*), x - x_* \rangle \ge 0. $$

By the first optimality condition (2.8a), this amounts to show that

$$ \forall x \in X_G: \langle \lambda_*, c'(x_*)(x - x_*) \rangle \le 0. $$

By the second optimality condition (2.8b), $\lambda_* \in N_{c(x_*)}(G = (T_{c(x_*)} G)^{-})$, so that it suffices to show that

$$ \forall x \in X_G: c'(x_*)(x - x_*) \in T_{c(x_*)} G. $$

Now, by definition of the derivative

$$ c'(x_*)(x - x_*) = \lim_{t \downarrow 0} \frac{1}{t} [c(x_* + t(x - x_*)) - c(x_*)]. $$

For $t \in [0, 1]$, $c(x_* + t(x - x_*)) = c((1 - t)x_* + tx) \in G$ (since $x_*$ and $x$ are in the convex set $X_G$), so that the right-hand side is in the closure of $\mathbb{R}_+(G - c(x_*))$, which is $T_{c(x_*)} G$. $\square$

### 2.1.3 Robinson's Condition

It is not easy to verify that a given function $c$ is qualified to represent $X_G$ at $x \in X_G$, in the sense of definition 2.4. Like for the classical problems ($P_E$) and ($P_{EI}$), one knows sufficient conditions ensuring that qualification. The most famous of them (there are reasons for that) is the *Robinson condition* [119], which at $x_0 \in X_G$ reads

$$ (CQ-R) \qquad 0 \in \text{int}(c(x_0) + c'(x_0)\mathbb{E} - G). \qquad (2.10) $$

The goal of this section is to analyze and clarify this very rich condition. To arouse the curiosity of the reader, let us mention that (2.10) reduces to the Mangasarian-Fromovitz condition (CQ-MF) when the problem ($P_{EI}$) is viewed as a particular instance of problem ($P_G$); see exercise 2.1.4.

The condition (CQ-R) may look abstruse at first glance, but it is worth the effort to get familiar with it, since it is useful on several accounts. Its clarification and its application to the constraint qualification lie on the following important equivalence, which makes a link between (CQ-R) and the notion of metric regularity of the multifunction $x \in \mathbb{E} \to c(x) - G \subseteq \mathbb{F}$, associated with the constraint of ($P_G$). Recall the definition and notation (1.1) of the distance from a point to a set.
**Theorem 2.10 (Robinson qualification and metric regularity)** If c is continuously differentiable in a neighborhood of $x_0 \in X_G$, then the following properties are equivalent:

(i) the Robinson condition (CQ-R) holds at $x_0$,

(ii) there exists a constant $\mu \ge 0$, such that $\forall (x, y) \in \mathbb{E} \times \mathbb{F}$ near $(x_0, 0)$, the following inequality holds

$$ \mathrm{dist}(x, c^{-1}(G + y)) \le \mu \mathrm{dist}(c(x), G + y). \quad (2.11) $$

The meaning of the metric regularity property, given in the condition (ii) of the preceding theorem, is illustrated in figure 2.1: $G + y$ is a small perturbation (translation)

<figure><img src="image_9.png" /><figcaption>**Fig. 2.1.** Illustration of the notion of metric regularity for the set $X_G$.</figcaption></figure>

of the closed convex set $G$, $c^{-1}(G + y)$ is then a small perturbation of the possibly nonconvex feasible set $c^{-1}(G)$, and the distance from $x$ to the latter is estimated by means of the distance from $c(x)$ to the former. Practically, this estimate may be interesting, since $\mathrm{dist}(c(x), G + y)$ (a distance to a convex set) is usually more easily computed than $\mathrm{dist}(x, c^{-1}(G + y))$ (a distance to a possibly weird set).

Before giving a proof of this important theorem, which is long and complex, we start by giving two of its straightforward corollaries. This is a way of getting familiar with its meaning.

The first corollary gives an error bound for $X_G$. An error bound is an estimate of the distance to a set by a quantity more easily computable (numerically or analytically). In general, $X_G$ is a set that is more “complex” than $G$, if only because $G$ is convex, which may not the case of $X_G = c^{-1}(G)$, which can be tortuous through the action of the arbitrary function $c$. The error bound of Robinson (2.12) below gives an estimate of the distance $\mathrm{dist}(x, X_G)$, which may be difficult to compute, by the much simple distance $\mathrm{dist}(c(x), G)$.

**Corollary 2.11 (Robinson's error bound for $X_G$)** If c is continuously differentiable in a neighborhood of $x_0 \in X_G$ and if Robinson's constraint qualification (CQ-R) holds at $x_0$, then, there exists a constant $\mu \ge 0$, such that, for all $x$
near $x_0$, the following inequality holds

$$ \mathrm{dist}(x, X_G) \le \mu \mathrm{dist}(c(x), G). \qquad (2.12) $$

*Proof.* Just take $y = 0$ in (2.11) and use the fact that $X_G = c^{-1}(G)$. $\square$

Robinson's error bound (2.12) will play a major part in the proof of the fact that (CQ-R) is a sufficient condition of constraint qualification (proposition 2.21).

The inequalities (2.11) of theorem 2.10 form a family of error bounds for the sets $c^{-1}(G + y)$, with $y$ small enough, which are small perturbations of $X_G$. Theorem 2.10 claims that this family of error bounds is an equivalent condition to (CQ-R), while its corollary 2.11 tells us that the single error bound (2.12) is a consequence of (CQ-R).

The distance to an empty set is infinite (see the remark after (1.1)). Since the distance in the right-hand side of (2.11) is finite ($G$ is nonempty), the one in the left-hand side is also finite. This means that $c^{-1}(G + y)$ is nonempty for small perturbations $y$ of $G$. It is this stability result for small perturbations that is claimed in the second corollary. The comments in this paragraph serve as its proof.

**Corollary 2.12 (stability of $X_G$ for small perturbations)** If $c$ is continuously differentiable in a neighborhood of $x_0 \in X_G$ and if Robinson's constraint qualification (CQ-R) holds at $x_0$, then, for any perturbation $y \in \mathbb{F}$ close to 0, the following holds

$$ \{x \in \mathbb{R} : c(x) \in G + y\} \neq \emptyset. \qquad (2.13) $$

Remark that (2.13) makes no reference to the point $x_0$, which can therefore be an arbitrary point in $X_G$ satisfying (CQ-R). Exercise 2.1.4 tells us that, for ($P_{EI}$), (CQ-R) is equivalent to (CQ-MF), so that the following example shows that the reciprocal of the claim of corollary 2.12 is false: stability does not imply (CQ-R). Consider indeed the following set

$$ \{x \in \mathbb{R}^2 : -x_1^3 \le x_2 \le x_1^3\}. $$

<figure><img src="image_10.png" /></figure>

This one reads $\{x \in \mathbb{R}^2 : c(x) \in G\}$ with $c: \mathbb{R}^2 \to \mathbb{R}^2 : (x_1, x_2) \mapsto (-x_1^3 + x_2, -x_1^3 - x_2)$ and $G = \mathbb{R}^2$. It is nonempty, whatever the translation $y$ of $G$ is, while (CQ-MF) does not hold at $x = 0$ (because the gradients of the constraints $\nabla c_1(0)$ and $\nabla c_2(0)$ are collinear and opposite).

The rest of this section is entirely dedicated to the proof of theorem 2.10, whose generality suggests its strength, but also augurs the difficulty of its analysis. The hurried reader or the reader not interested in the proof can go directly to the following section 2.1.4. This one only uses from this section the corollary 2.11.
The proof of theorem 2.10, which will be given on page 70, is the consequence of two interpretations and two main results (theorem 2.15 and proposition 2.19). The analysis uses the multifunction toolbox. The following two multifunctions will play a major part:

$$T: \mathbb{E} \to \mathbb{F}: x \mapsto T(x) := c(x) - G, \qquad (2.14a)$$

$$T_0: \mathbb{E} \to \mathbb{F}: x \mapsto T_0(x) := c(x_0) + c'(x_0) \cdot (x - x_0) - G. \qquad (2.14b)$$

The multifunction $T$ was already used in (2.2) to provide a sufficient condition ensuring the convexity of the feasible set $X_G = T^{-1}(0)$, while $T_0$ is a kind of linearization of $T$ at $x_0$, in which only $c$ is linearized, not $G$. One can now give the scheme of the proof of theorem 2.10.

1. First interpretation. Since the range of $T_0$ is $c(x_0) + c'(x_0)\mathbb{E} - G$, Robinson's condition (CQ-R) at $x_0$ reads

$$0 \in \text{int} \mathcal{R}(T_0).$$

This justifies the introduction of $T_0$.

2. First result. For a convex multifunction, like $T_0$ (but not $T$!), this last condition turns out to be equivalent to the metric regularity of $T_0$ at $(x_0, 0) \in \mathcal{G}(T_0)$ ( theorem 2.15). This means that there exists a constant $\mu_0 \ge 0$ such that, for all $(x, y)$ near $(x_0, 0)$, the following inequality holds

$$\text{dist}(x, T_0^{-1}(y)) \le \mu_0 \text{dist}(y, T_0(x)).$$

This notion is clarified below, after its definition 2.14.

3. Second result. When $x$ is close to $x_0$, $T$ is “close” to $T_0$ near $x_0$ (and reciprocally), in a sense that will be made precise below. Then, one uses the fact that the metric regularity of $T_0$ is “diffused” to $T$ (proposition 2.19): there exists a constant $\mu \ge 0$ such that, for $(x, y)$ near $(x_0, 0)$, the following inequality holds

$$\text{dist}(x, T^{-1}(y)) \le \mu \text{dist}(y, T(x)).$$

4. Second interpretation. To get (2.11), it suffices now to observe that

$$T^{-1}(y) = c^{-1}(G + y) \quad \text{and} \quad \text{dist}(y, T(x)) = \text{dist}(c(x), G + y).$$

The first identity results from the equivalences $x' \in T^{-1}(y) \Leftrightarrow y \in T(x') = c(x') - G \Leftrightarrow c(x') \in G + y \Leftrightarrow x' \in c^{-1}(G + y)$; while the second identity comes from $\text{dist}(y, T(x)) = \text{dist}(y, c(x) - G) = \text{dist}(c(x), G + y)$.

This proof scheme will be resumed in the proof of theorem 2.10 at the end of the section (on page 70). Let us now establish the results that will allow us to implement it.

We start by giving expressions that are equivalent to the fact that a point $y_0$ is interior to the range of a convex multifunction. As explained in the proof scheme aforementioned (see its steps 1 and 2), this result will be applied to the multifunction $T_0$ defined in (2.14b), not to $T$ defined in (2.14a), which is generally nonconvex. We shall need the two important multifunction properties described by the definitions 2.13 and 2.14 below.
**Definition 2.13 (open multifunction)** A multifunction $T: \mathbb{E} \to \mathbb{F}$ is said to be open at $(x_0, y_0) \in \mathcal{G}(T)$ with ratio $\rho > 0$, if there exists a neighborhood $W$ of $(x_0, y_0)$ and a maximal radius $r_{\max} > 0$, such that, for all $(x, y) \in W \cap \mathcal{G}(T)$ and all $r \in [0, r_{\max}]$, the following holds

$$y + \rho r \bar{B}_{\mathbb{F}} \subseteq T(x + r \bar{B}_{\mathbb{E}}). \qquad (2.15)$$

The ratio $\rho$ is the quotient between the radius of the ball $y + \rho r \bar{B}_{\mathbb{F}}$ of $\mathbb{F}$ that can be inscribed in the image $T(x + r \bar{B}_{\mathbb{E}})$ and the radius $r$. $\square$

By taking $r = 0$ in the inclusion (2.15), it appears that $(x, y)$ must necessarily belong to the graph of $T$, and this fact is indeed assumed in the definition.

The picture in the left-hand side of figure 2.2 illustrates the notion of open multifunction.

<figure><img src="image_11.png" /><figcaption>**Fig. 2.2.** Illustration of the notions of open multifunction of ratio $\rho$ (left) and of metric regularity of modulus $\mu$ (right): both notions describe the variation of $T(x)$ with $x$; the openness property makes this description from inside the graph, the metric regularity property makes it from outside; these are not infinitesimal concepts.</figcaption></figure>

One can see the balls centered at $y$ in $T(x + r\bar{B}_{\mathbb{E}})$ and $T(x + 2r\bar{B}_{\mathbb{E}})$, for a certain radius $r > 0$ (they are translated for giving more visibility). The increase rate of the radius of these balls with $r$ provides the ratio $\rho$. This ratio is not an infinitesimal notion. Thus, it does not provide the infinitesimal variation of the size of $T(x + r\bar{B}_{\mathbb{E}})$ with $r$, at $r = 0$, but provides an approximation of this variation from inside the graph of $T$ (the pairs $(x, y)$ belong to this graph).

Whilst the openness of $T$ describes the variation of $T(x)$ with $x$, from inside the graph $\mathcal{G}(T)$, the metric regularity defined below provides a similar description, but from outside that graph.

**Definition 2.14 (metric regular multifunction)** A multifunction $T: \mathbb{E} \to \mathbb{F}$ is said to be *metric regular* at $(x_0, y_0) \in \mathcal{G}(T)$ of modulus $\mu > 0$, if for all $(x, y)$ near $(x_0, y_0)$, the following inequality holds

$$\mathrm{dist}(x, T^{-1}(y)) \le \mu \mathrm{dist}(y, T(x)). \qquad (2.16)$$

This inequality assumes that $\mathrm{dist}(\cdot, \emptyset) = +\infty$. $\square$

The picture in the right-hand side of figure 2.2 illustrates the notion of *metric regularity* and its link with the notion of open multifunction. Note first that, to have an estimate (2.16) bringing information, it is necessary to have $(x, y)$ outside the
graph $\mathcal{G}(T)$ (otherwise $y \in T(x)$, $y \in T^{-1}(y)$), and the two distances in (2.16) vanish), hence not to have $(x_0, y_0)$ in the interior of that graph, but on its boundary, like in the picture. We see that the modulus $\text{dist}(y, T(x))/\text{dist}(x, T^{-1}(y)) \simeq 1/\mu$ has a meaning that is similar to the ratio $\rho$ in the left-hand side picture.

Note that (2.15) and (2.16) contain existence results. Indeed, when (2.15) holds and $y' \in y + \rho r \bar{B}_E$, then, there exists an $x' \in x + r \bar{B}_E$ such that $y' \in T(x')$: hence, the inclusion problem “given $y'$, find an $x'$ such that $y' \in T(x')$” has a solution. Similarly, when (2.16) holds, $\text{dist}(x, T^{-1}(y))$ is finite (because $\text{dist}(y, T(x))$ is always finite), which means that $T^{-1}(y) \neq \emptyset$ or that there exists an $x'$ such that $y \in T(x')$. In the proof of the theorem below, we use these openness and metric regularity properties in that manner.

**Theorem 2.15 (open multifunction)** Let $\bar{B}_E$ and $\bar{B}_F$ be the closed unit balls of $E$ and $F$ respectively, $T: E \to F$ be a convex multifunction, and $(x_0, y_0) \in \mathcal{G}(T)$. Then, the following properties are equivalent:

(i) $y_0 \in \text{int} \mathcal{R}(T)$,

(ii) for any $r > 0$, one has $y_0 \in \text{int} T(x_0 + r \bar{B}_E)$,

(iii) $T$ is open at $(x_0, y_0)$ with some ratio $\rho > 0$,

(iv) $T$ is *metric regular* at $(x_0, y_0)$ with some modulus $\mu > 0$.

One can take $\mu = 1/\rho$ in point (iv) if $\rho$ is given by point (iii).

Before proving this theorem, let us make some remarks on its assumptions and its meaning.

* The open multifunction theorem above generalizes to convex multifunctions, which is a nonlinear object, the open mapping theorem on linear continuous maps, which is a basic tool in functional analysis [24]. This latter result is proposed in the exercise 2.1.2 as an equivalence between three claims (i)-(iii) (its proof in finite dimension is easy). Its claim (i) is comparable to point (i) above; its point (ii) is similar to point (ii) and (iii) above and it point (iii) is related to point (iv) above.

* The convexity of $T$ cannot be discarded without loosing the implications (i) $\Rightarrow$ (ii) and (i) $\Rightarrow$ (iii). Indeed, for the nonconvex multifunction $T$, whose graph is given in the figure below, $y_0 \in \text{int} \mathcal{R}(T)$, but $y_0 \notin \text{int} T(x_0 + r \bar{B}_E)$ for small $r > 0$;

<figure><img src="image_12.png" /></figure>

furthermore, $T$ is not open at $(x_0, y_0)$, since $T(x_0 + r \bar{B}_E)$ does not contain any ball in $F$ centered at $y_0$.

* By its equivalence (i) $\Leftrightarrow$ (iv), the theorem allows us to translate (CQ-R) in a metric regularity property, which is what we wanted to do, but the equivalence is limited to convex multifunctions for the while.
* The equivalence between points (iii) and (iv) makes explicit the link between open multifunction and metric regularity, in a rigorous manner. Thus, a large value of $\rho$ testifies a fast variation of $T(x)$ with $x$, while a large value of $\mu$ expresses a slow variation of $T(x)$ with $x$.

*Proof of proposition 2.15.* $[(i) \Rightarrow (ii)]$ Let $r > 0$. By the convexity of $T$ and (1.45), $T(x_0 + r\bar{B}_E)$ is convex. Then, it suffices to show that $y_0$ is absorbing for $T(x_0 + r\bar{B}_E)$; see (1.14). Let $p \in \mathbb{F}$. Since $y_0 \in \text{int } \mathcal{R}(T)$, one can find an $\alpha > 0$ such that $y_0 + \alpha p \in \mathcal{R}(T)$. This implies that there exists $d_\alpha \in \mathbb{E}$ such that

$$y_0 + \alpha p \in T(x_0 + d_\alpha).$$

This $d_\alpha$ is not necessarily in $r\bar{B}_E$. By the convexity of $T$, one can scale $\alpha p$ and $d_\alpha$ in the same proportion. Indeed, because $y_0 \in T(x_0)$, we also have for all $t \in [0, 1]$ (see exercise ??):

$$(1-t)y_0 + t(y_0 + \alpha p) \in T((1-t)x_0 + t(x_0 + d_\alpha)).$$

Hence, $y_0 + t\alpha p \in T(x_0 + td_\alpha) \subseteq T(x_0 + r\bar{B}_E)$, for $t > 0$ small enough.

[(ii) ⇒ (iii)] By (ii), there exist radiuses $\alpha > 0$ and $\beta > 0$ such that

$$y_0 + \beta \bar{B}_F \subseteq T(x_0 + \alpha \bar{B}_E). \qquad (2.17)$$

The question now is to know whether such an inclusion is maintained for pairs $(x, y) \in \mathcal{G}(T)$ near $(x_0, y_0)$ and for variable radiuses. Let us show that one can take

$$\left\{ \begin{array}{l} W = (x_0 + \alpha \bar{B}_E) \times (y_0 + \frac{\beta}{2} \bar{B}_F) \\ \rho = \frac{\beta}{4\alpha} \\ r_{\max} = 2\alpha. \end{array} \right.$$

<figure><img src="image_13.png" /></figure>

Indeed, let $(x, y) \in W \cap \mathcal{G}(T)$. Observe that, by the definition of $W$ and (2.17):

$$y + \frac{\beta}{2} \bar{B}_F \subseteq y_0 + \beta \bar{B}_F \subseteq T(x_0 + \alpha \bar{B}_E). \qquad (2.18)$$

Then, for any $t \in [0, 1]$, there holds

$$\begin{aligned} y + t \frac{\beta}{2} \bar{B}_F &= (1-t)y + t(y + \frac{\beta}{2} \bar{B}_F) \\ &\subseteq T((1-t)x + t(x_0 + \alpha \bar{B}_E)) \quad [T \text{ convex, } y \in T(x), (2.18)] \\ &= T(x + t((x_0 - x) + \alpha \bar{B}_E)) \\ &\subseteq T(x + 2t\alpha \bar{B}_E) \quad [x_0 \in x + \alpha \bar{B}_E]. \end{aligned}$$

Making the change of variable $t \rightsquigarrow r = 2t\alpha$, which is indeed in $[0, r_{\max}]$, we get the desired inclusion since then $t\beta/2 = r\beta/(4\alpha) = \rho r$.

[(iii) ⇒ (iv)] One can assume that the neighborhood $W$ of $(x_0, y_0)$ and the maximal radius $r_{\max}$ of the definition 2.13 satisfy

$$W := (x_0, y_0) + \varepsilon(\bar{B}_E \times \bar{B}_F) \quad \text{and} \quad r_{\max} \le \frac{\varepsilon}{2\rho}, \qquad (2.19)$$
for some $\varepsilon > 0$. Let us show that the metric regularity holds at $(x_0, y_0)$ with the module $\mu = 1/\rho$ in the neighborhood $W'$ of $(x_0, y_0)$ defined as follows

$$W' = (x_0, y_0) + \varepsilon'(\bar{B}_{\mathbb{E}} \times \bar{B}_{\mathbb{F}}), \quad \text{with } \varepsilon' \le \min \left( \varepsilon, \frac{\rho r_{\max}}{1 + \rho} \right). \qquad (2.20)$$

Clearly $W' \subseteq W$, since $\varepsilon' \le \varepsilon$. Let $(x, y) \in W'$. It suffices to show that the inequality (2.16) holds with $\mu = 1/\rho$ for this pair $(x, y)$. We consider two complementary cases, illustrated in figure 2.3.

<figure><img src="image_14.png" /><figcaption>Fig. 2.3. Illustration of the proof of the implication (iii) ⇒ (iv) of theorem 2.15: (2.15) is applied at $(x_0, y_0)$ in the left-hand side picture (case 1) and at $(x, y_\delta)$ in the right-hand side picture (case 2).</figcaption></figure>

First case, which works when $y$ is far enough from $T(x)$ in the sense that

$$\mathrm{dist}(y, T(x)) \ge (1 + \rho)\varepsilon'. \qquad (2.21)$$

One can apply (2.15) at $(x_0, y_0) \in \mathcal{G}(T) \cap W$ (red circle in the left-hand-side picture in figure 2.3), which yields

$$\forall r \in [0, r_{\max}]: \quad y_0 + \rho r \bar{B}_{\mathbb{F}} \subseteq T(x_0 + r \bar{B}_{\mathbb{E}}). \qquad (2.22)$$

Note that $y \in y_0 + \rho r \bar{B}_{\mathbb{F}}$, since $\|y - y_0\| \le \varepsilon' \le \rho r_{\max} ((x, y) \in W'$ and $\varepsilon' \le \rho r_{\max}$ by (2.20)). One can also write

$$y = y_0 + \rho \underbrace{\frac{\|y - y_0\|}{\rho}}_{:=r} \underbrace{\begin{cases} \frac{y-y_0}{\|y-y_0\|} & \text{if } y \ne y_0 \\ 0 & \text{otherwise,} \end{cases}}_{\in \bar{B}_{\mathbb{F}}}$$

which shows that $y \in y_0 + \rho r \bar{B}_{\mathbb{F}}$ with $r := \|y - y_0\|/\rho \le \varepsilon'/\rho \le r_{\max}$. Therefore, by (2.22), there exists a point $x' \in x_0 + r \bar{B}_{\mathbb{E}}$ such that $y = T(x')$. We can now estimate the distance $\mathrm{dist}(x, T^{-1}(y))$ as follows

$$\begin{align*}
\mathrm{dist}(x, T^{-1}(y)) &\le \|x - x'\| \quad [x' \in T^{-1}(y)] \\
&\le \|x - x_0\| + \|x_0 - x'\| \quad \text{[triangular inequality]} \\
&\le \|x - x_0\| + \frac{1}{\rho}\|y - y_0\| \quad [\|x' - x_0\| \le r = \|y - y_0\|/\rho] \\
&\le \varepsilon' + \frac{1}{\rho}\varepsilon' \quad \text{[choice of $x$ and $y$].} \\
&\le \frac{1}{\rho}\mathrm{dist}(y, T(x)) \quad [(2.21)],
\end{align*}$$
which is the desired inequality when $\mu = 1/\rho$.

Second case, which works when $y$ is close enough to $T(x)$ in the sense that

$$ \mathrm{dist}(y, T(x)) < (1 + \rho)\varepsilon'. \qquad (2.23) $$

Then, for any $\delta > 0$ sufficiently small, one can find $y_\delta \in T(x)$ such that

$$ \|y - y_\delta\| \le \mathrm{dist}(y, T(x)) + \delta \quad [\text{definition of the distance}] \quad (2.24) $$

$$ \le (1 + \rho)\varepsilon' \quad [(2.23) \text{ and } \delta > 0 \text{ small}] \qquad (2.25) $$

$$ \le \rho r_{\max} \quad [(2.20)] \qquad (2.25) $$

$$ \le \frac{\varepsilon}{2} \quad [(2.19)]. \qquad (2.26) $$

One can apply (2.15) at $(x, y_\delta)$ (red circle in the right-hand-side picture in figure 2.3), since $(x, y_\delta) \in W \cap G(T)$. Indeed, $(x, y_\delta) \in G(T)$ by construction of $y_\delta \in T(x)$. Next, $\|x - x_0\| \le \varepsilon' \le \varepsilon$, by $(x, y) \in W'$ and (2.20). Finally,

$$ \|y_\delta - y_0\| \le \|y_\delta - y\| + \|y - y_0\| \le \frac{1}{2}\varepsilon + \frac{1}{2}\varepsilon = \varepsilon, $$

where the last inequality comes from (2.26) and from $\|y - y_0\| \le \varepsilon' \le \rho r_{\max} \le \varepsilon/2$ (because $(x, y) \in W'$ and by (2.20) and (2.19)).

The application of (2.15) at $(x, y_\delta)$ (red circle in the right-hand-side picture in figure 2.3) yields

$$ \forall r \in [0, r_{\max}] : \quad y_{\delta} + \rho r \bar{B}_{\mathbb{F}} \subseteq T(x + r \bar{B}_{\mathbb{E}}). \qquad (2.27) $$

Like in the first case, one can also write

$$ y = y_{\delta} + \rho \underbrace{\frac{\|y - y_{\delta}\|}{\rho}}_{=:r} \underbrace{\left\{ \begin{array}{ll} \frac{y - y_{\delta}}{\|y - y_{\delta}\|} & \text{if } y \neq y_{\delta} \\ 0 & \text{otherwise,} \end{array} \right.}_{\in \bar{B}_{\mathbb{F}}} $$

which shows that $y \in y_\delta + \rho r \bar{B}_\mathbb{F}$ with $r := \|y - y_\delta\|/\rho \le r_{\max}$ by (2.25). Therefore, by (2.27), there exists a point $x'' \in x + r \bar{B}_\mathbb{E}$ such that $y = T(x'')$. This point $x''$ allows us to have the following estimation of the distance $\mathrm{dist}(x, T^{-1}(y)):

$$ \begin{aligned} \mathrm{dist}(x, T^{-1}(y)) &\le \|x - x''\| \quad [x'' \in T^{-1}(y)] \\ &\le \frac{1}{\rho} \|y - y_\delta\| \quad [x'' \in x + r \bar{B}_\mathbb{E} \text{ with } r = \|y - y_\delta\|/\rho] \\ &\le \frac{1}{\rho} (\mathrm{dist}(y, T(x)) + \delta) \quad [(2.24)]. \end{aligned} $$

Since $\delta > 0$ can be taken arbitrarily small, one deduces the desired inequality when $\mu = 1/\rho$.

[(iv) ⇒ (i)] Let us show the contrapositive. If $y_0 \notin \mathrm{int}\,\mathcal{R}(T)$, one can find a $y \notin \mathcal{R}(T)$ as close as desired to $y_0$. For such a $y$, $T^{-1}(y)$ is empty, implying that $\mathrm{dist}(x_0, T^{-1}(y)) = +\infty$, so that the inequality (2.16) cannot hold for $y$ close to $y_0$, since this one would imply that $T(x_0) = \emptyset$, which is in contradiction with the fact that $(x_0, y_0) \in \mathcal{G}(T)$. □
The goal of property 2.19 below is to show that the metric regularity property can “diffuse” from one multifunction to another one close to it, at least for particular forms of multifunctions and perturbations, those in which we are interested in, namely $T$ and $T_0$ in (2.14). We mean by this that, under certain conditions expressing the proximity of $T$ and $T_0$, if $T_0$ is metric regular, $T$ is also metric regular. It is that property that allows us to have the metric regularity of $T$ from that of $T_0$, and reciprocally. The result does not require the convexity of the multifunctions under consideration.

The idea of the proposed proof (there are other possibilities) derives from the following change in perspective [35]. The metric regularity gives an upper bound of $\text{dist}(x, T^{-1}(y))$. Observe that

$$x \in T^{-1}(y) \iff y \in T(x) \iff \text{dist}(y, T(x)) = 0,$$

where the last equivalence assumes that $T(x)$ is closed (this assumption is verified if the multifunction $T$ is given by (2.14a) and $G$ is closed). Let us introduce the function $\varphi_y : \mathbb{E} \to \mathbb{R}_+$ defined at $x \in \mathbb{E}$ by

$$\varphi_y(x) := \mu \text{dist}(y, T(x)), \qquad (2.28)$$

with $\mu > 0$. We see now that

$$T^{-1}(y) \text{ is the set of the zeros of } \varphi_y. \qquad (2.29)$$

The metric regularity property can then be expressed as follows:

$$\forall (x, y) \text{ near } (x_0, y_0) : \quad \varphi_y \text{ has a zero in } \bar{B}(x, \varphi_y(x)), \qquad (2.30)$$

where $\bar{B}(x, r)$ is the closed ball centered at $x$ with radius $r$.

This viewpoint suggests us to look at conditions ensuring that a function with values in $\mathbb{R}_+$ has a zero that is not too far from a given point $x$. We do this by using two function properties and one lemma.

**Definition 2.16 (subcontinuous function)** A function $\varphi : \mathbb{E} \to \mathbb{R}_+$ is subcontinuous if, for all sequence $\{x_k\} \to x$ such that $\varphi(x_k) \to 0$, one has $\varphi(x) = 0$. $\square$

A continuous function is clearly subcontinuous.

**Definition 2.17 (r-steep function)** A function $\varphi : \mathbb{E} \to \mathbb{R}_+$ is r-steep at $x$, with $r \in [0, 1)$, if

$$\forall x' \in \bar{B}\left(x, \frac{\varphi(x)}{1-r}\right), \quad \exists x'' \in \bar{B}\left(x', \varphi(x')\right) : \quad \varphi(x'') \le r \varphi(x'). \qquad \square$$

One can express this property as follows: for each point $x'$ in the ball $\bar{B}(x, \varphi(x)/(1-r))$, one can find another point $x''$, not too far from $x'$ ($x'' \in \bar{B}(x', \varphi(x'))$), at which $\varphi$ decreases significantly ($\varphi(x'') \le r \varphi(x')$). Note that, assuming $\varphi(x') \ne 0$,

$$\frac{\varphi(x') - \varphi(x'')}{\|x' - x''\|} \ge \frac{\varphi(x') - r\varphi(x')}{\varphi(x')} = 1 - r,$$
which provides a guarantee on the decrease of $\varphi$.

As shown by the next lemma, a function having the two preceding properties has a zero that is not too far from the point at which it is r-steep.

**Lemma 2.18 (Lyusternik)** If $\varphi : \mathbb{E} \to \bar{\mathbb{R}}_+$ is subcontinuous and r-steep at $x \in \text{dom } \varphi$, with $r \in [0, 1)$, then, $\varphi$ has a zero in $\bar{B}(x, \varphi(x)/(1-r))$.

*Proof.* Let us construct a sequence $\{x_k\}_{k \ge 0} \subseteq \mathbb{E}$ with the following properties:

$$ \text{dist}(x_{k+1}, x_k) \le \varphi(x_k) \quad \text{and} \quad 0 \le \varphi(x_{k+1}) \le r\varphi(x_k). \quad (2.31) $$

Take $x_0 = x$. Now, suppose that $x_0, \dots, x_k$ have been determined and let us show how to compute $x_{k+1}$. Thanks to the properties (2.31), one has

$$ \text{dist}(x_k, x) \le \sum_{i=0}^{k-1} \text{dist}(x_{i+1}, x_i) \le \sum_{i=0}^{k-1} \varphi(x_i) \le \left( \sum_{i=0}^{k-1} r^i \right) \varphi(x) \le \frac{\varphi(x)}{1-r}. \quad (2.32) $$

Since $\varphi$ is r-steep at $x$, one can find $x_{k+1} \in \mathbb{E}$ such that (2.31) holds.

The sequence $\{x_k\}$ is a Cauchy sequence, since $\text{dist}(x_{k+1}, x_k) \le r^k \varphi(x)$, by (2.31). Therefore, for positive integers $p < q$, there holds

$$ \text{dist}(x_q, x_p) \le \left( \sum_{k=p}^{q} r^k \right) \varphi(x), $$

where the factor of $\varphi(x)$ in the right-hand side tends to zero when $p$ and $q \to \infty$. As a result, the sequence $\{x_k\}$ converges: $x_k \to x \in \bar{B}(x, \varphi(x)/(1-r))$ by (2.32). Furthermore, taking the limit in $\varphi(x_{k+1}) \le r\varphi(x_k)$ shows that $\varphi(x_k) \to 0$. The subcontinuity of $\varphi$ now implies that $\varphi(x) = 0$. $\square$

If $c$ is continuous and if the multifunction $T$ is metric regular, then, the function $\varphi_y$ defined by (2.28) is subcontinuous and 0-steep:

* it is even continuous since $x \mapsto \text{dist}(y, T(x)) = \text{dist}(y, c(x) - G) = \text{dist}(c(x) - y, G)$ is the composition of the continuous functions $x \mapsto c(x) - y$ and $\text{dist}(\cdot, G)$,

* it is 0-steep by the expression (2.30) of the metric regularity.

It looks now reasonable to think that these two properties are maintained for a small perturbation of $T$. It is the underlying idea of the proof of the next proposition.

**Proposition 2.19 (metric regularity diffusion)** let $c : \mathbb{E} \to \mathbb{F}$ be a continuous function, $\delta : \mathbb{E} \to \mathbb{F}$ be a Lipschitz continuous function of modulus $L > 0$ in a neighborhood of a point $x_0 \in \mathbb{E}$, and $G$ be a nonempty convex set of $\mathbb{F}$. If the multifunction

$$ T : \mathbb{E} \to \mathbb{F} : x \mapsto c(x) - G $$
is metric regular at $(x_0, y_0) \in \mathcal{G}(T)$ with modulus $\mu < 1/L$, then the multifunction

$$ \tilde{T} : \mathbb{E} \to \mathbb{F} : x \mapsto c(x) + \delta(x) - G $$

is metric regular at $(x_0, y_0 + \delta(x_0)) \in \mathcal{G}(\tilde{T})$ with modulus $\mu/(1 - L\mu)$, i.e., for all $(x, y)$ near $(x_0, y_0 + \delta(x_0))$, the following inequality holds

$$ \mathrm{dist}(x, \tilde{T}^{-1}(y)) \le \frac{\mu}{1 - L\mu} \mathrm{dist}(y, \tilde{T}(x)). \quad (2.33) $$

*Proof.* One can suppose that $\delta(x_0) = 0$ since the metric regularity is invariant with respect to translation of the graph $\mathcal{G}(T)$ in $\mathbb{E} \times \mathbb{F}$. The effects of the continuity are better seen if the function $c$ in $T$ is made visible. One gets, for all $(x, y) \in \mathbb{E} \times \mathbb{F}$:

$$ T^{-1}(y) = c^{-1}(G + y), \qquad \tilde{T}^{-1}(y) = \tilde{c}^{-1}(G + y), \quad (2.34a) $$

$$ \mathrm{dist}(y, T(x)) = \mathrm{dist}(c(x), G + y), \qquad \mathrm{dist}(y, \tilde{T}(x)) = \mathrm{dist}(\tilde{c}(x), G + y). \quad (2.34b) $$

The identity (2.34a) comes from the equivalences $x \in T^{-1}(y) \Leftrightarrow y \in T(x) \Leftrightarrow y \in c(x) - G \Leftrightarrow c(x) \in G + y \Leftrightarrow x \in c^{-1}(G + y)$. The identity (2.34b) can be obtained by $\mathrm{dist}(y, T(x)) = \mathrm{dist}(y, c(x) - G) = \mathrm{dist}(c(x), G + y)$.

1) Consider the map

$$ \tilde{\varphi}_y : x \in \mathbb{E} \mapsto \tilde{\varphi}_y(x) := \mu \mathrm{dist}(y, \tilde{T}(x)), \quad (2.35) $$

which can be compared to the one introduces in (2.28). Let us show the it suffices to prove the next claim, in which $r := L\mu < 1$:

$$ \exists U \in \mathcal{N}(x_0), \exists V \in \mathcal{N}(y_0), \forall (x, y) \in U \times V, \qquad (2.36) \\ \tilde{\varphi}_y \text{ is subcontinuous on } \mathbb{E} \text{ and } r\text{-steep at } x. $$

Indeed, by Lyusternik's lemma (lemma 2.18), $\tilde{\varphi}_y$ has then a zero in the ball $\bar{B}(x, \tilde{\varphi}_y(x)/(1-r))$. Yet, the zet of zeros of $\tilde{\varphi}_y$ is $\tilde{T}^{-1}(y)$ (by the smae reasoning as the one yielding (2.29); it is here that we use the closure of $G$). As a result, for all $(x, y) \in U \times V$, one gets (2.33):

$$ \mathrm{dist}(x, \tilde{T}^{-1}(y)) \le \frac{\tilde{\varphi}_y(x)}{1-r} = \frac{\mu}{1-L\mu} \mathrm{dist}(y, \tilde{T}(x)). $$

2) It remains to prove (2.36).

By the continuity of $c$ and the continuity of the distance to a convex set, one sees that $\tilde{\varphi}_y$ is continuous on $\mathbb{E}$, hence subcontinuous on $\mathbb{E}$.

Let us now determine the neighborhoods $U$ of $x_0$ and $V$ of $y_0$ such that, for all $(x, y) \in U \times V$, $\tilde{\varphi}_y$ is $r$-steep at $x$.

* By the $\mu$-metric regularity of $T$ at $(x_0, y_0)$ and by (2.34), one can find the neighborhoods $U_1$ of $x_0$ and $V_1$ of $y_0$ such that, for all $(x, y) \in U_1 \times V_1$, there holds

$$ \mathrm{dist}(x, c^{-1}(G + y)) \le \mu \mathrm{dist}(c(x), G + y). \quad (2.37a) $$
* One can also find the neighborhoods $U_2 \subseteq U_1$ of $x_0$ and $V_2 \subseteq V_1$ of $y_0$ such that, for all $(x, y) \in U_2 \times V_2$, there holds

$$ \bar{B}(x, \mu \operatorname{dist}(\tilde{c}(x), G + y)) \subseteq U_1 \quad \text{and} \quad y - \delta(x) \in V_1. \quad (2.37b) $$

The inclusion in $U_1$ comes from the continuity of $(x, y) \mapsto \operatorname{dist}(\tilde{c}(x), G + y)$ and its vanishment at $(x_0, y_0) \in G(T)$; the belonging in $V_1$ comes from the continuity of the map $(x, y) \mapsto y - \delta(x)$ and its value $y_0$ at $(x_0, y_0)$.

* Finalement, one takes neighborhoods $U \subseteq U_2$ of $x_0$ and $V \subseteq V_2$ of $y_0$ such that, for all $(x, y) \in U \times V$, there holds

$$ \bar{B}\left(x, \frac{\mu}{1-r} \operatorname{dist}(\tilde{c}(x), G+y)\right) \subseteq U_2. \quad (2.37c) $$

This is again possible by continuity and vanishment of $\operatorname{dist}(\tilde{c}(x), G + y)$ at $(x, y) = (x_0, y_0)$ (like above).

Let us show that, for all $(x, y) \in U \times V$, $\tilde{\varphi}_y$ is $r$-steep at $x$. Let us fix $(x, y) \in U \times V$. Let $x' \in \bar{B}(x, \tilde{\varphi}_y(x)/(1-r))$. One must now find $x'' \in \bar{B}(x', \tilde{\varphi}_y(x'))$ such that $\tilde{\varphi}_y(x'') \le r\tilde{\varphi}_y(x')$.

* Since $x' \in \bar{B}(x, \tilde{\varphi}_y(x)/(1-r))$, the definition (2.35) of $\tilde{\varphi}_y$ and (2.37c) show that $x' \in U_2$.

* Since $y \in V \subseteq V_2$, one can apply (2.37b) at $(x, y) \dashv (x', y)$, which yields

$$ \bar{B}(x', \mu \operatorname{dist}(\tilde{c}(x'), G + y)) \subseteq U_1 \quad \text{and} \quad y' := y - \delta(x') \in V_1. \quad (2.38) $$

* One can therefore use (2.37a) at $(x, y) \dashv (x', y')$, which yields

$$ \operatorname{dist}(x', c^{-1}(y' + G)) \le \mu \operatorname{dist}(c(x'), y' + G). $$

Since $c^{-1}(y' + G)$ is closed, this implies that there exists

$$ x'' \in c^{-1}(y' + G) \quad (2.39) $$

such that

$$ \begin{aligned} \operatorname{dist}(x', x'') &\le \mu \operatorname{dist}(c(x'), y' + G) \\ &= \mu \operatorname{dist}(c(x'), y - \delta(x') + G) \quad [y' = y - \delta(x') \text{ by (2.38)}] \\ &= \mu \operatorname{dist}(\tilde{c}(x'), G + y) \quad [\tilde{c} = c + \delta] \\ &= \mu \operatorname{dist}(y, \tilde{T}(x')) \quad [(2.34b)] \\ &= \tilde{\varphi}_y(x') \quad [(2.35)]. \end{aligned} \quad (2.40) $$

Therefore, we have found a point $x''$ at an appropriate distance from $x'$. We still have to show that this point provides an appropriate decrease of $\tilde{\varphi}_y$.

* Let us use (2.39), which reads

$$ c(x'') \in y' + G \quad \text{or} \quad c(x'') + \delta(x') \in G + y. \quad (2.41) $$

Then,
## 2. Optimality Conditions

$$
\begin{align*}
\operatorname{dist}(y, \tilde{T}(x'')) &= \operatorname{dist}(\tilde{c}(x''), G + y) \quad [(2.34\text{b})] \\
&\le \operatorname{dist}(c(x'') + \delta(x''), c(x'') + \delta(x')) \quad [(2.41)] \\
&= \operatorname{dist}(\delta(x''), \delta(x')) \\
&\le L \operatorname{dist}(x'', x') \\
&\le L \tilde{\varphi}_y(x') \quad [(2.40)].
\end{align*}
$$

If the two extreme sides are multiplied by $\mu$, we get thanks to (2.35):

$$ \tilde{\varphi}_y(x'') \le L\mu\tilde{\varphi}_y(x') = r\tilde{\varphi}_y(x'). $$

This is the expected inequality. $\square$

<figure><img src="image_15.png" /></figure>

*Proof of proposition 2.10.* Let $T_0$ be the multifunction defined by (2.14b). Then, we have seen that

$$ (\text{CQ-R}) \text{ at } x_0 \iff 0 \in \text{int} \, \mathcal{R}(T_0). $$

The multifunction $T$ is convex, since $x \mapsto c(x_0) + c'(x_0) \cdot (x - x_0)$ is affine and $G$ is a convex set, and $(x_0, 0) \in \mathcal{G}(T_0)$, since $x_0 \in X_G$. Then, one can apply theorem 2.15, whose equivalence (i) $\Leftrightarrow$ (iv) yields

$$ (\text{CQ-R}) \text{ at } x_0 \iff T_0 \text{ is } \mu_0\text{-metric regular at } (x_0, 0). $$

We now apply proposition 2.19, with $T \rightsquigarrow T_0$, $\tilde{T} \rightsquigarrow T$ (the multifunction defined in (2.14a)) and $\delta: \mathbb{E} \to \mathbb{F}$ is defined at $x \in \mathbb{E}$ by

$$ \delta(x) = c(x) - c(x_0) - c'(x_0) \cdot (x - x_0). $$

Since $c$ is $\mathcal{C}^1$ in a neighborhood of $x_0$, $\delta$ is Lipschitz continuous in a neighborhood of $x_0$:

$$
\begin{align*}
\|\delta(x'') - \delta(x')\| &= \|c(x'') - c(x') - c'(x_0) \cdot (x'' - x')\| \\
&\le \left( \sup_{z \in [x', x'')} \|c'(z) - c'(x_0)\| \right) \|x'' - x'\| \\
&\le L \|x'' - x'\|,
\end{align*}
$$

where $L > 0$ can be taken as small as desired, provided $x'$ and $x''$ are sufficiently close to $x_0$ ($c'$ is continuous), in particular $< 1/\mu_0$. Then, proposition 2.19 shows that the metric regularity of $T_0$ at $(x_0, 0)$ implies that of $T$ at the same point. One can reverse the roles of $T_0$ and $T$, since the convexity of one of the multifunctions does not intervene in proposition 2.19 and $L$ can be taken arbitrarily small by reducing the neighborhood of $x_0$. As a result, the metric regularity of $T$ at $(x_0, 0)$ implies that of $T_0$ at the same point. We have shown that

$$ (\text{CQ-R}) \text{ at } x_0 \iff T \text{ is } \mu\text{-metric regular at } (x_0, 0). $$

It remains to give an interpretation to the right-hand side of the previous equivalence. This one actually means that, for all $(x, y)$ near $(x_0, 0)$, the following holds

$$ \operatorname{dist}(x, T^{-1}(y)) \le \mu \operatorname{dist}(y, T(x)). $$

Since $\operatorname{dist}(x, T^{-1}(y)) = \operatorname{dist}(x, c^{-1}(G + y))$ and $\operatorname{dist}(y, T(x)) = \operatorname{dist}(c(x), G + y)$, the equivalence of proposition 2.10 is proven. $\square$

<figure><img src="image_16.png" /></figure>
### 2.1.4 Robinson's Constraint Qualification

Let us recall the Robinson condition (2.42) and write it at a point $x \in \mathbb{E}$:

$$ (\text{CQ-R}) \qquad 0 \in \text{int}(c(x) + c'(x)\mathbb{E} - G). \qquad (2.42) $$

The main goal of this section is to show that this condition is sufficient for ensuring that the constraint qualification conditions (2.6) hold at a given point of $X_G$. To achieve this goal, it is useful to have at hand the few equivalent formulations of (CQ-R), given in the next proposition. Recall some definitions: for a closed convex set $C$ and a point $x \in C$, the cone of feasible directions to $C$ at $x$ reads $T_x^f C := \mathbb{R}_+(C - x)$, while the tangent cone $T_x C$ to $C$ at $x$ is the closure of $T_x^f C$.

**Proposition 2.20 (other formulations of (CQ-R))** If $c$ is differentiable at $x \in X_G$, the following properties are equivalent:

$$ 0 \in \text{int}(c(x) + c'(x)\mathbb{E} - G), \qquad (2.43a) $$

$$ c'(x)\mathbb{E} - T_{c(x)}^f G = \mathbb{F}, \qquad (2.43b) $$

$$ c'(x)\mathbb{E} - T_{c(x)} G = \mathbb{F}, \qquad (2.43c) $$

$$ c'(x)\mathbb{E} - T_{c(x)} G = \mathbb{F}. \qquad (2.43d) $$

*Proof.* [(2.43a) ⇒ (2.43b)] It suffices to prove the inclusion “$\supseteq$”. Let $y \in \mathbb{F}$. Then, by (2.43a), $y/t \in c'(x)\mathbb{E} - (G - c(x))$ for a sufficiently large $t > 0$. Hence $y \in c'(x)[t\mathbb{E}] - [t(G - c(x))] \subseteq c'(x)\mathbb{E} - T_{c(x)}^f G$.

[(2.43b) ⇒ (2.43c) ⇒ (2.43d)] These implications are clearly satisfied, since the sets in the left-hand sides are larger and larger.

[(2.43c) ⇒ (2.43b)] We start by exploiting the link between $T_{c(x)}^f G$ and $T_{c(x)} G$:

$$ \begin{align*} c'(x)\mathbb{E} - T_{c(x)} G &= c'(x)\mathbb{E} - \overline{T_{c(x)}^f G} & [\text{definition of } T_{c(x)} G] \\ &\subseteq \overline{c'(x)\mathbb{E} - T_{c(x)}^f G} & [A + B \subseteq A + B] \\ &\subseteq \overline{c'(x)\mathbb{E} - T_{c(x)} G} & [T_{c(x)}^f G \subseteq T_{c(x)} G] \\ &= \mathbb{F} \quad [(2.43d)]. \end{align*} $$

Taking the closure of all these sets shows that

$$ \overline{c'(x)\mathbb{E} - T_{c(x)}^f G} = \mathbb{F}. $$

Since $c'(x)\mathbb{E} - T_{c(x)}^f G$ is convex, this identity certainly implies (2.43b) (see also exercise 1.2.4).

[(2.43b) ⇒ (2.43a)] From (1.14), it suffices to prove that $0$ is absorbing for the convex set $C := c(x) + c'(x)\mathbb{E} - G$ de $\mathbb{F}$. Let $y \in \mathbb{F}$. Condition (2.43b) implies that there exists $d \in \mathbb{E}$, $y_1 \in G$, and $\alpha > 0$ such that $y = c'(x)d - \alpha(y_1 - c(x))$. For $t := 1/\alpha$, we get $ty = c(x) + c'(x)(td) - y_1 \in C$; hence $0$ is absorbing for $C$. □
Note that, in (2.43b)-(2.43d), one can change the minus sign by a plus, since $c'(x)\mathbb{E}$ and $\mathbb{F}$ are vector spaces. Conditions (2.43b) and (2.43c) convey the fact that $\mathbb{F}$ can be written as the sum of a subspace, say $\mathbb{F}_0$, and a cone, say $K$. According to exercise 1.2.7, this is equivalent to saying that

$$ \mathbb{F}_0 + \mathrm{vect} K = \mathbb{F} \quad \text{and} \quad \mathbb{F}_0 \cap (\mathrm{ri} K) \neq \emptyset. $$

**Proposition 2.21 (constraint qualification by (CQ-R))** If $c$ is continuously differentiable in the neighborhood of a point $x \in X_G$ and if the Robinson condition (CQ-R) holds at this point, then, the constraint $c$ is qualified to represent $X_G$ at $x$, in the sense of definition 2.4.

*Proof.* We must show that (CQ-R) implies the two properties (2.6a) and (2.6b).

[(2.6a)] For this step of the proof, it suffices to use Robinson's error bound (2.12). According to proposition 2.3, it suffices to show the inclusion $T'_x X_G \subseteq T_x X_G$. Let $d \in T'_x X_G$. To show that $d \in T_x X_G$, it suffices to build a sequence $\{x_k\} \subseteq X_G$ (a priori a difficult task) and a sequence $\{t_k\} \downarrow 0$ such that $(x_k - x)/t_k \to d$. The followed approach is illustrated by figure 2.4: thanks to the Robinson error bound (2.12), one

<figure><img src="image_17.png" /><figcaption>**Fig. 2.4.** Illustration of the proof of (2.6a) to establish proposition 2.21</figcaption></figure>

can create a sequence $\{x_k\} \subseteq X_G := c^{-1}(G)$ with the desired properties; these are due to the good feature of the sequence $\{c(x + t_k d)\}$ in $\mathbb{F}$, which is to be asymptotically very close to the sequence $\{y_k\}$. Here are the details.

Since $d$ is in the linearizing cone $T'_x X_G$, it satisfies $c'(x) \cdot d \in T_{c(x)} G$, which implies that there exist sequences $\{y_k\} \subseteq G$ and $\{t_k\} \downarrow 0$ (it is the good one!), such that

$$ \frac{y_k - c(x)}{t_k} \to c'(x) \cdot d \quad \text{or} \quad c(x) + c'(x) \cdot (t_k d) - y_k = o(t_k). \quad (2.44) $$

Consider the sequence $\{x'_k\} \subseteq \mathbb{E}$ defined by

$$ x'_k := x + t_k d. $$

This sequence is not necessary in $X_G$; hence the sequence $\{c(x'_k)\}$ is not necessary in $G$, but it is not far from $\{y_k\}$ (which is in $G$) asymptotically. Indeed, by the differentiability of $c$, one has

$$ c(x'_k) = c(x) + c'(x) \cdot (t_k d) + o(t_k) $$
and therefore, using (2.44),

$$c(x'_{k}) = y_{k} + o(t_{k}). \qquad (2.45)$$

We now build the appropriate sequence {$x_k$} $\subseteq X_G$ thanks to Robinson's error bound (2.12) at $x_0 \not\sim x$. This one can be applied at $x'_k$ since this point is close to $x$ for sufficiently large $k$ (and $c$ is $C^1$ in a neighborhood of $x$). It tells us that there exists a constant $\mu \ge 0$ such that, for sufficiently large $k$, one has

$$\begin{aligned} \mathrm{dist}(x'_{k}, X_G) &\le \mu \mathrm{dist}(c(x'_{k}), G) \quad [(2.12)] \\ &\le \mu \mathrm{dist}(c(x'_{k}), y_k) \quad [y_k \in G] \\ &= o(t_k) \quad [(2.45)]. \end{aligned}$$

This implies that there exists a sequence {$x_k$} $\subseteq X_G$ such that $x_k = x'_k + o(t_k)$. We have built the desired sequence {$x_k$} since

$$\frac{x_k - x}{t_k} = \frac{x_k - x'_k}{t_k} + \frac{x'_k - x}{t_k} = \frac{o(t_k)}{t_k} + d \to d.$$

[(2.6b)] This step of the proof uses the expression (2.43c) of (CQ-R). We consider a convergent sequence in the cone $K := c'(x)^*[(T_{c(x)} G)^+]$, whose closure has to be shown:

$$c'(x)^* \lambda_k \to y, \qquad (2.46)$$

where {$\lambda_k$} $\subseteq (T_{c(x)} G)^+$. The goal now is to show that $y$ is in $K$. In finite dimension, it suffices to show that the sequence {$\lambda_k$} is bounded (then, one extracts from it a convergent subsequence, whose limit is in the closed cone $(T_{c(x)} G)^+$, and one takes the limit in (2.46), which shows that $y \in K$). One proceeds by contradiction. If {$\lambda_k$} is unbounded, one can extract a subsequence from {$\lambda_k/\|\lambda_k\|$} $\subseteq (T_{c(x)} G)^+$, which converges to a nonzero vector (it has unit norm), say $\mu$. We see on (2.46) that $\mu$ verifies

$$c'(x)^* \mu = 0 \quad \text{and} \quad \mu \in (T_{c(x)} G)^+. \qquad (2.47)$$

Since $\mu \in \mathbb{F}$, (2.43c) tells us that it can be written $\mu = c'(x)d - p$ for some $d \in \mathbb{E}$ and $p \in T_{c(x)} G$. Therefore,

$$\|\mu\|^2 = \langle \mu, c'(x)d - p \rangle = -\langle \mu, p \rangle \le 0,$$

where we have used (2.47) and $p \in T_{c(x)} G$. This implies that $\mu = 0$, which is in contradiction with the fact observed above, indicating that $\mu \ne 0$. $\square$

### 2.1.5 Set of optimal multipliers

In the light of the optimality conditions (2.8a)-(2.8b), the set of optimal multipliers associated with a stationary point $x$ of problem ($P_G$) reads

$$\Lambda = \{\lambda \in \mathbb{N}_{c(x)} G : \nabla f(x) + c'(x)^* \lambda = 0\}, \qquad (2.48)$$

where we have alleviated notation by dropping the star indices. As an intersection of a closed convex cone and an affine subspace, this is a closed convex set. This section gives more properties of this set.
The next proposition cares about the boundedness of $\Lambda$ (hence of its compactness) and, in this sense, extends point 1 of proposition 1.42 from problem ($P_{EI}$) to problem ($P_G$). It does it by computing first its asymptotic cone $\Lambda^\infty$ and then uses proposition 1.13 to characterize the boundedness of $\Lambda$.

**Proposition 2.22 (boundedness of the set of multipliers, Gauvin's property)** Suppose that $f$ and $c$ are differentiable at a stationary point $x$ of problem ($P_G$) and that the set $\Lambda$ of associated multipliers is nonempty. Then, the asymptotic cone of $\Lambda$ reads

$$ \Lambda^{\infty} = (N_{c(x)} G) \cap \mathcal{N}(c'(x)^*) = [c'(x)\mathbb{E} - T_{c(x)} G]^{+}. \quad (2.49) $$

It results that, $\Lambda$ is bounded if and only if the Robinson condition (CQ-R) holds at $x_0 = x$.

*Proof.* According to exercise 1.2.13, the asymptotic cone of $\Lambda$ is given by the first identity in (2.49). Now, using point 4 of proposition 1.7, $N_{c(x)} G = (-T_{c(x)} G)^+$, and $\mathcal{N}(c'(x)^*) = \mathcal{R}(c'(x))^{\perp} = (c'(x)\mathbb{E})^+$, we get the second identity in (2.49).

Next, according to proposition 1.13, $\Lambda$ is bounded if and only if its asymptotic cone is reduced to $\{0\}$. Hence, we only have to prove

$$ [c'(x)\mathbb{E} - T_{c(x)} G]^{+} = \{0\} \iff (\text{CQ-R}). \quad (2.50) $$

The implication “$\Leftarrow$” is clear, if we consider the form (2.43c) of (CQ-R). For the reverse implication “$\Rightarrow$”, take the dual of the two sides of the identity in the left-hand side of (2.50) and use (1.16) to get $\text{cl}(c'(x)\mathbb{E} - T_{c(x)} G) = \mathbb{F}$, which is equivalent to (CQ-R) by (2.43d). $\square$

The final claim of the previous proposition may look strange since (CQ-R) only depends on the constraints of the optimization problem ($P_G$), while the optimal multiplier set $\Lambda$ defined by (2.48), which is used to characterize (CQ-R), also depends on the objective of the problem. Observe, however, that the characterization only uses the asymptotic cone $\Lambda^\infty$, which does not depend on the objective of the optimization problem.

Proposition 2.24 [129] below highlights conditions ensuring that $\Lambda$ is a singleton, which is an esoteric way of saying that there is a unique multiplier associated with the given stationary point $x$. We pave the way to this uniqueness result by the next lemma, which gives an expression of the dual cone of $c'(x)\mathbb{E} - [(T_{c(x)} G) \cap \lambda^\perp]$, where, for $\lambda \in \mathbb{F}$:

$$ \lambda^{\perp} := \{\mu \in \mathbb{F} : \langle \mu, \lambda \rangle = 0\} = (\mathbb{R}\{\lambda\})^{\perp}. $$

Note that the a priori larger set $c'(x)\mathbb{E} - T_{c(x)} G$ is equal to $\mathbb{F}$, when (CQ-MF) holds; see proposition 2.20. A comparison with the dual cone of $c'(x)\mathbb{E} - T_{c(x)} G$, whose expression is given in (2.49), may be instructive.
**Lemma 2.23** Let $x \in \mathbb{E}$ be a feasible point of problem ($P_G$) and let $\lambda \in \mathbb{N}_{c(x)} G$. Then,

$$ [(T_{c(x)} G) \cap \lambda^{\perp}]^{+} = -T_{\lambda}(N_{c(x)} G), \quad (2.51a) $$

$$ (c'(x)\mathbb{E} - [(T_{c(x)} G) \cap \lambda^{\perp}])^{+} = \mathcal{N}(c'(x)^*) \cap T_{\lambda}(N_{c(x)} G). \quad (2.51b) $$

*Proof.* [(2.51a)] Let us first compute

$$ \begin{aligned} [(T_{c(x)} G) \cap \lambda^{\perp}]^{+} &= \overline{(T_{c(x)} G)^{+} + \{\lambda^{\perp}\}^{+}} \quad [(1.21)] \\ &= -\overline{N_{c(x)} G + \mathbb{R}\{\lambda\}} \quad [(T_{c(x)} G)^{+} = -N_{c(x)} G] \\ &= -\overline{T_{\lambda}^{f}(N_{c(x)} G)} \quad [\lambda \in \mathbb{N}_{c(x)} G \text{ and exercise 1.2.11}] \\ &= -T_{\lambda}(N_{c(x)} G) \quad [(1.22)]. \end{aligned} $$

[(2.51b)] Using property 6 of proposition 1.7, one gets

$$ (c'(x)\mathbb{E} - [(T_{c(x)} G) \cap \lambda^{\perp}])^{+} = (c'(x)\mathbb{E})^{+} \cap -[(T_{c(x)} G) \cap \lambda^{\perp}]^{+}. $$

One can then conclude by using $(c'(x)\mathbb{E})^{+} = \mathcal{R}(c'(x))^{\perp} = \mathcal{N}(c'(x)^*)$, since $c'(x)\mathbb{E} = \mathcal{R}(c'(x))$ is a subspace, and (2.51a). $\square$

**Proposition 2.24 (uniqueness of the optimal multiplier)** Let $(x, \lambda) \in \mathbb{E} \times \mathbb{F}$ be a stationary pair of problem ($P_G$) and denote by $\Lambda$ the set (2.48) of optimal multipliers associated with $x$. Consider the following properties:

(i) $\Lambda = \{\lambda\}$,

(ii) $\mathcal{N}(c'(x)^*) \cap T_{\lambda}^f(N_{c(x)} G) = \{0\}$,

(iii) $\mathcal{N}(c'(x)^*) \cap T_{\lambda}(N_{c(x)} G) = \{0\}$,

(iv) $c'(x)\mathbb{E} - [(T_{c(x)} G) \cap \lambda^{\perp}] = \mathbb{F}$.

Then, (i) $\Leftrightarrow$ (ii) $\Leftrightarrow$ (iii) $\Leftrightarrow$ (iv). If $T_{\lambda}^f(N_{c(x)} G) = T_{\lambda}(N_{c(x)} G)$, then the four properties (i)-(iv) are equivalent.

*Proof.* [(i) $\Rightarrow$ (ii)] Let $\mu \in \mathcal{N}(c'(x)^*) \cap T_{\lambda}^f(N_{c(x)} G)$. It suffices to show that $\mu = 0$. Since $\mu \in T_{\lambda}^f(N_{c(x)} G)$, it is of the form $\mu = \alpha(\lambda' - \lambda)$ for some $\alpha \ge 0$ and $\lambda' \in \mathbb{N}_{c(x)} G$. If $\alpha = 0$, we get $\mu = 0$ as desired. Otherwise, $\lambda' = \lambda + \mu/\alpha$, which satisfies

$$ \nabla f(x) + c'(x)^* \lambda' = 0 \quad \text{and} \quad \lambda' \in \mathbb{N}_{c(x)} G. $$

Hence $\lambda' \in \Lambda = \{\lambda\}$, implying that $\lambda' = \lambda$. Hence $\mu = 0$.

[(i) $\Leftarrow$ (ii)] Let $\lambda' \in \Lambda$ and set $\mu := \lambda' - \lambda$. It suffices to show that $\mu = 0$. It immediately follows from $\lambda$ and $\lambda' \in \Lambda$ in (2.48) that

$$ c'(x)^* \mu = 0 \quad \text{and} \quad \mu \in T_{\lambda}^f(N_{c(x)} G). $$
Then, (ii) implies that $\mu = 0$.

[(ii) $\Leftarrow$ (iii)] This is because $T_{\lambda}^{f}(N_{c(x)} G) \subseteq T_{\lambda}(N_{c(x)} G)$.

[(iii) $\Rightarrow$ (iv)] Taking the dual of both sides of the identity in (iii) and using (2.51b), we have that the closure of $c'(x)\mathbb{E} - [(T_{c(x)} G) \cap \lambda^{\perp}]$ is $\mathbb{F}$ (see (1.16)). Since this last set is convex, we certainly have (iv) (see exercise 1.2.4).

[(iii) $\Leftarrow$ (iv)] Taking the dual of both sides of the identity in (iv) and using (2.51b), we get (iii).

[Last claim] If $T_{\lambda}^{f}(N_{c(x)} G) = T_{\lambda}(N_{c(x)} G)$, then (ii) and (iii) are clearly identical and, therefore, all the properties (i)-(iv) are equivalent. $\square$

**Remarks 2.25** 1) When $G$ is a convex polyhedron, like in problem (P$_{EI}$), its normal cone $N_{c(x)} G$ is also a convex polyhedron (see (1.27a)). Then, the tangent cone and the cone of feasible directions to $N_{c(x)} G$ are identical (see (1.26a)) and the four properties (i)-(iv) of proposition 2.24 are equivalent.

2) One can recover the conditions 2.(ii) and 2.(iii) of proposition 1.42 for problem (P$_{EI}$) from the conditions (iii) and (iv) of the previous proposition. This is part of the subject of exercise 2.1.6.

### 2.1.6 Other problems ▲

In this section, we show how the results obtained for the general problem (P$_{G}$) can be applied to other problems.

#### Problem with an additional set constraint ▲

Let $\mathbb{E}$ and $\mathbb{F}$ be two Euclidean vector spaces. Consider the problem

$$ (P_{Q,G}) \quad \begin{cases} \min & f(x) \\ & x \in Q \\ & c(x) \in G, \end{cases} \qquad (2.52) $$

where $f: \mathbb{E} \to \mathbb{R}$ and $c: \mathbb{E} \to \mathbb{F}$ are two smooth functions, $Q$ is a nonempty closed convex set of $\mathbb{E}$ and $G$ is a nonempty closed convex set of $\mathbb{F}$. We denote its feasible set by

$$ X_{Q,G} := \{x \in \mathbb{E} : x \in Q, c(x) \in G\}. $$

We now give a series of results, whose proofs are proposed in exercise 2.1.8.

We first look at various adaptations to problem (P$_{Q,G}$) of the Robinson constraint qualification assumption (CQ-R) associated with problem (P$_{G}$). They are similar to those given in proposition 2.20.

**Proposition 2.26 (constraint qualification)** If $c$ is differentiable at a feasible point $x \in X_{Q,G}$, the following properties are equivalent:
$$0 \in \text{int}(c(x_*) + c'(x_*)(Q - x_*) - G), \qquad (2.53a)$$

(2.53b)

(2.53c)

(2.53d)

The following result gives necessary first order optimality conditions (NC1) for problem ($P_{Q,G}$).

**Proposition 2.27 (NC1 for problem ($P_{Q,G}$))** Let $x_*$ be a local solution to problem ($P_{Q,G}$). Suppose that $f$ and $c$ are differentiable at $x_*$ and that the constraint qualification assumption (2.53) holds. Then, there exists $\lambda_* \in \mathbb{F}$ such that

$$\nabla f(x_*) + c'(x_*)^* \lambda_* \in (T_{x_*} Q)^+ \qquad (2.54a)$$

$$\lambda_* \in N_{c(x_*)} G. \qquad (2.54b)$$

As usual, the NC1 become sufficient optimality conditions of the first order (SC1) for a “convex problem” ($P_{Q,G}$), in a sense specified in the next proposition.

**Proposition 2.28 (SC1 for a convex ($P_{Q,G}$))** Suppose that problem ($P_{Q,G}$) is convex in the sense that $f$ is convex and its feasible set $X_{Q,G}$ is convex. Suppose also that $f$ and $c$ are differentiable at a point $x_* \in X_{Q,G}$, and that there exists a multiplier $\lambda_* \in \mathbb{F}$ such that $(x_*, \lambda_*)$ verifies the first order optimality conditions (2.54). Then, $x_*$ is a global solution to ($P_{Q,G}$).

One can also adapt, from propositions 2.22 and 2.24, the conditions ensuring the boundedness of the set of optimal multipliers and the uniqueness of the optimal multiplier.

**Proposition 2.29 (boundedness of the set of multipliers, Gauvin's property)** Suppose that $f$ and $c$ are differentiable at a stationary point $x$ of problem ($P_{Q,G}$) and that the set $\Lambda$ of associated multipliers is nonempty. Then, the asymptotic cone of $\Lambda$ reads

$$\Lambda^{\infty} \qquad (2.55)$$

It results that, $\Lambda$ is bounded if and only if
**Proposition 2.30 (uniqueness of the optimal multiplier)** Let $(x, \lambda) \in \mathbb{E} \times \mathbb{F}$ be a stationary pair of problem $(P_{Q,G})$ and denote by $\Lambda$ the set (2.48) of optimal multipliers associated with $x$. Consider the following properties:

(i) $\Lambda = \{\lambda\}$,

(ii)

(iii)

(iv)

Then, $(i) \Leftrightarrow (ii) \Leftrightarrow (iii) \Leftrightarrow (iv)$.

## Composite optimization

Let $\mathbb{E}$ and $\mathbb{F}$ be two Euclidean vector spaces. As already quoted in example 2.2(3), a composite optimization problem is an optimization problem of the form

$$ (P_{\text{comp}}) \quad \left\{ \begin{array}{l} \min_{x \in \mathbb{E}} (g \circ F)(x) \\ x \in Q, \end{array} \right. \qquad (2.56) $$

where $F: \mathbb{E} \to \mathbb{F}$ is a differentiable function, $g \in \text{Conv}(\mathbb{F})$, $(g \circ F)$ denotes the composition of $g$ and $F$ [hence $(g \circ F)(x) = g(F(x))$] and $Q$ is a nonempty closed convex set of $\mathbb{E}$. These assumptions are made in all this section.

**Definition 2.31 (convex problem ($P_{\text{comp}}$))** The problem ($P_{\text{comp}}$) is said to be convex if the function $(g \circ F) + \mathcal{I}_Q$ is convex or, equivalently, if $g \circ F$ is convex on the convex set $Q$. $\square$

Problem (2.56) is equivalent to (same optimal value, identical $x$-solution)

$$ \left\{ \begin{array}{l} \min_{(x, \alpha) \in \mathbb{E} \times \mathbb{R}} \alpha \\ x \in Q \\ (g \circ F)(x) \le \alpha. \end{array} \right. $$

Since the first constraint also reads $(x, \alpha) \in Q \times \mathbb{R}$ and the second constraint also reads $g(F(x)) \le \alpha$ or $(F(x), \alpha) \in \text{epi}(g)$, this last problem, and therefore (2.56), is equivalent to solving

$$ \left\{ \begin{array}{l} \min_{(x, \alpha) \in \mathbb{E} \times \mathbb{R}} \alpha \\ (x, \alpha) \in Q \times \mathbb{R} \\ (F(x), \alpha) \in \text{epi}(g). \end{array} \right. \qquad (2.57) $$

Problem (2.57) is of the form $(P_{Q,G})$ in (2.52), so that the results obtained for this latter problem can be used to determine analog properties for problem $(P_{\text{comp}})$.

The proof of the propositions of this section are proposed in exercise 2.1.9.

We start by adapting to problem $(P_{\text{comp}})$ the constraint qualification assumptions (2.53) associated with problem (2.57). The reason of the need of such a function qualification might not be obvious when one looks at the formulation (2.56) of the composite problem. Actually, it is linked to implicit constraints introduced by the infinite values that $g$ can take. Observe indeed that the equivalent conditions (2.58) of the next proposition, in particular its condition (2.58c), are satisfied if the considered
point $x \in \mathbb{E}$ is such that $F(x) \in \text{int}(\text{dom } g)$ (since then $T_{F(x)}(\text{dom } g) = \mathbb{F}$), that is, when the infinite values of $g$ do not appear in the neighborhood of $F(x)$.

**Proposition 2.32 (function qualification)** *The following properties are equivalent:*

$$0_{\mathbb{F}} \in \text{int} (F(x) + F'(x)(Q - x) - (\text{dom } g)), \quad (2.58\text{a})$$

$$F'(x)(T_x^f Q) - T_{F(x)}^f (\text{dom } g) = \mathbb{F}, \quad (2.58\text{b})$$

$$F'(x)(T_x Q) - T_{F(x)}(\text{dom } g) = \mathbb{F}, \quad (2.58\text{c})$$

$$\overline{F'(x)(T_x Q) - T_{F(x)}(\text{dom } g)} = \mathbb{F} \quad (2.58\text{d})$$

and, for any $\alpha \ge g(F(x))$, these conditions are equivalent to the Robinson constraint qualification (CQ-R) at $(x, \alpha)$ for the constraints of problem (2.57).

Proposition 2.27 for problem (2.57) yields the following necessary optimality conditions of the first order (NC1) for problem ($P_{\text{comp}}$). Observe that if $g$ is differentiable at $F(x)$, (2.59) becomes

$$\nabla(g \circ F)(x_*) \in (T_{x_*} Q)^+,$$

which is then the expected Peano-Kantorovich optimality condition (1.51) for problem ($P_{\text{comp}}$). This observation should help to understand and remember (2.59).

**Proposition 2.33 (NC1 for problem ($P_{\text{comp}}$))** *Suppose that $x_*$ is a local solution to problem ($P_{\text{comp}}$) and that the function qualification condition (2.58) holds. Then, there exists $\lambda_* \in \mathbb{F}$ such that*

$$F'(x_*)^* \lambda_* \in (T_{x_*} Q)^+, \quad (2.59\text{a})$$

$$\lambda_* \in \partial g(F(x_*)), \quad (2.59\text{b})$$

where $\partial g(y)$ denotes the subdifferential of $g$ at $y$.

As usual, the NC1 become sufficient conditions of the first order (SC1) for global optimality of a convex problem ($P_{\text{comp}}$). It turns out that the appropriate notion of convexity for problem ($P_{\text{comp}}$) is the one of definition 2.31 (actually, it has been introduced for being useful in the next proposition).

**Proposition 2.34 (SC1 for a convex ($P_{\text{comp}}$))** *Suppose that problem ($P_{\text{comp}}$) is convex in the sense of definition 2.31, that $x_* \in Q$ and that there exists a multiplier $\lambda_* \in \mathbb{F}$ such that $(x_*, \lambda_*)$ verifies the first order optimality conditions (2.59). Then, $x_*$ is a global solution to ($P_{\text{comp}}$).*
Notes

The condition (2.43c) is reminiscent of the notion of transversality in differential geometry [109]. The link between the boundedness of the set of optimal multipliers and (CQ-MF) in nonlinear optimization (point 1 of proposition 1.42, extended to problem (P<sub>G</sub>) by proposition 2.22) was observed by Gauvin [59; 1977]. More on metric regularity can be found in [44; 2009].

Exercises

2.1.1. *Convex* ($P_{EI}$). Let $G = \{0_{\mathbb{R}^{m_E}}\} \times \mathbb{R}^{m_I}$ and $T: \mathbb{R}^n \to \mathbb{R}^m: x \mapsto c(x) - G$ be the multifunction associated with the constraint of problem ($P_{EI}$). Show that $T$ is convex if and only if $c_E$ is affine and $c_I$ is componentwise convex.

2.1.2. *Open mapping theorem.* Let $A: \mathbb{E} \to \mathbb{F}$ be a linear map between the finite dimension normed vector spaces $\mathbb{E}$ and $\mathbb{F}$ (the result also holds for infinite dimension Banach spaces, but is more difficult to prove [24]). Denote by $\bar{B}_{\mathbb{E}}$ and $\bar{B}_{\mathbb{F}}$ the closed unit balls of $\mathbb{E}$ and $\mathbb{F}$ respectively. Then, the following properties are equivalent:

(i) A is surjective,

(ii) $\exists \rho > 0$ such that $\rho \bar{B}_{\mathbb{E}} \subseteq A(\bar{B}_{\mathbb{E}})$,

(iii) $\exists \mu > 0$ such that: $\forall y \in \mathbb{F}, \exists x \in \mathbb{E}$ such that $Ax = y$ and $\|x\| \le \mu \|y\|$.

2.1.3. *Examples of use of Robinson's constraint qualification condition.* Consider the following sets of the form $X_G := \{x \in \mathbb{E} : c(x) \in G\}$, with $G \subseteq \mathbb{F}$, and points $x_0 \in X_G$:

1) $\mathbb{E} = \mathbb{F} = \mathbb{R}^2$, and $c$ and $G$ are defined by

$$c(x) = (x_1^2+(x_2-1)^2-1, x_1^2+(x_2+1)^2-1), \quad G = \mathbb{R}_-^2, \quad \text{and} \quad x_0 = (0,0),$$

2) $\mathbb{E} = \mathbb{F} = \mathbb{R}^2$, and $c$ (2 identical constraints) and $G$ are defined by

$$c(x) = (x_2, x_2), \quad G = \mathbb{R}_+^2, \quad \text{and} \quad x_0 = (0,0).$$

For these sets $X_G$ and points $x_0 \in X_G$,

(i) determine whether Robinson's constraint qualification condition holds at $x_0$, without using its equivalence with (CQ-MF),

(ii) find a mudulus of metric regularity of the multifunction $x \mapsto c(x) - G$ at $(x_0, 0)$ if any.

2.1.4. *Robinson's constraint qualification condition for (P<sub>EI</sub>).* Viewing problem (P<sub>EI</sub>) as a particular instance of problem (P<sub>G</sub>), show that the Robinson constraint qualification condition (CQ-R) is equivalent to the Mangasarian-Fromovitz's constraint qualification condition (CQ-MF).

2.1.5. *Robinson's constraint qualification and the primal SDO problem.* Let $S^n$ be the set of symmetric matrices of order $n$, which is equipped with the scalar product $\langle A, B \rangle = \text{tr} AB$ (the trace of $AB$). Let $S_+^n$ be the cone of $S^n$ made of the positive semidefinite matrices and $S_{++}^n$ be the cone of $S^n$ made of the positive definite matrices. We abbreviate $X \ge 0$ for $X \in S_+^n$ and $X > 0$ for $X \in S_{++}^n$.

Consider the primal semidefinite optimization (SDO) problem, written as follows

$$(P) \quad \begin{cases} \inf_{X \in S^n} \langle C, X \rangle \\ A(X) = b \\ X \ge 0, \end{cases} \qquad (2.60)$$