where $C \in S^n$, $A: S^n \to \mathbb{R}^m$ is a linear map, and $b \in \mathbb{R}^m$. The feasible and strictly feasible sets of this problem are respectively denoted by

$$ \mathcal{F}_P := \{X \in S_+^n : A(X) = b\} \quad \text{and} \quad \mathcal{F}_P^s := \{X \in S_{+}^n : A(X) = b\}. $$

We assume that $\mathcal{F}_P \neq \emptyset$.

Let us represent the feasible set of problem (2.60) by $\mathcal{F}_P := \{X \in S^n : c(X) \in G\}$, where

$$ c: X \in S^n \to (A(X) - b, X) \in \mathbb{R}^m \times S^n \quad \text{and} \quad G = \{0_{\mathbb{R}^m}\} \times S_+^n. \quad (2.61) $$

Let (CQ-R) denote Robinson's constraint qualification condition for the above representation of $\mathcal{F}_P$.

1) Show that (CQ-R) at $X_0 \in \mathcal{F}_P$ can equivalently be written

$$ (A, I)S^n - \{0_{\mathbb{R}^m}\} \times T_{X_0} S_+^n = \mathbb{R}^m \times S^n, \quad (2.62) $$

where $(A, I): S^n \to \mathbb{R}^m \times S^n$ is the linear map $X \mapsto (A(X), X)$.

2) Show that if (CQ-R) holds at some point $X_0 \in \mathcal{F}_P$, then

$$ A \text{ is surjective and } \mathcal{F}_P^s \neq \emptyset. \quad (2.63) $$

3) Show that if (2.63) holds then (CQ-R) holds at any point $X_0 \in \mathcal{F}_P$.

4) Show that if $X$ solves (P) and (2.63) holds then there is a pair $(y, S) \in \mathbb{R}^m \times S^n$ such that

$$ A^*(y) + S = C, \quad S \ge 0, \quad \text{and} \quad \langle X, S \rangle = 0. \quad (2.64) $$

Furthermore, the set of pairs $(y, S) \in \mathbb{R}^m \times S^n$ satisfying these three conditions is compact.

5) Reciprocally, show that if $X \in \mathcal{F}_P$ is such that the set of pairs $(y, S)$ verifying (2.64) is nonempty and bounded, then (2.63) holds.

**2.1.6. Multiplier uniqueness for two-side inequality constraints.** Consider the optimization problem ($P_G$), in which $\mathbb{F}$ is $\mathbb{R}^m = \mathbb{R}^{m_E} \times \mathbb{R}^{m_I}$ and

$$ G = \{0_{\mathbb{R}^{m_E}}\} \times [l, u], $$

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\}$. Let $(x, \lambda) \in \mathbb{E} \times \mathbb{R}^m$ be a stationary pair of the problem ($P_G$) and denote by $\Lambda$ the set (2.48) of optimal multipliers associated with $x$. Define the following index sets

$$ \begin{align*} I^l &:= \{i \in I : c_i(x) = l_i\}, & I^u &:= \{i \in I : c_i(x) = u_i\}, \\ I^{l0} &:= \{i \in I : c_i(x) = l_i, \lambda_i = 0\}, & I^{u0} &:= \{i \in I : c_i(x) = u_i, \lambda_i = 0\}, \\ I^{-l} &:= \{i \in I : c_i(x) = l_i, \lambda_i < 0\}, & I^{u+} &:= \{i \in I : c_i(x) = u_i, \lambda_i > 0\}. \end{align*} $$

Show that the following properties are equivalent:

(i) $\Lambda = \{\lambda\}$,

(ii) there is no nonzero $\alpha \in \mathbb{R}^{|E \cup I^l \cup I^u|}$ such that

$$ \sum_{i \in E \cup I^l \cup I^u} \alpha_i \nabla c_i(x) = 0, \quad \alpha_{I^{l0}} \le 0, \quad \text{and} \quad \alpha_{I^{u0}} \ge 0, $$

(iii) for any $v \in \mathbb{R}^{|E \cup I^l \cup I^u|}$, there is a $d \in \mathbb{E}$ such that

$$ c'_{E \cup I^{l-} \cup I^{u+}}(x) d = v_{E \cup I^{l-} \cup I^{u+}}, \quad c'_{I^{l0}}(x) d \le v_{I^{l0}}, \quad \text{and} \quad c'_{I^{u0}}(x) d \ge v_{I^{u0}}, $$

(iv) $c'_{E \cup I^{l-} \cup I^{u+}}(x)$ is surjective and there is a $d \in \mathbb{E}$ such that

$$ c'_{E \cup I^{l-} \cup I^{u+}}(x) d = 0, \quad c'_{I^{l0}}(x) d < 0, \quad \text{and} \quad c'_{I^{u0}}(x) d > 0. $$
**2.1.7.** Multiplier uniqueness for ($P_G$) with $G = S_+^n$ [129]. Consider the problem ($P_G$) in which $\mathbb{F}$ is the vector space $S^n$ formed of the symmetric matrices of order $n$ equipped with the scalar product $\langle \cdot, \cdot \rangle : (A, B) \in S^n \times S^n \to \langle A, B \rangle = \text{tr} AB \in \mathbb{R}$ (the trace of the matrix $AB$) and $G = S_+^n$ is the cone of $S^n$ made of the positive semidefinite matrices. The problem reads

$$ \left\{ \begin{array}{l} \min f(x) \\ c(x) \in S_+^n. \end{array} \right. \qquad (2.65) $$

We also define $S_-^n = -S_+^n$. Let $(x, \lambda) \in \mathbb{E} \times S^n$ be a stationary pair of (2.65). Let $r := \text{rank}(c(x))$ be the rank of the matrix $c(x) \in S^n$, so that there is an $n \times (n-r)$ injective matrix $V$ such that $\mathcal{N}(c(x)) = \mathcal{R}(V)$.

1) Show that $\lambda$ is of the form $\lambda = V\Theta V^T$, for some $\Theta \in S_-^{n-r}$.

2) Show that $\text{rank}(\lambda) + \text{rank}(c(x)) \le n$.

From now on, we assume that strict complementarity holds, which means that $\text{rank}(\lambda) + \text{rank}(c(x)) = n$.

3) Show that $T_\lambda^f(N_{c(x)} S_+^n) = T_\lambda(N_{c(x)} S_+^n) = \{V\Theta V^T : \Theta \in S_-^{n-r}\}$.

4) Show that $x$ has a unique associated multiplier $\lambda$ if and only if

$$ c'(x)\mathbb{E} + \{Z \in S^n : V^T ZV = 0\} = S^n. $$

**2.1.8.** Optimality conditions of the first order for a problem with an additional set-inclusion constraint. Prove propositions 2.26, 2.27, 2.28, 2.29 and 2.30.

**2.1.9.** Optimality conditions of the first order for a composite problem. Prove propositions 2.32, 2.33 and 2.34.

## 2.2 Second Order Optimality Conditions for ($P_{EI}$)

Second order optimality conditions are used to determine whether a stationary point is a local minimizer or maximizer; sometimes these conditions are not precise enough to conclude. One makes a distinction between necessary optimality conditions (those that are implied by a local minimizer) and sufficient optimality conditions (those that guarantee that a given point is a local minimizer).

The necessary optimality conditions of the second order for the problem with equality and inequality constraints ($P_{EI}$) defined in section 1.4.4 can neither be obtained as easily nor be written as simply as for a problem with only equality constraints (theorem 1.33). There is a common feature however, which is that it is the Hessian of the Lagrangian that intervenes in these conditions; the reason is that, like for the equality constrained problem, the gradient of the Lagrangian vanishes at a local solution to the problem (compare theorems 1.30 and 1.40). But there are two main differences. First, it is not on the tangent cone to the feasible set that the Hessian of the Lagrangian is positive semi-definite, but on a smaller one, called the critical cone (this is further discussed in section 2.2.1). The second difference comes from the choice of the optimal multiplier that intervenes in the Hessian of the Lagrangian (for an inequality constrained problem, it is frequent that the set of optimal multipliers associated with a given solution is not reduced to a singleton): the key observation is that the optimal multiplier must be chosen according to the given critical direction (this is further discussed in section 2.2.2).
Getting second order sufficient conditions of optimality is not a difficult task (section 2.2.4), but getting the second order necessary conditions of optimality is much more serious (section 2.2.3). There are many possibilities to establish them. Our strategy is the following. The approach assumes at once that the Mangasarian-Fromovitz constraint qualification condition (CQ-MF) holds at the solution. This one is strong enough to show the existence of paths in the feasible set, emanating from the considered solution. Then, the behavior of the objective of the problem is examined along these paths, which allows us to derive weak necessary optimality conditions of the second order. These optimality conditions can be reinforced in the presence of stronger constraint qualification conditions. It is the subject of exercise ?? to consider the case of (CQ-A) and (CQ-LI) and to ask to show that a strong form of the second order optimality conditions are then obtained (this is not surprising for (CQ-LI), since then the optimal multiplier is uniquely determined).

### 2.2.1 Critical Cone

It is tempting to try to generalize the necessary optimality conditions of the second order of problem ($P_E$), stated in theorem 1.33, to problem ($P_{EI}$). This extension could be that, at a stationary pair ($x_*, \lambda_*$), one must have $\langle L_*d, d \rangle \ge 0$ for all tangent directions $d \in T_{x_*} X_{EI}$ (we have denoted by $L_* := \nabla^2_{xx} \ell(x_*, \lambda_*)$ the Hessian of the Lagrangian at the considered stationary pair). This result is not correct, since the tangent cone $T_{x_*} X_{EI}$ is not the appropriate one, as shown by the following example

$$ \min \left\{ \frac{-1}{x+1} : x \in \mathbb{R}_+ \right\}. \qquad (2.66) $$

This problem has for unique stationary point ($x_*, \lambda_*$) = (0, 1) and the tangent cone at $x_*$ reads $T_{x_*} X_{EI} = \mathbb{R}_+$, so that one can take $d = 1$ as tangent direction, but $\langle L_*d, d \rangle = -2$ has not the right sign. We shall see that $\langle L_*d, d \rangle \ge 0$, but for directions $d$ in a cone that is smaller than the tangent cone.

Looking for a smaller cone, one could imagine it as a tangent cone to a smaller set than $X_{EI}$. Observe now that a solution $x_*$ to ($P_{EI}$) also minimises $f$ locally on the smaller set

$$ X_{EI}^{\equiv} := \{x \in \mathbb{E} : c_{E \cup I_*^0}(x) = 0, c_{I \setminus I_*^0}(x) < 0\}. $$

Theorem 1.33 tells us that $\langle L_*d, d \rangle \ge 0$ for all directions $d \in T_{x_*} X_{EI}$ and all associated multipliers $\lambda_* \in \Lambda_*$ (these are also multipliers of the problem consisting in minimizing $f$ on $X_{EI}$). We shall see, however, that $T_{x_*} X_{EI}$ is too small, in the sense that it does not allow us to establish sufficient optimality condition of the second order. Consider indeed the problem

$$ \min \{-x^2 : x \in \mathbb{R}_+\}. \qquad (2.67) $$

The point $x_* = 0$ is a stationary point of this problem (for arbitrary multipliers in $\mathbb{R}_+$). Since $X_{EI}^{\equiv} = \{0\}$, it follows that $T_{x_*} X_{EI}^{\equiv} = \{0\}$. Furthermore, the Hessian of
the Lagrangian at $(x_*, \lambda_*)$ is $L_* = -2$ (for any chosen multiplier). Now, $\langle L_*d, d \rangle$ is positive for all $d$ in $T_{x_*} X_{EI}^\perp \setminus \{0\} = \emptyset$, but $x_*$ not a local minimum of the problem.

The appropriate cone will turn out to be the linearizing cone $T'_{x_*}(\text{Sol}(P_{EI}))$ to the solution set of $(P_{EI})$, written as follows

$$ \text{Sol}(P_{EI}) := \{x \in X_{EI} : f(x) \le f(x_*)\}. \qquad (2.68) $$

This cone is smaller than the linearizing cone to the feasible set $X_{EI}$ at $x_*$, but sufficiently large to yield sufficient optimality condition of the second order (theorem 2.39). It is called the critical cone of the problem.

**Definition 2.35** The critical cone of problem $(P_{EI})$ at a feasible point $x \in X_{EI}$ is the polyhedral cone denoted and defined by

$$ C(x) := \{d \in \mathbb{E} : c'_{E}(x) \cdot d = 0, c'_{I^{0}(x)}(x) \cdot d \le 0, f'(x) \cdot d \le 0\}. \qquad (2.69a) $$

A direction $d \in C(x)$ is called a critical direction at $x$. We shall use the simplified notation $C_* := C(x_*)$. $\square$

Therefore, the critical cone is the linearizing cone (1.56), with the additional constraint $f'(x) \cdot d \le 0$ on its directions $d$.

In the example (2.66), $C_* = \{0\}$ is smaller than the tangent cone $T_{x_*} X_{EI} = \mathbb{R}_+$.
In the example (2.67), $C_* = \mathbb{R}_+$ is larger than the tangent cone $T_{x_*} X_{EI}^\perp = \{0\}$. It is remarkable that the optimality at the second order can be synthetised by means of the single critical cone, while the two previous problems cover very different situations.

At a stationary pair $(x_*, \lambda_*)$, the critical cone at $x_*$ also reads

$$ C_* = \{d \in \mathbb{E} : c'_{E}(x_*) \cdot d = 0, c'_{I^0}(x_*) \cdot d \le 0, f'(x_*) \cdot d = 0\}, \qquad (2.69b) $$

$$ = \{d \in \mathbb{E} : c'_{E \cup I^0}(x_*) \cdot d = 0, c'_{I^{00}}(x_*) \cdot d \le 0\}, \qquad (2.69c) $$

where we have used the index sets

$$ I_*^0 := \{i \in I : c_i(x_*) = 0\}, $$

$$ I_*^{0+} := \{i \in I_*^0 : (\lambda_*)_i > 0\}, $$

$$ I_*^{00} := \{i \in I_*^0 : (\lambda_*)_i = 0\}. $$

The expressions (2.69b) and (2.69c) can be obtained by using the optimality conditions (1.58). Observe finally that, if strict complementarity holds, in the sense (1.59), the critical cone simply reads

$$ C_* = \{d \in \mathbb{E} : c'_{E \cup I^0}(x_*) \cdot d = 0\}, \qquad (2.69d) $$

which is the linearizing cone $T'_{x_*} X_{EI}^\perp$ (it is a linear subspace in $\mathbb{E}$). Without strict complementarity, the linear subspace (2.69d) is included in $C_*$, itself included in $T'_{x_*} X_{EI}$.
### 2.2.2 Three Instructive Examples

Another difficulty in establishing second order optimality conditions for problem ($P_{EI}$) comes from the fact that the optimal multiplier intervening in the Hessian of the Lagrangian $L_* := \nabla^2_{xx} \ell(x_*, \lambda_*)$ must be chosen according to the critical direction. In others words, the proof of theorem 1.33, based on the development of the Lagrangian $\ell(\cdot, \lambda_*)$ for an a priori given multiplier $\lambda_*$ no longer works for a solution satisfying only the Mangasarian-Fromovitz constraint qualification (CQ-MF) (see exercise ?? for the constraint qualification (CQ-A) and (CQ-LI), for which such a technique can be used). We give three examples to better understand the situation and to learn how to select the correct sequence of quantifiers to apply to $d \in C_*$ and $\lambda_* \in \Lambda_*$.

Consider first the simple two variable problem

$$ \begin{cases} \min x_2 \\ x_2 \ge x_1^2. \end{cases} \qquad (2.70) $$

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

Its feasible set is represented in the right-hand side above. The problem has for unique solution $x_* = (0,0)$ and there is a unique associated multiplier $\lambda_* = 1$. Since the constraint is active at $x_*$, $(x_*, \lambda_*)$ is also a stationary pair of the equality constrained problem $\min\{x_2 : x_2 = x_1^2\}$, so that the Hessian of the Lagrangian $L_* := \nabla^2_{xx} \ell(x_*, \lambda_*) = \text{diag}(2,0)$ must be positive semi-definite on the tangent space $\{d \in \mathbb{R}^2 : d_2 = 0\}$. This is the most simple situation that can occur. Below, we shall say that the strong second order optimality conditions hold, meaning that, for any optimal multiplier $\lambda_*$ (there is a single one here), $L_*$ is positive semi-definite on the critical cone. These conditions are verified if there is a unique multiplier, like here, or when the constraint qualification conditions (CQ-A) or (CQ-LI) hold (see exercise ??).

Consider now a variation of problem (2.70), in which a superfluous constraint is added:

$$ \begin{cases} \min x_2 \\ x_2 \ge x_1^2 \\ x_2 \ge -\frac{1}{2}x_1^2. \end{cases} \qquad (2.71) $$

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

The second constraint does not modify the solution to the problem, which is again $x_* = (0,0)$, but there are now several optimal multipliers, forming the set $\Lambda_* = \{\lambda \in \mathbb{R}^2_+ : \lambda_1 + \lambda_2 = 1\}$. By taking the multiplier $\lambda_* = (1,0)$, a vertex of $\Lambda_*$, one ignores the second constraint, which is appropriate, and one has the preceding result on the positive semi-definiteness of $L_* = \text{diag}(2,0)$ on the critical cone $C_* = \{d \in \mathbb{R}^2 : d_2 = 0\}$. In contrast, with $\lambda_* = (0,1)$, the other vertex of $\Lambda_*$, the Hessian of the Lagrangian $L_* = \text{diag}(-1,0)$ is negative definite on $C_*$. This is normal; with that $\lambda_*$, the Lagrangian $\ell(\cdot, \lambda_*)$ can only see the second constraint, hence ignoring the first one, and $(0,0)$ is only a stationary point of the problem $\min\{x_2 : x_2 \ge -\frac{1}{2}x_1^2\}$, not a local minimum. Below, we shall say that the semi-strong second order optimality conditions hold, meaning that, there exists an optimal multiplier $\lambda_*$, such that $L_*$ is positive semi-definite on the critical cone.

An inequality constrained optimization problem is not always as simple as problem (2.71), in which one can locally (around the solution) discard all the constraints but
one, while keeping optimality of the solution. Sometimes, each time a constraint is discarded, the optimality is lost and this phenomenon is reflected in the second order optimality conditions. Here is an example with three variables:

$$ \left\{ \begin{array}{l} \min x_3 \\ x_3 \ge (x_1 + x_2)(x_1 - x_2) \\ x_3 \ge (x_2 + 3x_1)(2x_2 - x_1) \\ x_3 \ge (2x_2 + x_1)(x_2 - 3x_1). \end{array} \right. \qquad (2.72) $$

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

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

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

The three pictures in the right-hand side above represent, for each of the three constraints, the coordinates $(x_1, x_2)$ giving a positive value of their right-hand side. We see that, for any nonzero $(x_1, x_2)$, one of these right-hand side is positive. As a result, the unique solution to the problem is $x_* = 0$. Furthermore, the set of associated optimal multipliers is the unit simplex $\Lambda_* = \{\lambda \in \mathbb{R}_+^3 : \lambda_1 + \lambda_2 + \lambda_3 = 1\}$. Finally, the Hessian of the Lagrangian reads

$$ L(x, \lambda) = \begin{pmatrix} 2\lambda_1 - 6(\lambda_2 + \lambda_3) & 5(\lambda_2 - \lambda_3) & 0 \\ 5(\lambda_2 - \lambda_3) & -2\lambda_1 + 4(\lambda_2 + \lambda_3) & 0 \\ 0 & 0 & 0 \end{pmatrix}. $$

Whatever is the vector $\lambda_*$ chosen in $\Lambda_*$, $L_*$ is not positive semi-definite on the critical cone $C_* = \{d \in \mathbb{R}^3 : d_3 = 0\}$. Indeed, the element $(1, 1)$ of $L_*$ has the value $8\lambda_1 - 6$ and the element $(2, 2)$ is $4 - 6\lambda_1$, so that the positive definiteness of $L_*$ would require to have $\lambda_1 > 3/4$ and $\lambda_1 < 2/3$, an impossibility. Below, we shall say that the weak second order optimality conditions hold, meaning that, for all critical direction $d$, there is a multiplier $\lambda_*$ (depending on $d$), such that $\langle L_*d, d \rangle \ge 0$.

### 2.2.3 Second Order Necessary Optimality Conditions

Theorem 2.37 below states necessary optimality conditions of the second order, assuming that the Mangasarian-Fromovitz constraint qualification (CQ-MF) holds at the considered solution. This assumption is not very restrictive, since it is the weakest of the sufficient constraint qualification conditions presented in section 1.4.4. Theorem 2.39 states sufficient optimality conditions of the second order, without constraint qualification conditions.

The necessary conditions lie on the examination of the behavior of the criterion $f$ along paths $t \mapsto \xi(t)$ emanating from the considered solution $x_*$ at $t = 0$ and remaining in the feasible set $X_{EI}$ for small positive values of the parameter $t$. More paths of this type are considered, more information will be obtained. The approach is the same for the equality constrained problem ($P_E$), but it turned out that all the paths having the same tangent at the origin gave the same second order information for that problem. In the presence of inequality constraints, for a given tangent direction $d \in T_{x_*} X_{EI}$, it is useful to distinguish paths having $d = \xi'(0)$ as tangent at the origin, but having distinct curvatures $h = \xi''(0)$. Therefore, for given $d$ and $h$, one looks for paths $t \mapsto \xi(t)$ such that

$$ \xi(0) = x_*, \quad \xi'(0) = d, \quad \xi''(0) = h, \quad \xi(t) \in X_{EI}, \text{ for small } t \ge 0. \qquad (2.73) $$

Tangency and curvature must satisfy compatibility relations so that (2.73) holds. Let us guess what can be these conditions; the first three (2.74a)-(2.74c) determined below
are necessary and the last one (2.74d) has a sufficient flavor. Lemma 2.36 will show that they can be satisfied under (CQ-MF) and that, all together, they are indeed sufficient to guarantee the existence of a path satisfying (2.73).

Consider first the equality constraints: the map $\xi$ must verify $c_E(\xi(t)) = 0$, for all small $t \ge 0$. Differentiating once the vanishing map $t \mapsto c_E(\xi(t))$, we get $c'_E(\xi(t)) \cdot \xi'(t) = 0$ for all small $t \ge 0$. At $t = 0$, (2.73) gives

$$c'_{E}(x_{*}) \cdot d = 0. \qquad (2.74a)$$

Differentiating once the vanishing map $t \mapsto c'_E(\xi(t)) \cdot \xi'(t)$, we get $c''_E(\xi(t)) \cdot (\xi'(t))^2 + c'_E(\xi(t)) \cdot \xi''(t) = 0$ for all small $t \ge 0$. At $t = 0$, (2.73) gives

$$c''_{E}(x_{*}) \cdot d^{2} + c'_{E}(x_{*}) \cdot h = 0. \qquad (2.74b)$$

Consider now the inequality constraints: the map $\xi$ must verify $c_I(\xi(t)) \le 0$, for all small $t \ge 0$. If $i \in I \setminus I^0(x_*)$, $c_i(x_*) < 0$, so that $c_i(\xi(t)) \le 0$ for small $t \ge 0$ if both $c_i$ and $\xi$ are continuous. Consider now the indices $i \in I^0(x_*)$ of the active constraints at $x_*$. Taking a first order development of the map $t \mapsto c_i(\xi(t))$ around $t = 0$ and using (2.73), we get $c_i(x_*) + [c'_i(x_*) \cdot d]t + o(t) \le 0$ for all small $t \ge 0$. Since $c_i(x_*) = 0$, dividing by $t > 0$ and taking the limit when $t \downarrow 0$, we see that we must have

$$c'_{I^0}(x_*) \cdot d \le 0. \qquad (2.74c)$$

Taking a second order development of $t \mapsto c_i(\xi(t))$, we see that we must have

$$\underbrace{c_i(x_*)}_{=0} + t \underbrace{c'_i(x_*)}_{\le 0} \cdot d + \frac{t^2}{2} (c''_i(x_*) \cdot d^2 + c'_i(x_*) \cdot h) + o(t^2) \le 0.$$

Here, one cannot deduce a necessary condition on $d$ and $h$, but to have satisfaction of the previous inequality it is sufficient to impose

$$c''_{i}(x_{*}) \cdot d^{2} + c'_{i}(x_{*}) \cdot h \le -\varepsilon e, \qquad (2.74d)$$

where $\varepsilon > 0$ and $e$ is the vector of all ones.

Note that $d$ satisfying (2.74a) and (2.74c) is, by definition, a direction of the linearizing cone to $X_{EI}$ at $x_*$, hence a tangent direction to $X_{EI}$ at $x_*$ if the constraints are qualified at $x_*$.

**Lemma 2.36 (existence of a feasible path)** Let $x_* \in X_{EI}$. Suppose that $c_E$ is $C^2$ in a neighborhood of $x_*$, that $c_{I^0}$ is twice differentiable at $x_*$, and that $c_{I^*}$ is continuous at $x_*$. Suppose also that the Mangasarian-Fromovitz constraint qualification condition (CQ-MF) holds at $x_*$. Let $\varepsilon > 0$. Then,

1) for all $d \in T_{x_*} X_{EI}$, there exists $h \in E$ such that (2.74b) and (2.74d) hold,

2) for all $(d, h) \in E \times E$ satisfying (2.74), there exists a path $\xi: t \in \mathbb{R} \mapsto \xi(t) \in E$ of class $C^2$, defined for $|t|$ sufficiently small, such that (2.73) holds.

*Proof.* 1) This is a direct consequence of (CQ-MF), expressed by the point (ii) of proposition 1.39.
2) Let $A_E := c'_E(x_*)$ be the Jacobian of $c_E$ at $x_*$. This one being surjective, one can find a linear operator $Z : \mathbb{E} \to \mathbb{R}^{n-m_E}$, such that

$$ \begin{pmatrix} A_E \\ Z \end{pmatrix} : \mathbb{E} \to \mathbb{R}^n \text{ is bijective.} \qquad (2.75) $$

Note that this property implies that $\mathcal{N}(A_E) \cap \mathcal{N}(Z) = \emptyset$ and $\mathcal{N}(A_E) + \mathcal{N}(Z) = \mathbb{E}$, so that $\mathbb{E}$ can be written as a direct sum: $\mathbb{E} = \mathcal{N}(A_E) \oplus \mathcal{N}(Z)$.

For $d \in T_{x_*} X_{EI}$ and $h \in \mathbb{E}$ given by point 1, one considers the function $F : \mathbb{E} \times \mathbb{R} \to \mathbb{R}^n$ defined at $(\xi, t) \in \mathbb{E} \times \mathbb{R}$ by

$$ F(\xi, t) = \begin{pmatrix} c_E(\xi) \\ Z(\xi - x_* - td - \frac{t^2}{2}h) \end{pmatrix}. $$

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

If $F(\xi, t) = 0$, $\xi \in \mathbb{E}$ is necessarily a point on the manifold $c_E^{-1}(0)$, while $\xi - x_* - td - (t^2/2)h$ is a displacement in the null space of $Z$, which is complementary to the null space of $A_E$, itself tangent to the manifold $c_E^{-1}(0)$ at $x_*$. The path $t \mapsto \xi(t)$ is obtained by imposing the nullity of $F(\xi, t)$ and using the implicit function theorem. By assumption, the function $F$ is of class $C^2$ in a neighborhood of $(x_*, 0)$, $F(x_*, 0) = 0$ and $F'_\xi(x_*, 0)$ is nonsingular. By the implicit function theorem, there exists a function $t \mapsto \xi(t)$, defined for $|t|$ small, of class $C^2$, such that $F(\xi(t), t) = 0$ for all small $|t|$ and $\xi(0) = x_*$. By differentiating once $F(\xi(t), t) = 0$ at $t = 0$, one gets

$$ \begin{pmatrix} A_E \\ Z \end{pmatrix} \xi'(0) = \begin{pmatrix} 0 \\ Zd \end{pmatrix} = \begin{pmatrix} A_E \\ Z \end{pmatrix} d, $$

because $A_E d = 0$. Therefore, (2.75) shows that $\xi'(0) = d$. By differentiating twice $F(\xi(t), t) = 0$ at $t = 0$, one gets

$$ \begin{pmatrix} A_E \\ Z \end{pmatrix} \xi''(0) = \begin{pmatrix} -c_E''(x_*) \cdot d^2 \\ Zh \end{pmatrix} = \begin{pmatrix} A_E \\ Z \end{pmatrix} h, $$

by (2.74b). Therefore, $\xi''(0) = h$. Finally, $\xi(t) \in X_{EI}$ for small $t \ge 0$, thanks to the choice of $h$ verifying (2.74c) and (2.74d). $\square$

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

**Theorem 2.37 (NC2 for ($P_{EI}$) with (CQ-MF))** Suppose that $x_*$ is a local solution to ($P_{EI}$), that $f$ and $c_E$ are $C^2$ in a neighborhood of $x_*$, that $c_{I_*}^0$ is twice differentiable at $x_*$, that $c_{I_*}^\infty$ is continuous at $x_*$, and that the Mangasarian-Fromovitz constraint qualification condition (CQ-MF) holds at $x_*$. Then
$$ \forall d \in C_* : \max_{\lambda_* \in \Lambda_*} \langle L_*d, d \rangle \ge 0, \qquad (2.76) $$

where $L_* := \nabla^2_{xx} \ell(x_*, \lambda_*)$ is the Hessian of the Lagrangian.

*Proof.* Let $d \in C_* \subseteq T'_{x_*} X_{EI}$ be fixed. For each choice of $h \in E$ verifying (2.74b) and (2.74d), lemma 2.36 ensures the existence of a path $t \mapsto \xi(t)$ of class $C^2$ satisfying (2.73). The direction $h$ will be chosen to get the best information. Let us see this. A second order development of $t \mapsto f(\xi(t))$ at $t = 0$ reads

$$ f(\xi(t)) = f(x_*) + t f'(x_*) \cdot d + \frac{t^2}{2} [f''(x_*) \cdot d^2 + f'(x_*) \cdot h] + o(t^2). $$

By optimality, $f(\xi(t)) \ge f(x_*)$, for $t \ge 0$ small (since then $\xi(t) \in X_{EI}$), and $f'(x_*) \cdot d \le 0$ (since $d \in C_*^0$). Therefore,

$$ 0 \le \frac{t^2}{2} [f''(x_*) \cdot d^2 + f'(x_*) \cdot h] + o(t^2). $$

Dividing by $t^2 > 0$ and taking the limit when $t \downarrow 0$, we get

$$ 0 \le f''(x_*) \cdot d^2 + f'(x_*) \cdot h. \qquad (2.77) $$

To get as much information as possible, it is better to find an $h$ minimizing the right-hand side of the above inequality. This remark leads us to the following linear problem in $h \in E$:

$$ \left\{ \begin{array}{ll} \inf & f'(x_*) \cdot h + f''(x_*) \cdot d^2 \\ c'_i(x_*) \cdot h + c''_i(x_*) \cdot d^2 = 0, & \text{for } i \in E \\ c'_i(x_*) \cdot h + c''_i(x_*) \cdot d^2 + \epsilon \le 0, & \text{for } i \in I_*^0. \end{array} \right. \qquad (2.78) $$

This problem is feasible (i.e., its feasible set is nonempty, thanks to (CQ-MF)) and bounded (by zero). Therefore, by (1.63), the problem has a solution and by the sentence after (1.66), there is no duality gap between its optimal value and the optimal value of its dual: these are both equal and nonnegative by (2.77). The dual problem is the following linear optimization problem in $\lambda \in \mathbb{R}^m$

$$ \left\{ \begin{array}{l} \sup \langle L(x_*, \lambda) d, d \rangle + \epsilon \|\lambda_I\|_1 \\ \nabla_x \ell(x_*, \lambda) = 0 \\ \lambda_I^0 \ge 0 \\ \lambda_I^* = 0. \end{array} \right. $$

Observe now that the feasible set of this last problem is the set of optimal multipliers $\Lambda_*$. Therefore, we have shown that

$$ 0 \le \max_{\lambda_* \in \Lambda_*} \langle L_*d, d \rangle + \epsilon \|(\lambda_*)_I\|_1. $$

We have used the operator “max”, since $\Lambda_*$ is ocmpact by (CQ-MF). Since $\epsilon > 0$ is arbitrary and since $\Lambda_*$ is compact, one gets the result by taking $\epsilon \to 0$. $\square$
When (CQ-MF) holds at $x_*$, $\Lambda_*$ is compact, so that the condition (2.76) also reads

$$ \forall d \in C_*, \exists \lambda_* \in \Lambda_* : \langle L_*d, d \rangle \ge 0. \qquad (2.79a) $$

It is then said that the weak necessary optimality conditions of the second order hold. They are satisfied under the assumptions given by theorem 2.37. This is the case in the example 2.72. If stronger conditions holds, namely

$$ \exists \lambda_* \in \Lambda_*, \forall d \in C_* : \langle L_*d, d \rangle \ge 0, \qquad (2.79b) $$

it is said that the semi-strong necessary optimality conditions of the second order hold. They are satisfied in example 2.71. If even stronger conditions holds, namely

$$ \forall \lambda_* \in \Lambda_*, \forall d \in C_* : \langle L_*d, d \rangle \ge 0, \qquad (2.79c) $$

it is said that the strong necessary optimality conditions of the second order hold. They are satisfied in example 2.70.

The strong second order necessary conditions of optimality (2.79c) are clearly satisfied when there is a unique optimal multiplier, since then (2.79a), (2.79b), and (2.79c) contain the same information and (2.79a) holds by theorem 2.37. These conditions are also satisfied when some constraint qualification conditions stronger than (CQ-MF) are satisfied. The next theorem claims that this is the case when (CQ-A) or (CQ-LI) holds; this result was the one presented in most textbooks on nonlinear optimization prior to 1980, say; see [53, 95, 34, 8; 1968-1976] for instance.

**Theorem 2.38 (NC2 for ($P_{EI}$) with (CQ-A) or (CQ-LI))** Suppose that $x_*$ is a local solution to ($P_{EI}$), that $f$ and $c$ are twice differentiable at $x_*$, and that the constraint qualification conditions (CQ-A) or (CQ-LI) hold at $x_*$. Then, the strong second order necessary conditions of optimality (2.79c) hold.

*Proof.* See exercise ??.

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

The numerical verification of the necessary optimality conditions of the second order is not an easy task. Even when the semi-strong conditions (2.79b) hold for an optimal multiplier $\lambda_*$, one has to verify that the quadratic form $d \mapsto \langle L_*d, d \rangle$ associated with the Hessian of the Lagrangian is positive semi-definite on the critical cone $C_*$, which is polyhedral; in other words, $L_*$ is $C_*$-copositive [70, 16, 68]. In all generality, such a verification is an NP-hard problem [104, 43]. Now, if strict complementarity also holds, the critical cone reduces to the linear subspace (2.69d) and the verification of the positive semi-definiteness of $d \mapsto \langle L_*d, d \rangle$ on this subspace is then a simple linear algebra operation.

### 2.2.4 Second Order Sufficient Optimality Conditions

The next proposition gives sufficient conditions of optimality of the second order for problem ($P_{EI}$). It is worth noting that these do not call on a constraint qualification assumption. The fact that the critical cone also intervenes in these conditions is an
evidence of its relevance. The inequality (2.81) is known as the quadratic growth property. It tells us that $f$ grows at least quadratically on the “interior” of the feasible set $X_{EI}$.

**Theorem 2.39 (SC2 for ($P_{EI}$))** Suppose that $f$ and $c_{E \cup I_*^0}$ are differentiable on a neighborhood of a point $x_* \in \mathbb{E}$ and twice differentiable at $x_*$. Suppose also that the set $\Lambda_*$ of optimal multipliers $\lambda_*$ such that $(x_*, \lambda_*)$ verifies the KKT optimality conditions (1.58) is nonempty. Suppose finally that the following equivalently properties hold ($\| \cdot \|$ is an arbitrary norm)

$$ \forall d \in C_* \setminus \{0\}, \exists \lambda_* \in \Lambda_* : \langle L_*d, d \rangle > 0, \quad (2.80a) $$

$$ \exists \bar{\gamma} > 0, \forall d \in C_*, \exists \lambda_* \in \Lambda_* : \langle L_*d, d \rangle \ge \bar{\gamma} \|d\|^2. \quad (2.80b) $$

Then, for all $\gamma \in [0, \bar{\gamma})$, there exists a neighborhood $V$ of $x_*$ such that

$$ \forall x \in (X_{EI} \cap V) \setminus \{x_*\} : \quad f(x) > f(x_*) + \frac{\gamma}{2} \|x - x_*\|^2. \quad (2.81) $$

In particular, $x_*$ is a strict local minimum of ($P_{EI}$).

*Proof.* Let us first show that (2.80a) and (2.80b) are equivalent. It is clear that (2.80b) implies (2.80a). Let us show the contrapositive of the reverse implication, assuming that (2.80b) does not hold. Then, there would exist a sequence $\{d_k\} \subset C_*$ such that

$$ \|d_k\| = 1 \quad \text{and} \quad \langle L(x_*, \lambda_*)d_k, d_k \rangle \to 0, $$

where $\lambda_*$ is arbitrary fixed in $\Lambda_*$. Since $C_*$ is closed, one could extract a converging subsequence $d_k \to d \in C_* \setminus \{0\}$. Then, for any $\lambda_* \in \Lambda_*$, we get $\langle L_*d, d \rangle = 0$, for some $d \in C_* \setminus \{0\}$. This contradicts (2.80a).

We prove the main claim of the theorem by contradiction, assuming that one can find $\gamma \in [0, \bar{\gamma})$ and a sequence $\{x_k\} \subset X_{EI}$ such that $x_k \to x_*$, $x_k \neq x_*$, and

$$ f(x_k) \le f(x_*) + \frac{\gamma}{2} \|x_k - x_*\|^2. \quad (2.82) $$

Extracting a subsequence if needed, one can assume that with $t_k := \|x_k - x_*\|$, there holds

$$ \frac{x_k - x_*}{t_k} \to d. $$

Therefore, $d \in T_{x_*} X_{EI} \setminus \{0\}$. Furthermore, from (2.82) and $f(x_k) = f(x_*) + f'(x_*) \cdot (x_k - x_*) + o(\|x_k - x_*\|)$ (differentiability of $f$ at $x_*$, one gets $f'(x_*) \cdot d \le 0$. We have shown that $d \in C_* \setminus \{0\}$.

To get a contradiction, we take a second order expansion of the Lagrangian $\ell(\cdot, \lambda_*)$, where $\lambda_*$ is the multiplier associated with $d$ by (2.80b):

$$ \ell(x_k, \lambda_*) = \ell(x_*, \lambda_*) + \frac{1}{2} \ell''_{xx}(x_*, \lambda_*) \cdot (x_k - x_*)^2 + o(\|x_k - x_*\|^2). $$

By the stationarity of $x_*$ (see (1.58)), it follows that $\ell(x_*, \lambda_*) = f(x_*)$. By the feasibility of $x_k$ and $(\lambda_*)_I \ge 0$, one gets $\ell(x_k, \lambda_*) \le f(x_k)$, which does not exceed $f(x_*) + \frac{\gamma}{2} \|x_k - x_*\|^2$ by (2.82). Therefore,
## 2. Optimality Conditions

$$ \frac{\gamma}{2} \|x_k - x_*\|^2 \geq \frac{1}{2} \langle L_*(x_k - x_*), x_k - x_* \rangle + o(\|x_k - x_*\|^2). $$

Dividing by $t_k^2$ and taking the limit yield

$$ \langle L_*d, d \rangle \leq \gamma \|d\|^2, $$

which contradicts (2.80b), since $\gamma < \bar{\gamma}$ and $d \in C_*\setminus\{0\}$. $\square$

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

Condition (2.81) is known as the quadratic growth property of $f$ in $X_{EI}$ around $x_*$. The equivalent conditions (2.80a) and (2.80b) are called the weak sufficient optimality conditions of the second order. Obviously, the conclusion of the theorem is still true if in (2.80a), $\lambda_*$ can be taken independently of $d$:

$$ \exists \lambda_* \in \Lambda_*, \forall d \in C_*\setminus\{0\} : \langle L_*d, d \rangle > 0. \qquad (2.83) $$

It is then said that semi-strong sufficient optimality conditions of the second order hold. Obviously also, the conclusion of the theorem remains true, if $\lambda_*$ can be chosen arbitrarily:

$$ \forall \lambda_* \in \Lambda_*, \forall d \in C_*\setminus\{0\} : \langle L_*d, d \rangle > 0. \qquad (2.84) $$

It is then said that strong sufficient optimality conditions of the second order hold.

A natural question to ask is whether the conditions of the previous theorem not only ensure that $x_*$ is a strict local minimum, but that it is also an isolated minimum. The answer is negative, as shown by the following counter-example [121; (2.5)].

**Counter-example 2.40 (strict but nonisolated minimum)** Consider the following problem in $x \in \mathbb{R}$:

$$ \min \{\frac{1}{2} x^2 : c(x) = 0\}, \quad \text{where} \quad c(x) = \begin{cases} x^6 \sin \frac{1}{x} & \text{if } x \neq 0 \\ 0 & \text{otherwise.} \end{cases} $$

The conditions of theorem 2.39 are satisfied at the solution $x_* = 0$ with the multiplier $\lambda_* = 0$ since $\ell''_{xx}(x_*, \lambda_*) = 1$ but $x_*$ is not an isolated minimum. Indeed, 0 is an accumulation point of the feasible set, which reads $\{0\} \cup \{k\pi : k \in \mathbb{N}\}$, and every feasible point is a local minimizer. $\square$

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

The undesirable situation of counter-example 2.40 would not occur if the (CQ-MF) constraint qualification was added to the assumptions of the theorem; see [121; § 2].

## Notes

There are many ways to get second order conditions of optimality. The one followed here, which is based on the design of paths in the feasible set, on the expression of the behavior of the objective along these path, and on the dualization of this expression is the one followed in the short account of Gauvin [60].

Second order optimality conditions for $(P_{EI})$ were given in [53; 1968] under restrictive conditions. The conditions related here can be found in [72, 13, 15; 1979-1982]. See also the exact penalty viewpoint of Burke [28].
Exercises

**2.2.1. Second order optimality conditions.** Consider the following nonlinear optimization problem in $x \in \mathbb{R}^2$:

$$ \begin{cases} \min -\frac{1}{2}(x_1^2 + x_2^2) \\ x_2 \ge x_1^2 - 1 \\ x_1 \ge 0. \end{cases} $$

Using the Lagrangian $\ell: \mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R}$ defined at $(x, \lambda)$ by

$$ \ell(x, \lambda) = -\frac{1}{2}(x_1^2 + x_2^2) + \lambda_1(x_1^2 - x_2 - 1) + \lambda_2(-x_1), $$

it can be shown that the first order optimality conditions are verified by the following primal-dual pairs

$$ x = 0 \quad \text{and} \quad \lambda = 0, \qquad (2.85a) $$

$$ x = (0, -1) \quad \text{and} \quad \lambda = (1, 0), \qquad (2.85b) $$

$$ x = (\sqrt{2}/2, -1/2) \quad \text{and} \quad \lambda = (1/2, 0). \qquad (2.85c) $$

Using the second order optimality conditions, determine analytically which of the points in (2.85) are (strict) local minimum, (strict) local maximum, or undetermined.
<figure><img src="image_28.png" /></figure>
# 3 Perturbation Analysis

## 3.1 Linear System ▲

## 3.2 Nonlinear System ▲

## 3.3 Optimization ▲

Let $\mathbb{E}$ and $\mathbb{F}$ be a vector spaces, $\Omega$ be an open convex set of $\mathbb{E}$, and $\mathcal{P}$ be a topological space. Consider the family of optimization problems

$$ (P_K^p) \quad \begin{cases} \min_x f(x, p) \\ c(x, p) \in K, \end{cases} $$

parametrized by $p \in \mathcal{P}$, in which $f: \Omega \times \mathcal{P} \to \mathbb{R}$ and $c: \Omega \times \mathcal{P} \to \mathbb{F}$ are smooth functions, and $K \subseteq \mathbb{F}$ is a nonempty closed convex cone. This problem will be viewed as a perturbation of a problem of the form (2.1), that is supposed to be recovered when $p$ is set to some reference parameter $p_0 \in \mathcal{P}$, in the sense that $f(\cdot, p_0) = f(\cdot)$ and $c(\cdot, p_0) = c(\cdot)$. Here, the set $G = K$ of problem $(P_G)$ is supposed to be a cone, which was not necessarily the case in chapter 2.

We assume that, for some given point $x_0 \in \Omega$, the following smoothness properties of $f$ and $c$ hold:

* for all $p$ in $\mathcal{P}$, $f(\cdot, p)$ and $c(\cdot, p)$ are differentiable on $\Omega$,

* $f(\cdot, p_0)$ and $c(\cdot, p_0)$ are twice continuously differentiable on $\Omega$,

* $f, c, f'_x$, and $c'_x$ are continuous on $\Omega \times \mathcal{P}$.

We have denoted by $f'_x$ and $c'_x$ the derivatives of $f$ and $c$, respectively, with respect to $x$. Similarly, we denote the second derivatives with respect to $x$ of $f$ and $c$ by $f''_{xx}$ and $c''_{xx}$, respectively.

From theorem 2.6 and proposition 2.21, it is known that at a local minimizer $x \in \Omega$ of $(P_K^p)$ at which the following constraint qualification (CQ-R) holds

$$ 0 \in \text{int}(c(x, p) + c'_x(x, p)\mathbb{E} - K), \quad (3.1) $$

one can associate a multiplier $\lambda \in \mathbb{F}$ such that

$$ \left\{ \begin{array}{l} \nabla_x f(x, p) + c'_x(x, p)^* \lambda = 0 \\ K^- \ni \lambda \perp c(x, p) \in K. \end{array} \right. \quad (3.2) $$

Let us introduce the *multiplier multifunction* $\Lambda: \Omega \times \mathcal{P} \to \mathbb{F}$, which is defined at $(x, p) \in \Omega \times \mathcal{P}$ by
$$ \Lambda(x, p) := \{ \lambda \in \mathbb{F} : (x, p, \lambda) \text{ satisfies (3.2)} \}, $$

as well as the stationary point multifunction $\Sigma : \mathcal{P} \to \Omega$, which is defined at $p \in \mathcal{P}$ by

$$ \Sigma(p) := \{x \in \Omega : \Lambda(x, p) \neq \emptyset\}. $$

**Proposition 3.1 (stability of $(P_K)$ with a polyhedral $K$) In the framework**

presented above, assume that

(i) $\mathcal{P}$ is a subset of a vector space,

(ii) $K$ is a convex polyhedral cone,

(iii) $f'_x$, $c$ and $c'_x$ are Lipschitz continuous near some $(x_0, p_0) \in \Omega \times \mathcal{P}$,

(iv) (3.1) holds for $(x, p) = (x_0, p_0)$, and

(v) there is a $\lambda_0 \in \Lambda(x_0, p_0)$ such that the strong SC2 holds for $(P_K^{p_0})$.

Then, there exists a constant $L \ge 0$, such that, for all $p$ near $p_0$, one has

1) $\Sigma(p) \neq \emptyset$,

2) for all $x \in \Sigma(p)$ near $x_0$ and all $\lambda \in \Lambda(x, p)$, one has

$$ \mathrm{dist}((x, \lambda), \{x_0\} \times \Lambda(x_0, p_0)) \le L \|p - p_0\|. $$

## Notes

Proposition 3.1 rephrases corollary 4.3 in [121; 1982].
# 4 A Few Methods for Nonsmooth Systems

This chapter presents and analyzes algorithms to solve various nonsmooth “systems” by “pseudo-linearization” techniques. The term systems is vague, but may be viewed as “mathematical models” in the discussion that follows; the types of systems considered in this chapter will be clarified in section 4.1.1; they includes variational problems, variational inequality problems, complementarity problems, first order optimality conditions of an optimization problem, nonsmooth equations, to mention a few of the most important ones. The important qualifier nonsmooth means that these systems are defined by functions that are not differentiable in the classical sense of Fréchet, or are defined by multifunctions. The term pseudo-linearization refers to the fact that this lack of differentiability makes a true linearization impossible, but that some kind of surrogate is nevertheless available.

It may be instructive to gather the various approaches presented in this chapter into two classes. Both classes are constituted of algorithms that have a fast speed of convergence in a neighborhood of a regular solution (a concept to be defined, which depends on the considered system and algorithm), which is due to the pseudo-linearization of the systems they solve.

* We gather into the first class, the methods that try to have a rather precise description of the system to solve around the current iterate. The amount of information collected there gives to the iteration a nonlinear nature. This results in algorithms that have a rather complex iteration, which may require a rather significant computing effort to be processed (usually more than a single linear system to solve, certainly). An advantage of these algorithms is that they are often rather easy to globalize, meaning that one can design convergent versions of these algorithms even though the starting iterate is far from a solution.

The first example of methods of this class is the Josephy-Newton algorithm for solving functional inclusions. It is analyzed in section 4.1. Its rather precise description at the current iterate of the system to solve is obtained by keeping unaltered the part of the system that is not easy to linearize, the one that involves a multifunction.

The SQP algorithm of section 5.1 is also a member of the first class of approaches, since it can be viewed as an application of the Josephy-Newton algorithm to the first order optimality system of the optimization problem ($P_{EI}$), which has equality and inequality constraints. The SQP algorithm is one of the most frequently used methods to solve ($P_{EI}$). It was mainly developed in the mid-1970s.

The B-Newton algorithm of section 4.2, which solves a nonsmooth system of equations, has also a complex iteration. This one is due to the nonlinear nature of the
B-differential that is used to compute the new iterate. When applied to some re-
formulation of the first optimality conditions of a nonlinear optimization problem,
however, it results in a simpler iteration than the SQP algorithm.

* We gather into the second class of methods, those that have a very economical iteration, in the sense that a single linear system needs to be solved at each iteration.

The semismooth algorithm of section 4.4, which solves a nonsmooth system of equations, belongs to this second class. The linear system to solve at the current iteration comes from a choice of local first order approximation of the nonsmooth system. Despite this poor description, a fast local convergence is also possible, which is a surprising and remarkable fact. On paper, the description of the algorithm is simple, but in practice the choice of the linear system is not always easy to determine. It may also be inappropriate, when the globalization of the method is an issue.

Interior point methods in linear, conic, or nonlinear optimization also belong to this class of methods, but we shall see them in another chapter, chapter ??.

## 4.1 Josephy-Newton Algorithm for Functional Inclusions

The Josephy-Newton (JN) algorithm has been designed to solve functional inclu-
sions. This type of systems is described in section 4.1.1; they include variational
problems (section 4.1.1), variational inequality problems (section 4.1.1), complemen-
tarity problems (section 4.1.1), and various systems of optimality conditions (the
Peano-Kantorovich condition of the general problem ($P_X$) and the first order nec-
essary optimality conditions of the problems ($P_G$) or ($P_{EI}$); see section 4.1.1). The
algorithm is described in section 4.1.2, its asymptotic behavior is analyzed in sec-
tion 4.1.4, and conditions ensuring its local convergence are provided in section 4.1.5.

### 4.1.1 A Gallery of Problems

#### Functional Inclusion Problem

Let $\mathbb{E}$ and $\mathbb{F}$ be two vector spaces having the same finite dimension. In this section, we are interested in solving a *functional inclusion problem*<fnref n="1" />, which, by definition, is a problem that reads in the following manner:

$$ (P_{\mathbb{F}1}) \quad F(x) + N(x) \ni 0. \qquad (4.1) $$

In this problem model, $F: \mathbb{E} \to \mathbb{F}$ is a function that is supposed to be differentiable and $N: \mathbb{E} \to \mathbb{F}$ is a multifunction "sufficiently simple". This system means that one has to determine a point $x$ in $\mathbb{E}$ such that the set $F(x) + N(x)$ contains the zero element of $\mathbb{F}$; one can also say that $x$ is sought such that the vector $-F(x)$ is in the set $N(x)$. If $N$ is the zero multifunction, one recovers a nonlinear system to solve

<footnote n="1">¹ This is the author's own terminology. One more frequently finds the vaguer terms *generalized equation* [120, 46] or *variational inclusion* [2].</footnote>
$F(x) = 0$. One could also incorporate $F$ in $N$, hence removing the presence of the function value $F(x)$ in ($P_{FI}$), without loss of generality, but the linearization method presented in section 4.1.2 takes advantage of this smooth function; furthermore, $N$ could not be “simple” with this incorporation.

As we shall see, the system ($P_{FI}$) models many problems.

## Variational Problem

A variational problem<fnref n="2" /> is a functional inclusion problem of the form ($P_{FI}$), in which $\mathbb{F} = \mathbb{E}$ and the multifunction $N: \mathbb{E} \to \mathbb{E}$ is the normal cone map $N_X$ to a nonempty closed set $X \subseteq \mathbb{E}$ (the notation $N$ in ($P_{FI}$) comes from this problem); in other words, $N_X(x)$ is the normal cone (1.50) to $X$ at $x$. The problem reads and can be viewed as below:

$$ (P_v) \qquad F(x) + N_X(x) \ni 0. \qquad (4.2) $$

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

With the convention that $N_x X = \emptyset$ when $x \notin X$, one looks for a point $x \in X$ such that $-F(x)$ is in the normal cone to $X$ at $x$.

The first order necessary condition of optimality of Peano-Kantorovich (1.51) is a variational problem of the form ($P_v$), in which $F$ is the gradient of a function $f: \mathbb{E} \to \mathbb{R}$. However, unless the feasible set $X$ is simple, its normal cone is often too complex for allowing the problem to be solved by the Josephy-Newton algorithm introduced in section 4.1.2 below.

## Variational Inequality Problem

A variational inequality problem is a variational problem of the form ($P_v$), in which the set $X \equiv C$ is nonempty, closed, and convex. Then, according to (1.23), problem ($P_v$), which reads $-F(x) \in N_C(x)$, can also be written

$$ (P_{vi}) \qquad \begin{cases} x \in C \\ \langle F(x), y - x \rangle \ge 0, \quad \forall y \in C. \end{cases} \qquad (4.3) $$

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

The presence of the infinite number of inequalities induces the problem name. Now, it is usually better not to see this problem as one with that infinite number of inequalities, but to see it in terms of multifunction like in ($P_v$).

The system (4.3) can be written like a nonsmooth equation in $x$ (see exercise 4.1.2)

$$ P_C(x - F(x)) - x = 0. \qquad (4.4) $$

This reformulation of the variational inequality problem is not necessarily advantageous, since the use of the projector $P_C$ on $C$ in (4.4) often yields a system that lacks appropriate differentiability properties (see remark 1.12), at a point that the usual

<footnote n="2">² One also encounters the denomination variational condition [126, 124].</footnote>
techniques for solving equations cannot be used. This point of view may change for particular convex sets C.

An equilibrium problem is a significant extension of a variational inequality problem. Being given a set X of a topological space E and a function f : X × X → R, one seeks a point x such that

$$ \begin{cases} x \in X \\ f(x, y) \ge 0, \quad \forall y \in X. \end{cases} \qquad (4.5) $$

We will not talk about this problem in these notes.

**Proposition 4.1 (existence of solution for (Pvi))** Consider the variation inequality problem (Pvi) in (4.3) with a nonempty closed convex set C, on which F is continuous. Then, the set of solutions to (Pvi) is closed. This solution set is also nonempty if C is bounded.

Proof.

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

## Complementarity Problem

A complementarity problem is a functional inclusion problem of the form (PFI), in which F is a Euclidean space and the multifunction N is defined at x ∈ E by N(x) = NK+(G(x)), where G : E → F, K is a nonempty closed convex cone of F, K+ is the positive dual cone of K in F, and NK+ is the application “normal cone to K+”. Then, by proceeding in the same way as for obtaining (Pvi), the function inclusion becomes

$$ G(x) \in K^{+} \quad \text{and} \quad \left( \forall y \in K^{+} : \langle F(x), y - G(x) \rangle \ge 0 \right). $$

Next, taking y = 2G(x) and y = G(x)/2 (or zero, since K+ is closed) as test elements in K+ above, we see that the problem can be written

$$ (P_c) \qquad K^+ \ni G(x) \perp F(x) \in K. \qquad (4.6) $$

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

This expression means that three conditions must be satisfied at the sought x: F(x) ∈ K, G(x) ∈ K+, and ⟨F(x), G(x)⟩_F = 0.

## Constrained Optimization

Let E and F be two Euclidean vector spaces. Consider the problem of the form (PG):

$$ \begin{cases} \min f(x) \\ c(x) \in K, \end{cases} \qquad (4.7) $$
in which $f: \mathbb{E} \to \mathbb{R}$ and $c: \mathbb{E} \to \mathbb{F}$ are differentiable maps and $K$ is a nonempty closed convex cone of $\mathbb{F}$. Its optimality conditions at a local solution $x \in \mathbb{E}$ is the following system in $(x, \lambda) \in \mathbb{E} \times \mathbb{F}$ (see theorem 2.6, in the case when $G \equiv K$ is a closed convex cone)

$$ \nabla f(x) + c'(x)^*\lambda = 0 \quad \text{and} \quad K^- \ni \lambda \perp c(x) \in K. \qquad (4.8) $$

This optimality system can also be written as a complementarity problem of the form $(P_{CP})$, whose objects are topped by a tilde: the spaces are $\tilde{\mathbb{E}} = \tilde{\mathbb{F}} := \mathbb{E} \times \mathbb{F}$, the function $\tilde{G} := I_{\tilde{\mathbb{E}}}$, while the function $\tilde{F} : \tilde{\mathbb{E}} \to \tilde{\mathbb{E}}$ and the set $\tilde{K} \subseteq \tilde{\mathbb{E}}$ are defined as follows

$$ \tilde{F}(\tilde{x}) = \begin{pmatrix} \nabla f(x) + c'(x)^*\lambda \\ -c(x) \end{pmatrix} \quad \text{and} \quad \tilde{K} = \{0_{\mathbb{E}}\} \times (-K), \qquad (4.9a) $$

where we have set $\tilde{x} := (x, \lambda)$. Since $\tilde{K}^+ = \mathbb{E} \times K^-$, the system (4.8) reads

$$ \tilde{K}^+ \ni \tilde{x} \perp \tilde{F}(\tilde{x}) \in \tilde{K}, \qquad (4.9b) $$

which is of the form of $(P_{CP})$ in (4.6).

Since the optimization problem $(P_{EI})$, with equality and inequality constraints, can be written like (4.7) with $\mathbb{F} = \mathbb{R}^{m_E} \times \mathbb{R}^{m_I}$, $c = (c_E, c_I) : \mathbb{E} \to \mathbb{R}^{m_E} \times \mathbb{R}^{m_I}$, and $K = \{0_{\mathbb{R}^{m_E}}\} \times \mathbb{R}^{m_I}$, its optimality conditions, the KKT system (1.58), can also be written as a complementarity problem (4.9b). From (4.9a), it suffices to take $\tilde{x} := (x, \lambda)$ and

$$ \tilde{F}(\tilde{x}) := \begin{pmatrix} \nabla f(x) + c'(x)^*\lambda \\ -c(x) \end{pmatrix} \quad \text{and} \quad \tilde{K} = \{0_{\mathbb{E}}\} \times (\{0_{\mathbb{R}^{m_E}}\} \times \mathbb{R}_+^{m_I}). \qquad (4.10) $$

### Equality and Inequality Systems

When $N$ is the constant multifunction $x \in \mathbb{E} \mapsto \{0_{\mathbb{R}^{m_E}}\} \times \mathbb{R}_+^{m_I} \subseteq \mathbb{R}^m \equiv \mathbb{F}$, where $E$ and $I$ form a partition of $[1:m]$, the functional inclusion problem $(P_{FI})$ amounts to find a point $x \in \mathbb{E}$ satisfying a system of equalities and inequalities:

$$ F_E(x) = 0 \quad \text{and} \quad F_I(x) \le 0. $$

Nevertheless, as we shall see, the algorithmic approach of section 4.1 will not be immediately workable to find a solution to such a system, because its solutions are usually not isolated.

### 4.1.2 The Josephy-Newton Algorithm

The Josephy-Newton (JN) algorithm is an iterative method to solve the functional inclusion problem $(P_{FI})$ in (4.1). It generates a sequence $\{x_k\} \subseteq \mathbb{E}$ as follows. Knowing $x_k \in \mathbb{E}$, the next iterate $x_{k+1} \in \mathbb{E}$ is computed as a solution in $x$ (if this is possible!) to the functional inclusion $(P_{FI})$, “linearized” in $x$, namely

$$ F(x_k) + F'(x_k) \cdot (x - x_k) + N(x) \ni 0. \qquad (4.11) $$

The linearization is only partial: whilst $F$ is linearized at $x_k$ like in Newton's algorithm (1.68), the multifunction $N$ is left unchanged. Such a linearization of $(P_{FI})$ is named a
JN linearization below. The system (4.11) to solve in $x_{k+1}$ at each iteration is therefore often “nonlinear”, meaning that it is not enough to solve a single linear system to get one of its solutions. As a result, the algorithm is generally more expensive than the standard Newton algorithm (1.68) for the system of equations (1.67). One can also say that the algorithm captures from the system, much more than the linear approximation of its functions, since $N$ is used without approximation. For future references, let us write explicitly the functional inclusion verified by $x_{k+1} \in \mathbb{E}$:

$$F(x_k) + F'(x_k) \cdot (x_{k+1} - x_k) + N(x_{k+1}) \ni 0. \qquad (4.12)$$

Now, it may arise that no algorithm is known to solve (4.11) efficiently; in which case, it is necessary to turn towards other solution approaches.

One can now understand the assumptions required on $F$ and $N$ after (4.1). The function $F$ must be differentiable so that its derivative operator $F'(x_k)$ can be used in the definition (4.12) of the algorithm. The multifunction $N$ needs not have differentiability properties, but must be simple enough to make the computation of a solution to (4.12) not too expensive.

### 4.1.3 Regularity

The standard quadratic convergence result of Newton’s method for finding a zero of a nonlinear system of equations $F(x) = 0$, the one of theorem 1.48, requires the nonsingularity of $F'(x_*)$. We would like to extend this assumption to the more complex functional inclusion system ($P_{FI}$) in (4.1), which is not straightforward with the presence of the multifunction $N$, in order to ensure quadratic convergence of the Josephy-Newton algorithm. Getting such an extension is often a matter of rephrasing.

Consider the system $F(x) = 0$, for which we rephrase the property of the injectivity of $F'(x_*)$, which is equivalent to the nonsingularity of $F'(x_*)$ when $\dim \mathbb{E} = \dim \mathbb{F}$. Observe that, when $F(x_*) = 0$, the definition of the assumed differentiability of $F$ implies that

$$F(x) = F'(x_*)(x - x_*) + o(\|x - x_*\|).$$

Now, if $F'(x_*)$ is injective, this development implies that, for some constant $\sigma_1 > 0$ and $\sigma_2 > 0$, independent of $x$,

$$\|x - x_*\| \le \sigma_1 \quad \implies \quad \|x - x_*\| \le \sigma_2 \|F(x)\|.$$

This property can also be written as follows: there are constants $\sigma_1 > 0$ and $\sigma_2 > 0$ such that

$$\left.
\begin{array}{l}
(x, p) \in \mathbb{E} \times \mathbb{F} \\
F(x) = p \\
\|x - x_*\| \le \sigma_1
\end{array}
\right\} \implies \|x - x_*\| \le \sigma_2 \|p\|.$$

It is this formulation of the injectivity of $F'(x_*)$ that we chose to keep as a desired property of a root $x_*$ of the functional inclusion system, because it makes no use of the differential of $F$ at the considered zero $x_*$ and can therefore be applied to $F+N$. This concept is called semi-stability; it was introduced in [19].
**Definition 4.2 (semi-stability)** A solution $x_*$ to the functional inclusion $(P_{FI})$ in (4.1) is said to be *semi-stable* if there are constants $\sigma_1 > 0$ and $\sigma_2 > 0$ such that

$$ (x, p) \in \mathbb{E} \times \mathbb{F} \\ \left. \begin{array}{l} F(x) + N(x) \ni p \\ \|x - x_*\| \le \sigma_1 \end{array} \right\} \implies \|x - x_*\| \le \sigma_2 \|p\|. \quad \square $$

In plain words, one can also say that $x_*$ is semi-stable if any solution $x$ of the slightly perturbed system $F(x) + N(x) \ni p$ that is close to $x_*$, depends on the perturbation $p$ in a Lipschitz manner.

**Remarks 4.3**

1) The semi-stability is a concept that applies on the “nonlinear” functional inclusion $F(x) + N(x) \ni 0$, not on its “linearization” $F(x_*) + F'(x_*)(x - x_*) + N(x') \ni 0$. By proposition 4.6 below, we shall see, however, that the semi-stability implies a property on the linearized functional inclusion and that this property is actually equivalent to the semi-stability if $N$ is the normal cone to a convex polyhedron (proposition 4.7).

2) The semi-stability does not claim anything on the existence of solution to the functional inclusion $F(x) + N(x) \ni p$ for the considered $(x, p)$. It only requires a Lipschitz property with respect to the perturbation of the solutions to the perturbed system $F(x) + N(x) \ni p$, if these solutions exist and are close to $x_*$.

3) The straightforward following observation will have important consequences below.

**Proposition 4.4 (isolation of a semi-stable solution)** A semi-stable solution to $(P_{FI})$ is isolated.

*Proof.* It is certainly sufficient to show that, if $x_*$ is a semi-stable solution to $(P_{FI})$, the functional inclusion has no other solution than $x_*$ in $\bar{B}(x_*, \sigma_1)$, where $\sigma_1 > 0$ is the constant appearing in the definition of the semi-stability. Let $x'_* \in \bar{B}(x_*, \sigma_1)$ be a solution to $(P_{FI})$. Hence $\|x'_* - x_*\| \le \sigma_1$ and $F(x'_*) + N(x'_*) \ni 0$, so that $\|x'_* - x_*\| \le \sigma_2 \|0\|$, implying that $x'_* = x_*$. $\square$

4) Semi-stability can also be viewed as a *local error bound* for the isolated solution set $\{x_*\}$, since it also reads: there exist positive constants $\sigma_1$ and $\sigma_2$ such that

$$ \|x - x_*\| \le \sigma_1 \implies \|x - x_*\| \le \sigma_2 \operatorname{dist}(0, F(x) + N(x)). \quad (4.13) $$

Indeed, taking the infimum in $p \in F(x) + N(x)$ in the definition 4.2 of the semi-stability yields the implication above. Conversely, this implication yields the one in definition 4.2 since $\operatorname{dist}(0, F(x) + N(x)) \le \|p\|$ when $\operatorname{dist}(0, F(x) + N(x)) \ni p$.

5) As expected by its construction, the notion of semi-stability reduces to the injectivity of $F'(x_*)$ in the absence of the multifunction $N$ (hence to its nonsingularity when $\dim \mathbb{E} = \dim \mathbb{F}$).
**Proposition 4.5 (semi-stability and nonsingularity)** Assume that $N \equiv 0$ in $(P_{F1})$ and that $F$ is differentiable at a point $x_*$ such that $F(x_*) = 0$. Then $x_*$ is a semi-stable solution to $(P_{F1})$ if and only if $F'(x_*)$ is injective.

*Proof.* [⇒] Let $d$ such that $F'(x_*)d = 0$ and set $x_t := x_* + td$ with $t > 0$. Then $F(x_t) = o(t)$ by the differentiability of $F$ at $x_*$ and $F(x_*) = 0$. The semi-stability of $x_*$ then implies that, as soon as $t > 0$ is small enough, $t\|d\| = \|x_t - x_*\| \le \sigma_2 o(t)$. Hence, one must have $d = 0$.

[⇔] This is a consequence of the reasoning that led to the definition of the semi-stability (see the discussion before definition 4.2). By the differentiability of $F$ at $x_*$ and $F(x_*) = 0$, one has

$$F(x) = F'(x_*)(x - x_*) + o(\|x - x_*\|). \quad (4.14)$$

By the injectivity of $F'(x_*)$, there is a constant $C > 0$ such that

$$\|F'(x_*)h\| \ge C\|h\|, \quad \forall h \in \mathbb{E}. \quad (4.15)$$

Furthermore, by (4.14), there exists $\sigma_1 > 0$ such that

$$\|x - x_*\| \le \sigma_1 \implies \|F(x) - F'(x_*)(x - x_*)\| \ge \frac{C}{2} \|x - x_*\|. \quad (4.16)$$

Combining (4.14), (4.15), and (4.16), we obtain

$$\|x - x_*\| \le \sigma_1 \implies \|F(x)\| \ge \frac{C}{2} \|x - x_*\|.$$

Setting $\sigma_2 = 2/C$, we see that if $(x, p) \in \mathbb{E} \times \mathbb{F}$ verifies $\|x - x_*\| \le \sigma_1$ and $F(x) = p$, the following holds $\|x - x_*\| \le \sigma_2\|p\|$. $\square$

We have observed that a semi-stable solution to the functional inclusion $(P_{F1})$ is an isolated solution (proposition 4.4). The next result tells us that it is also an isolated solution to the functional inclusion, derived from $(P_{F1})$ by linearizing $F$ at $x_*$:

$$F(x_*) + F'(x_*)(x - x_*) + N(x) \ge 0. \quad (4.17)$$

We shall see in proposition 4.7 that the reciprocal holds when $N$ is the multifunction "normal cone to a convex polyhedron".

**Proposition 4.6 (isolated solution to the linearized functional inclusion)** Let $x_*$ be a semi-stable solution to the functional inclusion $(P_{F1})$, in which $F$ is differentiable at $x_*$. Then, $x_*$ is an isolated solution to (4.17).

*Proof.* Let $\sigma_1 > 0$ and $\sigma_2 > 0$ be the constants given by the semi-stability of $x_*$. Suppose that there is a solution $x$ to (4.17) that is arbitrary close to $x_*$. Then,
$$F(x) + N_C(x) \ni F(x) - F(x_*) - F'(x_*)(x - x_*) \quad \text{and} \quad \|x - x_*\| \le \sigma_1.$$

By the semi-stability and the differentiability of $F$ at $x_*$, the following holds

$$\|x - x_*\| \le \sigma_2 \|F(x) - F(x_*) - F'(x_*)(x - x_*)\| = o(\|x - x_*\|).$$

This implies that $x = x_*$. Hence a solution close to $x_*$ cannot be different for $x_*$. $\square$

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

We understand that the semi-stability property of a solution $x_*$ to the functional inclusion problem ($P_{FI}$) is rather restrictive, since it requires in particular that

* $x_*$ be an isolated solution to the functional inclusion ($P_{FI}$) (proposition 4.4),

* $x_*$ be an isolated solution to (4.17), the functional inclusion linearized at $x_*$ (proposition 4.6).

One of the interests of semi-stability is to identify the situations where the JN algorithm described and analyzed in section 4.1 has fast convergence (proposition 4.9 and theorem 4.12) and it is known that linearization algorithms, like Newton's method (section 1.5.2) or the JN algorithm (section 4.1.2) or the SQP algorithm (section 5.1), can behave badly when the aimed solution is not isolated.

We conclude this section with characterizations of the semi-stability, when $N$ is the map “normal cone $N_C$ to a nonempty convex polyhedron $C$”, that highlight the role of the linearized functional inclusion. The condition (ii) will be used for characterizing the semi-stability of a stationary point of ($P_{EI}$) (proposition ??) and the condition (iii) for characterizing the semi-stability of a local solution to ($P_{EI}$) (proposition 5.4). Be mindful that the normal cone is evaluated at the point $x_*$ in (iii), while this evaluation is done at $x$ in (ii) and (iv).

**Proposition 4.7 (charaterization of the semi-stability of a polyhedral**

VI) Suppose that $\mathbb{E} = \mathbb{F}$ and that $x_* \in \mathbb{E}$ is a solution to the functional inclusion ($P_{FI}$), in which $F$ is differentiable at $x_*$ and $N$ is the map normal cone $N_C$ to a nonempty closed convex set $C$ of $\mathbb{E}$. Then, the implications (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (iv) hold for the following claims:

(i) $x_*$ is semi-stable,

(ii) $x_*$ is an isolated solution to the linearized functional inclusion

$$F(x_*) + F'(x_*)(x - x_*) + N_C(x) \ni 0, \quad (4.18)$$

(iii) any $x \in C\{x_*\}$ verifying

$$\langle F(x_*), x - x_* \rangle = 0 \quad (4.19a)$$

$$F(x_*) + F'(x_*)(x - x_*) + N_C(x_*) \ni 0, \quad (4.19b)$$

is such that $\langle F'(x_*)(x - x_*), x - x_* \rangle > 0$,

(iv) the system in $x$ below has no other solution than $x_*$:
$$N_C(x) \subseteq N_C(x_*) \qquad (4.20a)$$

$$\langle F(x_*), x - x_* \rangle = 0 \qquad (4.20b)$$

$$\mathbb{R}_+ F(x_*) + F'(x_*)(x - x_*) + N_C(x) \ni 0. \qquad (4.20c)$$

If C is a nonempty convex polyhedron, then the four properties (i)-(iv) are equivalent.

*Proof.* [(i) ⇒ (ii)] This is proposition 4.6 for the particular case when $N = N_C$.

[(ii) ⇒ (iii)] We show the contrapositive, assuming that there exists an $x_1 \in C \setminus \{x_*\}$ such that (iii) does not hold or

$$\langle F(x_*), x_1 - x_* \rangle = 0, \qquad (4.21a)$$

$$F(x_*) + F'(x_*)(x_1 - x_*) + N_C(x_*) \ni 0, \qquad (4.21b)$$

$$\langle F'(x_*)(x_1 - x_*), x_1 - x_* \rangle \le 0 \qquad (4.21c)$$

and show that $x_t := (1-t)x_* + tx_1$ is a solution to (4.18) for all $t \in [0, 1]$, which contradicts (ii).

Observe first that one has an equality in (4.21c):

$$\langle F'(x_*)(x_1 - x_*), x_1 - x_* \rangle = 0. \qquad (4.22)$$

This is because by (4.21b) and $x_1 \in C$, one has $\langle F(x_*) + F'(x_*)(x_1 - x_*), x_1 - x_* \rangle \ge 0$. Next, using (4.21a) in this inequality yields $\langle F'(x_*)(x_1 - x_*), x_1 - x_* \rangle \ge 0$, which is the reverse inequality of (4.21c), hence (4.22).

To show that $x_t$ is a solution to (4.18), we have to prove that $x_t \in C$, which is clear by the convexity of $C$, and that, for all $y \in C$, the following value is nonnegative:

$$\begin{align*}
& \langle F(x_*) + F'(x_*)(x_t - x_*), y - x_t \rangle \\
&= \langle F(x_*) + t F'(x_*)(x_1 - x_*), y - x_* - t(x_1 - x_*) \rangle \\
&= \langle F(x_*) + t F'(x_*)(x_1 - x_*), y - x_* \rangle \quad [(4.21a) \text{ and } (4.22)] \\
&\ge (1-t) \langle F(x_*), y - x_* \rangle \quad [(4.21b)] \\
&\ge 0 \quad [1-t \ge 0 \text{ and } F(x_*) + N_C(x_*) \ni 0].
\end{align*}$$

[(iii) ⇒ (iv)] We show the contrapositive: assuming that there exists an $x \ne x_*$ satisfying (4.20), we find some $t > 0$ such that $x_t := x_* + t(x - x_*)$ satisfies

$$\langle F(x_*), x_t - x_* \rangle = 0, \qquad (4.23a)$$

$$F(x_*) + F'(x_*)(x_t - x_*) + N_C(x_*) \ni 0, \qquad (4.23b)$$

$$\langle F'(x_*)(x_t - x_*), x_t - x_* \rangle \le 0, \qquad (4.23c)$$

which contradicts (4.19).

Observe already that (4.23a) follows at once from (4.20b). To get (4.23c), we use (4.20c), which reads for some $\alpha \ge 0$:

$$\langle \alpha F(x_*) + F'(x_*)(x - x_*), y - x_* \rangle \ge 0, \quad \forall y \in C. \qquad (4.24)$$
Now (4.23c) follows by taking $y = x_* \in C$ in this inequality, multiplying the left-hand side by $t^2$ (hence $x - x_*^*$ becomes $x_t - x_*$) and using (4.23a). It remains to show (4.23b), which also reads

$$ \langle F(x_*) + F'(x_*)(x_t - x_*), y - x_* \rangle \ge 0, \quad \forall y \in C. \quad (4.25) $$

This is almost the form (4.24) of (4.20c). We examine two cases.

* If $\alpha > 1$, we divide the left-hand side of (4.24) by $\alpha$ and get (4.25) with $t = 1/\alpha \in (0, 1]$.

* If $\alpha \in [0, 1]$, instead of (4.24), we use (4.20a) and (4.20c) to get for some $\alpha \ge 0$:

$$ \langle \alpha F(x_*) + F'(x_*)(x - x_*), y - x_* \rangle \ge 0, \quad \forall y \in C. \quad (4.26) $$

Now, $F(x_*) + N_C(x_*) \ni 0$ ($x_*$ is a solution to (P$_{VI}$)) implies that

$$ \langle F(x_*), y - x_* \rangle \ge 0, \quad \forall y \in C. $$

Multiplying the left-hand side of these inequalities by $1 - \alpha \ge 0$ and combining with (4.26), yield (4.25) with $t = 1$.

[(iv) ⇒ (i)] Suppose now that $C$ is a convex polyhedron. We show the contra-positive, assuming that $x_*$ is not semi-stable and show that the system (4.20) has a solution $x \ne x_*^*$.

Letting the constants $\sigma_1 \to 0$ and $\sigma_2 \to \infty$ in the definition 4.2 of the semi-stability, we see that one can find sequences $\{x_k\} \subseteq \mathbb{E}$ and $\{p_k\} \subseteq \mathbb{F}$ such that

$$ F(x_k) + N_C(x_k) \ni p_k, \quad (4.27a) $$

$$ x_k \to x_* \quad \text{with} \quad x_k \ne x_*, \quad (4.27b) $$

$$ \|p_k\|/\|x_k - x_*\| \to 0. \quad (4.27c) $$

Extracting a subsequence if necessary, one can suppose that, with $t_k := \|x_k - x_*\|$, we have $(x_k - x_*)/t_k \to d$. Since $x_k \in C$ by (4.27a), it clearly follows that $d \in T_C(x_*) \setminus \{0\}$.

Let us now take the limit in (4.27a), after the expansion of $F(x_k)$ around $x_*$ and division by $t_k > 0$:

$$ \frac{1}{t_k} F(x_*) + F'(x_*) \frac{x_k - x_*}{t_k} + \frac{o(\|x_k - x_*\|)}{t_k} + N_C(x_k) \ni \frac{p_k}{t_k}. $$

The first term is annoying since $t_k \to 0$, but it belongs to $\mathbb{R}_+ F(x_*)$ and we can replace it by that set, while keeping the inclusion. The second term tends to $F'(x_*)d$ and the third one to zero. By extracting a subsequence if necessary, one can fix the normal cones in the fourth term to a unique one (exercise 1.2.1), which is denoted by $N_C(x_k) = N_C(x_0)$ below. Finally, the right-hand side tends to zero by (4.27c). Since $\mathbb{R}_+ F(x_*) + N_C(x_0)$ is closed (the sum of two convex polyhedrons is a polyhedron [a property recalled in point 2 of proposition 1.1], hence closed), we obtain at the limit:

$$ \mathbb{R}_+ F(x_*) + F'(x_*)d + N_C(x_0) \ni 0. $$

This inclusion resembles (4.20c), which we now try to establish for the point

$$ x = x_* + \varepsilon d, $$
where $\varepsilon > 0$ is taken sufficiently small in order to have $x \in C\setminus\{x_*\}$; this is possible since $d \neq 0$ and $d \in T_C(x_*) = T_C^f(x_*)$ by (1.26a). With that $x$, the preceding inclusion becomes

$$ \mathbb{R}_+ F(x_*) + F'(x_*)(x - x_*) + N_C(x_0) \ni 0. \quad (4.28) $$

For $y \in C$, let us denote by $I(y)$ the set of the indices of the active inequality affine constraints defining the polyhedron $C$ that are active at $y$. To get (4.20) and therefore conclude, it is sufficient to show that

$$ I(x_0) \subseteq I(x) \subseteq I(x_*), \quad (4.29a) $$

$$ \langle F(x_*), x - x_* \rangle = 0. \quad (4.29b) $$

Indded, by (1.27b), (4.29a) implies that $N_C(x_0) \subseteq N_C(x) \subseteq N_C(x_*)$ and therefore (4.20a); (4.29b) is (4.20b); and (4.28) and $N_C(x_0) \subseteq N_C(x)$ implies (4.20c).

Consider first (4.29a). Observe that the convergence $x_k \to x_*$ and the fact that $I(x_k) = I(x_0)$ (for the subsequence $\{x_k\}$ having the same $I(x_k)$, selected above) imply that

$$ I(x_k) = I(x_0) \subseteq I(x_*). $$

Therefore, if $i \in I(x_k)$, it follows that $i \in I(x_*)$ and that $i \in I((1 - \varepsilon/t_k)x_* + (\varepsilon/t_k)x_k)$. Since $([1 - \varepsilon/t_k]x_* + [\varepsilon/t_k]x_k) = x_* + \varepsilon(x_k - x_*)/t_k \to x_* + \varepsilon d = x$, we have the first inclusion in (4.29a). For the second inclusion in (4.29a), we take $\varepsilon > 0$ small enough, so that $x = x_* + \varepsilon d$ is sufficiently close to $x_*$ to have $I(x) \subseteq I(x_*)$.

Consider now (4.29b). First, $\langle F(x_*), x - x_* \rangle \ge 0$, since $F(x_*) + N_C(x_*) \ni 0$ and $x \in C$. To get the reverse inequality, we use (4.27a) and $x_* \in C$ to get $\langle F(x_k) - p_k, x_* - x_k \rangle \ge 0$. Dividing by $t_k > 0$ and taking the limit in $k$ yield $\langle F(x_*), d \rangle \le 0$ since $(x_* - x_k)/t_k \to -d$, hence $\langle F(x_*), x - x_* \rangle \le 0$ since $d = (x - x_*)/\varepsilon$. $\square$

**Definition 4.8 (strong regularity)** A solution $x_*$ to the functional inclusion ($P_{FI}$) is said to be strongly regular if there is a constant $\varepsilon > 0$ such that, for all $p$ near zero, the system

$$ \begin{cases} F(x_*) + F'(x_*)(x - x_*) + N(x) \ni p \\ \|x - x_*\| \le \varepsilon \end{cases} $$

has a unique solution $x(p)$ and $x(\cdot)$ is Lipschitz near zero. $\square$

This is a much stronger assumption than semi-stability in that it assumes the existence of a solution for small perturbations $p$ and that this solution is unique.

### 4.1.4 Speed of Convergence

In this section, we consider a structurally slight but important generalization of the JN algorithm (4.12), in which the next iterate $x_{k+1}$ following the current one $x_k$ is computed by

$$ F(x_k) + M_k(x_{k+1} - x_k) + N(x_{k+1}) \ni 0, \quad (4.30) $$

where $M_k \in \mathcal{L}(\mathbb{E}, \mathbb{F})$ may be the Jacobian $F'(x_k)$ or an approximation to it. Hence this algorithm includes the quasi-Newton versions of the JN algorithm.
Let us now highlight conditions ensuring superlinear and quadratic convergence of the sequences generated by the JN algorithm (4.30). In this analysis, we assume that a sequence {$x_k$} is generated by the algorithm and that this sequence converges to a solution $x_*$ to ($P_{FI}$). These conditions depend on the smoothness of $F$, on the quality of the approximation of $F'(x_k)$ by $M_k$, and on the regularity of the solution $x_*$ (its semi-stability, actually). The conditions on $M_k$ used in proposition 4.9 below have to be compared with the Dennis and Moré condition for nonlinear systems (proposition 1.49): fast convergence is guaranteed, provided $M_k$ is close to $F'(x_k)$ along the displacement direction $x_{k+1} - x_k$. Nothing is required on the multifunction $N$; a posteriori, this can be understood by the fact that the algorithm takes all information from $N$, not only a kind of linearization like it does for $F$.

**Proposition 4.9 (sufficient conditions for fast convergence)** Let $x_*$ be a semi-stable solution to ($P_{FI}$). Suppose that $F$ is differentiable in a neighborhood of $x_*$ and that $F'$ is continuous at $x_*$. Let {$x_k$} be a sequence satisfying the recurrence (4.30) and converging to $x_*$.

1) If $(M_k - F'(x_*))(x_{k+1} - x_k) = o(\|x_{k+1} - x_k\|)$, then the convergence of {$x_k$} is superlinear.

2) If $(M_k - F'(x_*))(x_{k+1} - x_k) = O(\|x_{k+1} - x_k\|^2)$ and if $F'$ is radially Lipschitz at $x_*$, then the convergence of {$x_k$} is quadratic.

*Proof.* Let $\sigma_1$ and $\sigma_2$ be the positive constants of the semi-stable solution $x_*$ and let us simplify the writing by introducing $s_k := x_{k+1} - x_k$ and $\Delta_k := (M_k - F'(x_*))s_k$.

0) We want to apply the semi-stability to have an estimate of the updated error $x_{k+1} - x_*$, hence having an implication of the form

$$ F(x_{k+1}) + N(x_{k+1}) \ni p_{k+1} \quad \Rightarrow \quad \|x_{k+1} - x_*\| \le \sigma_2 \|p_{k+1}\|. \quad (4.31) $$

The fact that $\|x_{k+1} - x_*\| \le \sigma_1$ is guaranteed for large $k$, by the assumed convergence of {$x_k$} to $x_*$. For the inclusion in the left-hand side of (4.31), it is natural to start with the iteration recurrence (4.30), which provides the aforementioned inclusion with

$$ p_{k+1} := F(x_{k+1}) - [F(x_k) + M_k s_k] = F(x_{k+1}) - F(x_k) - F'(x_*) s_k - \Delta_k. $$

Therefore, by the implication (4.31), we have

$$ \|x_{k+1} - x_*\| \le \sigma_2 \|p_{k+1}\|. \quad (4.32) $$

The goal now is to get an estimate of $\|p_{k+1}\|$ in terms of $\|x_k - x_*\|$. By the mean value theorem (corollary 1.25), we have that

$$ \|p_{k+1}\| \le \left( \sup_{t \in [0,1]} \|F'(x_k + t s_k) - F'(x_*)\| \right) \|s_k\| - \Delta_k. \quad (4.33) $$

1) The continuity of $F'$ at $x_*$ and the assumption $\Delta_k = o(\|s_k\|)$ of the case allow us to deduce from (4.33) that $p_{k+1} = o(\|s_k\|)$. Therefore $x_{k+1} - x_* = o(\|s_k\|)$ by
(4.32). We deduce from this estimate that $x_{k+1} - x_* = o(\|x_k - x_*\|)$, which is the mark of the superlinear convergence of $\{x_k\}$.

2) If $F'$ is L-Lipschitz continuous near $x_*$ and $\Delta_k = O(\|s_k\|^2)$, we can estimate $p_{k+1}$ from (4.33) as follows

$$ \|p_{k+1}\| \le L\|x_k - x_*\| \|s_k\| + O(\|s_k\|^2) = O(\|x_k - x_*\|^2), $$

since $s_k \sim (x_k - x_*)$, by the superlinear convergence of $\{x_k\}$ established in point 1 and lemma 1.47. Then, one deduces from (4.32) that $x_{k+1} - x_* = O(\|x_k - x_*\|^2)$, which is the mark of the quadratic convergence of $\{x_k\}$. $\square$

The next corollary, whose proof is straightforward, essentially deals with the case when $M_k = F'(x_k)$.

**Corollary 4.10 (speed of convergence of the JN algorithm)** Suppose that $F$ is $C^1$ in a neighborhood of a semi-stable solution $x_*$ to $(P_{F1})$ and that the sequence $\{x_k\}$ satisfies the recurrence (4.11) and converges to $x_*$. 1)

1) If $M_k \to F'(x_*)$, then the convergence of $\{x_k\}$ is superlinear.

2) If $M_k - F'(x_*) = O(\|x_k - x_*\|)$ and if $F'$ is radially Lipschitz at $x_*$, then the convergence of $\{x_k\}$ is quadratic.

*Proof.* 1) Point 1 follows immediately from point 1 of proposition 4.9.

2) If $M_k - F'(x_*) = O(\|x_k - x_*\|)$, then $(M_k - F'(x_*))(x_{k+1} - x_k) = O(\|x_k - x_*\| \|x_{k+1} - x_k\|)$, which implies the superlinear convergence of $\{x_k\}$ by point 1 of proposition 4.9. Next lemma 1.47 implies that $(x_k - x_*) \sim (x_{k+1} - x_k)$, from which we have $(M_k - F'(x_*))(x_{k+1} - x_k) = O(\|x_{k+1} - x_k\|^2)$. Now the quadratic convergence of $\{x_k\}$ follows from the radial Lipschitz continuity of $F'$ at $x_*$ and point 2 of proposition 4.9. $\square$

### 4.1.5 Local Convergence

The preceding section analyzed the speed of convergence of the sequence of iterates $\{x_k\}$ generated by the JN algorithm, assuming that such a sequence is generated and that this one converges to some semi-stable solution to the functional inclusion problem $(P_{F1})$ in (4.1). This section clarifies the last two aspects. On the one hand, the well-posedness of the algorithm is shown, which amounts to ensure that the linearized functional inclusion (4.11) has a solution. On the other hand, the local convergence of the algorithm is proved, meaning that the generated sequence converges to the considered neighboring solution $x_*$. For the two goals, the current iterate $x_k$ is supposed to be close to a solution $x_*$, having an additional property.

Whilst the semi-stability of definition 4.2 has a local injectivity flavor, revealed by propositions 4.4 and 4.5, the hemi-stability defined below has a local surjectivity interpretation, in the sense that it requires the pseudo-linearized function inclusion to have a solution at linearization points close to $x_*$. □
**Definition 4.11 (hemi-stability)** A solution $x_*$ to $(P_{FI})$ is said to *hemi-stable* if for all $\alpha > 0$, there exists $\beta > 0$ such that, for all $x_0 \in \bar{B}(x_*, \beta)$, the following functional inclusion in $x$

$$F(x_0) + F'(x_0)(x - x_0) + N(x) \ni 0$$

has a solution in $\bar{B}(x_*, \alpha)$.

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

In plain words, $x_*$ is hemi-stable if one can find a solution to the linearized functional inclusion (4.11) that is as close as desired to $x_*$, just by taking the point of linearization $x_k$ sufficiently close to $x_*$. It is not claimed that, when $x_k$ is close to $x_*$, the linearized functional inclusion (4.11) has a unique solution; in particular, this one could have another solution that is not close to $x_*$. In the next theorem, we use the phrase “can generate” to express the fact that, when $x_k$ is close to an hemi-stable solution, the JN algorithm takes a solution $x_{k+1}$ to the linearized inclusion (4.11) that is also close to the solution $x_*$. □

**Theorem 4.12 (local convergence of the JN algorithm)** Let $x_*$ be a semi-stable and hemi-stable solution to $(P_{FI})$. Suppose that $F$ is differentiable in a neighborhood of $x_*$ and that $F'$ is continuous at $x_*$. Consider the JN algorithm (4.12). Then, there exists an $\varepsilon > 0$, such that

1) if the first iterate $x_1$ is in the closed ball $\bar{B}(x_*, \varepsilon)$, then the JN algorithm can generate a sequence $\{x_k\}$ in $\bar{B}(x_*, \varepsilon)$,

2) any sequence $\{x_k\}$ generated in $\bar{B}(x_*, \varepsilon)$ by the JN algorithm converges superlinearly to $x_*$ (and quadratically if $F'$ is radially Lipschitz at $x_*$).

*Proof. 0)* Let us first fix a few constants in the right order. Let $\sigma_1 > 0$ and $\sigma_2 > 0$ be the constants given by the semi-stability at $x_*$. Define

$$p(x, x') := F(x') - F(x) - F'(x)(x' - x).$$

The mean value theorem (corollary 1.25) allows us to write

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

By the assumed continuity of $F'$ at $x_*$, the factor in parentheses can be made as small as desired by taking $x$ and $x'$ close enough to $x_*$. Therefore, one can find a constant $\alpha \in (0, \sigma_1]$ such that

$$x, x' \in \bar{B}(x_*, \alpha) \quad \implies \quad \|p(x, x')\| \le \frac{1}{3\sigma_2} \|x' - x\|. \quad (4.34)$$

Let $\beta > 0$ be the constant associated with $\alpha$ by the hemi-stability of $x_*$ and set $\varepsilon := \min(\alpha, \beta)$.

1) Suppose now that $x_k \in \bar{B}(x_*, \varepsilon)$. By the hemi-stability of $x_*$ and $\varepsilon \le \beta$, there exists a new iterate $x_{k+1} \in \bar{B}(x_*, \alpha)$ such that

$$F(x_k) + F'(x_k)(x_{k+1} - x_k) + N(x_{k+1}) \ni 0. \quad (4.35)$$
Since this inclusion is the JN algorithm recurrence formula (4.12), the algorithm can take this $x_{k+1}$ as the iterate following $x_k$. Therefore, we have shown that the JN algorithm can generate a sequence in $\bar{B}(x_*, \varepsilon)$.

2) Assume now that the JN generates a sequence $\{x_k\}$ in $\bar{B}(x_*, \varepsilon)$. Hence the inclusion (4.35) holds. Let us now apply the semi-stability property of $x_*$. It follows from (4.35) that

$$F(x_{k+1}) + N(x_{k+1}) \ni F(x_{k+1}) - F(x_k) - F'(x_k)(x_{k+1} - x_k) = p(x_k, x_{k+1}).$$

Since $x_{k+1} \in \bar{B}(x_*, \varepsilon)$ and $\varepsilon \le \alpha \le \sigma_1$, the semi-stability at $x_*$ implies that

$$ \begin{aligned} \|x_{k+1} - x_*\| &\le \sigma_2 \|p(x_k, x_{k+1})\| \\ &\le \frac{1}{3} \|x_{k+1} - x_k\| \quad [(4.34) \text{ and } x_k, x_{k+1} \in \bar{B}(x_*, \alpha)] \\ &\le \frac{1}{3} \|x_{k+1} - x_*\| + \frac{1}{3} \|x_k - x_*\|. \end{aligned} $$

Therefore $\|x_{k+1} - x_*\| \le \frac{1}{2}\|x_k - x_*\|$. We have shown that $x_k \to x_*$.

The superlinear and quadratic convergence speed of convergence follows from corollary 4.10. □

### 4.1.6 Globalization by Line-Search ▲

#### Notes

Historically, the variational inequality problem ($P_{VI}$) was introduced by Hartman and Stampacchia [64; 1966] for solving some nonlinear elliptic partial differential equation and was subsequently developed in many papers, including [94, 131, 96]. Karamardian [81; 1971] was the first to establish the relationship between the variational inequality problem ($P_{VI}$) in (4.3) and the complementarity problem ($P_{CP}$). The existence result for variational inequality problems, the one of theorem 4.1, is taken from [46; theorem 2A.1]. Surveys on variational inequality problems can be found in [63, 50, 76].

Josephy [79; 1979] considers the complementarity problem ($P_{CP}$), hence a functional inclusion in which the multifunction $N$ is the normal cone to a closed convex cone $K$, and shows existence, uniqueness, and convergence of a sequence satisfying the iterations (4.12), provided the sought solution $x_*$ is strongly regular in the sense of Robinson [120]. Bonnans [19; 1994] introduces the weaker regularity condition that is presented here, namely the semi-stability and hemi-stability of the sought solution, and so provides the strongest local convergence result of the functional inclusion problem ($P_{FI}$) known so far. The results presented in this section are essentially those in [19]. For an analysis of the local convergence of the inexact JN algorithm, in which the recurrence formula (4.12) is solved inexact, we refer the reader to [75]; many algorithms enter that framework, like the stabilized version of SQP and the linearly constrained augmented Lagrangian methods. Josephy has also given a Kantorovich-like existence result based on the iterations (4.12) in [79] and a quasi-Newton analysis of the algorithm in [80]. Analyzes of the inexact version of the Josephy-Newton algorithm have been undergone in [75, 45].
Exercises

4.1.1. *Explicit variational problem.* Let $\mathbb{E}$ be a Euclidean space, $X$ be a (not necessarily convex) subset of $\mathbb{E}$, and $F: \mathbb{E} \to \mathbb{E}$ be a smooth map. Consider the variational problem

$$ (P_v) \quad F(x) + N_X(x) \ni 0, $$

where $N_X(x)$ is the normal cone to $X$ at $x$. Suppose that $\mathbb{F}$ is another Euclidean space and that $X$ has actually the following form

$$ X := \{x \in \mathbb{E} : c(x) \in G\}, $$

in which $c: \mathbb{E} \to \mathbb{F}$ is a smooth function and $G$ is a closed convex set of $\mathbb{F}$. Show that if $x_*$ is a solution to (Pv) satisfying

$$ 0 \in \text{int}\{c(x_*) + c'(x_*)\mathbb{E} - G\}, $$

then, there exists $\lambda_*$ in the normal cone to $G$ at $c(x_*)$ such that

$$ F(x_*) + c'(x_*)^*\lambda_* = 0. $$

4.1.2. *Equation formulation of a variational inequality problem.* Show that $x \in \mathbb{E}$ is a solution to the variational inequality problem (4.3) if and only if $x$ solves (4.4).

4.1.3. *Normal map reformulations.*

1) *Variational inequality problem* [123]. Show that $x \in \mathbb{E}$ solves the variational inequality problem (Pvi) in (4.3) if and only if $x = P_C(z)$ where $z \in \mathbb{E}$ solves

$$ F(P_C(z)) + z - P_C(z) = 0. \quad (4.36) $$

2) *Complementarity problem.* Show that $x \in \mathbb{E}$ solves the complementarity problem ($P_C$) in (4.6) if and only if there is a $z \in \mathbb{E}$ such that $(x, z)$ solves

$$ F(x) = P_K(z) \quad \text{and} \quad G(x) = -P_{K^{-}}(z). \quad (4.37) $$

4.1.4. *JN algorithm for a complementarity problem.* Let $\mathbb{E}$ and $\mathbb{F}$ be two Euclidean spaces, $K$ be a nonempty closed convex cone of $\mathbb{F}$, $K^+$ its positive dual, and $F$ and $G: \mathbb{E} \to \mathbb{F}$ be two differentiable functions. Consider the complementarity problem

$$ K \ni G(x) \perp F(x) \in K^+. \quad (4.38) $$

Show that the algorithm that computes the next iterate $x_{k+1}$ from the current one $x_k$ by solving the linear complementarity problem in $x$

$$ K \ni (G(x_k) + G'(x_k)(x - x_k)) \perp (F(x_k) + F'(x_k)(x - x_k)) \in K^+, \quad (4.39) $$

is the JN algorithm on a certain functional inclusion problem like (4.1), in which the multifunction $N$ is the normal cone map to a convex cone; which one?
## 4.2 B-Newton Method for Systems of Equations ▲

## 4.3 Linearization method for $\mathcal{P}\mathcal{C}^1$ functions ▲

## 4.4 Semismooth Newton Method for nonlinear systems

Let $\mathbb{E}$ and $\mathbb{F}$ be two finite dimensional vector spaces. In this section, we present a linearization algorithm for solving a nonlinear system of equations of the form

$$F(x) = 0, \qquad (4.40)$$

where $F: \Omega \to \mathbb{F}$ is a nonsmooth function defined on an open set $\Omega \subseteq \mathbb{E}$. The nonsmoothness means here that $F$ is differentiable, but in a weaker sense than that of Fréchet. We shall see that a fast (superlinear or quadratic) local convergence can be obtained if $F$ is semismooth, a concept presented in section 4.4.3.

Section 4.4.1 presents some examples where such nonsmooth systems occur. It also discuss an example of function $F$ showing that the Lipschitz continuity of $F$ is not a sufficiently strong assumption for guaranteeing the convergence of the Newton algorithm, since this one may then cycle whatever the solution proximity of the initial iterate can be. A first guess of an appropriate smoothness assumption ensuring the local convergence of a Newton-like algorithm is also presented. Section 4.4.3 defines the concept of semismoothness and gives some of its main properties. A remarkable one is that it is transmissible to the minimum or maximum of two semismooth functions, which makes the concept widespread. The semismooth Newton algorithm is set out in section 4.4.4 and its local convergence is analyzed.

Prerequisite: generalized differentiability (section 4.4.2).

### 4.4.1 Motivation, Orientation, Examples

Let us start by giving some examples of problems that can be reformulated as nonsmooth systems of equations.

**Examples 4.13 1) Reformulation of a complementarity problem.** Consider the complementarity problem (4.6), in which $\mathbb{F} = \mathbb{R}^n$, $K = \mathbb{R}_+^n$, and $F$ and $G$ are renamed $A$ and $B$, to avoid confusion with the function $F$ introduced above:

$$0 \le A(x) \perp B(x) \ge 0. \qquad (4.41)$$

In this system, $A$ and $B: \mathbb{E} \to \mathbb{R}^n$ are two functions defined on a vector space $\mathbb{E}$. This problem means that one seeks a point $x \in \mathbb{E}$ such that $A(x) \ge 0$, $B(x) \ge 0$, and $A(x)^{\top}B(x) = 0$ (or equivalently $A_i(x)B_i(x) = 0$ for all $i \in [1:n]$, which highlights the combinatorial aspect of the problem). Such a problem can be written in the form of a nonsmooth equation, thanks to a C-function. A C-function (C for complementarity) is a function $\varphi: \mathbb{R}^2 \to \mathbb{R}$ such that

$$\varphi(a, b) = 0 \iff a \ge 0, \ b \ge 0, \ ab = 0. \qquad (4.42)$$
Hence $\varphi(a, b) = 0$ expresses the complementarity of the two scalars $a$ and $b$. The most frequently encountered C-functions are the C-function “min” and the Fischer C-function.

• The min C-function is defined by

$$ \varphi(a, b) = \min(a, b). \qquad (4.43) $$

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

It is easy to verify that (4.42) holds for this function. The min function is concave (minimum of two linear functions) and nondifferentiable at points $(a, b)$ verifying $a = b$.

• The Fischer C-function is defined by

$$ \varphi(a, b) = \sqrt{a^2 + b^2} - (a + b). \qquad (4.44) $$

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

It is also easy to verify that (4.42) holds for this function. This function is convex (it is the $l_2$ norm of $(a, b)$ minus a linear function) and differentiable everywhere except at $(0, 0)$.

With a C-function $\varphi$, the complementarity problem (4.41) can be written like the nonsmooth equation

$$ F(x) = \begin{pmatrix} \varphi(A_1(x), B_1(x)) \\ \vdots \\ \varphi(A_n(x), B_n(x)) \end{pmatrix} = 0. $$

2) Reformulation of a variational inequality problem. The variational inequality problem (4.3), written here $\Phi(x) + N_C(x) \ni 0$, where $N_C$ is the multifunction “normal cone to the nonempty closed convex set $C$”, can be rewritten like a nonsmooth equation $F(x) = 0$ by observing that $-\Phi(x) \in N_C(x)$ if and only if the projection of $x - \Phi(x)$ on $C$ is $x$ [47]. Then, it suffices to define $F: \mathbb{E} \to \mathbb{E}$ at $x \in \mathbb{E}$ by

$$ F(x) := x - P_C(x - \Phi(x)), $$

where $P_C$ is the orthogonal projector on $C$. Note that the boundary of $C$ must have some smoothness to make this approach work (recall remark 1.12).

Another way of reformulating a variational inequality problem as a nonsmooth equation is to introduce an equation characterizing the point $z := x - \Phi(x)$ instead of $x$. This point of view is examined in the exercise 4.1.3.

Below, we consider the generalization of the Newton algorithm for solving the nonsmooth equation (4.40) that reads locally

$$ x_{k+1} := x_k - J_k^{-1} F(x_k), \qquad (4.45) $$
where $J_k \in \mathcal{L}(\mathbb{E}, \mathbb{F})$ is a nonsingular element of the Clarke differential $\partial_C F(x_k)$. The target we fix ourselves is very ambitious, since the iteration (4.45) only requires the solution to a linear system, which is much less expensive than the JN algorithm, whose iteration is potentially nonlinear. We shall see that one can take assumptions on $F$, often verified, such that locally this algorithm generates sequences that converge superlinearly or quadratically to a “regular” zero of $F$. Therefore, one recovers the two conditions that are required for ensuring the convergence of the Newton algorithm: a certain smoothness of $F$ and the regularity of the sought zero, in a sense that still needs to be clarified.

Let us start by observing that, without an adequate smoothness assumption on $F$, the proposed generalization (4.45) of Newton’s method is doomed for failure, even though the iterates only visit points of differentiability of $F$, with nonsingular Jacobians. This is what is shown in the next example.

**Counter-example 4.14 (nonconvergence of the Newton algorithm for a nonsmooth equation [88])** We construct a function $F : [-1, 1] \subseteq \mathbb{R} \to [-1, 1] \subseteq \mathbb{R}$, by repeating indefinitely a pattern that is scaled in proportion to its proximity to the unique zero $x_* = 0$ of the function. The pattern is designed in order to force the Newton method to make a cycle, which can be arbitrary close to the zero (the graph of the function is given on the right-hand side of figure 4.1).

<figure><img src="image_37.png" /><figcaption>**Fig. 4.1.** Kummer’s function [88], for which the Newton method makes cycles, as close as desired to its unique zero $x_* = 0$. The function is constructed by repeating the pattern on the left-hand side, scaling it in proportion to its proximity to the zero.</figcaption></figure>

Here is how this function is constructed. The function is defined on $[-1, 1]$, is continuous and odd (meaning that $F(-x) = -F(x)$ for all $x \in [-1, 1]$), so that it suffices to define it on $(0, 1]$ and to set $F(0) = 0$. This is done by means of a function pattern that is piecewise affine on the intervals $[1/n, 1/(n-1)]$ for all integer $n \ge 2$, takes the value $1/(n-1)$ at $x = 1/(n-1)$ and the value $1/n$ at $x = 1/n$ (see the graph of the pattern in the left-hand side of figure 4.1). This pattern is then reproduced and scaled to define the function on $(0, 1]$. Let us denote by
$$m_n := \frac{1}{2} \left( \frac{1}{n} + \frac{1}{n-1} \right) = \frac{2n-1}{2n(n-1)}$$

the middle point of the interval $[1/n, 1/(n-1)]$. This point will be a point of a cycle for Newton's method, if $F$ is affine near $m_n$ with the values

$$f_n(x) = a_n(x + m_n), \quad \text{where} \quad a_n = \frac{1/(n-1)}{1/(n-1) + m_n} = \frac{2n}{4n-1}.$$

Indeed, in this case, the iterate that follows $m_n$ is $-m_n$ (because $f_n(-m_n) = 0$), itself followed by $m_n$ (by the oddness of the function); hence the Newton algorithm (4.45) cycles between $m_n$ and $-m_n$. The second affine part of the pattern is the function $g_n$ that must take the value $1/n$ at $x = 1/n$ (so that the connexion with the following pattern is done continuously) and must have a sufficiently large slope $b_n$ (so that its intersection with $f_n$ occurs at an abscissa lower than $m_n$ (so that the previously mentioned cycle can still occur). As we shall see, this last condition is satisfied if $g_n$ vanishes at $x = m_{2n}$, i.e., if

$$g_n(x) = b_n(x - m_{2n}), \quad \text{with} \quad b_n = \frac{1/n}{1/n - m_{2n}} = \frac{8n-4}{4n-3}.$$

To check that the slope $b_n$ of $g_n$ is large enough, it suffices to verify that, for any integer $n \ge 2$, we have $f_n(m_n) < g_n(m_n)$, which reads $4n^2 + n - 1 > 0$, an inequality that is verified for all positive integers.

The function $F$ so obtained has its graph represented on the right-hand side in figure 4.1. Its unique zero is $x_* = 0$. It is Lipschitz continuous on $[-1, 1]$, with the modulus $\max_n b_n = b_2 = 12/5$. Since, for all $x$ in the interval $[1/n, 1/(n-1)]$, $F(x)$ is in the same interval, it follows that $F(x)/x \in [(n-1)/n, n/(n-1)]$ and therefore, by parity, $F'(0) = 1$. The C-differential $\partial_C F(0)$ is the convex hull of the limits of the $a_n$ and $b_n$ when $n \to \infty$, by the definition 4.15, that is $[1/2, 2]$. This C-differential does not contain the zero slope. In summary:

$$F : \mathbb{R} \to \mathbb{R} \text{ is Lipschitz continuous and has directional derivatives,} \quad (4.46a)$$

$$F(0) = 0, \quad (4.46b)$$

$$F'(0) = 1, \quad (4.46c)$$

$$\partial_C F(0) = [\frac{1}{2}, 2] \not\subseteq 0. \quad (4.46d)$$

□

What is wrong with the nonsmooth function $F$ in example 4.14? Is there no hope to get local convergence of the Newton algorithm with a nonsmooth function? An answer is given by the following expression of the error $x_{k+1} - x_*$:

$$\begin{align*}
x_{k+1} - x_* &= x_k - x_* - J_k^{-1} F(x_k) \quad [(4.45)] \\
&= -J_k^{-1} [F(x_k) - F(x_*) - J_k(x_k - x_*)] \quad [F(x_*) = 0] \\
&= -J_k^{-1} [F(x_* + h_k) - F(x_*) - J_k h_k] \quad [h_k := x_k - x_*].
\end{align*}$$

As a result, if $\{J_k^{-1}\}$ is bounded and if
$$F(x_* + h_k) - F(x_*) - J_k h_k = o(\|h_k\|), \quad (4.47)$$

the superlinear convergence of the generated sequence is guaranteed. Conversely, if {$J_k$} is bounded and the generated sequence converges superlinearly, then (4.47) holds. Hence this condition is almost necessary and sufficient to get superlinear convergence.

The condition (4.47) makes no assumption on the way of choosing $J_k$ (only the boundedness of {$J_k$} and {$J_k^{-1}$} is assumed in the discussion). In the semismooth Newton algorithm of section 4.4.4 below, $J_k$ is chosen in $\partial_C F(x_k)$, so that (4.47) becomes a condition of the generalized differential $\partial_C F(x_k) = \partial_C F(x_* + h_k)$, not a condition on $\partial_C F(x_*)$, as an analogy with the Fréchet differentiability condition “$F(x_* + h_k) - F(x_*) - F'(x_*)h_k = o(\|h_k\|)$” would incline us to do. This small change is a fundamental aspect of semismoothness, which takes indeed the condition (4.47) in its definition 4.20. We shall see that this notion of weak differentiability is to be shared by a large number of functions, so that superlinear convergence of a Newton-like method is attainable for many nonsmooth systems of equations. This is good news.

Let us come back to the counter-example 4.14 and show that the condition (4.47) does not hold at $x_* = 0$, which explains a posteriori why the local convergence of the Newton method cannot be guaranteed for the constructed function. The Jacobians $J_k$ are the slopes $a_n$, whose inverses $a_n^{-1} = 2 - 1/(2n)$ form a bounded sequence. Consider now the condition (4.47). If we take a sequence of points $h_n \in (1/n, y_n)$, where $y_n$ is the abscissa of the intersection of $f_n$ and $g_n$, we have

$$\begin{align*}
\lim_{n \to \infty} \frac{|F(0 + h_n) - F(0) - F'(h_n) \cdot h_n|}{|h_n|} &= \lim_{n \to \infty} \frac{|b_n(h_n - m_{2n}) - b_n h_n|}{h_n} \\
&\ge \lim_{n \to \infty} \frac{b_n m_{2n}}{m_n} \quad [h_n \le m_n] \\
&= 1,
\end{align*}$$

which is nonzero. Taking $h_n = m_n$ would have given the limit $1/2$. Hence, the condition (4.47) does not hold.

### 4.4.2 Generalized Differentiability

#### Definition

Let $\mathbb{E}$ and $\mathbb{F}$ be two finite dimensional normed spaces and $F: \mathbb{E} \to \mathbb{F}$ be a function. We assume that the reader is aware of the notions introduced in sections 1.3.2 and 1.3.4.

**Definitions 4.15 (B-differential, C-differential)** The B-differential<fnref n="3" /> of $F$ at $x$ is the set denoted and defined by

$$\partial_B F(x) := \{J \in \mathcal{L}(\mathbb{E}, \mathbb{F}) : \exists \{x_k\} \subseteq \mathcal{D}_F \text{ such that } x_k \to x, F'(x_k) \to J\}.$$

The C-differential<fnref n="4" /> of $F$ at $x$ is the convex hull of the B-differential, namely

$$\partial_C F(x) := \co \partial_B F(x). \quad \square$$

<footnote n="3">³ The “B” of the B-differential is honoring Bouligand [122].</footnote>

<footnote n="4">⁴ The “C” of the C-differential is for Clarke.</footnote>
If $F: \mathbb{E} \to \mathbb{F}$ is differentiable near $x \in \mathbb{E}$ and if $F'$ is continuous at $x$, it is clear that $\partial_B F(x) = \partial_C F(x) = \{F'(x)\}$. But if $F$ is Lipschitz near $x$ and only differentiable at $x$, $\partial_C F(x)$ is not necessarily a singleton (Kummer's function in section 4.4.1, with its properties (4.46c) and (4.46d), will provide an example of this curiosity); nevertheless, by taking $x_k = x$ for all $k$ in the definition of $\partial_B F(x)$, we see that $F'(x) \in \partial_B F(x)$ in this case.

We refer the reader to the monograph [32] for a detailed study of the C-differential. Below, we try to say as little as possible, although enough to cover our future needs. The notion of upper semi-continuous multifunction used below has been introduced in section 1.3.4.

**Proposition 4.16 (compactness and upper semi-continuity)** If $F: \Omega \to \mathbb{F}$ is $L$-Lipschitz near $x \in \Omega$, then

1) $\partial_C F(x)$ is nonempty compact ($\subseteq L\bar{B}$) and convex,

2) $\partial_C F$ is upper semi-continuous at $x$.

*Proof.* 0) Let us start by showing that $\|F'(x_0)\| \le L$ for all $x_0 \in \mathcal{D}_F$ near $x$. By the differentiability of $F$ at $x_0$, it follows that $F(x') = F(x_0)+F'(x_0)(x'-x_0)+o(\|x'-x_0\|)$. Hence, for small $\varepsilon > 0$, there exists $\delta > 0$ such that, for $x' \in \bar{B}(x_0, \delta)$, one has $\|F'(x_0)(x'-x_0)\| \le \|F(x') - F(x_0)\| + \varepsilon\|x' - x_0\| \le (L + \varepsilon)\|x' - x_0\|$. We deduce from this that $\|F'(x_0)\| \le L + \varepsilon$, and next that $\|F'(x_0)\| \le L$ since $\varepsilon > 0$ is arbitrary.

1) The C-differential is convex by construction. Next, it suffices to show that $\partial_B F(x)$ is nonempty, closed, and in $L\bar{B}$ (since, according to (1.2), the convex hull of a compact set is compact).

* $[\partial_B F(x) \ne \emptyset]$ Since $\Omega \setminus \mathcal{D}_F$ has measure zero, one can find a sequence $\{x_k\} \subseteq \mathcal{D}_F$ converging to $x$ (otherwise there would exists an $\varepsilon > 0$ such that $x + \varepsilon B \subseteq \Omega \setminus \mathcal{D}_F$, which is in contradiction with the zero measure of $\Omega \setminus \mathcal{D}_F$). Since the sequence $\{F'(x_k)\}$ is bounded (point 0), one can extract a convergent subsequence. The limit of this one is therefore in $\partial_B F(x)$, by definition of this last set.

* $[\partial_B F(x)$ is closed] Indeed, if $\{J_k\} \subseteq \partial_B F(x)$ and $J_k \to J$, then, for all $\varepsilon > 0$, one can find an index $k$ such that $\|J_k - J\| \le \varepsilon$ and a point $x_k \in \mathcal{D}_F$ such that $\|F'(x_k) - J_k\| \le \varepsilon$ and $\|x_k - x\| \le \varepsilon$. Clearly, when $\varepsilon \downarrow 0$, the sequence $\{x_k\}$ so constructed converges to $x$ and $F'(x_k)$ converges to $J$. Hence $J \in \partial_B F(x)$.

* $[\partial_B F(x) \subseteq L\bar{B}]$ Any element $J \in \partial_C F(x)$ is the limit of operators $F'(x_k)$ with a norm not exceeding $L$ (point 0). Hence $\|J\| \le L$, by the continuity of the norm.

2) It suffices to show that,

$$ \forall \varepsilon > 0, \exists \delta > 0, \forall x' \in x + \delta B: \partial_B F(x') \subseteq \partial_C F(x) + \varepsilon B. $$

Indeed, this last inclusion implies the desired inclusion $\partial_C F(x') \subseteq \partial_C F(x) + \varepsilon B$, since $\partial_C F(x) + \varepsilon B$ is a convex set.

We proceed by contradiction. If the claim is not true, there exists $\varepsilon > 0$ and a sequence $\{x_k\} \subseteq \mathbb{E}$ converging to $x$ and elements $J_k \in \partial_B F(x_k)$ that are not in $\partial_B F(x) + \varepsilon B$. Then,

$$ (J_k + \frac{\varepsilon}{2} B) \cap (\partial_B F(x) + \frac{\varepsilon}{2} B) = \emptyset. $$
The fact that $J_k \in \partial_B F(x_k)$ implies, by definition, that there is a point $\tilde{x}_k \in D_F$ such that $\|\tilde{x}_k - x_k\| \le 1/k$ and $F'(\tilde{x}_k) \in J_k + \frac{\epsilon}{2}B$. On the other hand, since $x_k \to x$, the sequence $\{F'(x_k)\}$ is bounded and, by extracting a subsequence if needed, one can assume that it converges to some $J$. Then, one would have $\tilde{x}_k \to x$ and $F'(\tilde{x}_k) \to J$, so that $J \in \partial_B F(x)$. But then $F'(\tilde{x}_k) \in \partial_B F(x) + \frac{\epsilon}{2}B$ for $k$ large. We have the contradiction since $F'(\tilde{x}_k)$ belongs to the two sets $J_k + \frac{\epsilon}{2}B$ and $\partial_B F(x) + \frac{\epsilon}{2}B$, which have been shown to be disjoint. $\square$

## Properties

The standard quadratic convergence result of the Newton method to solve the smooth system $F(x) = 0$ requires that the Jacobian $F'(x_*)$ be nonsingular at the sought root $x_*$ (this has been recalled in proposition 1.48). When $F \in C^1$, this nonsingularity property is “diffused” to the Jacobians $F'(x)$ if $x$ is close to $x_*$ (this is due to the continuity of $F'$ and the fact that the set of nonsingular operators is open), which makes the Newton algorithm well defined in a neighborhood of a “regular” root of $F$. This diffusion property is made precise in the following Banach perturbation lemma, which is recalled below in the finite dimension setting.

**Lemma 4.17 (Banach perturbation lemma)** Let $\mathbb{E}$ and $\mathbb{F}$ be two vector spaces, $A : \mathbb{E} \to \mathbb{F}$ be a nonsingular linear operator, and $B : \mathbb{E} \to \mathbb{F}$ be another linear operator sufficiently close to $A$ in the sense that $\|A^{-1}(B - A)\| < 1$. Then, $B$ is also nonsingular and

$$ \|B^{-1}\| \le \frac{\|A^{-1}\|}{1 - \|A^{-1}(B - A)\|} $$

In the case of the semismooth Newton algorithm of section 4.4.4, this regularity assumption becomes the nonsingularity of all the generalized Jacobians in $\partial_C F(x_*)$, a property that is called C-regularity.

**Definitions 4.18 (regular C-differential, C-regular point)** The C-differential $\partial_C F(x)$ is said to be regular if all its jacobians $J \in \partial_C F(x)$ are nonsingular. Then, one also say that the point $x$ is C-regular for $F$. $\square$

The next proposition shows a property similar to the Banach perturbation lemma, but for a locally Lipschitz function $F$: the points close to a C-regular point for $F$ are also C-regular and a bound on the Jacobians of their C-differential, and their inverse, can be given.

**Proposition 4.19 (C-regularity diffusion)** If $F : \mathbb{E} \to \mathbb{F}$ is Lipschitz near a C-regular point $x \in \mathbb{E}$, then, there are constants $C > 0$ and $\delta > 0$ such that any
point in $B(x, \delta)$ is C-regular and

$$ \sup_{\substack{x' \in B(x, \delta) \\ J \in \partial_C F(x')}} \max (\|J\|, \|J^{-1}\|) \le C. \quad (4.48) $$

*Proof.* 1) Let us first show the bound on $\|J\|$. By point 1 of proposition 4.16, we know that $\partial_C F(x) \subseteq L_x \bar{B}$, for a constant $L_x \ge 0$ depending on $x$. We now use the upper semi-continuity of $\partial_C F$ with the open neighborhood $\partial_C F(x) + B$ of $\partial_C F(x)$: one can find $\varepsilon > 0$ such that, if $x' \in B(x, \varepsilon)$, it follows that $\partial_C F(x') \subseteq \partial_C F(x) + B$. As a result, for all $x' \in B(x, \varepsilon)$ and all $J \in \partial_C F(x')$, we have $\|J\| \le L_x + 1$.

2) Let us now show the bound on $\|J^{-1}\|$. Consider first a particular Jacobian $J_0 \in \partial_C F(x)$. This one is nonsingular by the C-regularity of $x$. By the Banach perturbation lemma, if $\|J - J_0\| \le \varepsilon(J_0) := 1/(2\|J_0^{-1}\|)$, it follows that $\|J_0^{-1}(J - J_0)\| \le 1/2$ and therefore

$$ \|J^{-1}\| \le \frac{\|J_0^{-1}\|}{1 - \|J_0^{-1}(J - J_0)\|} \le 2\|J_0^{-1}\|. \quad (4.49) $$

Consider now a cover of $\partial_C F(x)$ by the open sets $\{J + \varepsilon(J)B : J \in \partial_C F(x)\}$. By the compacity of $\partial_C F(x)$ (point 1 of proposition 4.16), one can extract a finite sub-cover (Heine-Borel-Lebesgue property): one can find $m$ elements $J_i \in \partial_C F(x)$, such that the open set

$$ V := \bigcup_{i \in [1:m]} (J_i + \varepsilon(J_i)B) $$

covers $\partial_C F(x)$. Remark that the operators in $V$ have bounded inverses: for all $J \in V$, one has

$$ \|J^{-1}\| \le \max_{i \in [1:m]} 2\|J_i^{-1}\| =: \beta. \quad (4.50) $$

thanks to (4.49). It now suffices to show that $\partial_C F(x') \subseteq V$ when $x'$ is close to $x$. To this end, one uses the compacity of $\partial_C F(x)$ and the upper semi-continuity of $\partial_C F$.

By compacity of $\partial_C F(x)$, one can find an $\varepsilon > 0$ such that

$$ \partial_C F(x) + \varepsilon B \subseteq V. $$

Indeed, otherwise, one could find operator sequences $\{J_k'\}$ and $\{J_k''\}$ such that $J_k' \notin V$, $J_k'' \in \partial_C F(x)$, and $\|J_k' - J_k''\| \le 1/k$. By compacity $\partial_C F(x)$, one can extract a subsequence of $\{J_k''\}$ converging to some $J \in \partial_C F(x)$. Obviously $J_k' \to J$, so that $J_k'$ is in some $J_i + \varepsilon(J_i)B$ for some $i \in [1:m]$, and therefore $J_k' \in V$, which contradicts the starting assumption.

Finally, by the upper semi-continuity of $\partial_C F$: one can find a $\delta > 0$ such that, if $x' \in x + \delta B$, one has $\partial_C F(x') \subseteq \partial_C F(x) + \varepsilon B \subseteq V$, which is what we wanted to show. $\square$
### 4.4.3 Semismoothness ▲

#### Definition

Throughout this section, $\mathbb{E}$ and $\mathbb{F}$ are two normed spaces and $\Omega$ be an open set of $\mathbb{E}$.

**Definitions 4.20 (semismoothness)** Let $F: \Omega \to \mathbb{F}$ be a function and $x \in \Omega$. The function $F$ is said to be *semismooth* at $x$ if the following three conditions hold:

(SS1) $F$ is Lipschitz near $x$,

(SS2) $F$ has directional derivatives at $x$ in all directions,

(SS3) when $h \to 0$ in $\mathbb{E}$, one has

$$ \sup_{J \in \partial_C F(x+h)} \|F(x+h) - F(x) - Jh\| = o(\|h\|). \quad (4.51a) $$

The function $F$ is said to be *strongly semismooth* at $x$ if it is strongly semismooth at $x$ with (SS3) strengthened into

(SS3') for $h$ near 0, one has

$$ \sup_{J \in \partial_C F(x+h)} \|F(x+h) - F(x) - Jh\| = O(\|h\|^2). \quad (4.51b) $$

The function $F: \Omega \to \mathbb{F}$ is said to be *semismooth* (resp. *strongly semismooth*) on a part $P$ of $\Omega$ if it is semismooth (resp. strongly semismooth) at all points of $P$. $\square$

**Remarks 4.21 1) The local Lipschitz continuity of $F$ at $x$ in (SS1) guarantees that the Clarke differential $\partial_C F$ is well defined and nonempty near $x$ (point 1 of proposition 4.16), so that its use in (SS3) and (SS3') makes sense. Property (SS2) is useful so that the semismoothness enjoys good properties, those given in propositions 4.23-4.29 below. As announced in the discussion of section 4.4.1, property (SS3) is the one that ensures the superlinear convergence of the semismooth Newton algorithm and property (SS3') its quadratic convergence (theorem 4.31). We stress again the fact that, in (SS3) and (SS3'), the Jacobians $J$ are taken in the $C$-differential $\partial_C F(x+h)$ and not in $\partial_C F(x)$, as one could be tempted for mimicking the Fréchet differentiability; the motivation of this choice has been given in section 4.4.1.**

2) The differential $\partial_C F$ is not always easy to compute. However, if an overestimate $D$ of this one is known, in the sense that $\partial_C F(x') \subseteq D(x')$ for all $x'$ near the point $x$ of interest, and if (4.51a) or (4.51b) can be verified with $\partial_C F$ replaced by $D$, the corresponding smoothness property will hold.

As shown in the next proposition, semismoothness (resp. strong semismoothness) can be defined by other properties. More precisely, the assumption (SS3) (resp. (SS3')) can be replaced by other assumptions.
**Proposition 4.22 (semismoothness characterizations)** Let $F: \Omega \to \mathbb{F}$ be a function and $x \in \Omega$. Suppose that $F$ satisfies (SS1) and (SS2). Then the following properties are equivalent:

(i) $F$ is semismooth (resp. strongly semismooth) at $x$,

(ii) for $h \to 0$, there holds

$$ \sup_{J \in \partial_C F(x+h)} \|Jh - F'(x; h)\| = o(\|h\|) \quad (\text{resp.} = O(\|h\|^2)), $$

(iii) for $h \to 0$ such that $x+h \in D_F$, there holds

$$ F'(x+h)h - F'(x; h) = o(\|h\|) \quad (\text{resp.} = O(\|h\|^2)). $$

*Proof.*

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

## Properties

Here are a few useful properties of semismooth functions. There is no need to know them for proving theorem 4.31 giving the local convergence of the semismooth Newton algorithm, but they are very useful for recognizing the semismoothness of functions and therefore for knowing whether the convergence result applies to them.

The first property tells us that sufficiently smooth functions are semismooth, which is somehow reassuring.

**Proposition 4.23 (differentiability and semismoothness)** If $F: \Omega \to \mathbb{F}$ is differentiable near $x \in \Omega$ and $F'$ is continuous at $x$ (resp. radially Lipschitz at $x$), then $F$ is semismooth (resp. strongly semismooth) at $x$.

*Proof.* [(SS1)] By the mean value theorem 1.24, for $x_1$ and $x_2$ near $x$, there holds

$$ \|F(x_2) - F(x_1)\| \le \left( \sup_{z \in (x_1, x_2)} \|F'(z)\| \right) \|x_2 - x_1\|. $$

By the continuity of $F'$ at $x$, the first factor in the right-hand side is as close to $\|F'(x)\|$ as desired, by taking $x_1$ and $x_2$ sufficiently close to $x$. Le Lipschitz continuity of $F$ near $x$ follows.

[(SS2)] This property is a consequence of the differentiability of $F$ at $x$: $F'(x; h) = F'(x)h$.

[(SS3)] By the differentiability of $F$ at $x$ and the continuity of $F'$ at $x$, we get

$$ F(x+h) - F(x) - F'(x+h)h = (F'(x) - F'(x+h))h + o(\|h\|) = o(\|h\|). $$

[(SS3')] Assume now that $F'$ is radially L-Lipschitz at $x$. By the mean value corollary 1.25, for $h$ small, there holds
124 4. A Few Methods for Nonsmooth Systems

$$
\begin{align*}
& \|F(x+h) - F(x) - F'(x+h)h\| \\
\le & \left( \sup_{z \in (x, x+h)} \|F'(z) - F'(x+h)\| \right) \|h\| \\
\le & L \left( \sup_{t \in (0,1)} \|(1-t)x + t(x+h) - (x+h)\| \right) \|h\| \\
\le & L \|h\|^2.
\end{align*}
$$

This shows the strong semismoothness of F at x.

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

**Proposition 4.24 (semismoothness of a convex function)** If $f: \Omega \to \mathbb{R}$ is convex on the open convex set $\Omega \subseteq \mathbb{E}$ and if $x \in \Omega$, then $f$ is semismooth at $x$.

*Proof*. A convex function is Locally Lipschitz on the relative interior of its domain [65], hence certainly on $\Omega$ in our case. It has also directional derivatives at any point of its domain (but these can have infinite values), which have here finite values since $f$ takes only finite values on $\Omega$. In addition, $\partial_C f(x)$ is the subdifferential of $f$ at $x$ in the sense of convex analysis [32; propositions 2.2.6 and 2.2.7]. . . . (for the sequel, see [100] or the prof of [50; prop. 7.4.5(c)]). $\square$

In the proposition below, $F: \Omega \to \mathbb{F}$ is said to be piecewise semismooth at $x \in \Omega$, if there is a neighborhood $V$ of $x$ and semismooth functions $F_i: V \to \mathbb{F}$, for $i \in I$ with finite $|I|$, such that, for all $x' \in V$, there is an index $i \in I$ such that $F(x') = F_i(x')$.

**Proposition 4.25 (piecewise semismoothness)** If $F: \Omega \to \mathbb{F}$ is piecewise semismooth at $x \in \Omega$, then $F$ is semismooth en $x$.

The function $F$ is said to be piecewise affine at $x$ if the pieces in the definition of piecewise semismoothness are affine.

**Proposition 4.26 (piecewise affinity)** If $F: \Omega \to \mathbb{F}$ is piecewise affine at $x \in \Omega$, then $F$ is strongly semismooth at $x$.

The semismoothness of a vector-valued function can be deduced from the semismoothness of its components.

**Proposition 4.27 (componentwise semismoothness)** Let $F_1: \Omega \to \mathbb{F}_1$ and $F_2: \Omega \to \mathbb{F}_2$ be two functions with values in the finite dimensional normed spaces $\mathbb{F}_1$ and $\mathbb{F}_2$, and let $x \in \Omega$. Then,
$$ (F_1, F_2) : x' \in \Omega \to (F_1(x'), F_2(x')) \in \mathbb{F}_1 \times \mathbb{F}_2 $$

is semismooth (resp. strongly semismooth) at $x$ if and only if $F_1$ and $F_2$ are semismooth (resp. strongly semismooth) at $x$.

Semismoothness is stable by composition.

**Proposition 4.28 (semismoothness and composition)** If $F : \Omega \to \mathbb{F}$ is semismooth (resp. strongly semismooth) at $x \in \Omega$, if $\Omega_{\mathbb{F}}$ is a neighborhood of $F(x)$ in $\mathbb{F}$, and if $G : \Omega_{\mathbb{F}} \to \mathbb{G}$ is semismooth (resp. strongly semismooth) at $F(x)$, then $G \circ F$ is semismooth (resp. strongly semismooth) at $x$.

An important asset of the semismoothness is to be stable with respect to the minimum or maximum of functions, which is of course not the case for the Fréchet differentiability! Since many nonsmooth functions can be defined by using these operators, these functions are often semismooth.

**Proposition 4.29 (calculus)** If $F_1 : \Omega \to \mathbb{F}$ and $F_2 : \Omega \to \mathbb{F}$ are semismooth (resp. strongly semismooth) at $x$, then the following functions are semismooth (resp. strongly semismooth) at $x$ (for the last two, $\mathbb{F} = \mathbb{R}^m$ and the operators "max" and "min" act componentwise):

$$ F_1 + F_2, \quad \langle F_1, F_2 \rangle, \quad \max(F_1, F_2), \quad \text{and} \quad \min(F_1, F_2). $$

*Proof.* The semismoothness result for $F_1 + F_2$ can be obtained by viewing this function as the composition of $x \mapsto (F_1(x), F_2(x))$, which is semismooth (resp. strongly semismooth) by proposition 4.27, and the addition $(u, v) \mapsto u + v$, that is linear. Now, use proposition 4.28 to conclude.

The function $\langle F_1, F_2 \rangle$ is also a composition of semismooth (resp. strongly semismooth) functions, namely $x \mapsto (F_1(x), F_2(x))$ like above and the scalar product of $\mathbb{F}$, which is bilinear, hence $C^\infty$.

The function $\max(F_1, F_2)$ (the same reasoning holds for $\min(F_1, F_2)$) is still the composition of $x \mapsto (F_1(x), F_2(x))$ and the function $(u, v) \in \mathbb{F} \times \mathbb{F} \mapsto \max(u, v)$ which is piecewise linear, hence strongly semismooth by proposition 4.26. $\square$

Here are a few examples and counter-examples of (strongly) semismooth functions.

**Examples 4.30 1)** We already know that a norm is semismooth, due to its convexity (proposition 4.24). The $\ell_p$ norms are, furthermore, strongly semismooth (exercise 4.4.1).

2) The “min” and Fischer C-functions, (4.43) and (4.44), are strongly semismooth (exercise 4.4.2).
3) The projector on a convex set defined by $C^2$ constraints is strongly semismooth at a point of the convex set that satisfies (CQ-LI) (exercise ??).

4) For an arbitrary convex set $C$, the projector $P_C$ may not have directional derivatives at a point not belonging to $C$ [86, 128] and is therefore not semismooth at such a point. This is not good news for solving variational inequality problem using the reformulation in example 4.13(2). Nevertheless, the situation is more favorable if $C$ is a polyhedron or has a smooth boundary. Also semismooth-Newton-like algorithms give excellent results by using some kind of pseudo-generalized Jacobians [93; 2018]. □

### 4.4.4 The Semismooth Newton Method ▲

The semismooth Newton algorithm is designed to solve the system (4.40), in which $F: \Omega \to \mathbb{F}$ is semismooth (section 4.4.3). Locally (i.e., near a solution $x_*$ to this system), it consists in generating a sequence $\{x_k\}$ in the open set $\Omega \subseteq \mathbb{E}$ by the recurrence

$$x_{k+1} := x_k - J_k^{-1} F(x_k), \qquad (4.52)$$

where $J_k$ is a nonsingular Jacobian of the Clarke differential $\partial_C F(x_k)$. To be well defined, it is clear that such a Jacobian must exist in the C-differential of $F$ at the visited points. But the technique of proof used below requires a little more than that, namely the boundedness of the sequence of inverses $\{J_k^{-1}\}$ and the property (SS3) or (SS3') of the semismoothness. In the terms of theorem 4.31 below, the boundedness of $\{J_k^{-1}\}$ is ensured by the regularity of $\partial_C F(x_*)$ and proposition 4.19.

It is important to observe that the semismooth Newton method is particularly computationally sober, since it only requires to solve a linear system per iteration, like the Newton algorithm for smooth systems, but unlike the JN algorithm for functional inclusions (section 4.1.2) or the SQP algorithm for nonlinear optimization (section 5.1), derived from the latter. Now, all these algorithms are not used to solve similar problems and cannot be globalized with the same ease.

**Theorem 4.31 (local convergence of the semismooth Newton algorithm)** Suppose that $F$ is semismooth at a C-regular solution $x_*$ to (4.40). Then, there exists a neighborhood $V$ of $x_*$ such that, if the first iterate $x_1$ is in $V$, the semismooth Newton algorithm (4.52) is well defined and generates a sequence $\{x_k\}$ in $V$, which converges superlinearly to $x_*$ (and quadratically if $F$ is strongly semismooth at $x_*$).

*Proof.* The regularity of $\partial_C F(x_*)$ and proposition 4.19 imply that there exist constants $C_1 > 0$ and $\varepsilon_1 > 0$ such that

$$\sup_{\substack{x \in \bar{B}(x_*, \varepsilon_1) \\ J \in \partial_C F(x)}} \max (\|J\|, \|J^{-1}\|) \le C_1. \qquad (4.53)$$

By the semismoothness property (SS3) of $F$ at $x_*$, one can find $\varepsilon \in (0, \varepsilon_1]$ such that
$$ \|F(x) - F(x_{*}) - J(x - x_{*})\| \le \frac{1}{2C_{1}} \|x - x_{*}\|, \qquad (4.54) $$

when $x \in \bar{B}(x_{*}, \varepsilon)$ and $J \in \partial_{C}F(x)$.

Suppose now that $x_k \in V := \bar{B}(x_{*}, \varepsilon)$. Then the algorithm is well defined at this point since any Jacobian $J_k$ chosen in $\partial_C F(x_k)$ is nonsingular (by $\varepsilon \le \varepsilon_1$ and (4.53)). A new iterate $x_{k+1}$ can therefore be computed by (4.52). One has

$$ x_{k+1} - x_{*} = x_{k} - x_{*} - J_{k}^{-1} F(x_{k}) = -J_{k}^{-1}(F(x_{k}) - F(x_{*}) - J_{k}(x_{k} - x_{*})), $$

hence

$$ \|x_{k+1} - x_{*}\| \le \|J_{k}^{-1}\| \|F(x_{k}) - F(x_{*}) - J_{k}(x_{k} - x_{*})\|. \qquad (4.55) $$

By (4.53) and (4.54), $\|x_{k+1} - x_{*}\| \le \frac{1}{2}\|x_{k} - x_{*}\|$, which shows that $x_{k+1} \in \bar{B}(x_{*}, \varepsilon) = V$, the wellposedness of the algorithm, and the convergence of the convergence $\{x_k\}$ to $x_*$.

Then, the semismoothness implies that $F(x_k) - F(x_*) - J_k(x_k - x_*) = o(\|x_k - x_*\|)$, so that $x_{k+1} - x_* = o(\|x_k - x_*\|)$ by (4.55) and (4.53). This is the superlinear convergence of $\{x_k\}$ to $x_*$.

In case of strong semismoothness, $F(x_k) - F(x_*) - J_k(x_k - x_*) = O(\|x_k - x_*\|^2)$, so that $x_{k+1} - x_* = O(\|x_k - x_*\|^2)$ by (4.55) and (4.53), showing that the convergence is quadratic. □

### 4.4.5 Globalization by linesearch ▲

It is well known that the Newton direction is a descent direction to the least-squares merit function. If this surprising local property is not able to ensure global convergence of the damped Newton iterates to a zero of $F$, when this one exists, it paves the way to algorithmic techniques having interesting properties, in particular when trust regions are used.

This descent property is no longer guaranteed when $F$ is only semismooth. Nevertheless, when the least-squares merit function is smooth, some interesting properties can be obtained [78; 1999]. We describe this particular case in this section.

Let us start by giving a concrete example of such a situation, which has numerous applications.

Here is a short review of what has been explored.

* Jiang and Ralph [78; 1999] analyze semismooth Newton and Gauss-Newton algorithms, globalized with lineaserch or trust regions on the least-squares merit function, provided this one is smooth (with application to the nonlinear complementarity problem).

* Ueda and Yamashita [134; 2012] also suppose that the least-squares merit function is smooth and analyze the complexity of the Levenberg-Morrison-Marquardt approach for nonsmooth equations (with application to the nonlinear complementarity problem).

* See also [114; 2016] (with application to the nonlinear complementarity problem) and many other papers.
### 4.4.6 Globalization by trust regions ▲

### 4.4.7 Examples of use ▲

#### Notes

The notion of semismoothness was first introduced by Mifflin [100; 1977] for real-valued functions and extended to vector-valued functions by Qi and Sun [112, 113; 1993]. Excellent textbooks have been written on the semismooth Newton method; let us cite [83, 50, 74, 76; 2002-2014].

#### Exercises

4.4.1. Strong semismoothness of the $l_p$-norm. For $p \in [1, \infty]$, the $l_p$-norm $\| \cdot \|_p : \mathbb{R}^n \to \mathbb{R}$, defined at $x \in \mathbb{R}^n$ by

$$ \|x\|_p = \begin{cases} \left(\sum_{1 \le i \le n} |x_i|^p\right)^{1/p} & \text{if } 1 \le p < \infty, \\ \max_{1 \le i \le n} |x_i| & \text{if } p = \infty, \end{cases} $$

is strongly semismooth.

4.4.2. Strong semismoothness of C-functions. The C-function “min” (4.43) and of Fischer (4.44) are strongly semismooth.

### 4.5 Reformulation Methods for Complementarity Problems ▲

Let $\mathbb{E}$ be a Euclidean space, and $F: \mathbb{E} \to \mathbb{R}^n$ and $G: \mathbb{E} \to \mathbb{R}^n$ be two smooth functions. The (nonlinear) complementarity problem (CP) consists in finding a point $x \in \mathbb{E}$ such that

$$ 0 \le F(x) \perp G(x) \ge 0. \quad (4.56) $$

This system means that $x$ must be such that $F(x) \ge 0$ and $G(x) \ge 0$, componentwise, and $F(x)^T G(x) = 0$. A more general setting is presented in (4.56); here, we limit our presentation to the case where the functions $F$ and $G$ take their values in $\mathbb{R}^n$ and the cone $K$ of $\mathbb{R}^n$ is its nonnegative orthant $\mathbb{R}_+^n$ (recall that $\mathbb{R}_+^n$ is self-dual, meaning that its positive dual cone $(\mathbb{R}_+^n)^+)$ is $\mathbb{R}_+^n$). Less or more recent states of the art on the analysis of complementarity problems and numerical methods to solve them can be found in [103, 73, 107, 50, 39, 40, 76].

Occasionally, we shall make reference to the linear complementarity problem (LCP) in its standard form, which reads

$$ 0 \le x \perp (Mx + q) \ge 0, \quad (4.57) $$

where its unknown is $x \in \mathbb{R}^n$, while $q \in \mathbb{R}^n$ and $M \in \mathbb{R}^{n \times n}$ are its data. It corresponds to the nonlinear complementarity problem (4.56) with $F: x \mapsto Mx + q$ is affine and $G: x \mapsto x$ is the identity operator.

A major difficulty of problem (4.56) (and (4.57)) comes from its combinatorial aspect. Since both $F(x)$ and $G(x)$ must have nonnegative components, the orthogonality conditions $F(x)^T G(x) = 0$ is equivalent to the $n$ identities
$$ \forall i \in [1:n]: \quad F_i(x)G_i(x) = 0. \qquad (4.58) $$

There are $2^n$ possibilities to realize (4.58), by forcing, for each $i \in [1:n]$, either $F_i(x)$ of $G_i(x)$ to vanish. This fact yields much difficulty to the algorithms to find a solution. For instance, even when the functions $F$ and $G$ are affine like in (4.57), finding a solution is NP-hard [31, 84; 1989-1991].

Since at a solution $\bar{x}$ to (4.56), either $F(\bar{x}) = G(\bar{x}) = 0$, or $0 = F(\bar{x}) < G(\bar{x})$, or $F(\bar{x}) > G(\bar{x}) = 0$, it is natural to introduce the following index sets:

$$ \begin{aligned} \mathcal{E}(x) &:= \{i \in [1:n] : F_i(x) = G_i(x)\}, \\ \mathcal{F}(x) &:= \{i \in [1:n] : F_i(x) < G_i(x)\}, \\ \mathcal{G}(x) &:= \{i \in [1:n] : F_i(x) > G_i(x)\}. \end{aligned} \qquad (4.59) $$

Obviously, these form a partition of $[1:n]$.

The decomposition of the orthogonality condition $F(x)^T G(x) = 0$ into the $n$ complementarity conditions (4.58) also shows that these count for $n$ equations. Indeed, if the index sets $\mathcal{E}(\bar{x})$, $\mathcal{F}(\bar{x})$, and $\mathcal{G}(\bar{x})$ at a solution $\bar{x}$ of (4.56) were known, this solution would also satisfy the following system of $n$ equations

$$ \begin{cases} F_i(x) = 0 & \text{if } i \in \tilde{\mathcal{F}}(\bar{x}), \\ G_i(x) = 0 & \text{if } i \in \tilde{\mathcal{G}}(\bar{x}), \end{cases} $$

where the pair $(\tilde{\mathcal{F}}(\bar{x}), \tilde{\mathcal{G}}(\bar{x}))$ forms a partition of $[1:n]$ and satisfies $\tilde{\mathcal{F}}(\bar{x}) \supseteq \mathcal{F}(\bar{x})$ and $\tilde{\mathcal{G}}(\bar{x}) \supseteq \mathcal{G}(\bar{x})$, together with the implicit constraints $F(x) \ge 0$ and $G(x) \ge 0$. Therefore, the system (4.56) has more chance to be well-posed if $\dim \mathbb{E} = n$. It is often the case that the complementarity system (4.56) is completed by equality constraints; the system is then called a *mixed complementarity problem*; if there is $m$ such equalities, it is natural to have $\dim \mathbb{E} = n + m$.

Complementarity conditions arise spontaneously in the first order optimality conditions of an optimization problem with inequality constraints and these conditions can be written like the system (4.56); see (1.58c) in the KKT system or, more generally, (??).. The complementarity system (4.56) is also often used to model in part problems in which several systems of equations are, to some extend, in competition. The one that is active in a given place and at a given time, corresponding to a common index of $F(x)$ and $G(x)$, depends on threshold effects; if the threshold $F_i(x) = 0$ is not reached, i.e., $F_i(x) > 0$, then the equation $G_i(x) = 0$ is active, and vice versa. Examples include problems in nonsmooth mechanics and dynamics [1, 25], the phase transition problem in multiphase flows [98, 99, 12, 41, 9, 27, 10, 11], precipitation-dissolution problems in chemistry [26, 85], portfolio management in finance [58], computer graphics [48], meteorology simulation, economic equilibrium, to mention a few. Surveys on examples of applications of the complementarity problem can be found in [63, 73, 107, 52, 50].

Many techniques have been proposed to solve (4.56) since the problem was introduced by Cottle in his PhD thesis, dated 1964 [36, 37]. It is out of the scope of this section to review all of them and we refer instead the interested reader to the monographs [50, 76]. Below, we limit our account to the algorithms using the two most often encountered reformulation of (4.56) in the form of a nonsmooth equation. The reformulation by the Fischer function is examined in section 4.5.1 and the reformulation using the minimum function is considered in sections 4.5.2 and 4.5.2.
### 4.5.1 Fischer-Newton Algorithm

#### The Fischer C-Function

In this section, we consider the reformulation based on the Fischer [54] C-function $\varphi_F : \mathbb{R}^2 \to \mathbb{R}$, defined at $(a, b) \in \mathbb{R}^2$ by

$$ \varphi_F(a, b) = \sqrt{a^2 + b^2} - (a + b). \qquad (4.60) $$

This is indeed a C-function since, for two real numbers $a$ and $b$, $\varphi_F(a, b) = 0$ if and only if $a \ge 0$, $b \ge 0$, and $ab = 0$. This function is convex (it is the Euclidean norm plus a linear function) and is $C^\infty$, except at $(a, b) = (0, 0)$ where it is non differentiable. The function is strongly semismooth however (exercise 4.4.2).

The equation reformulation of (4.56) using $\varphi_F$ reads

$$ \Phi_F(x) = 0, \qquad (4.61a) $$

where $\Phi_F : \mathbb{R}^n \to \mathbb{R}^n$ is defined at $x$ by

$$ \Phi_F(x) = \varphi_F(F(x), G(x)), \qquad (4.61b) $$

where $\varphi_F$ acts componentwise. A natural merit function associated with the reformulation (4.61) is the least-square function $\theta_F : \mathbb{R}^n \to \mathbb{R}$, defined at $x \in \mathbb{R}^n$ by

$$ \theta_F(x) = \frac{1}{2} \|\Phi_F(x)\|^2, $$

where $\| \cdot \|$ denotes the Euclidean norm.

We have the following smoothness result.

**Proposition 4.32 (smoothness of the Fischer reformulation)** If $F$ and $G$ are $C^{1,1}$, then $\Phi_F$ is locally Lipschitz and $\theta_F$ is $C^{1,1}$.

*Proof.* See [51, 30].

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

#### Globalization

A function $F : \mathbb{E} \to \mathbb{E}$ is called a *uniform P-function* [29] if there is an $\alpha > 0$ such that for all $x, y \in \mathbb{E}$:

$$ \max_{i \in [1:n]} (y_i - x_i)(F_i(y) - F_i(x)) \ge \alpha \|y - x\|^2. $$
**Proposition 4.33 (smoothness of the Fischer reformulation) Suppose F :**
$\mathbb{R}^n \to \mathbb{R}^n$ is a $C^1$ uniform P-function. Then, for any $x \in \mathbb{R}^n$ and any $J \in \partial\Phi_F(x)$,
$J$ is nonsingular.

*Proof.* See [77; 1997, proposition 3.2].

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

### 4.5.2 Newton-Min Algorithm

#### The Minimum C-Function

In this section, we consider the reformulation based on the Minimum C-function $\varphi_{\min}: \mathbb{R}^2 \to \mathbb{R}$, defined at $(a, b) \in \mathbb{R}^2$ by

$$ \varphi_{\min}(a, b) = \min(a, b). \qquad (4.62) $$

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

This is indeed a C-function since, for two real numbers $a$ and $b$, $\varphi_{\min}(a, b) = 0$ if and only if $a \ge 0$, $b \ge 0$, and $ab = 0$. This function is concave (minimum of two linear functions) and strongly semismooth (exercise 4.4.2).

#### Plain Newton-Min algorithm

#### Polyhedral Newton-Min Algorithm

#### Notes

There are many other C-functions than those used in sections 4.5.1 and 4.5.2 that have been proposed in the literature. Tseng [133] studies the C-function obtained by replacing the $l_2$ norm of $(a, b)$ in the Fischer Function by its $l_p$ norm.
<figure><img src="image_43.png" /></figure>
# 5 A Few Methods for Optimization

## 5.1 SQP Algorithm for ($P_{EI}$)

In this section, we apply the Josephy-Newton (JN) algorithm of section 4.1.2 to the equality and inequality constrained optimization problem ($P_{EI}$), more precisely to the system formed by its first order optimality conditions. As already observed in section 4.1.1, this optimality system can indeed be written as a complementarity problem, which is a special case of function inclusion. This approach yields an algorithm named SQP for Sequential Quadratic Programming, which is one of the most often used algorithm to solve problem ($P_{EI}$), when derivatives are available.

In addition to give a consistent and illuminating way of introducing the SQP algorithm, this approach is also fruitful. In particular, it offers to possibility to get the conditions of local convergence inherited from those ensuring the local convergence of the JN algorithm (theorem 4.12), which were not known before this technique was introduced in [19; 1994].

For the reader's convenience, we recall the form of the optimization problem ($P_{EI}$):

$$ (P_{EI}) \quad \begin{cases} \min f(x) \\ c_i(x) = 0, & i \in E \\ c_i(x) \le 0, & i \in I. \end{cases} $$

In this setting, the vector $x$ to optimize lies in a Euclidean vector space $\mathbb{E}$ and the functions $f: \mathbb{E} \to \mathbb{R}$ and $c_i: \mathbb{E} \to \mathbb{R}$ defining the objective and the constraints are supposed smooth. The index sets $E$ and $I$ form a partition of $[1:m]: E \cup I = [1:m]$ and $E \cap I = \emptyset$.

Here are some more notation. We denote by $c: \mathbb{E} \to \mathbb{R}^m$ the function whose $i$th component is $c_i$. The cardinality of $E$ and $I$ are denoted by $m_E := |E|$ and $m_I := |I|$, so that $m = m_E + m_I$. If $v \in \mathbb{R}^m$, we denote by $v_E$ (resp. $v_I$) the vector of $\mathbb{R}^{m_E}$ (resp. $\mathbb{R}^{m_I}$) formed of the components $v_i$ of $v$ with index $i \in E$ (resp. $i \in I$). Applying this to $c$, $c_E: \mathbb{E} \to \mathbb{R}^{m_E}$ (resp. $c_I: \mathbb{E} \to \mathbb{R}^{m_I}$) is now the constraint function defining the equality (resp. inequality) constraints. To a vector $v \in \mathbb{R}^m$, we associate the vector $v^\# \in \mathbb{R}^m$, defined by

$$ (v^\#)_i = \begin{cases} v_i & \text{if } i \in E \\ v_i^+ & \text{if } i \in I, \end{cases} $$

where $v_i^+ = \max(0, v_i)$. With this notation, the constraints of ($P_{EI}$) read $c(x)^\# = 0$, whose interest lies in its compactness (note indeed that $x \mapsto c(x)^\#$ is usually nonsmooth, so that the difficulty associated with the inequality constraints has been transferred to the difficulty coming from nonsmoothness).
5.1.1 The SQP Algorithm

Figure 5.1 below gives a flowchart that can allow the reader to see schematically the

<figure><img src="image_44.png" /><figcaption>Fig. 5.1. Flowchart of the systems encountered in section 5.1.1.</figcaption></figure>

links between all the systems encountered in this section, which lead to the definition
of the SQP algorithm and its osculating quadratic problem (OQP). The meaning of its
blocs, which refer to formulas not already encountered, will be revealed progressively
throughout the section. A simple horizontal arrow indicates an implication between
the systems; a double horizontal arrow means an equivalence. The labels of the vertical
arrows indicate the type of transformation used to go from the upper box to the lower
one. Even though we do not have all the elements at hand to understand this diagram,
we can already outline it.

1. Most presentations of the SQP algorithm confine themselves to the leftmost two blocs, hence viewing the osculating quadratic problem (OQP) defined below as a kind of hybrid quadratization of ($P_{EI}$).

2. When, one goes through the first order optimality conditions, the (KKT) bloc in the flowchart, one gets the first order optimality conditions (KKT') of the OQP by a pseudo-linearization, which linearizes the functions in the KKT system, while keeping its structure. This is probably the fastest and meaningful way of presenting the SQP algorithm and its osculating quadratic problem.

3. It makes even more sense, and this is what we do below, to view the KKT system as the functional inclusion problem (5.2a), denoted FIP in the flowchart, and apply the JN linearization to it. Then, one gets (5.4a), which is actually a functional inclusion expression of (KKT').

4. The approach made in point 3 on the functional inclusion form (5.2a) of (KKT), can also be done on its complementarity form (5.2b). The linearization of the functions appearing in the latter yields (5.4b), which is the complementarity form of (KKT').

We now expound the approach described schematically in the points 3 and 4 afore-
mentioned, with more precision.

Like Newton's method for solving an unconstrained optimization method, the
SQP algorithm for solving ($P_{EI}$) focuses on the solutions to the first order optimality
conditions of the problem or its KKT system (1.58), which we recall below for the reader's convenience. It is the following system in $(x, \lambda) \in \mathbb{E} \times \mathbb{R}^m$:

$$ (KKT) \quad \left\{ \begin{array}{l} \nabla f(x) + c'(x)^* \lambda = 0 \\ c_E(x) = 0 \\ 0 \le \lambda_I \perp -c_I(x) \ge 0. \end{array} \right. \qquad (5.1) $$

With the inequality $-c_I(x) \ge 0$, the last complementarity condition is written slightly differently than in (1.58), since for the sequel we would like to have $\lambda_I$ and $-c_I(x)$ to belong to dual cones (actually to $\mathbb{R}_+^{m_I}$, which is self-dual in the sense that $(\mathbb{R}_+^{m_I})^+ = \mathbb{R}_+^{m_I}$). A pair $(x, \lambda)$ solution to this system is called a *primal-dual solution* and the primal solution $x$ is also sometimes called a *stationary point*.

We have seen in section 4.1.1, and this is a fundamental observation, that this system reads like the following functional inclusion or complementarity problem in $z := (x, \lambda)$:

$$ F(z) + N_{K^+}(z) \ni 0, \qquad (5.2a) $$

$$ K^+ \ni z \perp F(z) \in K, \qquad (5.2b) $$

where

$$ F(z) = \begin{pmatrix} \nabla f(x) + c'(x)^* \lambda \\ -c(x) \end{pmatrix} \quad \text{and} \quad K = \{0_{\mathbb{E}}\} \times (\{0_{\mathbb{R}}^{m_E}\} \times \mathbb{R}_+^{m_I}). \qquad (5.3) $$

Because of the importance of this equivalence for this section, let us check it again. Since $K^+ = \mathbb{E} \times (\mathbb{R}^{m_E} \times \mathbb{R}_+^{m_I})$, we have that

* $(x, \lambda) \in K^+$ reads $\lambda_I \ge 0$,

* $F(x, \lambda) \in K$ reads $\nabla_x \ell(x, \lambda) = 0, c_E(x) = 0, \text{ and } c_I(x) \le 0$,

* $(x, \lambda) \perp F(x, \lambda)$ amounts then to the complementarity expression $\lambda_I \perp c_I(x)$.

Hence, one recovers indeed (5.1).

The pure JN algorithm (4.11), that is with $M_k = F'(x_k)$, applied to the functional inclusion (5.2a) or to the complementarity problem in (5.2b) leads to determine the next iterate $z_{k+1} := (x_{k+1}, \lambda_{k+1})$ from the current one $z_k := (x_k, \lambda_k)$ by solving in $z := (x, \lambda)$ the following linearized functional inclusion problem or its equivalent linearized complementarity problem:

$$ F(z_k) + F'(z_k)(z - z_k) + N_{K^+}(z) \ni 0, \qquad (5.4a) $$

$$ K^+ \ni z \perp (F(z_k) + F'(z_k)(z - z_k)) \in K. \qquad (5.4b) $$

Let us see the form of this algorithm when $(F, K)$ is given by (5.3). Observe that

$$ F'(z) = \begin{pmatrix} L(x, \lambda) & c'(x)^* \\ -c'(x) & 0 \end{pmatrix}, \qquad (5.5) $$

where we simplified the notation by introducing

$$ L(x, \lambda) := \nabla_{xx}^2 \ell(x, \lambda). $$

Consider (5.4b).
• The condition $z \in K^+$ reads like above

$$ \lambda_I \ge 0. \qquad (5.6a) $$

• The condition $F(z_k) + F'(z_k)(z - z_k) \in K$ means

$$ \nabla_x \ell(x_k, \lambda) + L(x_k, \lambda_k)(x - x_k) + c'(x_k)^*(\lambda - \lambda_k) = 0, \qquad (5.6b) $$

$$ c_E(x_k) + c'_E(x_k)(x - x_k) = 0, \qquad (5.6c) $$

$$ c_I(x_k) + c'_I(x_k)(x - x_k) \le 0. \qquad (5.6d) $$

• Finally, the orthogonality relation $z \perp (F(z_k) + F'(z_k)(z - z_k))$ can be expressed by

$$ \lambda_I \perp [c_I(x_k) + c'_I(x_k)(x - x_k)]. \qquad (5.6e) $$

Gathering the conditions in (5.6) yields the system

$$ (\text{KKT}') \quad \left\{ \begin{array}{l} \nabla_x \ell(x_k, \lambda_k) + L(x_k, \lambda_k)(x - x_k) + c'(x_k)^*(\lambda - \lambda_k) = 0, \\ c_E(x_k) + c'_E(x_k)(x - x_k) = 0, \\ 0 \le \lambda_I \perp [c_I(x_k) + c'_I(x_k)(x - x_k)] \le 0. \end{array} \right. \qquad (5.7) $$

We could obtain the same system from the KKT system (5.1) by linearizing its functions and keeping its structure, made of the equalities, inequalities and perpendicularity operator.

Solving (KKT') is not an easy task: this system is not a classic problem that can be solved by the usual pieces of software; in addition, the original optimization nature of problem ($P_{EI}$) looks lost in this formulation. This latter observation is in appearance only, since the fact that the system (KKT') comes from the linearization of a KKT system, it is also a KKT system, but now of a quadratic optimization problem. Let us see this. Note first that it is not the I-component of the multiplier $(\lambda - \lambda_k)$ appearing in the first equation of (5.7) that must be nonnegative, but $\lambda_I$, as imposed by the last condition in (5.7). This is problematic when one tries to see (5.7) as a KKT system. But there is cure to that difficulty, which consists in eliminating $\lambda_k$ from the first equation of (5.7) (it appears twice in terms that cancel each other). The system becomes

$$ \left\{ \begin{array}{l} \nabla f(x_k) + L(x_k, \lambda_k)(x - x_k) + c'(x_k)^*\lambda = 0, \\ c_E(x_k) + c'_E(x_k)(x - x_k) = 0, \\ 0 \le \lambda_I \perp [c_I(x_k) + c'_I(x_k)(x - x_k)] \le 0. \end{array} \right. \qquad (5.8) $$

Now, it is not difficult to observe that (5.8) is formed of the first order optimality conditions of the following quadratic optimization problem

$$ \left\{ \begin{array}{l} \min_x \langle \nabla f(x_k), (x - x_k) \rangle + \frac{1}{2} \langle L(x_k, \lambda_k)(x - x_k), (x - x_k) \rangle \\ c_E(x_k) + c'_E(x_k)(x - x_k) = 0 \\ c_I(x_k) + c'_I(x_k)(x - x_k) \le 0. \end{array} \right. $$

Note that the multiplier associated with the linearized constraints is the sought dual solution $\lambda$ to this problem, not the increment $\lambda - \lambda_k$. For the sequel, it is convenient to set $d = x - x_k$, so that the previous quadratic problem can also be written as a quadratic problem in $d \in \mathbb{E}$:
$$ (OQP)_k \quad \left\{ \begin{array}{l} \min_d \langle \nabla f(x_k), d \rangle + \frac{1}{2} \langle \nabla_{xx}^2 \ell(x_k, \lambda_k) d, d \rangle \\ c_E(x_k) + c'_E(x_k) d = 0 \\ c_I(x_k) + c'_I(x_k) d \le 0. \end{array} \right. \qquad (5.9) $$

This problem is called the osculating quadratic problem of ($P_{EI}$) at ($x_k, \lambda_k$). Its objective has a hybrid nature, since the linear term is formed with the gradient of the objective of ($P_{EI}$), while the quadratic term is formed with the Hessian of the Lagrangian of the problem.

One can now specify the local SQP iteration, local means here without globalization technique like those of sections 5.1.4 and 5.1.5.

**Algorithm 5.1 (local SQP)** One iteration, from ($x_k, \lambda_k$) $\in E \times \mathbb{R}^m$ to ($x_{k+1}, \lambda_{k+1}$) is made of the following steps:

1. Stopping test: if the current pair ($x_k, \lambda_k$) is satisfactory, stop;

2. QP solve: let ($d_k, \lambda_{k+1}$) be an appropriate primal-dual solution to the osculating quadratic problem (5.9), if any;

3. New iterate: set $x_{k+1} := x_k + d_k$ and $\lambda_{k+1} := \lambda_{k+1}$.

This algorithm deserves some remarks.

**Remarks 5.2** 1) The SQP algorithm decomposes the computation of a solution to ($P_{EI}$) in a sequence of osculating quadratic optimization problems (5.9), easier to solve than ($P_{EI}$). Therefore, the combinatorial aspect of problem ($P_{EI}$) (liked to the determination of the active inequality constraints), is transferred to the OQP, where it is still serious, but less than in the nonlinear problem ($P_{EI}$).

2) The computationally expensive part of the SQP algorithm is the computation of the solution to the osculation quadratic problem (OQS), which can be much more computation time consuming than a linear system. Therefore, we are in the class of algorithms with an expensive iteration; this is expected since we have seen that the SQP algorithm is derived from the JN algorithm, which has that property.

3) The OQP is still computationally expensive to solve:

* if $L_k \nleq 0$, then the OQP is NP-hard,

* if $L_k \ge 0$, then the OQP can be solved in polynomial time (by an interior point method, but this is not necessarily the best approach).

For this reason, many implementations approach the Hessian of the Lagrangian $L_k$ by a positive definite matrix (using a quasi-Newton technique for example), see also section 5.1.4.

4) We shall see in section 5.1.2 that algorithm 5.1 enjoys a local rapid convergence: it is quadratic if $f$ and $c$ are sufficiently smooth (of class $C^{2,1}$). This means that, once an iterate is close to a “regular solution” (a notion that will be clarify in the next section), the convergence to that solution is very fast (less than 5 or 10 iterations, to give a number), whatever the dimension of the problem is. Furthermore, the algorithm provides a very accurate approximation to the solution. Nothing is done, however, in algorithm 5.1 to ensure the convergence if the initial iterate ($x_1, \lambda_1$) is not close to a regular solution. This subject is considered in sections 5.1.4 and 5.1.5.
5) The phrase “if any” in step 2 of the algorithm hides a lot of difficulties that a fully developed piece of software must overcome. Let us mention the three main ones.

* It may occur that the linearized constraints of the OQP are not compatible, even if problem $(P_{EI})$ is feasible. For example, assume that in $(P_{EI})$, $n = 1$, $m_E = 0$, and $m_I = 2$, with the constraints

$$x \ge 0 \quad \text{and} \quad \log(x + 1) \le 1,$$

which is a complicated way of requiring to have $x \in [0, 9]$. The linearization of these compatible constraints at $x = 99$ reads “$x \ge 0$ and $2 + (x - 99)/100 \le 1$” or “$x \ge 0$ and $x \le -1$”, which are not compatible.

* It may occur that the OQP is feasible but unbounded (its optimal value is $-\infty$).

* If none of the previous situations occur, the OQS has a solution (like in linear optimization, since one can show that a possibly nonconvex quadratic optimization problem with a real optimal value has a solution [56; 1956, appendix (i)]). Nevertheless, it may have undesirable solutions. Here is an example. Consider the following problem in $x \in \mathbb{R}$:

$$\begin{cases} \min_x \log(x + 1) \\ 0 \le x \le 3. \end{cases}$$

Its solution is $x_* = 0$ and there is a unique associated multiplier $\lambda_* = (1, 0)$. The OQP at $(x_*, \lambda_*)$ reads

$$\begin{cases} \min_d d - \frac{1}{2} d^2 \\ 0 \le d \le 3. \end{cases}$$

This problem has three stationary points: 0, which is a local minimum, 1, which a global maximum, and 3, which is a global minimum. Clearly, only the first one is satisfactory (at a solution to a problem any sensible algorithm should provide a zero displacement).

### 5.1.2 Local Convergence

**Definition 5.3** A stationary pair $z_* := (x_*, \lambda_*)$ of $(P_{EI})$ is said to be semi-stable (resp. hemi-stable) if $z_*$ is a semi-stable (resp. hemi-stable) solution to the functional inclusion (5.2a) with $F$ and $K$ given by (5.3).

If $(x_*, \lambda_*)$ verifies the KKT conditions, it follows that

$$F(x_*, \lambda_*) = \begin{pmatrix} 0_E \\ 0_{\mathbb{R}^{m_E}} \\ -c_I(x_*) \end{pmatrix}, \quad (5.10)$$

$$F(x_*, \lambda_*) + F'(x_*, \lambda_*)(d, \mu) = \begin{pmatrix} L_*d + c'(x_*)^*\mu \\ -c'_E(x_*)d \\ -c_I(x_*) - c'_I(x_*)d \end{pmatrix}. \quad (5.11)$$

where we have used (5.5) and set $L_* := L(x_*, \lambda_*) := \nabla_{xx}\ell(x_*, \lambda_*)$. The condition $F(x_*, \lambda_*) + F'(x_*, \lambda_*)(d, \mu) + N_{K^+}(x_*, \lambda_*) \ni 0$ reads
$$L_*d + c'(x_*)^*\mu = 0, \\ c'_{E \cup I_*^{0+}}(x_*)d = 0, \quad c'_{I_*^{00}}(x_*)d \le 0, \quad c_{I_*^c}(x_*) + c'_{I_*^c}(x_*)d \le 0.$$

**Proposition 5.4 (semi-stability of a local minimum)** If $x_*$ is a local min- imum of ($P_{EI}$) and $\lambda_*$ is an associated optimal multiplier, then the following properties are equivalent:

(i) $(x_*, \lambda_*)$ is semi-stable,

(ii) $\lambda_*$ is the unique optimal multiplier associated with $x_*$ and the second order sufficient conditions of optimality hold: $\langle L_*d, d \rangle > 0$, for all $d \in C_* \setminus \{0\}$.

*Proof.* 1) We take advantage of the equivalence (i) ⇔ (iii) of proposition 4.7 to get another expression of the semi-stability of $(x_*, \lambda_*)$, hence another expression of point (i) in the present proposition. To this end, we introduce

$$(d, \mu) := z - z_* = (x - x_*, \lambda - \lambda_*)$$

and we observe that, with $F$ defined in (5.3), with (5.10) and (5.11), one has

$$\langle F'(x_*, \lambda_*)(d, \mu), (d, \mu) \rangle = \langle L_*d, d \rangle, \\ \langle F(x_*, \lambda_*)(d, \mu) \rangle = 0 \iff \mu_{I_*^c} = 0.$$

By the equivalence (i) ⇔ (iii) of proposition 4.7, the semi-stability of $(x_*, \lambda_*)$ is equivalent to

$$\text{one has } \langle L_*d, d \rangle > 0 \text{ for all } (d, \mu) \in \mathbb{E} \times \mathbb{R}^m \text{ such that} \quad (5.12\text{a})$$

$$(d, \mu) \neq 0, \quad (5.12\text{b})$$

$$(\lambda_* + \mu)_{I_*^0} \ge 0, \quad \mu_{I_*^c} = 0, \quad (5.12\text{c})$$

$$L_*d + c'_{E \cup I_*^{0}}(x_*)^* \mu_{E \cup I_*^{0}} = 0, \quad (5.12\text{d})$$

$$d \in C_*, \quad \text{and} \quad c_{I_*^c}(x_*) + c'_{I_*^c}(x_*)d \le 0. \quad (5.12\text{e})$$

where $C_* := \{d \in \mathbb{E} : c'_{E \cup I_*^{0+}}(x_*)d = 0, c'_{I_*^{00}}(x_*)d \le 0\}$ is the critical cone.

2) [(i) ⇒ (ii)] Since $(x_*, \lambda_*)$ is semi-stable, it is an isolated solution to the optimality system (1.58) (proposition 4.4). Since the set of optimal multipliers associated with $x_*$ is convex (it is a convex polyhedron), this one must be a singleton, which proves the first part of (ii).

The set of optimal multipliers associated with $x_*$ being bounded (it is a singleton), the constraint qualification condition (CQ-MF) holds (see proposition 2.22 and exercise 2.1.4). Therefore, by the second order necessary conditions of optimality (theorem 2.37), $\langle L_*d, d \rangle \ge 0$ for all critical directions $d \in C_*$. To show that the second order sufficient conditions of optimality also holds, we proceed by contradiction, assuming that there is a nonzero direction $d_1 \in C_*$ such that $\langle L_*d_1, d_1 \rangle = 0$. Then, this direction $d_1$ is a solution to the quadratic problem

$$\left\{ \begin{array}{l} \min \langle L_*d, d \rangle \\ c'_{E \cup I_*^{0+}}(x_*)d = 0 \\ c'_{I_*^{00}}(x_*)d \le 0, \end{array} \right.$$
whose constraints define critical directions. Since (CQ-A) holds for this problem, its optimality conditions ensure the existence of a multiplier $\mu_1 \in \mathbb{R}^m$ such that

$$ 
\begin{array}{l}
(\mu_1)_{I_*} = 0, \\
L_*d_1 + c'(x_*)^*\mu_1 = 0, \\
c'_{E \cup I_*^0}(x_*)d_1 = 0, \\
0 \le (\mu_1)_{I_*^{00}} \perp c'_{I_*^{00}}(x_*)d_1 \le 0.
\end{array}
$$

Then $(d, \mu) = t(d_1, \mu_1)$, for $t > 0$ sufficiently small, verifies (5.12b)-(5.12e) but not the conclusion $\langle L_*d, d \rangle > 0$ in (5.12a). This contradiction shows that SC2 is verified.

3) $[(i) \leftarrow (ii)]$ To show the semi-stability of $(x_*, \lambda_*)$, we show that (5.12) holds. Let $(d, \mu)$ verifying (5.12b)-(5.12e). It suffices to show that $d \ne 0$, since then $d \in C_* \setminus \{0\}$ and the conclusion $\langle L_*d, d \rangle > 0$ in (5.12a) follows from the SC2 that is assumed in (ii). We proceed again by contradiction, assuming that $d = 0$. Then $\mu \ne 0$ by (5.12b) and it is plain to see by (5.12c)-(5.12d) that $\lambda_* + \mu$ would then be another optimal multiplier associated with $x_*$, which would contradict the uniqueness of the optimal multiplier, assumed in (ii). $\square$

**Proposition 5.5 (sufficient condition of hemi-stability)** If $x_*$ is a local minimum of $(P_{EI})$, with an associate multiplier $\lambda_*$ such that $(x_*, \lambda_*)$ is semi-stable, then $(x_*, \lambda_*)$ is also hemi-stable.

*Proof.* By the definition 4.11 of the hemi-stability, one has to show that, for all $\alpha > 0$, one can find $\beta > 0$, such that, for all $(x_0, \lambda_0) \in \bar{B}((x_*, \lambda_*), \beta)$, the following inclusion in $(x, \lambda)$

$$ \left( \begin{array}{c} \nabla f(x_0) + c'(x_0)^* \lambda_0 \\ -c(x_0) \end{array} \right) + \left( \begin{array}{cc} L(x_0, \lambda_0) & c'(x_0)^* \\ -c'(x_0) & 0 \end{array} \right) \left( \begin{array}{c} x - x_0 \\ \lambda - \lambda_0 \end{array} \right) + N_{K^+}(x, \lambda) \ni 0 $$

has a solution in $\bar{B}((x_*, \lambda_*), \alpha)$. This inclusion is the first order optimality system of the following quadratic optimization problem in $x \in \mathbb{E}$:

$$ 
\left\{ 
\begin{array}{l}
\min \langle \nabla f(x_0), x - x_0 \rangle + \frac{1}{2} \langle L(x_0, \lambda_0)(x - x_0), x - x_0 \rangle \\
c_E(x_0) + c'_E(x_0)(x - x_0) = 0 \\
c_I(x_0) + c'_I(x_0)(x - x_0) \le 0.
\end{array}
\right.
\qquad (5.13)
$$

The system (5.13) can be viewed as a perturbation of the quadratic optimization problem in $x \in \mathbb{E}$ that is obtained by taking $(x_0, \lambda_0) = (x_*, \lambda_*)$, namely

$$ 
\left\{ 
\begin{array}{l}
\min \langle \nabla f(x_*) , x - x_* \rangle + \frac{1}{2} \langle L_*(x - x_*), x - x_* \rangle \\
c_E(x_*) + c'_E(x_*)(x - x_*) = 0 \\
c_I(x_*) + c'_I(x_*)(x - x_*) \le 0.
\end{array}
\right.
\qquad (5.14)
$$

The first order optimality conditions of (5.14) read: there exists $\lambda \in \mathbb{R}^m$ such that
$$
\begin{align*}
\nabla f(x_*) + L_*(x - x_*) + c'(x_*)^*\lambda &= 0 \\
c_E(x_*) + c'_E(x_*)(x - x_*) &= 0 \\
0 \le \lambda \perp (c_I(x_*) + c'_I(x_*)(x - x_*)) &\le 0.
\end{align*}
$$

By the KKT conditions of problem (P<sub>EI</sub>), this system is verified by (x, λ) = (x<sub>*</sub>, λ<sub>*</sub>). Now, by proposition 5.4, the assumed semi-stability of (x<sub>*</sub>, λ<sub>*</sub>) implies that λ<sub>*</sub> is the unique optimal multiplier associated with x<sub>*</sub> and that the second order sufficient conditions of optimlaty hold. We deduce from this that first (x<sub>*</sub>, λ<sub>*</sub>) verifies the second order optimality conditions of (5.14), which are the same as those of (P<sub>EI</sub>), and that (CQ-MF) holds for (5.14) (by the uniqueness of the associated multiplier and the Gauvin property of proposition 2.22). By proposition 3.1, these properties ensure that the perturbed problem (5.13) has a primal-dual solution (x, λ) (it may have other undesirable solutions, however), whose distance to (x<sub>*</sub>, λ<sub>*</sub>) is bounded by a constant times the norm of the perturbation (x<sub>0</sub> − x<sub>*</sub>, λ<sub>0</sub> − λ<sub>*</sub>). □

**Theorem 5.6 (local convergence of the SQP algorithm)** If f and c are $C^{2,1}$ in a neighborhood of a local minimum $x_*$ of ($P_{EI}$), if there exists a unique multiplier associated with $x_*$, and if the sufficient conditions of optimality of the second order are satisfied, then there exists a neighborhood V of ($x_*$, $\lambda_*$) such that, if the first iterate ($x_1$, $\lambda_1$) $\in$ V, then

1) the SQP algorithm can generate a sequence $\{(x_k, \lambda_k)\}$ in V,

2) $\{(x_k, \lambda_k)\}$ converges quadratically to $(x_*, \lambda_*)$.

*Proof.* By proposition 5.4, the uniqueness of the optimal multiplier, and the second order optimality conditions, ($x_*, \lambda_*$) is a semi-stable solution of (5.2). By proposition 5.5, this is also an hemi-stable solution. One can then apply theorem 4.12, which gives the result. □

5.1.3 Exact Penalization

Motivation

A review of penalty techniques

The augmented Lagrangian is a first way of getting an exact penalization, provided one knows an optimal multiplier (since this is usually not the case, the multiplier method generates a sequence approaching an optimal multiplier). The underlying idea is to penalize quadratically a function whose first derivative vanishes at the considered solution, which is the Lagrangian $\ell(\cdot, \lambda_*)$.

Another way of getting an exact penalty function is to do this using a nondif-
ferentiable function. Let us illustrate the idea in the case of the following simple
optimization problem in $x \in \mathbb{R}$:

$$
\left\{
\begin{array}{ll}
\inf & 1 - x - \frac{1}{3}x^3 \\
\text{find} & x \le 0.
\end{array}
\right.
\qquad (5.15)
$$
<figure><img src="image_45.png" /><figcaption>Fig. 5.2. Nondifferentiable penalization for the problem (5.15) with $\sigma = 1, 2, 3$ and 4.</figcaption></figure>

Figure 5.2 shows that if the term $\sigma x^+ = \sigma \max(0, x)$ is added to the objective of the problem, one gets an exact penalty function, as soon as $\sigma > 1$. This threshold $\sigma = 1$ comes in the present case from the slope of $f$ at zero. More generally, it is the “slope” (if this one exists) of the value function at zero that is important, so that it is the optimal multipliers associated with $x_*$ that will play a key role in the determination of the value of the threshold above which an exact penalty is obtained.

### An exact penalty function

In this section, we consider the following penalty function, which is associated with problem (P$_{EI}$):

$$ \Theta_{\sigma}(x) = f(x) + \sigma \|c(x)\|_{P}, \qquad (5.16) $$

where $\sigma > 0$ and $\| \cdot \|_P$ is an arbitrary norm. The fundamental result is given in theorem 5.11; it provides conditions ensuring the exactness of $\Theta_{\sigma}$. Its proof uses the following three lemmas.

The first lemma is relevant in a larger context than ours, since it highlights conditions for having the directional differentiability of a composition of functions and shows that the chain rule (5.17) applies in that case. To motivate the Lipschitz assumption taken in the lemma, let us point out that the composition of functions having directional derivatives may not have a directional derivative.

### Counter-example 5.7 (not directionally differentiable composition)
Let $\varphi : \mathbb{R} \to \mathbb{R}^2$ and $\psi : \mathbb{R}^2 \to \mathbb{R}$ be defined by

$$ \varphi(x) = \begin{cases} (x, x^2 \sin(1/x)) & \text{if } x \neq 0 \\ 0 & \text{if } x = 0 \end{cases} \quad \text{and} \quad \psi(y_1, y_2) = \begin{cases} y_1 & \text{if } y_2 = 0 \\ 0 & \text{if } y_2 \neq 0. \end{cases} $$

It is plain to see that $\varphi$ is Fréchet differentiable at zero, that $\psi$ is positively homogeneous, hence directionally differentiable at zero, but that $\psi \circ \varphi$ is not directionally differentiable at zero. $\square$
This counter-example [127; p. 484] shows that the Lipschitz continuity of the second function of the composition, the function $\psi$, assumed in the lemma below, is not superfluous. It is worth noting that the notion of directional differentiability in the sense of Hadamard (i.e., $[f(x+t_k d_k) - f(x)]/t_k$ converges to the same vector whatever the sequences $\{d_k\} \to d$ and $\{t_k\} \downarrow 0$ are) is stable for the composition and the chain rule applies [127; proposition 3.6].

**Lemma 5.8 (directional differentiability of a composition)** Let $\mathbb{E}$, $\mathbb{F}$, and $\mathbb{G}$ be three normed vector spaces. Suppose that $\varphi: \mathbb{E} \to \mathbb{F}$ has a directional derivative at $x \in \mathbb{E}$ in the direction $h \in \mathbb{E}$ and that $\psi: \mathbb{F} \to \mathbb{G}$ is Lipschitz continuous in a neighborhood of $\varphi(x)$ and has a directional derivative at $\varphi(x)$ in the direction $\varphi'(x; h)$. Then $(\psi \circ \varphi)$ has a directional derivative at $x$ in the direction $h$ and there holds

$$ (\psi \circ \varphi)'(x; h) = \psi'(\varphi(x); \varphi'(x; h)). \qquad (5.17) $$

*Proof.* For $t \downarrow 0$, use successively the directional differentiability of $\varphi$, the Lipschitz continuity of $\psi$, and the directional differentiability of $\psi$:

$$ \begin{aligned} (\psi \circ \varphi)(x + th) &= \psi(\varphi(x) + t\varphi'(x; h) + o(t)) \\ &= \psi(\varphi(x) + t\varphi'(x; h)) + o(t) \\ &= (\psi \circ \varphi)(x) + t\psi'(\varphi(x); \varphi'(x; h)) + o(t). \end{aligned} $$

The result follows.

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

The second lemma explores the differentiability of $\Theta_{\sigma}$ and uses the operator $P_v: \mathbb{R}^m \to \mathbb{R}^m$, defined for $u \in \mathbb{R}^n$ and $v \in \mathbb{R}_-$ by

$$ (P_v u)_i = \begin{cases} u_i & \text{if } i \in E, \\ u_i^+ & \text{if } i \in I \text{ and } v_i = 0, \\ 0 & \text{if } i \in I \text{ and } v_i < 0. \end{cases} $$

to have an explicit expression of $\Theta'_{\sigma}(x; d)$ at a point $x$ that is feasible or ($P_{EI}$).

**Lemma 5.9** If $f$ and $c$ have directional derivatives at $x \in \mathbb{E}$, then $\Theta_{\sigma}$ has directional derivatives at $x$. In particular, if $x$ is feasible for ($P_{EI}$), the following formula holds

$$ \Theta'_{\sigma}(x; d) = f'(x; d) + \sigma \| P_{c(x)} c'(x; d) \|_{\mathbb{P}}. $$

*Proof.* The directional differentiability of $\Theta_{\sigma} = f + \sigma(\| \cdot \|_{\mathbb{P}} \circ (\cdot)^{\#} \circ c)$ comes from lemma 5.8, the assumptions on $f$ and $c$, and the fact that $\| \cdot \|_{\mathbb{P}}$ and $(\cdot)^{\#}$ are Lipschitz continuous and have directional derivatives.

If $x$ is feasible, $c(x)^{\#} = 0$ and we have from lemma 5.8,

$$ \Theta'_{\sigma}(x; d) = f'(x; d) + \sigma(\| \cdot \|_{\mathbb{P}})'(0; (c^{\#})'(x; d)). $$
We now observe that

$$ (\| \cdot \|_{\mathbb{P}})'(0; v) = \lim_{t \to 0+} \frac{1}{t} (\|tv\|_{\mathbb{P}} - 0) = \|v\|_{\mathbb{P}} $$

and

$$ (c^{\#})'(x; d) = (\cdot^{\#})'(c(x); c'(x; d)) = P_{c(x)}c'(x; d). $$

The result follows.

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

The third lemma shows that, when $\sigma$ is sufficiently large, $\Theta_{\sigma}$ dominates the Lagrangian $\ell(\cdot, \lambda_*)$ on $\mathbb{E}$ ($\lambda_*$ is an optimal multiplier associated with $x_*$). Recall that the dual norm of $\| \cdot \|_{\mathbb{P}}$ for the Euclidean scalar product is the norm $\| \cdot \|_{\mathbb{D}} : \mathbb{R}^m \to \mathbb{R}$ defined at $v \in \mathbb{R}^m$ by

$$ \|v\|_{\mathbb{D}} = \sup_{\|u\|_{\mathbb{P}} \le 1} v^{\top} u. $$

The generalized Cauchy-Schwarz inequality

$$ \forall u, v \in \mathbb{R}^m : \quad |u^{\top} v| \le \|u\|_{\mathbb{P}} \|v\|_{\mathbb{D}}. \qquad (5.18) $$

follows readily from the definition of the dual norm.

**Lemma 5.10** If $\lambda \in \mathbb{R}^m$ satisfies $\sigma \ge \|\lambda\|_{\mathbb{D}}$ and $\lambda_I \ge 0$, then, for all $x \in \mathbb{E}$, one has $\ell(x, \lambda) \le \Theta_{\sigma}(x)$.

*Proof.* We have successively

$$ \begin{aligned} \ell(x, \lambda) &= f(x) + \lambda^{\top} c(x) \quad [\text{definition of the Lagrangian}] \\ &\le f(x) + \lambda^{\top} c(x)^{\#} \quad [\lambda_I \ge 0 \text{ and } c(x) \le c(x)^{\#}] \\ &\le f(x) + \|\lambda\|_{\mathbb{D}} \|c(x)\|_{\mathbb{P}}^{\#} \quad [(5.18)] \\ &\le f(x) + \sigma \|c(x)\|_{\mathbb{P}}^{\#} \quad [\|\lambda\|_{\mathbb{D}} \le \sigma] \\ &= \Theta_{\sigma}(x). \end{aligned} \quad \square $$

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

Here is the announced result giving sufficient conditions ensuring the exactness of $\Theta_{\sigma}$ at a solution $x_*$ of $(P_{EI})$. Assumption (5.19) can only hold if the set of optimal multipliers $\Lambda_*$ is bounded, which amounts to say that the Mangasarian-Fromovitz sufficient qualification condition (CQ-MF) holds (see below definition 1.38, exercise 2.1.4 and Gauvin's property of proposition 2.22).

**Theorem 5.11 (exactness of $\Theta_{\sigma}$)** Let $x_*$ be a local minimum of $(P_{EI})$. Suppose that $f$ and $c$ are twice differentiable at $x_*$ and Lipschitz continuous in a neighborhood of $x_*$. Suppose also that $x_*$ satisfies the weak second order conditions of optimality (2.80) and denote by $\Lambda_*$ the nonempty set of optimal multi-
pliers associated with $x_*$. Suppose finally that

$$ \sigma \ge \sup_{\lambda_* \in \Lambda_*} \|\lambda_*\|_D \quad \text{and} \quad \sigma > \|\hat{\lambda}_*\|_D, \text{ for some } \hat{\lambda}_* \in \Lambda_* \quad (5.19) $$

Then, $x_*$ is a strict local minimum of the penalty function $\Theta_\sigma$ given by (5.16).

*Proof.* We prove the result by contradiction, assuming that $x_*$ is not a strict local minimum of $\Theta_\sigma$. Then, there exists a sequence $\{x_k\}$ such that $x_k \ne x_*$, $x_k \to x_*$ and

$$ \Theta_{\sigma}(x_k) \le \Theta_{\sigma}(x_*), \quad \forall k \ge 1. \quad (5.20) $$

We now want to show that the preceding inequalities imply that $x_k$ must approach $x_*$ along a nonzero critical direction.

Since the sequence $\{(x_k - x_*)/\|x_k - x_*\|\}$ is bounded (here $\|\cdot\|$ denotes an arbitrary norm), it has a subsequence such that $(x_k - x_*)/\|x_k - x_*\| \to d$, where $\|d\| = 1$. Denoting $t_k := \|x_k - x_*\|$, one has

$$ x_k = x_* + t_k d + o(t_k). $$

Let us show that $d$ is the desired critical direction.

* On the one hand, because $\Theta_\sigma$ is Lipschitz continuous near $x_*$, the following holds

$$ \Theta_{\sigma}(x_k) = \Theta_{\sigma}(x_* + t_k d) + o(t_k). $$

This estimate and (5.20) show that $\Theta'_\sigma(x_*; d) \le 0$. Then, from lemma 5.9, one can write

$$ f'(x_*) \cdot d + \sigma \|P_{c(x_*)}(c'(x_*) \cdot d)\|_P \le 0. \quad (5.21) $$

This certainly implies that

$$ f'(x_*) \cdot d \le 0. \quad (5.22) $$

* On the other hand, from the assumptions, there is an optimal multiplier $\hat{\lambda}_*$ such that $\sigma > \|\hat{\lambda}_*\|_D$. We have

$$ \begin{aligned} -f'(x_*) \cdot d &= \hat{\lambda}_*^T (c'(x_*) \cdot d) \quad [\nabla_x \ell(x_*, \hat{\lambda}_*) = 0] \\ &\le \hat{\lambda}_*^T P_{c(x_*)} (c'(x_*) \cdot d) \quad [(\hat{\lambda}_*)_I \ge 0 \text{ and } (\hat{\lambda}_*)^T c_I(x_*) = 0] \\ &\le \|\hat{\lambda}_*\|_D \|P_{c(x_*)}(c'(x_*) \cdot d)\|_P \quad [(5.18)]. \end{aligned} $$

Then (5.21) and $\sigma > \|\hat{\lambda}_*\|_D$ imply that $P_{c(x_*)}(c'(x_*) \cdot d) = 0$, i.e.,

$$ \begin{cases} c'_i(x_*) \cdot d = 0 & \text{for } i \in E \\ c'_i(x_*) \cdot d \le 0 & \text{for } i \in I_*^0. \end{cases} $$

These and (5.22) show that $d$ is a nonzero critical direction.
Now, let $\lambda_*$ be the multiplier depending on $d$, determined by the weak second-order sufficient condition of optimality (2.80). By this condition and $d \in C_*\setminus\{0\}$, one has

$$ \langle \nabla_{xx}^2 \ell(x_*, \lambda_*) d, d \rangle > 0. $$

The following Taylor expansion (use $\nabla_x \ell(x_*, \lambda_*) = 0$)

$$ \ell(x_k, \lambda_*) = \ell(x_*, \lambda_*) + \frac{t_k^2}{2} \langle \nabla_{xx}^2 \ell(x_*, \lambda_*) d, d \rangle + o(t_k^2) $$

allows us to see that, for $k$ large enough,

$$ \ell(x_k, \lambda_*) > \ell(x_*, \lambda_*). \qquad (5.23) $$

Then, for large indices $k$, there holds

$$ \begin{aligned} \Theta_{\sigma}(x_k) &\le \Theta_{\sigma}(x_*) & \text{[(5.20)]} \\ &= f(x_*) & [c(x_*)^{\#} = 0] \\ &= \ell(x_*, \lambda_*) & [\lambda_*^T c(x_*) = 0] \\ &< \ell(x_k, \lambda_*) & \text{[(5.23)]} \\ &\le \Theta_{\sigma}(x_k) & \text{[lemma 5.10, } \sigma \ge \|\lambda_*\|_{\mathrm{D}}, \text{ and } (\lambda_*)_I \ge 0]. \end{aligned} $$

We have shown $\Theta_{\sigma}(x_k) < \Theta_{\sigma}(x_k)$, which is the expected contradiction. $\square$

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

### 5.1.4 Globalization by Line-Search for ($P_{EI}$) ▲

#### Definition of the algorithm

The global extension of the local SQP algorithm 5.1 analyzed in this section replaces the Hessian of the Lagrangian $\nabla_{xx}^2 \ell(x_k, \lambda_k)$ by a positive definite linear operator $M_k$: $\mathbb{E} \to \mathbb{E}$ (a property that we condense by the notation $M_k > 0$). Hence, the osculating quadratic problem (5.9) becomes

$$ (\text{OQP})_k \quad \begin{cases} \min_d \langle \nabla f(x_k), d \rangle + \frac{1}{2} \langle M_k d, d \rangle \\ c_E(x_k) + c'_E(x_k) d = 0 \\ c_I(x_k) + c'_I(x_k) d \le 0. \end{cases} \qquad (5.24) $$

We shall need the KKT system of this optimization problem: if $d_k$ solves (5.24), then there exists a multiplier $\lambda_k^{\mathrm{QP}} \in \mathbb{R}^m$ (since the constraints are qualified by (CQ-A)) such that

$$ \nabla f(x_k) + M_k d_k + c'(x_k)^* \lambda_k^{\mathrm{QP}} = 0, \qquad (5.25a) $$

$$ c_E(x_k) + c'_E(x_k) d_k = 0, \qquad (5.25b) $$

$$ 0 \le (\lambda_k^{\mathrm{QP}})_I \perp (c_I(x_k) + c'_I(x_k) d_k) \le 0. \qquad (5.25c) $$

There are several reasons motivating the choice of making the substitution $\nabla_{xx}^2 \ell(x_k, \lambda_k) \not\to M_k$, with a positive definite operator $M_k$. Some are related to remark 5.2:
* problem (OQP)$_k$ has more often a solution; this is actually the case if and only if its constraints are compatible (Frank and Wolfe [56]); furthermore, there are techniques that can face the situations where the constraints are inconsistent (but this is more technical);

* when (OQP)$_k$ has a solution, this one is unique in $d_k$ (but not in $\lambda_k^{QP}$, whose uniqueness depends on a constraint qualification);

* problem (OQP)$_k$ can be solved in polynomial time, which is crucial for the efficiency of the overall algorithm.

The inconvenient of this modification of the direction definition is that the primal-dual quadratic convergence of theorem 5.6 is normally lost (at least if the Hessian of the Lagrangian is not positive definite at the solution). Nevertheless, when $M_k$ is updated by a quasi-Newton formula, the convergence is often superlinear and a very precise solution can be obtained in very few iterations (for quasi-Newton methods the number of iterations is often roughly proportional to the number of variables, while with second derivative computation this number is independent of the number of variables).

Another reason for making the substitution $\nabla_{xx}^2 l(x_k, \lambda_k) \rightleftharpoons M_k$, with a positive definite operator $M_k$, is that the SQP direction $d_k$, solution to the above quadratic optimization problem (OQP)$_k$, is then a descent direction of the exact penalty function $\Theta_\sigma$ at $x_k$, as claimed by the following proposition.

**Proposition 5.12 (descent property of the SQP direction)** Suppose that $f$ and $c$ are differentiable at $x_k \in \mathbb{E}$, that $(d_k, \lambda_k^{QP}) \in \mathbb{E} \times \mathbb{R}^m$ is a stationary pair of the osculating quadratic optimization problem (5.24), and that $\| \cdot \|_P^{\#}$ is convex. Then,

1) $\Theta'_k(x_k; d_k) \le \Delta_k$, where

$$ \Delta_k := \langle \nabla f(x_k), d_k \rangle - \sigma \|c(x_k)\|_P^{\#}, \quad (5.26a) $$

$$ = - \langle M_k d_k, d_k \rangle + (\lambda_k^{QP})^T c(x_k) - \sigma \|c(x_k)\|_P^{\#}, \quad (5.26b) $$

$$ \le - \langle M_k d_k, d_k \rangle + (\|\lambda_k^{QP}\|_D - \sigma) \|c(x_k)\|_P^{\#}, \quad (5.26c) $$

2) if, furthermore, $\sigma \ge \|\lambda_k^{QP}\|_D$, then $\Theta'_k(x_k; d_k) \le -\langle M_k d_k, d_k \rangle$,

3) if, furthermore, $M_k > 0$, then $\Theta'_k(x_k; d_k) \le 0$,

4) if, furthermore, $x_k$ is not a stationary point of ($P_{EI}$), then $\Theta'_k(x_k; d_k) < 0$.

*Proof.* 1) Using lemma 5.8, we get

$$ \Theta'(x_k; d_k) = \langle \nabla f(x_k), d_k \rangle + \sigma (\| \cdot \|_P^{\#})' (c(x_k); c'(x_k)d_k). $$

Let us examine the last directional derivative. One has
$$
\begin{align*}
& (\| \cdot \# \|_{\mathrm{P}})'(c(x_k); c'(x_k)d_k) \\
&= \lim_{t \downarrow 0} \frac{1}{t} \left( \left\| \underbrace{c(x_k) + t c'(x_k) d_k}_{= (1-t)c(x_k) + t(c(x_k)+c'(x_k)d_k)} \right\|^*_{\mathrm{P}} - \|c(x_k)\|^*_{\mathrm{P}} \right) \\
&\le (1-t) \|c(x_k)\|^*_{\mathrm{P}} + t \|(c(x_k)+c'(x_k)d_k)\|^*_{\mathrm{P}} \\
&\qquad \text{[convexity of } \| \cdot \# \|_{\mathrm{P}} \text{]} \\
&\le - \|c(x_k)\|^*_{\mathrm{P}} \quad [(c(x_k) + c'(x_k)d_k)^* = 0],
\end{align*}
$$

where we have used the constraints of the OQP (5.24). This gives (5.26a). For getting
(5.26b), we rewrite $\langle \nabla f(x_k), d_k \rangle$ as follows

$$
\begin{align*}
\langle \nabla f(x_k), d_k \rangle &= -\langle M_k d_k, d_k \rangle - (\lambda_k^{\text{QP}})^\top c'(x_k) d_k \quad [(5.25\text{a})] \\
&= -\langle M_k d_k, d_k \rangle + (\lambda_k^{\text{QP}})^\top c(x_k),
\end{align*}
$$

since $c'_E(x_k)d_k = -c_E(x_k)$ by (5.25b) and $(\lambda_k^{\text{QP}})^\top I c'_I(x_k)d_k = -(\lambda_k^{\text{QP}})^\top I c_I(x_k)$ by (5.25c).
Inequality (5.26c) is now a consequence of (5.26b) and (5.18).

2) We have to show that, when $\sigma \ge \|\lambda_k^{\text{QP}}\|_{\text{D}}$, the last two terms in (5.26b) form a nonpositive difference. This is indeed the case, since

$$
\begin{align*}
& (\lambda_k^{\text{QP}})^{\top} c(x_k) - \sigma \|c(x_k)\|_{\text{P}} \\
\le & (\lambda_k^{\text{QP}})^{\top} c(x_k) \# - \sigma \|c(x_k)\|_{\text{P}} \quad [(\lambda_k^{\text{QP}})_I \ge 0] \\
\le & (\|\lambda_k^{\text{QP}}\|_{\text{D}} - \sigma) \|c(x_k)\|_{\text{P}} \quad [(5.18)] \\
\le & 0 \quad [\sigma \ge \|\lambda_k^{\text{QP}}\|_{\text{D}}].
\end{align*}
$$

3) Clear.

4) We proceed by contraposition. If $\Theta'_k(x_k; d_k) = 0$, $d_k = 0$ by the inequality in point 2. Now (5.25) with $d_k = 0$ shows that $(x_k, \lambda_k^{\text{QP}})$ is a stationary pair of $(P_{EI})$. $\square$

The assumption on the convexity of ‖·‖_P in the previous proposition is satisfied
by many standard norm, in particular by the ℓ_p-norms with 1 ≤ p ≤ ∞, but not by
all the norms. This question is examined in exercise 5.1.2.

The sufficient condition guaranteeing the descent of Θ_σ along the SQP direction d_k,
in point 2 of the previous proposition, namely σ ≥ ||λ_k^QP||_D, recalls the sufficient condi-
tion σ > sup{||λ_*||_D : λ_* ∈ A}, exhibited by theorem 5.11, that ensures the exactness
of the merit function Θ_σ. This is not surprising and reassuring on the correctness of
the analysis.

Observe now that the threshold sup{||λ*||_D : λ* ∈ A} above which σ must be is not known by the algorithm or the user of the algorithm (it depends on the optimal multipliers that are not known) but, in a certain way, the values ||λ_k^QP||_D, evolving along the iterations, can inform the algorithm on the value that σ must have to make Θ_σ exact at the limit point of the generated sequence of primal iterates {x_k}. This observation also indicates that the value of σ, which is monitored by the algorithm, may have to be updated during the iterative process. Therefore σ depend on the iteration counter k and is now denoted by σ_k. Specific update rules are used to ensure that

$$
\sigma_k \ge \|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma}, \qquad (5.27\text{a})
$$
where $\bar{\sigma} > 0$ is some constant safeguard. Typically, one takes

$$ \bar{\sigma} := \max(\sqrt{\epsilon}, \|\lambda_1^{\text{QP}}\|_{\text{D}}/100) \quad \text{and} \quad \sigma_1 := \|\lambda_1^{\text{QP}}\|_{\text{D}} + \bar{\sigma}, $$

where $\epsilon$ is the machine-epsilon. The inequality (5.27a) does not prevent from taking arbitrarily $\sigma_k$ very large, which is both harmful form the numerical efficiency of the algorithm and for its convergence analysis (for example, because one can force $\sigma_k$ to blow up without a reason motivated by the behavior of the algorithm). For this reason, one also requires that the following condition be satisfied:

$$ \{\lambda_k^{\text{QP}}\} \text{ is bounded} \implies \sigma_k \text{ is constant for } k \text{ large.} \quad (5.27b) $$

An example of update rule of $\sigma_k$ satisfying these conditions (5.27) is the following.

**Rule 5.13 (update of $\sigma_k$ - I)** Given a threshold $\bar{\sigma} > 0$, the current OQP multiplier $\lambda_k^{\text{QP}}$ and the previous penalty parameter $\sigma_{k-1}$, compute the new penalty parameter $\sigma_k$ as follows.

if $\sigma_{k-1} \ge \|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma}$;

then $\sigma_k = \sigma_{k-1}$;

else $\sigma_k = \max(1.5 \sigma_{k-1}, \|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma})$;

This update rule has the nice property to eventually fix $\sigma_k$ to a constant value when the sequence $\{\lambda_k^{\text{QP}}\}$ is bounded. It is not without flaw, however, since $\{\sigma_k\}$ is nondecreasing and is, therefore, penalized by a badly chosen initial penalty parameter $\sigma_1$ or a high value of the parameter determined far from the solution. For this reason, one often adds instructions to decrease $\sigma_k$ if this one is clearly too large, with respect to the current $\|\lambda_k^{\text{QP}}\|_{\text{D}}$.

**Rule 5.14 (update of $\sigma_k$ - II)** Given a threshold $\bar{\sigma} > 0$, the current OQP multiplier $\lambda_k^{\text{QP}}$ and the previous penalty parameter $\sigma_{k-1}$, compute the new penalty parameter $\sigma_k$ as follows.

if $\sigma_{k-1} \ge 1.1(\|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma})$;

then $\sigma_k = (\sigma_{k-1} + \|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma})/2$;

else

if $\sigma_{k-1} \ge \|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma}$;

then $\sigma_k = \sigma_{k-1}$;

else $\sigma_k = \max(1.5 \sigma_{k-1}, \|\lambda_k^{\text{QP}}\|_{\text{D}} + \bar{\sigma})$;

With the rule 5.14, property (5.27b) is no longer guaranteed, however, and the convergence result of proposition 5.17 below is no longer ensured.

One can now state a frequently used line-search version of the SQP algorithm.
**Algorithm 5.15 (SQP with line-search)** Let $\beta \in (0, 1)$ and $\omega \in (0, \frac{1}{2})$ be parameters used in the line-search (typically $\beta = 1/2$ and $\omega = 10^{-4}$). One iteration, from $(x_k, \lambda_k, M_k) \in \mathbb{E} \times \mathbb{R}^m \times \mathbb{R}^{n \times n}$ to $(x_{k+1}, \lambda_{k+1}, M_{k+1})$ is made of the following steps (the penalty parameter $\sigma_k$ is also updated):

1. Stopping test: if the current pair $(x_k, \lambda_k)$ is satisfactory, stop;

2. QP solve: let $(d_k, \lambda_k^{QP})$ be the primal-dual solution to the osculating quadratic problem (5.24), if any;

3. New penalty parameter: update $\sigma_k$ so that (5.27) is satisfied;

4. Armijo line-search: determine $\alpha_k := \beta^{i_k}$ where $i_k$ is the smallest nonnegative integer such that

$$ \Theta_{\sigma_k}(x_k + \alpha_k d_k) \le \Theta_{\sigma_k}(x_k) + \omega \alpha_k \Delta_k, \quad (5.28) $$

where $\Delta_k$ is given by (5.26);

5. Update $M_k$: by some technique (for example, modification of $\nabla^2_{xx} \ell(x_k, \lambda_k)$ or a quasi-Newton update);

6. New iterate: set $x_{k+1} := x_k + \alpha_k d_k$ and $\lambda_{k+1} = \lambda_k + \alpha_k (\lambda_k^{QP} - \lambda_k)$;

**Remarks 5.16** 1) The algorithm cannot do better than finding a stationary point of problem ($P_{EI}$), in particular because when it starts at such a point it may compute a vanishing displacement $d_k$ (and will do so if $M_1 > 0$). Therefore, the only reasonable stopping criterion in step 1 is to test the approximate satisfaction of the first order (KKT) optimality conditions (5.1).

2) In the line-search of step 4, instead of giving to the trial stepsizes the predetermined values $\beta^{i_k}$ it is better to do interpolation.

## Global convergence

**Proposition 5.17 (global convergence of the SQP algorithm with line-search)** Suppose that $f$ and $c$ are $C^{1,1}$, that $\| \cdot \|_{P}$ is convex, that the sequences $\{M_k\}$ and $\{M_k^{-1}\}$ are bounded, that at each iteration the OQP (5.24) has a solution $(d_k, \lambda_k^{QP})$, that the update rule of $\sigma_k$ satisfies (5.27), and that $\Theta_k(x_k)$ is bounded below. Then, one of the following two complementary situations occurs

1) the sequence $\{\sigma_k\}$ is unbounded, in which case $\{\lambda_k^{QP}\}$ is also unbounded,

2) the sequence $\{\sigma_k\}$ is bounded, in which case algorithm 5.15 converges, in the sense that

$$ \nabla_x \ell(x_k, \lambda_k^{QP}) \to 0, \quad c(x_k) \xrightarrow{\#} 0, \quad (\lambda_k^{QP})_I \ge 0 \quad \text{and} \quad (\lambda_k^{QP})_I^T c_I(x_k) \to 0. $$

*Proof.* 1) If $\{\sigma_k\}$ is unbounded, we see from rule (5.27b) that $\{\lambda_k^{QP}\}$ is unbounded.

2) If $\{\sigma_k\}$ is bounded, the inequality (5.27a) shows that $\{\lambda_k^{QP}\}$ is also bounded. Then, the rule (5.27b) guarantees that there exists an index $k_1$ such that $\sigma_k = \sigma$ for
all $k \ge k_1$. Now, each iteration after $k_1$ forces the decrease in the same function $\Theta_{\sigma}$. Since $\{\Theta_{\sigma}(x_k)\}$ is bounded below, Armijo's condition (5.28) shows that

$$ \alpha_k \Delta_k \to 0. $$

If we show $\{\alpha_k\}$ is bounded away from zero (i.e., $\alpha_k \ge \underline{\alpha}$ for some $\underline{\alpha} > 0$), the result follows. Indeed, then $\Delta_k \to 0$, and with (5.26c) and (5.27a), we deduce that

$$ d_k^T M_k d_k \to 0 \quad \text{and} \quad c(x_k)^\# \to 0, $$

so that the second claim is satisfied. Because $M_k$ is positive definite and has a bounded inverse, $d_k \to 0$. Then, from (5.25a) and the boundedness of $M_k$, we see that $\nabla_x \ell(x_k, \lambda_k^{\text{QP}}) \to 0$, so that the first claim is satisfied. Furthermore, (5.25c) shows that $(\lambda_k^{\text{QP}})_I \ge 0$, so that the third claim is satisfied. Finally, $\Delta_k = \nabla f(x_k)^\top d_k - \sigma \|c(x_k)\|_{\text{P}}^\# \to 0$ and $c(x_k)^\# \to 0$ imply that $\nabla f(x_k)^\top d_k \to 0$ and, using (5.25a), $(\lambda_k^{\text{QP}})^\top c'(x_k) d_k \to 0$. Hence

$$ \begin{align*} (\lambda_k^{\text{QP}})_I^\top c_I(x_k) &= -(\lambda_k^{\text{QP}})_I^\top c'_I(x_k) d_k \quad [(5.25c)] \\ &= (\lambda_k^{\text{QP}})_E^\top c'_E(x_k) d_k + o(1) \quad [(\lambda_k^{\text{QP}})^\top c'(x_k) d_k \to 0] \\ &= -(\lambda_k^{\text{QP}})_E^\top c_E(x_k) + o(1) \quad [(5.25b)] \\ &= o(1), \end{align*} $$

because $\{\lambda_k^{\text{QP}}\}$ is bounded and $c_E(x_k) \to 0$. We have shown the fourth and last claim.

Therefore, it remains to prove that $\alpha_k \ge \underline{\alpha} > 0$, for all $k$ and some constant $\underline{\alpha}$, which is a rather technical part of the proof. We can consider the indices $k$ of $\mathcal{K} := \{k \ge k_1 : \alpha_k < 1\}$. Then, from the rule determining the stepsize $\alpha_k$, the Armijo inequality is not verified for $\bar{\alpha}_k := \alpha_k/\beta$:

$$ \Theta_{\sigma}(x_k + \bar{\alpha}_k d_k) > \Theta_{\sigma}(x_k) + \omega \bar{\alpha}_k \Delta_k. \quad (5.29) $$

Let us expand the left-hand side of (5.29). Using the smoothness of $f$ and $c$, $\bar{\alpha}_k \le 1$, the convexity of $\|\cdot\|_{\text{P}}$ (hence its Lipschitz continuity), (5.25b), and finally (5.26), we have successively

$$ f(x_k + \bar{\alpha}_k d_k) = f(x_k) + \bar{\alpha}_k \nabla f(x_k)^\top d_k + O(\bar{\alpha}_k^2 \|d_k\|^2) $$

$$ c(x_k + \bar{\alpha}_k d_k) = c(x_k) + \bar{\alpha}_k c'(x_k) d_k + O(\bar{\alpha}_k^2 \|d_k\|^2) $$

$$ = (1 - \bar{\alpha}_k) c(x_k) + \bar{\alpha}_k (c(x_k) + c'(x_k) d_k) + O(\bar{\alpha}_k^2 \|d_k\|^2) $$

$$ \|c(x_k + \bar{\alpha}_k d_k)\|_{\text{P}}^\# \le (1 - \bar{\alpha}_k) \|c(x_k)\|_{\text{P}}^\# + \bar{\alpha}_k \|(c(x_k) + c'(x_k) d_k)\|_{\text{P}}^\# + O(\bar{\alpha}_k^2 \|d_k\|^2) $$

$$ = (1 - \bar{\alpha}_k) \|c(x_k)\|_{\text{P}}^\# + O(\bar{\alpha}_k^2 \|d_k\|^2) $$

$$ \Theta_{\sigma}(x_k + \bar{\alpha}_k d_k) \le \Theta_{\sigma}(x_k) + \bar{\alpha}_k \Delta_k + C_1 \bar{\alpha}_k^2 \|d_k\|^2. $$

Then (5.29) yields

$$ -(1 - \omega) \bar{\alpha}_k \Delta_k \le C_1 \bar{\alpha}_k^2 \|d_k\|^2. $$

But $\Delta_k = -d_k^T M_k d_k + (\lambda_k^{\text{QP}})^\top c(x_k) - \sigma \|c(x_k)\|_{\text{P}}^\# \le -d_k^T M_k d_k \le -C_2 \|d_k\|^2$ (boundedness of $\{M_k^{-1}\}$), so that we deduce from the above inequality:

$$ \bar{\alpha}_k \ge (C_2/C_1)(1 - \omega) > 0, $$

because $\omega < 1$. The positive lower bound on $\alpha_k$ can therefore be taken as $\underline{\alpha} := \beta(C_2/C_1)(1 - \omega)$. This concludes the proof. $\square$
Admissibility of the unit stepsize ▲

5.1.5 Globalization by Trust-Region for (P<sub>E</sub>) ▲

Notes ▲

The analysis of the local convergence of the SQP algorithm, inherited from the one
of the JN algorithm (section 5.1.2), has been taken up from [19; 1994]. This one
gives the local convergence result of theorem 5.6, with the weakest assumptions on
the limit point (uniqueness of the optimal multiplier and SC2) known so far. Before
that, one had results assuming the SC2 and the stronger (CQ-LI) [20; theorem 15.4]
and sometimes strict complementarity ([17; p. 252-256], [20; theorem 15.2], and the
original work [117]).

For the algorithmic issues, we refer the reader to the state of the art by Fletcher [55].

Exercises

**5.1.1. Nondifferentiable augmented Lagrangian.** Let $\mathbb{E}$ be a Euclidean vector space. Consider the optimization problem $(P_{EI})$ and its Lagrangian $\ell : (x, \lambda) \in \mathbb{E} \times \mathbb{R}^m \to \ell(x, \lambda) = f(x) + \lambda^\top c(x) \in \mathbb{R}$. Let $x_* \in \text{dom } \lambda_*$ be a local minimum of problem $(P_{EI})$ at which the KKT conditions hold and denote by $\Lambda_*^-$ the set of optimal multipliers associated with $x_*$. Suppose that the weak second-order sufficient condition of optimality holds at $x_*$. Let $\|\cdot\|_p$ be a norm on $\mathbb{R}^m$ and $\|\cdot\|_D$ be its dual norm with respect to the Euclidean scalar product. Let $\mu \in \mathbb{R}^m$ and $\sigma \in \mathbb{R}_+$ verifying

$$
\sigma \ge \sup_{\lambda_* \in \Lambda_*} \|\lambda_* - \mu\|_D \quad \text{and} \quad \sigma > \|\hat{\lambda}_* - \mu\|_D, \text{ for some } \hat{\lambda}_* \in \Lambda_*^-. \quad (5.30)
$$

We want to show that the function $\Theta_{\mu,\sigma}: \mathbb{E} \to \mathbb{R}$ defined at $x \in \mathbb{E}$ by

$$
\Theta_{\mu,\sigma}(x) := f(x) + \mu^\top c(x)^\# + \sigma \|c(x)^\#\|_p
$$

has a strict local minimum at $x_*$.

1. Show that if $\Theta_{\mu,\sigma}$ has not a strict local minimum at $x_*$, one can find a sequence $\{x_k\} \subset \mathbb{E}$, a sequence of positive real numbers $\{t_k\} \downarrow 0$, and a nonzero critical direction $d$ such that $x_k = x_* + t_k d + o(t_k)$.

2. Show that
$$ \exists \lambda_* \in \Lambda_*, \forall k \text{ large : } \ell(x_*, \lambda_*) < \ell(x_k, \lambda_*) $$

3. Get a contradiction.

**5.1.2. Norm assumptions.** For an arbitrary norm $\|\cdot\|$ on $\mathbb{R}^m$, show that the following properties are equivalent (the operators $|\cdot|$ and $(\cdot)^+$ act componentwise):

$$
(i) \quad 0 \le u \le v \Rightarrow \|u\| \le \|v\|,
$$

$$
(ii) \quad u \le v \Rightarrow \|u^+\| \le \|v^+\|,
$$

$$
(iii) \quad v \mapsto \|v^+\| \text{ is convex.}
$$

**Remark:** These equivalences show that the convexity of $\|\cdot\|^\#_p$ assumed in proposition 5.12 is satisfied with the $\ell_p$ norms, $1 \le p \le \infty$, since the $\ell_p$ norms satisfy (i).
## 5.2 SQP Algorithm for ($P_G$) ▲

### 5.2.1 The SQP Algorithm

Consider the optimization problem ($P_G$) in (2.1) with its Lagrangian $\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 (5.31) $$

The first order optimality conditions (2.8) at a primal-dual solution $(x, \lambda)$ (we drop the star indices to alleviate notation) read

$$ \nabla f(x) + c'(x)^* \lambda = 0 \quad \text{and} \quad \lambda \in N_G(c(x)). \qquad (5.32) $$

Let us show that this system reads like the following functional inclusion

$$ F(z) + N_G(z) \ni 0, \qquad (5.33) $$

for some variable $z$, some function $F$, and some closed convex set $C$. Observe first that (5.32) also reads as the following system in $z := (x, y, \lambda) \in \mathbb{E} \times \mathbb{F} \times \mathbb{F}$:

$$ \nabla f(x) + c'(x)^* \lambda = 0, \quad \lambda \in N_G(y) \quad \text{and} \quad y - c(x) = 0. \qquad (5.34) $$

This one can be written like (5.33) in the variable $z$, where the function $F$ and the closed convex set $C$ are defined by

$$ F(z) = \begin{pmatrix} \nabla f(x) + c'(x)^* \lambda \\ -\lambda \\ y - c(x) \end{pmatrix} \quad \text{and} \quad C = \mathbb{E} \times G \times \mathbb{F}. \qquad (5.35) $$

Indeed, $N_G(z) = N_{\mathbb{E}}(x) \times N_G(\lambda) \times N_{\mathbb{F}}(y) = \{0_{\mathbb{E}}\} \times N_G(y) \times \{0_{\mathbb{F}}\}$, so that (5.34) and (5.33) are the same systems.

The Josephy-Newton (JN) algorithm consists in determining $z_+ := (x_+, y_+, \lambda_+)$ as a solution to the linearized functional inclusion

$$ F(z) + F'(z) \cdot (z_+ - z) + N_G(z_+) \ni 0. $$

We have

$$ F'(z) = \begin{pmatrix} L & 0 & c'(x)^* \\ 0 & 0 & -I \\ -c'(x) & I & 0 \end{pmatrix} \qquad (5.36) $$

where $L := \nabla_{xx}^2 \ell(x, \lambda)$. Therefore, $z_+$ is determined as a solution to

$$ \begin{cases} \nabla f(x) + c'(x)^* \lambda + L(x_+ - x) + c'(x)^* (\lambda_+ - \lambda) = 0 \\ \lambda + (\lambda_+ - \lambda) \in N_G(y_+) \\ y - c(x) - c'(x)(x_+ - x) + (y_+ - y) = 0, \end{cases} $$

which after elimination of $y$ and $\lambda$ becomes

$$ \begin{cases} \nabla f(x) + L(x_+ - x) + c'(x)^* \lambda_+ = 0 \\ \lambda_+ \in N_G(y_+) \\ c(x) + c'(x)(x_+ - x) = y_+. \end{cases} $$
After elimination of $y_+$ and the introduction of $d = x_+ - x$, we get

$$ egin{cases} \nabla f(x) + Ld + c'(x)^*\lambda_+ = 0 \\ \lambda_+ \in N_G(c(x) + c'(x)d). \end{cases} $$

This system is the first order optimality conditions of the osculating quadratic problem

$$ (OQP) \quad \left\{ \begin{array}{l} \min_d \langle \nabla f(x), d \rangle + \frac{1}{2} \langle \nabla_{xx}^2 \ell(x, \lambda) d, d \rangle \\ c(x) + c'(x) \cdot d \in G. \end{array} \right. \qquad (5.37) $$

**Algorithm 5.18 (local SQP for ($P_G$))** One iteration, from $(x_k, \lambda_k) \in \mathbb{E} \times \mathbb{F}$ to $(x_{k+1}, \lambda_{k+1}) \in \mathbb{E} \times \mathbb{F}$ is made of the following steps:

1. Stopping test: if the current pair $(x_k, \lambda_k)$ is satisfactory, stop;

2. QP solve: let $(d_k, \lambda_k^{QP})$ be an appropriate primal-dual solution to the osculating quadratic problem (5.37), if any;

3. New iterate: set $x_{k+1} := x_k + d_k$ and $\lambda_{k+1} := \lambda_k^{QP}$.

### 5.2.2 Local Convergence
# 6 Self-dual Conic Optimization

Let $\mathbb{E}$ and $\mathbb{F}$ be two finite dimension vector spaces, and $\langle \cdot, \cdot \rangle$ be a scalar product on $\mathbb{E}$.
A conic optimization problem is an optimization problem of the form

$$ \left\{ \begin{array}{l} \inf_{x \in \mathbb{E}} \langle c, x \rangle \\ \mathcal{A}(x) = b \\ x \in K, \end{array} \right. \qquad (6.1) $$

where $c \in \mathbb{E}$, $\mathcal{A}: \mathbb{E} \to \mathbb{F}$ is a linear map, $b \in \mathbb{F}$, and $K$ is a closed cone of $\mathbb{E}$. Hence, one minimizes a linear function on the intersection of an affine space and a closed cone.

Problem (6.1) may look like a very structured problem, but without more specifications on $K$, a problem as general as $\inf_{x \in \mathbb{E}}\{f(x) : x \in X\}$, where $f: \mathbb{E} \to \mathbb{R}$ and $X \subseteq \mathbb{E}$, can be written in the form (6.1). This is a consequence of the following two observations.

* There is no restriction in assuming that the objective of an optimization problem is linear, like in (6.1). For example, the problem $\inf_{x \in \mathbb{E}}\{f(x) : x \in X\}$ can be rewritten into the problem $\inf_{(x,t) \in \mathbb{E} \times \mathbb{R}}\{t : f(x) \le t, x \in X\}$ (the equivalence is about the optimal values and the $x$-part of the solutions).

* We are now reduced to rewrite a problem of the form $\inf_{x \in \mathbb{E}}\{\langle c, x \rangle : x \in X\}$ into the form (6.1). This is done by a technique called conification of $X$ (also called homogenization [125; § 8], [118], but we prefer to avoid this term, which is used in the field of partial differential equations with a completely different meaning). One introduces the closed cone $X^\nabla$ of $\mathbb{E} \times \mathbb{R}$ defined by

$$ X^{\nabla} := \text{cl } X^{\vee}, \quad \text{where} $$

$$ X^{\vee} := \{(x, \alpha) \in \mathbb{E} \times \mathbb{R} : \alpha > 0, \alpha^{-1}x \in X\}. $$

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

Since $X^\nabla$ is clearly a cone of $\mathbb{E} \times \mathbb{R}$, $X^\nabla$ is a closed cone. Furthermore, $x \in X$ if and only if $(x, 1) \in X^\nabla$. Therefore, the problem $\inf_{x \in \mathbb{E}}\{\langle c, x \rangle : x \in X\}$ also reads $\inf_{(x,\alpha) \in \mathbb{E} \times \mathbb{R}}\{\langle c, x \rangle : (x, \alpha) \in X^\nabla$, and $\alpha = 1\}$, which is in the form of (6.1).

Therefore, to really take advantage of the structure of (6.1), more assumptions must be given on the cone $K$.

A certainly much more specific problem is obtained with (6.1) if one assumes that $K$ is a closed convex cone. This does not imply that problem (6.1) becomes easy to understand and to solve. A rather fruitful analysis is possible at this level of generality [14, 116], but in this chapter will limit our presentation to three particular
self-dual cones $K$, meaning that they verify $K^+ = K$ (hence $K$ is necessarily a closed convex cone).

* A semidefinite optimization problem is obtained from (6.1) when $\mathbb{E} = S^n$ is the space of symmetric matrices of order $n$ and $K = S_+^n$ is the cone of positive semi-definite matrices. This problem is analyzed in section 6.1.

* A circular optimization problem arises when $\mathbb{E} = \mathbb{R}^n$ and $K = \mathbb{R}_\nabla^n$ is the circular cone (section 6.2).

* In copositive optimization (section 6.3), the cone is formed of symmetric matrices ($\mathbb{E} = S^n$ again) whose associated quadratic form is nonnegative on the positive orthant.

These problems have been meticulously analyzed in the last decades for various reasons. The first reason deals with complexity issues. The first two problems can indeed be solved in a time that is polynomial in the dimension of the problem. The last one is NP-hard, despite the convexity of its objective, which is linear, and its convex feasible set; its computational complexity then comes from the complexity of the boundary of its feasible set, but the convexity of the latter and the convexity of the solution set make these problems very attractive to study. The second reason comes from the fact that many problems can be formulated as one of these three conic problems. If they can be written like the first two, they can then be solved in polynomial time. If the problem can be formulated as a copositive optimization problem, they benefit from the convexity of this problem, which makes it possible to approximate them by sequences of easier problems. As a last reason, let us mention that many nonconvex NP-hard problems have semidefinite or circular relaxations. Sometimes, this provides a rather precise lower bound on their optimal value, which is an important information in some branching approach to solve them.

# 6.1 Semidefinite Optimization

## 6.1.1 Primal and Dual Problems

### The Cones $S_+$ and $S_+$

Semidefinite optimization has an unknown belonging to the cone of positive definite matrices. We denote by $S^n$ the Euclidean space of symmetric $n \times n$ real matrices, equipped with the scalar product

$$ \langle \cdot, \cdot \rangle : (A, B) \in (S^n)^2 \mapsto \langle A, B \rangle = \text{tr}(AB) = \sum_{ij} A_{ij} B_{ij} \in \mathbb{R}, $$

where $\text{tr} M := \sum_{i=1}^n M_{ii}$ denotes the trace of a square matrix $M$. It is easy to see that, for $A$ and $B \in \mathbb{R}^{n \times n}$, $\text{tr} AB = \text{tr} BA$.

A real symmetric matrix $A \in S^n$ has $n$ real eigenvalues $\lambda_i \in \mathbb{R}$ with which are associated orthonormal eigenvectors $v_i$, $i \in [1:n]$:

$$ Av_i = \lambda_i v_i \quad \text{and} \quad v_i^\top v_j = \delta_{ij}, $$

where $\delta_{ij}$ is the Kronecker symbol ($\delta_{ij} = 1$ if $i = j$, $\delta_{ij} = 0$ if $i \neq j$). If we denote by $V \in \mathbb{R}^{n \times n}$ the matrix whose columns are the eigenvectors $v_1, \dots, v_n$, we have