$AV = V\Lambda$, where $\Lambda = \text{Diag}(\lambda_1, \dots, \lambda_n)$. Since $V$ is orthogonal, $V^{-1} = V^T$ and we get the spectral decomposition of $A \in S^n$:

$$A = V\Lambda V^T = \sum_{i=1}^{n} \lambda_i v_i v_i^T.$$

The cone of $S^n$ made of the positive semidefinite matrices is denoted by $S_+^n$. We use the notation $A \ge 0$ to quote the fact that $A \in S_+^n$. Recall that $A \ge 0$ if its eigenvalues are nonnegative:

$$A \ge 0 \iff A \in S_+^n \iff \forall v \in \mathbb{R}^n : v^T A v \ge 0 \iff \lambda(A) \ge 0,$$

where we have denoted by $\lambda(A)$ the vector of the eigenvalues of $A \in S^n$. The cone of $S^n$ made of the positive definite matrices is denoted by $S_{++}^n$. We use the notation $A > 0$ to quote the fact that $A \in S_{++}^n$. Recall that $A > 0$ if its eigenvalues are positive:

$$A > 0 \iff A \in S_{++}^n \iff \forall v \in \mathbb{R}^n \setminus \{0\} : v^T A v > 0 \iff \lambda(A) > 0.$$

**Lemma 6.1 (cones $S_+^n$ and $S_{++}^n$)**

1) $A \ge 0 \iff \forall B \in S_+^n : \langle A, B \rangle \ge 0$.

2) $A > 0 \iff \forall B \in S_+^n \setminus \{0\} : \langle A, B \rangle > 0$.

3) For $A$ and $B \in S_+^n : \langle A, B \rangle = 0 \iff AB = 0$.

*Proof.* 1) Let $A$ and $B \in S_+^n$. Take $B = \sum_i \lambda_i v_i v_i^T$ the spectral decomposition of $B$. Then,

$$\langle A, B \rangle = \sum_{i=1}^{n} \lambda_i \langle A, v_i v_i^T \rangle = \sum_{i=1}^{n} \lambda_i \operatorname{tr}(A v_i v_i^T) = \sum_{i=1}^{n} \lambda_i (v_i^T A v_i) \ge 0,$$

where we have used $\operatorname{tr}(A v_i v_i^T) = \operatorname{tr}(v_i^T A v_i) = v_i^T A v_i \in \mathbb{R}$ and, finally, the fact that $v_i^T A v_i \ge 0$ and $\lambda_i \ge 0$ by the positive semidefiniteness of $A$ and $B$ respectively.

Conversely, by taking $B = vv^T \ge 0$ for an arbitrary $v \in \mathbb{R}^n$, we get that $0 \le \langle A, vv^T \rangle = v^T A v$, which characterizes the positive semidefiniteness of $A$.

2) Let $A > 0$ and $B \ge 0$ with $B \ne 0$. In the spectral decomposition of $B = \sum_{i=1}^n \lambda_i v_i v_i^T$, at least one of the $\lambda_i$'s is positive and the others are nonnegative. Then, like above, $\langle A, B \rangle = \sum_{i=1}^n \lambda_i (v_i^T A v_i)$, which is positive since all the $v_i^T A v_i > 0$ and all the $\lambda_i > 0$, with at least one $\lambda_i > 0$.

Conversely, assume that $\langle A, B \rangle > 0$ for all nonzero $B \ge 0$. By taking $B = vv^T \ge 0$, with an arbitrary nonzero $v$, one must have $0 < \langle A, B \rangle = v^T A v$, which shows that $A > 0$.

3) With the spectral decomposition of $B = \sum_{i=1}^n \lambda_i v_i v_i^T$ (the $\lambda_i$'s are $\ge 0$) and $\langle A, B \rangle = 0$, one gets $\sum_{i=1}^n \lambda_i v_i A v_i^T = 0$. Since $A \in S_+^n$, this implies that $A v_i = 0$ when $\lambda_i > 0$. Then, $AB = \sum_{i=1}^n \lambda_i A v_i v_i^T = 0$.

Conversely, it is clear that $AB = 0$ implies $\langle A, B \rangle = 0$. $\square$

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

Here are some remarks and properties of the cones $S_+^n$ and $S_{++}^n$.
• Point 1 of lemma 6.1 expresses that fact that $S_+^n$ is self-dual:

$$ (S_+^n)^+ = S_+^n. $$

• Point 2 of lemma 6.1 is often used in the form of the following implication

$$ \langle A, B \rangle = 0, \quad A > 0 \quad \text{and} \quad B \ge 0 \quad \implies \quad B = 0. \qquad (6.2) $$

• The tangent and normal cone to $S_+^n$ have the following expressions:

$$ T_A S_+^n = \{D \in S^n : v^T D v \ge 0, \text{ for all } v \in \mathcal{N}(A)\}, \qquad (6.3) $$

$$ N_A S_+^n = \{N \in S_-^n : \langle A, N \rangle = 0\} = S_-^n \cap \{A\}^{\perp}. \qquad (6.4) $$

• $S_{++}^n$ is the cone of $S^n$ made of the positive definite matrices:

$$ A \ge 0 \text{ and } [v^T M v > 0, \forall v \in \mathcal{N}(A) \setminus \{0\}] \implies M + rA > 0 \text{ for large } r. $$

This last property is the so-called *Finsler lemma*.

## Problem Definitions

The primal and (Lagrange) dual of the SDO problem read

$$ (P) \quad \left\{ \begin{array}{l} \inf_{X \in S^n} \langle C, X \rangle \\ \mathcal{A}(X) = b \\ X \ge 0 \end{array} \right. \quad \text{and} \quad (D) \quad \left\{ \begin{array}{l} \sup_{(y,S) \in \mathbb{R}^m \times S^n} b^T y \\ \mathcal{A}^*(y) + S = C \\ S \ge 0, \end{array} \right. \qquad (6.5) $$

where

• $C \in S^n$ and $b \in \mathbb{R}^m$,

• $\mathcal{A}: S^n \to \mathbb{R}^m$ is linear ($\mathcal{A}^*: \mathbb{R}^m \to S^n$ is its adjoint).

Some notation

• Feasible sets:

$$ \mathcal{F}_P := \{X \in S_+^n : \mathcal{A}(X) = b\}, $$

$$ \mathcal{F}_D := \{(y, S) \in \mathbb{R}^m \times S_+^n : \mathcal{A}^*(y) + S = C\}, $$

$$ \mathcal{F} := \mathcal{F}_D \times \mathcal{F}_D. $$

• Strictly feasible sets:

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

$$ \mathcal{F}_D^s := \{(y, S) \in \mathbb{R}^m \times S_{++}^n : \mathcal{A}^*(y) + S = C\}, $$

$$ \mathcal{F}^s := \mathcal{F}_D \times \mathcal{F}_D. $$

• Optimal values: $\text{val}(P)$ and $\text{val}(D)$. Duality gap: $\text{val}(P) - \text{val}(D)$

• Solution sets: $\text{Sol}(P)$ and $\text{Sol}(D)$.
One can represent $\mathcal{A}$ by $m$ matrices $A_k \in S^n$ (Riesz-Fréchet representation theorem), as follows

$$ \mathcal{A}(X) = \begin{pmatrix} \langle A_1, X \rangle \\ \vdots \\ \langle A_m, X \rangle \end{pmatrix}. \qquad (6.6a) $$

In this representation, the map $\mathcal{A}$ is surjective if and only if the matrices $A_k$ are linearly independent in $S^n$. With the representation (6.6a) and the Euclidean scalar product on $\mathbb{R}^m$, the adjoint $\mathcal{A}^*$ of $\mathcal{A}$ takes at $y \in \mathbb{R}^m$ the value

$$ \mathcal{A}^*(y) = \sum_{k \in [1:n]} y_k A_k \in S^n. \qquad (6.6b) $$

Concrete problems usually specify $\mathcal{A}$ (resp. $\mathcal{A}^*$) using the representation (6.6a) (resp. (6.6b)), but the theory given in this chapter is easier to develop and present with the abstract forms $(P)$ and $(D)$ of the primal and dual problems.

The Lagrangian of problem $(P)$ is the function $\ell: S^n \times \mathbb{R}^m \times S^n \to \mathbb{R}$ that takes at $(X, y, S) \in S^n \times \mathbb{R}^m \times S^n$ the value

$$ \ell(X, y, S) = \langle C, X \rangle - \langle y, A(X) - b \rangle - \langle S, X \rangle. $$

Note that the dual problem can also be written by eliminating the variable $S$ as follows

$$ (D) \quad \begin{cases} \sup_{y \in \mathbb{R}^m} b^\top y \\ C - \mathcal{A}^*(y) \ge 0. \end{cases} $$

In that case it is more appropriate to take as Lagrangian of $(P)$ the function that only dualises the equality constraint:

$$ (X, y) \in S^n \times \mathbb{R}^m \mapsto \langle C, X \rangle - \langle y, A(X) - b \rangle. $$

**Proposition 6.2 (consequences of the Lagrangian dualization)**

1) $\text{val}(D) \le \text{val}(P)$.

2) $(X, y, S) \in \mathcal{F} \Rightarrow \langle C, X \rangle - b^\top y = \langle X, S \rangle \ge 0$.

3) $(X, y, S) \in \mathcal{F}, \langle X, S \rangle = 0$

$\Leftrightarrow X \in \text{Sol}(P), (y, S) \in \text{Sol}(D), \text{val}(D) = \text{val}(P),$

$\Leftrightarrow (X, (y, S))$ is a saddle-point of $\ell$ on $S^n \times (\mathbb{R} \times S_+^n)$.

*Proof.* 1) This is the weak duality inequality (1.60).

2) If $(X, y, S) \in \mathcal{F}$, then $\langle C, X \rangle = \langle \mathcal{A}^*(y) + S, X \rangle = \langle y, \mathcal{A}(X) \rangle + \langle X, S \rangle = \langle y, b \rangle + \langle X, S \rangle$. Furthermore $\langle X, S \rangle \ge 0$ since $X \ge 0$ and $S \ge 0$.

3) $\Rightarrow$ If $(X, y, S) \in \mathcal{F}$, the following holds

$$ b^\top y \le \text{val}(D) \le \text{val}(P) \le \langle C, X \rangle. $$

Since $\langle X, S \rangle = 0$, $b^\top y = \langle C, X \rangle$ by point 2 and therefore equality holds everywhere above, which implies that $X \in \text{Sol}(P), (y, S) \in \text{Sol}(D)$, and $\text{val}(D) = \text{val}(P)$.

$\Leftrightarrow$ Clearly, $(X, y, S) \in \mathcal{F}$, when $X \in \text{Sol}(P)$ and $(y, S) \in \text{Sol}(D)$. Furthermore, by point 2, $\langle X, S \rangle = \langle C, X \rangle - b^\top y = \text{val}(P) - \text{val}(D) = 0$. $\square$
### 6.1.2 Examples of SDO Formulation

Suppose that the principal submatrix A of the square symmetric matrix

$$K := \begin{pmatrix} A & B \\ B^\top & C \end{pmatrix}$$

is nonsingular. Then, the Schur complement of A in K is the matrix denoted and defined by

$$(A | K) := C - B^\top A^{-1} B.$$

This matrix can also be defined when K is nonsymmetric. It occurs in many circumstances [38]. From the block Gaussian factorization of K, which reads

$$K = \begin{pmatrix} I & 0 \\ B^\top A^{-1} & I \end{pmatrix} \begin{pmatrix} A & 0 \\ 0 & (A | K) \end{pmatrix} \begin{pmatrix} I & A^{-1} B \\ 0 & I \end{pmatrix},$$

we deduce that the following characterization of the positive definiteness of K:

$$K > 0 \iff \begin{cases} A > 0 \\ (A | K) > 0. \end{cases} \qquad (6.7)$$

As we shall see, this characterization often occurs in semi-definite optimization. For a characterization of the positive semi-definiteness of K with a Schur-like complement, see exercise 6.1.1.

#### Linear Optimization

#### Convex Quadratic Optimization

#### Global Minimization of Polynomials

Consider the problem of finding the global minimum of a real polynomial $p \in \mathbb{R}[x]$, in the variable $x \in \mathbb{R}^n$, which reads

$$\inf_{x \in \mathbb{R}^n} \left( p(x) := \sum_{\alpha \in \mathbb{N}^n} p_{\alpha} x^{\alpha} \right), \qquad (6.8)$$

where there is only a finite number of nonzero coefficients $p_{\alpha} \in \mathbb{R}$ and, for $\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^n$, the monomial $x^{\alpha}$ is a compact writing for

$$x^{\alpha} := x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_n^{\alpha_n}.$$

The degree of the monomial $x^{\alpha}$ is denoted by $|\alpha| := \sum_{i=1}^n \alpha_i$.

We show below, that when $n = 1$, problem (6.8) can be rewritten as an SDO problem. When $n > 1$, this is usually not the case, but more and more precise SDO relaxations of the problem can be obtained. SDO relaxations can also be defined for problems with polynomial constraints; for simplicity and by the need for brevity, we will not consider that possibility here; see [108, 90, 91, 6, 18, 92] for more complete presentations.

The optimal value of problem (6.8) can be obtained by solving
$$ \begin{cases} \sup_{s \in \mathbb{R}} s \\ p(x) \ge s, \quad \forall x \in \mathbb{R}^n. \end{cases} $$

This problem has a single unknown $s \in \mathbb{R}$ but an infinite number of constraints, which is not a desirable feature. This infinite number of constraints “disappears” if we trivially express them in terms of membership to the cone $\mathcal{P}$ of nonnegative polynomials:

$$ \left\{ \begin{array}{l} \sup_{s \in \mathbb{R}} s \\ p - s \in \mathcal{P}. \end{array} \right. \qquad (6.9) $$

Normally, we should not have gained much by these trivial transformations, unless membership to $\mathcal{P}$ can be described in a pleasant manner. Let us look at that.

A real nonnegative number $p \in \mathbb{R}$ can always be written as the square of another number $p = q^2$ (take the square root of $p$ for $q$). When $p$ is a nonnegative polynomial, it cannot be written in general as the square of another polynomial. For example $p(x) = x^2 + 1$ cannot be written $(ax + b)^2$, since one should have both $a = b = 1$ and $ab = 0$, which are not compatible conditions. It turns out, however, that for $n = 1$ a polynomial $p \in \mathcal{P}$ can be written as the sum of two squares of polynomials. This is a remarkable fact and we shall see below why this observation is useful.

**Proposition 6.3 (nonnegative univariate polynomial)** A univariate polynomial $p \in \mathbb{R}[x]$ is nonnegative on $\mathbb{R}$ if and only if it is of even degree, say $2m$, and reads $p = q^2 + r^2$, with $q, r \in \mathbb{R}[x]$, $\deg q = m$, and $\deg r \le m - 1$.

*Proof.* The given conditions are clearly sufficient. Let us show that they are necessary.

Being nonnegative on $\mathbb{R}$ the polynomial is necessary of even degree, say $2m$, and the leading coefficient is positive. There is therefore no loss of generality in supposing that this leading coefficient is 1. Then the polynomial can be decomposed in $m$ factors of the form

$$ (x - a)^2 + b^2. $$

It is indeed the form of $(x - r)(x - \bar{r})$ when $r$ and $\bar{r}$ are complex conjugate roots $a \pm ib$. On the other hand, any real root has an even multiplicity (otherwise the polynomial would have positive and negative values around the root) and each double root is of the form above with $b = 0$.

The $m$ factors of the form $q^2 + r^2$ are then multiplied successively, by using the following formula

$$ (q_j^2 + r_j^2)(q^2 + r^2) = (q_j q + r_j r)^2 + (q_j r - r_j q)^2 =: q_{j+1}^2 + r_{j+1}^2. $$

By induction, we see that $\deg q_j = j$ and $\deg r_j \le j - 1$. It is indeed the case for $j = 1$ since $\deg q_1 = 1$ and $\deg r_1 = 0$. Now, be $r$ vanishing or not, $\deg q_{j+1} = \deg q_j + 1 = j + 1$. Finally, if $r = 0$, $\deg r_{j+1} = \deg r_j + 1 \le j$ and, if $r \ne 0$, $\deg r_{j+1} \le \max(\deg q_j, \deg r_j + 1) \le j$. $\square$

A multivariate nonnegative polynomial cannot be written as the sum of two squares of polynomials, but, on a compact set, these can be approached by SOS polynomials. An SOS polynomial is a polynomial that can be written as a sum of squares of polynomials and the set of SOS polynomials is denoted by
$$ \Sigma[x]. $$

Since $\Sigma[x] \subseteq \mathcal{P}$, problem (6.9) can be approached by

$$ \left\{ \begin{array}{l} \sup_{s \in \mathbb{R}} s \\ p - s \in \Sigma[x]. \end{array} \right. \qquad (6.10) $$

This is a relaxation of problem (6.9) in the sense that its optimal value does not exceed the one of problem (6.9).

Proposition 6.4 tells us that a multivariate polynomial $p \in \Sigma[x]$ has a nice representation, making use of a positive semi-definite symmetric matrix $S$. As we shall see, a consequence of this observation is that problem (6.10) is an SDO problem, so that we have obtained an SDO relaxation of the problem consisting in finding the global minimum value of a multivariate polynomial. The proposition uses the vector $v_m(x)$, whose components are the multivariate monomials of degree $\le m$. Since there are

$$ \binom{n+d-1}{d} $$

monomials of degree $d$ (it is the number of combination with repetition of $d$ elements among $n$), the dimension of the vector $v_m(x)$ is

$$ N := \binom{n-1}{0} + \binom{n}{1} + \dots + \binom{n+d-1}{d} = \binom{n+m}{n}. $$

Hence a polynomial of degree $\le m$ can be written $s^T v_m(x)$, for some $s \in \mathbb{R}^N$.

**Proposition 6.4 (characterization of SOS polynomials)** A multivariate polynomial $p \in \mathbb{R}[x]$ of degree $\le 2m$ is a sum of $r$ squares of polynomials if and only if there exists a matrix $S \ge 0$ of order $N$ and of rank $\le r$ such that $p(x) = v_m(x)^T S v_m(x)$.

*Proof.* [⇒] If $p \in \mathbb{R}[x]$ is of degree $\le 2m$ and reads $\sum_{i=1}^r \sigma_i^2$, where $\sigma_i \in \mathbb{R}[x]$, the degrees $\deg \sigma_i \le m$. Therefore, on can find vectors $s_i \in \mathbb{R}^{m+1}$ such that

$$ p(x) = \sum_{i=1}^{r} (s_i^T v_m(x))^2 = \sum_{i=1}^{r} v_m(x)^T s_i s_i^T v_m(x) = v_m(x)^T S v_m(x), $$

where $S := \sum_{i=1}^r s_i s_i^T \ge 0$ is of rank $\le r$.

[ ⇐ ] Conversely, suppose that $p(x) = v_m(x)^T S v_m(x)$, with $S \ge 0$ of rank $\le r$. The spectral decomposition of $S = \sum_{i=1}^r s_i s_i^T$ allows us to write

$$ p(x) = \sum_{i=1}^{r} v_m(x)^{\top} s_i s_i^{\top} v_m(x) = \sum_{i=1}^{r} (s_i^{\top} v_m(x))^2, $$

showing that $p$ is the sum of the squares of at most $r$ polynomials. $\square$

Using the above propositions and setting $t := -s$, problem 6.10 can be written

$$ \left\{ \begin{array}{l} \inf_{(S,t) \in S^{m+1} \times \mathbb{R}} t \\ p(x) + t = v_m(x)^{\top} S v_m(x), \quad \forall x \in \mathbb{R}^n \\ S \ge 0. \end{array} \right. \qquad (6.11) $$
Knowing $p$, the first constraint in (6.11) is an affine constraint on the unknown $t \in \mathbb{R}$ and the unknown real coefficients of $S$, if we impose equality between the coefficients of the same monomials in both sides of the equality. Therefore, problem (6.11) is almost in the primal form of an SDO problem. The difference is the free variable $t$, which is only constrained by the affine constraint in (6.11), not by a nontrivial cone. This small difference can be dealt with by standard SDO codes.

### Rank Relaxation of a QCQP

#### 6.1.3 Existence of Solution, Optimality Conditions

##### Existence of Solution

In linear optimization, according to (1.63), a finite optimal value guarantees that the problem has a solution. We have seen this result as a consequence of the fact that the image $T(P)$ of a convex polyhedron $P$ by a linear map $T$ is a convex polyhedron, hence a closed set. This approach no longer works for an SDO problem. Although $T(\cdot) = \langle C, \cdot \rangle$ is linear, the feasible set $\mathcal{F}_P := \{X \in \mathcal{S}^n : A(X) = b, X \ge 0\}$ is not a convex polyhedron, so that $T(P)$ may not be closed. As a result, in general

$$ \mathrm{val}(P) \in \mathbb{R} \quad \Rightarrow \quad \mathrm{Sol}(P) \neq \emptyset. $$

See example 6.7-2 below. The existence of solution is then ensured by using some kind of constraint qualification.

The assumptions of the next proposition can be understood, or at least memorized, with the following scheme in mind. If $\mathcal{F}_D^s \neq \emptyset$, a kind of Slater constraint qualification (CQ-S) holds for the dual problem ($D$); hence, the dual solutions of ($D$), which are the solutions of ($P$), must exist and form a bounded set (recall that (CQ-S) is equivalent to (CQ-MF) or (CQ-R) for convex problems, and use propositions 2.6 and 2.22); this is point 1 of the proposition (this way of thinking is not quite correct, since it is not assumed there that the dual problem has a solution). Similarly, if $\mathcal{F}_P^s \neq \emptyset$, a kind of Slater constraint qualification (CQ-S) holds for the primal problem ($P$); hence, the dual solutions of ($P$), which are the solutions of ($D$), must exist and form a bounded set; this is point 2 of the proposition (this way of thinking is not quite correct, since it is not assumed there that the primal problem has a solution). Point 3 just gathers the results in points 1 and 2.

We start with a lemma giving a consequence of the strict primal or dual feasibility.

##### Lemma 6.5 (consequence of strict feasibility)

1) If $\mathcal{F}_P^s \neq \emptyset$, then any $(d, D) \in \mathbb{R}^m \times \mathcal{S}^n$ verifying $\langle b, d \rangle \ge 0$, $A^*(d) + D = 0$, $D \ge 0$ and $d \in \mathcal{R}(A)$ vanishes.

2) If $\mathcal{F}_D^s \neq \emptyset$, then any $D \in \mathcal{S}^n$ verifying $\langle C, D \rangle \le 0$, $A(D) = 0$ and $D \ge 0$ vanishes.

*Proof.* 1) Suppose that $(d, D) \in \mathbb{R}^m \times \mathcal{S}^n$ verifies $\langle b, d \rangle \ge 0$, $A^*(d) + D = 0$, $D \ge 0$ and $D \in \mathcal{R}A$. Since $\mathcal{F}_P^s \neq \emptyset$, there exists an $X_0 \in \mathcal{S}_{++}^n$ such that $A(X_0) = b$. Then,
$$
\begin{align*}
0 &= \langle X_0, \mathcal{A}^*(d) + D \rangle \quad [\mathcal{A}^*(d) + D = 0] \\
&= \langle b, d \rangle + \langle X_0, D \rangle \quad [\mathcal{A}(X_0) = b] \\
&\ge \langle X_0, D \rangle \quad [\langle b, d \rangle \ge 0] \\
&\ge 0 \quad [X_0 \ge 0 \text{ and } D \ge 0].
\end{align*}
$$

Hence $\langle X_0, D \rangle = 0$. Now $X_0 > 0$, $D \ge 0$ and (6.2) imply that $D = 0$. Next, $\mathcal{A}^*(d) = 0$ and $d \in \mathcal{R}(\mathcal{A})$ imply that $d = 0$.

2) Suppose that $D \in S^n$ verifies $\langle C, D \rangle \le 0$, $\mathcal{A}(D) = 0$ and $D \ge 0$. Since $\mathcal{F}_D^s \ne \emptyset$, there exists a pair $(y_0, S_0) \in \mathbb{R}^m \times S_++^n$ such that $\mathcal{A}^*(y_0) + S_0 = C$. Then,

$$
\begin{align*}
0 &= \langle y_0, \mathcal{A}(D) \rangle \quad [\mathcal{A}(D) = 0] \\
  &= \langle C, D \rangle - \langle S_0, D \rangle \quad [\mathcal{A}^*(y_0) + S_0 = C] \\
  &\le -\langle S_0, D \rangle \quad [\langle C, D \rangle \le 0] \\
  &\le 0 \quad [S_0 \ge 0 \text{ and } D \ge 0].
\end{align*}
$$

Hence $\langle S_0, D \rangle = 0$. Now $S_0 > 0$, $D \ge 0$ and (6.2) imply that $D = 0$. $\square$

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

**Proposition 6.6 (existence of compact sets of solutions)**

$$
1) \mathcal{F}_P \times \mathcal{F}_D^s \neq \emptyset \implies \text{Sol}(P) \text{ is nonempty and compact.}
$$

$$
2) \mathcal{F}_P^s \times \mathcal{F}_D \neq \emptyset \implies \text{Sol}(D) \cap (\mathcal{R}(\mathcal{A}) \times \mathcal{S}^n) \text{ is nonempty and compact.}
$$

$$
3) \mathcal{F}^s \neq \emptyset \implies \text{Sol}(P) \text{ and Sol}(D) \cap (\mathcal{R}(\mathcal{A}) \times \mathcal{S}^n) \text{ are nonempty and compact.}
$$

In all these cases, there is no duality gap: $\text{val}(D) = \text{val}(P)$.

Proof. 1) [Sol($P$) nonempty and compact] Problem ($P$) reads

$$
\inf_{X \in S^n} \left( \varphi(X) := \langle C, X \rangle + \mathcal{I}_{\mathcal{A}}(X) + \mathcal{I}_{S_+^n}(X) \right),
$$

where $\mathcal{A} := \{X \in S^n : \mathcal{A}(X) = b\}$. The value at $D \in S^n$ of the asymptotic function $\varphi^\infty$
of $\varphi$ reads

$$
\varphi^{\infty}(D) = \langle C, D \rangle + \mathcal{I}_{\mathcal{N}(\mathcal{A})}(D) + \mathcal{I}_{S_{+}^{n}}(D).
$$

By the implication (iv) $\Rightarrow$ (iii) of proposition 1.20, Sol($P$) is nonempty and compact
if we have that $\varphi^\infty(D) > 0$ for all nonzero $D$ or, equivalently, if

$$
\mathcal{A}(D) = 0, \quad D \ge 0, \quad \langle C, D \rangle \le 0 \quad \implies \quad D = 0. \qquad (6.12\text{a})
$$

By lemma 6.5, this is a consequence of $\mathcal{F}_D^s \neq \emptyset$.

[No duality gap] Consider first the case when $C \in \mathcal{R}(\mathcal{A}^*) = \mathcal{N}(\mathcal{A})^{\perp}$ (see figure 6.1,
left). Then, $C$ is perpendicular to $\mathcal{N}(\mathcal{A})$, any primal feasible $X \in \mathcal{F}_P$ should be a
solution and the optimal value $\text{val}(P)$ should not be affected by a perturbation of
$S_+^n$, so that $S_0 = 0$ should be an optimal dual variable. Let us check this rigorously.
Indeed, since when $C \in \mathcal{R}(\mathcal{A}^*)$, one can find a $y_0 \in \mathbb{R}^m$ such that $C = \mathcal{A}^*(y_0)$, we have
for an arbitrary $X \in \mathcal{F}_P$: $\text{val}(P) = \langle C, X \rangle = \langle y_0, \mathcal{A}(X) \rangle = \langle b, y_0 \rangle$. But $(y_0, 0) \in \mathcal{F}_D$,
hence $\text{val}(D) \ge \langle b, y_0 \rangle$, which shows the absence of duality gap.
<figure><img src="image_53.png" /><figcaption>Fig. 6.1. Artistic 2D illustration of the proof of proposition 6.6 ($S_+$ is much more complex than in the given representation): the simple case when $C \in \mathcal{N}(A)^\perp$ (left) and the separation technique when $C \notin \mathcal{N}(A)^\perp$ (right)</figcaption></figure>

Consider now the case when $C \notin \mathcal{R}(\mathcal{A}^*) = \mathcal{N}(\mathcal{A})^\perp$ (see figure 6.1, right). Take $\varepsilon > 0$. It suffices to find a $(y_0, S_0) \in \mathcal{F}_D$ such that $\langle b, y_0 \rangle \ge \text{val}(P) - \varepsilon$. The dual variable $S_0$ will be obtained by a separation argument, while $y_0$ will result as a by-product. Consider the two sets

$$C_1 := S_+^n \quad \text{and} \quad C_2 := \{X \in S^n : \mathcal{A}(X) = b, \langle C, X \rangle \le \text{val}(P) - \varepsilon\}.$$

These sets

* are closed and convex (clear),

* are nonempty (for $C_2$, take $H \in \mathcal{N}(\mathcal{A})$ such that $\langle C, H \rangle < 0$ [possible since $C \notin \mathcal{R}(\mathcal{A}^*)$] and observe that $\mathcal{A}(X + tH) = b$ and $\langle C, X + tH \rangle \to -\infty$ when $t \to \infty$),

* are disjoint (by the definition of $\text{val}(P)$) and

* verify $C_1^\infty \cap C_2^\infty = \{0\}$ (indeed, if $D \in C_1^\infty = S_+^n$ and $D \in C_2^\infty = \{D \in S^n : \mathcal{A}(D) = 0, \langle C, D \rangle \le 0\}$, we have $D = 0$ by (6.12a)).

Therefore, $C_1$ and $C_2$ can be strictly separated (point 2 of proposition 1.15): there exists $S_1 \in S^n$ such that

$$\alpha := \sup_{\substack{\mathcal{A}(X)=b \\ \langle C, X \rangle \le \text{val}(P) - \varepsilon}} \langle S_1, X \rangle < \inf_{X \ge 0} \langle S_1, X \rangle =: \beta.$$

Take in the right-hand side $X = 0$ to get $\alpha < 0$ and $X = tvv^T$ with $t \to \infty$ to get $S_1 \ge 0$. Next, observe that the problem in the left-hand side is a linear optimization problem on the vector space $S^n$, whose optimal value is finite. By (1.63), there exist multipliers $(y_1, \sigma_1) \in \mathbb{R}^m \times \mathbb{R}$ such that

$$\mathcal{A}^*(y_1) + S_1 = \sigma_1 C, \quad \sigma_1 \ge 0 \quad \text{and} \quad -\langle b, y_1 \rangle + \sigma_1(\text{val}(P) - \varepsilon) = \alpha < 0.$$

We necessarily have $\sigma_1 > 0$, since otherwise, the last inequality would yield $\langle b, y_1 \rangle > 0$ and, scalarly multiplying the first identity by an $X \in \mathcal{F}_P$ would give $\langle b, y_1 \rangle = -\langle X, S_1 \rangle \le 0$, a contradiction. Now setting $y_0 = y_1/\sigma_1$ and $S_0 := S_1/\sigma_1$, we get $(y_0, S_0) \in \mathcal{F}_D$ verifying $\langle b, y_0 \rangle > \text{val}(P) - \varepsilon$, as desired.

2) The claim can be shown like in the proof of point 1 (exercise 6.1.2).

3) This is a consequence of points 1 and 2. $\square$

The result in point 2 and 3 of proposition 6.6 simplify if $\mathcal{A}$ is surjective, since then they become
$$ \mathcal{F}_P^s \times \mathcal{F}_D \neq \emptyset, \mathcal{A} \text{ surjective} \implies \text{Sol}(D) \text{ is nonempty and compact.} $$

$$ \mathcal{F}^s \neq \emptyset, \mathcal{A} \text{ surjective} \implies \text{Sol}(P) \times \text{Sol}(D) \text{ is nonempty and compact.} $$

If $\mathcal{A}$ is not surjective, either $b \notin \mathcal{R}(\mathcal{A})$, in which case the feasible set $\mathcal{F}_P = \emptyset$ and $\text{val}(P) = +\infty$, or $b \in \mathcal{R}(\mathcal{A})$. In the latter case, when $\mathcal{A}$ has the representation (6.6a), one can remove redundant constraints $\langle A_k, X \rangle = b_k$ and end up with a linear independent set of matrices $A_k$ forming a new surjective operator $\mathcal{A}$. Therefore, numerically, adding an assumption on the surjectivity of $\mathcal{A}$ is not dramatic but, in theory, it is more elegant and it can be useful to avoid it.

We conclude this subsection by giving some examples and counter-examples related to proposition 6.6.

**Examples 6.7** Here are some situations that can occur (the proof of the claims made below are proposed in the exercise 6.1.3).

1) $\mathcal{A}$ is surjective, $(P)$ has a unique solution, $\mathcal{F}_D^s \neq \emptyset$, $\text{val}(D) \in \mathbb{R}$ but $(D)$ has no solution, there is no duality gap.

This situation is compatible with point 1 of proposition 6.6. Here is an example with $n = 2$ and $m = 2$:

$$ C = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad A_1 = \begin{pmatrix} -1 & 0 \\ 0 & 0 \end{pmatrix}, \quad A_2 = \begin{pmatrix} 0 & 0 \\ 0 & -1 \end{pmatrix}, \quad b = \begin{pmatrix} -1 \\ 0 \end{pmatrix}. $$

2) $\mathcal{A}$ is surjective, $\mathcal{F}_P^s \neq \emptyset$, $\text{val}(P) \in \mathbb{R}$ but $(P)$ has no solution, $(D)$ has a unique solution but $\mathcal{F}_D^s = \emptyset$, there is no duality gap.

This situation is compatible with point 2 of proposition 6.6. Here is an example with $n = 2$ and $m = 1$:

$$ C = \begin{pmatrix} 2 & -1 \\ -1 & 0 \end{pmatrix}, \quad A_1 = \begin{pmatrix} 0 & -1 \\ -1 & 2 \end{pmatrix} \quad \text{and} \quad b = 2. \quad \square $$

## Optimality Conditions

**Proposition 6.8 (optimality conditions)** Suppose that $\mathcal{F}_P^s \neq \emptyset$ or $\mathcal{F}_D^s \neq \emptyset$, then

$$ (X, (y, S)) \in \text{Sol}(P) \times \text{Sol}(D) \iff \left\{ \begin{array}{ll} \mathcal{A}^*(y) + S = C, & S \ge 0, \\ \mathcal{A}(X) = b, & X \ge 0, \\ \langle X, S \rangle = 0. \end{array} \right. \quad (6.13) $$

*Proof.* $[\Rightarrow]$ The first two conditions are the dual and primal feasibility, which is satisfied by a primal-dual solution. The third condition is the absence of duality gap, guaranteed by proposition 6.6.

$[\Leftarrow]$ This is point 3 of proposition 6.2.

$\square$
### 6.1.4 Interior Point Algorithms ▲

#### Central Path

There are good reasons to generate iterates well inside $\mathcal{F}_p^s$. This is obtained analytically (not geometrically) by an interior penalization:

$$ 
\begin{array}{l@{\quad}l@{\quad}l}
(P) & \rightleftharpoons & (P_\mu) & \left\{ \begin{array}{l} \inf_X \langle C, X \rangle + \mu \operatorname{ld}(X) \\ \mathcal{A}(X) = b, \end{array} \right. \\[1.5ex]
(D) & \rightleftharpoons & (D_\mu) & \left\{ \begin{array}{l} \sup_{(y,S)} \langle b, y \rangle - \mu \operatorname{ld}(S) \\ \mathcal{A}^*(y) + S = C, \end{array} \right.
\end{array}
$$

where $\operatorname{ld}: S^n \to \mathbb{R}$ is the strictly convex and closed function defined at $X$ by

$$ \operatorname{ld}(X) := \begin{cases} -\log \det(X) & \text{if } X > 0 \\ +\infty & \text{otherwise.} \end{cases} $$

Here are three properties of $\operatorname{ld}$ (with $X > 0$ and $H, K \in S^n$):

$$ 
\begin{align*}
\operatorname{ld}'(X) \cdot H &= -\langle X^{-1}, H \rangle, \\
\operatorname{ld}''(X) \cdot (H, K) &= \langle X^{-1} H X^{-1}, K \rangle, \\
\operatorname{ld}^\infty &= \mathcal{I}_{S_+^n}.
\end{align*}
$$

The central path is the smooth curve $\mathcal{C}: \mu \in \mathbb{R}_{++} \mapsto$ the unique solution to

$$ (O_\mu) \qquad \begin{cases} \mathcal{A}^*(y) + S = C, & S > 0, \\ \mathcal{A}(X) = b, & X > 0, \\ XS = \mu I. \end{cases} \qquad (6.14) $$

**Lemma 6.9 (equivalent definitions of the central path) Suppose that** $\mathcal{F}^s \neq \emptyset$ and $\mu > 0$. Then,

1) $X_\mu \in S_{++}^n$ solves problem $(P_\mu)$ if and only if there is a pair $(y_\mu, S_\mu) \in \mathbb{R}^m \times S_{++}^n$ such that $(O_\mu)$ holds,

2) $(y_\mu, S_\mu) \in \mathbb{R}^m \times S_{++}^n$ solves problem $(D_\mu)$ if and only if there is an $X_\mu \in S_{++}^n$ such that $(O_\mu)$ holds.

*Proof.* We alleviate the notation by dropping the subscript $\mu$ on the variables.

1) By the convexity of the objective of problem $(P_\mu)$ ($\operatorname{ld}$ is a convex function) and the affinity of its constraint (hence it is qualified by (CQ-A)), $X \in S_{++}^n$ solves $(P_\mu)$ if and only if it verifies $\mathcal{A}(X) = b$ and there exists a multiplier $y \in \mathbb{R}^m$ such that the gradient of the Lagrangian of the problem vanishes:

$$ C - \mu X^{-1} - \mathcal{A}^*(y) = 0. $$

Setting $S := \mu X^{-1} > 0$, we get $(O_\mu)$.

2) By the concavity of the objective of problem $(D_\mu)$ and the affinity of its constraint, $(y, S) \in \mathbb{R}^m \times S_{++}^n$ solves $(D_\mu)$ if and only if it verifies $\mathcal{A}^*(y) + S = C$ and
there exists a multiplier $X \in S^n$ such that the gradient of the Lagrangian of the problem vanishes:

$$ -b + \mathcal{A}(X) = 0 \quad \text{and} \quad -\mu S^{-1} + X = 0. $$

Hence $X = \mu S^{-1} > 0$ and we get also $(O_\mu)$.

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

**Proposition 6.10 (existence and smoothness of the central path)** Suppose that $\mathcal{F}^s \neq \emptyset$ and $\mu > 0$. Then,

1) the system $(O_\mu)$ has a solution $(X_\mu, y_\mu, S_\mu)$, unique in $S_{++}^n \times \mathcal{R}(A) \times S_{++}^n$,

2) the map $\mu \in \mathbb{R}_{++} \mapsto (X_\mu, y_\mu, S_\mu) \in S_{++}^n \times \mathcal{R}(A) \times S_{++}^n$ is $C^\infty$.

*Proof.* We alleviate the notation by dropping the subscript $\mu$ on the variables.

1) By lemma 6.9, $(X, y, S)$ solves $(O_\mu)$, if and only if $X$ solves $(P_\mu)$ and $(y, S)$ is a pair of optimal multipliers associated with the constraints of that problem.

Therefore, to prove the existence of a solution to $(O_\mu)$, it suffices to show that $(P_\mu)$ has a solution. Now, problem $(P_\mu)$ also reads

$$ \inf_{X \in S^n} \left( \varphi_\mu(X) := \langle C, X \rangle + \mu \mathrm{Id}(X) + \mathcal{I}_{\mathcal{A}}(X) \right), $$

where $\mathcal{A} := \{X \in S^n : \mathcal{A}(X) = b\}$. The value at $D \in S^n$ of the asymptotic function $\varphi_\mu^\infty$ of $\varphi_\mu$ reads

$$ \varphi_\mu^\infty(D) = \langle C, D \rangle + \mathcal{I}_{S^n}(D) + \mathcal{I}_{\mathcal{N}(A)}(D). $$

Like in the proof of proposition 6.6, $\mathcal{F}_D^s \neq \emptyset$ implies that $\varphi_\mu^\infty(D) > 0$ for $D \neq 0$. By the implication (iv) $\Rightarrow$ (iii) of proposition 1.20, $\varphi_\mu$ has a nonempty and compact set of minimizers.

The uniqueness of the solution $X_\mu$ of $(O_\mu)$ comes from the strict convexity of $\mathrm{Id}$, which ensures the uniqueness in $X_\mu$ of the solution to $(P_\mu)$ and the recalled equivalence between the solutions to $(P_\mu)$ and $(O_\mu)$. The uniqueness of $S_\mu$ comes from the uniqueness of $X_\mu$ and the equation $X_\mu S_\mu = \mu I$, which determines $S_\mu$ from $X_\mu$. The uniqueness of $y_\mu$ in $\mathcal{R}(A)$ comes from the following observations. Since $y$ only intervenes in $(O_\mu)$ through the equation

$$ A^*(y) + S = C, $$

and since any solution $y_\mu$ can be written $y_\mu = y_\mu^0 + y_\mu^1$ with $y_\mu^0 \in \mathcal{N}(A^*)$ and $y_\mu^1 \in \mathcal{N}(A^*)^\perp = \mathcal{R}(A)$, $(X_\mu, y_\mu^1, S_\mu)$ is also a solution to $(O_\mu)$ with its $y$-component in $\mathcal{R}(A)$. Now, if $(X_\mu, y_\mu, S_\mu)$ and $(X_\mu, y_\mu^1, S_\mu)$ are two solutions to $(O_\mu)$ with a $y$-component in $\mathcal{R}(A)$, $h := y_\mu^1 - y_\mu$ satisfies $h \in \mathcal{R}(A)$ and $h \in \mathcal{N}(A^*) = \mathcal{R}(A)^\perp$, hence $h = 0$ and $y_\mu = y_\mu^1$.

2) We have just shown, actually, that, when $\mathcal{F}^s \neq \emptyset$ and $\mu > 0$, $(X_\mu, y_\mu, S_\mu)$ is the unique solution to the system

$$ \begin{cases} A^*(y) + S = C, \\ \mathcal{A}(X) = b, \\ XS = \mu I \end{cases} $$
in the open set $S_{++}^n \times \mathcal{R}(\mathcal{A}) \times S_{++}^n$ of the vector space $S^n \times \mathcal{R}(\mathcal{A}) \times S^n$. Thanks to this system, the smoothness of the map $\mu \in (0, +\infty) \mapsto z_\mu := (X_\mu, y_\mu, S_\mu)$ can be derived from the implicit function theorem. Indeed, $(z_\mu, \mu)$ is a zero of $F(z, \mu)$, where

$$F : (S^n \times \mathcal{R}(\mathcal{A}) \times S^n) \times \mathbb{R} \to S^n \times \mathcal{R}(\mathcal{A}) \times S^n$$

is defined at $(z, \mu) \in (S^n \times \mathcal{R}(\mathcal{A}) \times S^n) \times \mathbb{R}$ by

$$F(z, \mu) = \begin{pmatrix} \mathcal{A}^*(y) + S - C \\ \mathcal{A}(X) - b \\ XS - \mu I \end{pmatrix}.$$

Since $F$ is infinitely continuously differentiable, this smoothness property will be inherited by the implicit function $\mu \mapsto z_\mu$, provide $F'_z(z_\mu, \mu)$ is bijective, or even injective since for fixed $\mu$ the dimension of the range space of $F$ is equal to the one of its definition space. Therefore, we only have to show that

$$\begin{pmatrix} 0 & \mathcal{A}^* & I \\ \mathcal{A} & 0 & 0 \\ S & 0 & X \end{pmatrix} \begin{pmatrix} d_X \\ d_y \\ d_S \end{pmatrix} = 0 \quad \text{and} \quad d_y \in \mathcal{R}(\mathcal{A})$$

implies that $(d_X, d_y, d_S) = 0$. From the last row, we get $d_X = -S^{-1}Xd_S$, which with the second row yields $AS^{-1}Xd_S = 0$. Since $d_S = -\mathcal{A}^*d_y$ by the first row, we get $AS^{-1}\mathcal{A}^*d_y = 0$. Now $S^{-1}X = \mu S^{-2} > 0$, so that $\mathcal{A}^*d_y = 0$ and finally $d_y = 0$ by the fact that $d_y \in \mathcal{R}(\mathcal{A})$. Next $d_S = -\mathcal{A}^*d_y = 0$ and $d_X = -S^{-1}Xd_S = 0$. $\square$

## A Convergent Algorithm With Feasible Iterates

A primal-dual path-following interior-point algorithm generates iterates

$$z_k := (X_k, y_k, S_k) \in \mathcal{F}^s$$

in a neighborhood $V(\theta)$ of the central path $\mathcal{C}$ ($\theta \in (0, 1)$ is a parameter that determines the size of the neighborhood). Each iteration proceeds along a Newton direction aiming a moving point on $\mathcal{C}$, whose central parameter if $\sigma \bar{\mu}(z)$ where $\sigma \in (0, 1)$ and

$$\bar{\mu}(z) := \frac{\langle X, S \rangle}{n}.$$

**Algorithm 6.11 (interior point scheme in SDO)** One iteration, from $z := (X, y, S)$ to the next one $z_+ := (X_+, y_+, S_+)$.

1. **Newton step**: Let $d$ be the Newton direction on a symmetrized version of $(O_{\sigma \bar{\mu}(z)})$.

2. **Displacement**: Determine a large stepsize $\alpha > 0$ such that $z + \alpha d \in V(\theta)$.

3. **New iterate**: $z_+ := z + \alpha d$.
A Practical Algorithm With Infeasible Iterates

6.1.5 A Nonsmooth Algorithm ▲

Notes

This chapter owes a lot to the reviews of Alizadeh [3; 1995], Vandenberghe and Boyd
[135; 1996], Monteiro and Todd [102; 2000], Todd [132; 2001] and to the book of
Nemirovskii and Nesterov [105; 1994]. The monographs of Saigal, Vandenberghe and
Wolkowicz [136; 2000], de Klerk [42; 2002] and Anjos and Lasserre [5; 2012] are rich in
information on the theory, algorithms and applications. Monteiro [101; 2003] reviews
methods for solving SDO problems, including approaches that do not use the notion
of interior points.

The proof of proposition 6.3 is taken from [111; 1976; VI 44]. The presented proof of the absence of duality gap in proposition 6.6 is due to Todd [132; theorem 4.1].

Exercises

6.1.1. Schur complement of a positive semi-definite matrix. Let $A \in S^n$, $C \in S^m$, and $B \in \mathbb{R}^{n \times m}$. Denote by $A^\dagger$ the pseudo-inverse of $A$. Show that

$$
\begin{pmatrix} A & B \\ B^\top & C \end{pmatrix} \ge 0 \iff \left\{ \begin{array}{l} A \ge 0 \\ \mathcal{R}(B) \subseteq \mathcal{R}(A) \\ C - B^\top A^\dagger B \ge 0. \end{array} \right. \qquad (6.15)
$$

6.1.2. Existence of a nonempty compact solution set and no duality gap. Prove point 2 of proposition 6.6 and the absence of duality gap in that case.

6.1.3. SDO examples. Prove the claims made in examples 6.7.

6.2 Circular Optimization ▲

6.3 Copositive Optimization ▲
Appendices
<figure><img src="image_55.png" /></figure>
References

[1] V. Acary, B. Brogliato (2008). *Numerical Methods for Nonsmooth Dynamical Systems - Applications in Mechanics and Electronics*. Lecture Notes in Applied and Computational Mechanics 35. Springer. [doi]. 129

[2] S. Adly, R.T. Rockafellar (2019). Sensitivity analysis of monotone inclusions via the proto-differentiability of the resolvent operator. Technical report. 98

[3] F. Alizadeh (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization. *SIAM Journal on Optimization*, 5, 13–51. 170

[4] L. Ambrosio, P. Tilli (2004). *Topics on Analysis in Metric Spaces*. Oxford Lecture Series in Mathematics and its Applications 25. Oxford University Press, Oxford. 31

[5] M.F. Anjos, J.B. Lasserre (2012). *Handbook on Semidefinite, Conic and Polynomial Optimization*, volume 166 of *International Series in Operations Research & Management Science*. Springer. [doi]. 170

[6] M.F. Anjos, J.B. Lasserre (2012). *Introduction to semidefinite, conic and polynomial optimization*, volume 166 of *International Series in Operations Research & Management Science*, chapter 1. Springer. 160

[7] A. Auslender, M. Teboulle (2003). *Asymptotic Cones and Functions in Optimization and Variational Inequalitites*. Springer Monographs in Mathematics. Springer, New York. 26

[8] M. Avriel (1976). *Nonlinear Programming, Analysis and Methods*. Prentice-Hall, Englewood Cliffs, New Jersey. 90

[9] L. Beaude, K. Brenner, S. Lopez, R. Masson, F. Smai (2019). Non-isothermal compositional liquid gas Darcy flow: formulation, soil-atmosphere boundary condition and application to high-energy geothermal simulations. *Computational Geosciences*, 23(3), 443–470. [doi]. 129

[10] I. Ben Gharbia, J. Dabaghi, V. Martin, M. Vohralík (2020). A posteriori error estimates for a compositional two-phase flow with nonlinear complementarity constraints. *Computational Geosciences*, 24(3), 1031–1055. [doi]. 129

[11] I. Ben Gharbia, E. Flauraud (2019). Study of compositional multiphase flow formulation using complementarity conditions. *Oil & Gas Sciences and Technology*, 74, 1–15. [doi]. 129

[12] I. Ben Gharbia, J. Jaffré (2014). Gas phase appearance and disappearance as a problem with complementarity constraints. *Mathematics and Computers in Simulation*, 99, 28–36. [doi]. 129

[13] A. Ben-Tal (1980). Second-order and related extremality conditions in nonlinear programming. *Journal of Optimization Theory and Applications*, 31(2), 143–165. [doi]. 92

[14] A. Ben-Tal, A. Nemirovski (2001). *Lectures on Modern Convex Optimization – Analysis, Algorithms, and Engineering Applications*. MPS-SIAM Series on Optimization 2. SIAM. 155

[15] A. Ben-Tal, J. Zowe (1982). A unified theory of first and second order conditions for extremum problems in topological vector spaces. *Mathematical Programming Study*, 19, 39–76. [doi]. 92
[16] A. Berman, N. Shaked-Monderer (2003). *Completely Positive Matrices*. World Scientific, River Edge, N.J, USA. 90

[17] D.P. Bertsekas (1982). Projected Newton methods for optimization problems with simple constraints. *SIAM Journal on Control and Optimization*, 20, 221–246. [doi]. 152

[18] G. Blekherman, P.A. Parrilo, R.R. Thomas (2013). *Semidefinite Optimization and Convex Algebraic Geometry*. MOS-SIAM Series on Optimization. SIAM and MPS, Philadelphia. [doi]. 160

[19] J.F. Bonnans (1994). Local analysis of Newton-type methods for variational inequalities and nonlinear programming. *Applied Mathematics and Optimization*, 29, 161–186. [doi]. 102, 112, 133, 152

[20] J.F. Bonnans, J.Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006). *Numerical Optimization – Theoretical and Practical Aspects* (second edition). Universitext. Springer Verlag, Berlin. [authors] [editor] [doi]. 152

[21] J.F. Bonnans, A. Shapiro (2000). *Perturbation Analysis of Optimization Problems*. Springer Verlag, New York. iii

[22] J.M. Borwein, A.S. Lewis (2000). *Convex Analysis and Nonlinear Optimization – Theory and Examples*. CMS Books in Mathematics 3. Springer, New York. 26

[23] J.M. Borwein, Q.J. Zhu (2010). *Techniques of Variational Analysis*. Computational Management Science. Springer Science+Business Media, Inc., Berlin. iii

[24] H. Brézis (1983). *Analyse Fonctionnelle Appliquée*. Masson, Paris. 62, 80

[25] B. Brogliato (2016). *Nonsmooth Mechanics - Models, Dynamics and Control* (third edition). Springer. [doi]. 129

[26] H. Buchholzer, Ch. Kanzow, P. Knabner, S. Kräutle (2011). The semismooth Newton method for the solution of reactive transport problems including mineral precipitation-dissolution reactions. *Computational Optimization and Applications*, 50(2), 193–221. [doi]. 129

[27] Q.M. Bui, H.C. Elman (2020). Semi-smooth Newton methods for nonlinear complementarity formulation of compositional two-phase flow in porous media. *Journal of Computational Physics*, 407, 109163. [doi]. 129

[28] J.V. Burke (1991). An exact penalization viewpoint of constrained optimization. *SIAM Journal on Control and Optimization*, 29, 968–998. 92

[29] C. Carathéodory (1907). Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. *Mathematische Annalen*, 64, 95–115. 12

[30] Jein-Shan Chen (2006). The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem. *Journal of Global Optimization*, 36(4), 565–580. [doi]. 130

[31] S.J. Chung (1989). NP-completeness of the linear complementarity problem. *Journal of Optimization Theory and Applications*, 60, 393–399. [doi]. 129

[32] F.H. Clarke (1983). *Optimization and Nonsmooth Analysis*. John Wiley & Sons, New York. Reprinted in 1990 by SIAM, Classics in Applied Mathematics 5 [doi]. 31, 119, 124

[33] F.H. Clarke (1990). *Optimization and Nonsmooth Analysis* (second edition). Classics in Applied Mathematics 5. SIAM, Philadelphia, PA, USA. [doi]. 31

[34] L. Collatz, W. Wetterling (1975). *Optimization Problems*. Springer-Verlag, New York. 90

[35] R. Cominetti (1990). Metric regularity, tangent sets, and second-order optimality conditions. *Applied Mathematics and Optimization*, 21(1), 265–287. [doi]. 66

[36] R.W. Cottle (1964). *Nonlinear Programs with Positively Bounded Jacobians*. PhD Thesis, University of California, Berkeley, USA. 129
[37] R.W. Cottle (1966). Nonlinear programs with positively bounded jacobians. *SIAM Journal on Applied Mathematics*, 14, 147-158. [doi]. 129

[38] R.W. Cottle (1974). Manifestations of the Schur complement. *Linear Algebra and its Applications*, 8, 189-211. 160

[39] R.W. Cottle (2005). Linear complementarity since 1978. In *Variational analysis and applications*, Nonconvex Optimization and Its Applications 79, pages 239-257. Springer, New York. [doi]. 128

[40] R.W. Cottle, J.-S. Pang, R.E. Stone (2009). *The Linear Complementarity Problem*. Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA. [doi]. 128

[41] J. Dabaghi, V. Martin, M. Vohralík (2017). Adaptive inexact semismooth Newton methods for the contact problem between two membranes. Technical report, INRIA. [hal-01666845]. 129

[42] E. de Klerk (2002). *Aspects of Semidefinite Programming - Interior Point Algorithms and Selected Applications*. Kluwer Academic Publishers, Dordrecht. [doi]. 170

[43] P.J.C. Dickinson, L. Gijben (2011). On the computational complexity of membership problems for the completely positive cone and its dual. Technical report. [Optimization Online]. 90

[44] A.L. Dontchev, R.T. Rockafellar (2009). *Implicit Functions and Solution Mappings – A View from Variational Analysis*. Springer Monographs in Mathematics. Springer. iii, 80

[45] A.L. Dontchev, R.T. Rockafellar (2013). Convergence of inexact Newton methods for generalized equations. *Mathematical Programming*, 139, 115-137. [doi]. 112

[46] A.L. Dontchev, R.T. Rockafellar (2014). *Implicit Functions and Solution Mappings – A View from Variational Analysis* (second edition). Springer Series in Operations Research and Financial Engineering. Springer. 98, 112

[47] B.C. Eaves (1971). On the basic theorem of complementarity. *Mathematical Programming*, 1, 68-75. 115

[48] K. Erleben (2013). Numerical methods for linear complementarity problems in physics-based animation. In *ACM SIGGRAPH 2013 Courses*, SIGGRAPH '13, pages 8:1-8:42. ACM, New York, NY, USA. [doi]. 129

[49] L.C. Evans, R.F. Gariepy (2015). *Measure Theory and Fine Properties of Functions* (revised edition). CRC Press, Boca Raton. 29, 31

[50] F. Facchinei, J.-S. Pang (2003). *Finite-Dimensional Variational Inequalities and Complementarity Problems* (two volumes). Springer Series in Operations Research. Springer. iii, 112, 124, 128, 129

[51] F. Facchinei, J. Soares (1997). A new merit function for nonlinear complementarity problems and a related algorithm. *SIAM Journal on Optimization*, 7(1), 225-247. [doi]. 130

[52] M.C. Ferris, J.-S. Pang (1997). Engineering and economic applications of complementarity problems. *SIAM Review*, 39, 669-713. [doi]. 129

[53] A.V. Fiacco, G.P. McCormick (1968). *Nonlinear Programming: Sequential Unconstrained Minimization Techniques*. John Wiley, New York. Reprinted in 1990 by SIAM in the collection "Classics in Applied Mathematics", number 4, [doi]. 90, 92

[54] A. Fischer (1992). A special Newton-type optimization method. *Optimization*, 24, 269-284. [doi]. 130

[55] R. Fletcher (2010). The sequential quadratic programming method. In G. Di Pillo, F. Schoen (editors), *Numerical Optimization*, Lecture Notes in Mathematics 1989, pages 165-214. Springer. 152

[56] M. Frank, P. Wolfe (1956). An algorithm for quadratic programming. *Naval Research Logistics Quarterly*, 3, 95-110. [doi]. 138, 147

[57] M. Fréchet (1911). Sur la notion de différentielle. *C. R. Acad. Sci. Paris*, 152, 845-847. [Gallica]. 28
[58] Y. Gao, H. Song, X. Wang, K. Zhang (2020). Primal-dual active set method for pricing American better-of option on two assets. *Communications in Nonlinear Science and Numerical Simulation*, 80. [doi]. 129

[59] J. Gauvin (1977). A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming. *Mathematical Programming*, 12, 136–138. 40, 80

[60] J. Gauvin (1992). *Théorie de la programmation mathématique non convexe*. Les Publications CRM, Montréal. 92

[61] J.Ch. Gilbert, J. Nocedal (1992). Global convergence properties of conjugate gradient methods for optimization. *SIAM Journal on Optimization*, 2, 21–42. [doi]. 48

[62] C. Gonzaga (2000). Two facts on the convergence of the Cauchy algorithm. *Journal of Optimization Theory and Applications*, 107, 591–600. [doi]. 49

[63] P.T. Harker, J.-S. Pang (1990). Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. *Mathematical Programming*, 48, 161–220. [doi]. 112, 129

[64] P. Hartman, G. Stampacchia (1966). On some non-linear elliptic differential-functional equations. *Acta Mathematica*, 115, 271–310. [doi]. 112

[65] J.-B. Hiriart-Urruty, C. Lemaréchal (1993). *Convex Analysis and Minimization Algorithms*. Grundlehren der mathematischen Wissenschaften 305-306. Springer. 124

[66] J.-B. Hiriart-Urruty, C. Lemaréchal (1996). *Convex Analysis and Minimization Algorithms* (second edition). Grundlehren der mathematischen Wissenschaften 305-306. Springer. 26

[67] J.-B. Hiriart-Urruty, C. Lemaréchal (2001). *Fundamentals of Convex Analysis*. Springer. 26

[68] J.-B. Hiriart-Urruty, A. Seeger (2010). A variational approach to copositive matrices. *SIAM Review*, 52, 593–629. 90

[69] R.B. Holmes (1973). Smoothness of certain metric projections on Hilbert space. *Transactions of the American Mathematical Society*, 184, 87–100. 20

[70] Kh.D. Ikramov, N.V. Savel'eva (2000). Conditionally definite matrices. *Journal of Mathematical Sciences*, 98, 1–50. 90

[71] A. Ioffe (1989). On some recent developments in the theory of second order optimality conditions. In S. Dolecki (editor), *Optimization*, Lecture Notes in Mathematics 1405, pages 54–68. Springer, Berlin. 53

[72] A.D. Ioffe (1979). Necessary and sufficient conditions for a local minimum. 3: second order conditions and augmented duality. *SIAM Journal on Control and Optimization*, 17, 266–288. [doi]. 92

[73] G. Isac (1992). *Complementarity Problems*. Lecture Notes in Mathematics 1528. Springer, Berlin. [doi]. 128, 129

[74] K. Ito, K. Kunisch (2008). *Lagrange Multiplier Approach to Variational Problems and Applications*. Advances in Design and Control. SIAM Publication, Philadelphia. [doi]. 128

[75] A.F. Izmailov, M.V. Solodov (2010). Inexact Josephy-Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization. *Computational Optimization and Applications*, 46(2), 347–368. [doi]. 112

[76] A.F. Izmailov, M.V. Solodov (2014). *Newton-Type Methods for Optimization and Variational Problems*. Springer Series in Operations Research and Financial Engineering. Springer. [doi]. iii, 112, 128, 129

[77] H. Jiang, L. Qi (1997). A new nonsmooth equations approach to nonlinear complementarity problems. *SIAM Journal on Control and Optimization*, 35, 178–193. [doi]. 131
[78] H. Jiang, D. Ralph (1999). Global and local superlinear convergence analysis of Newton-type methods for semismooth equations with smooth least squares. In M. Fukushima, L. Qi (editors), *Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods*, Applied Optimization 22, pages 181–209. Springer-Science+Business Media, B.V. 127

[79] N.H. Josephy (1979). Newton's method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison, WI, USA. 112

[80] N.H. Josephy (1979). Quasi-Newton's method for generalized equations. Summary Report 1966, Mathematics Research Center, University of Wisconsin, Madison, WI, USA. 112

[81] S. Karamardian (1971). Generalized complementarity problem. *Journal of Optimization Theory and Applications*, 8(3), 161–168. [doi]. 112

[82] W.E. Karush (1939). *Minima of Functions of Several Variables with Inequalities as Side Conditions*. Master's thesis, Department of Mathematics, University of Chicago, Chicago. 39

[83] D. Klatte, B. Kummer (2002). *Nonsmooth Equations in Optimization - Regularity, Calculus, Methods and Applications*, volume 60 of *Nonconvex Optimization and Its Applications*. Kluwer Academic Publishers, Dordrecht. [doi]. iii, 128

[84] M. Kojima, N. Megiddo, T. Noma, A. Yoshise (1991). *A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems*. Lecture Notes in Computer Science 538. Springer, Berlin. [doi]. 129

[85] S. Kräutle (2011). The semismooth Newton method for multicomponent reactive transport with minerals. *Advances in Water Resources*, 34(1), 137–151. [doi]. 129

[86] J. Kruskal (1969). Two convex counterexamples: a discontinuous envelope function and a nondifferentiable nearest-point mapping. *Proceedings of the American Mathematical Society*, 23, 697–703. 20, 126

[87] H.W. Kuhn, A.W. Tucker (1951). Nonlinear programming. In J. Neyman (editor), *Proceedings of the second Berkeley Symposium on Mathematical Studies and Probability*, pages 481–492. University of California Press, Berkeley, California. 39

[88] B. Kummer (1988). Newton's method for nondifferentiable functions. In J. Guddat, B. Bank, H. Hollatz, P. Kall, D. Klatte, B. Kummer, K. Lommatzsch, L. Tammer, M. Vlach, K. Zimmerman (editors), *Advances in Mathematical Optimization*, pages 114–125. Akademie-Verlag, Berlin. 116

[89] J. Kyparisis (1985). On uniqueness of Kuhn-Tucker multipliers in nonlinear programming. *Mathematical Programming*, 32, 242–246. [doi]. 40

[90] J.B. Lasserre (2001). Global optimization with polynomials and the problem of moments. *SIAM Journal on Optimization*, 11, 796–817. [doi]. 160

[91] J.B. Lasserre (2010). *Moments Positive Polynomials and Their Applications*. Imperial College Press Optimization Series 1. Imperial College Press. 160

[92] J.B. Lasserre (2015). *An Introduction to Polynomial and Semi-Algebraic Optimization*. Cambridge Texts in Applied Mathematics. Cambridge University Press. 160

[93] X. Li, D. Sun, K.-C. Toh (2018). A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. *SIAM Journal on Optimization*, 28(1). [doi]. 126

[94] J.L. Lions, G. Stampacchia (1967). Variational inequalities. *Communication on Pure and Applied Mathematics*, 20, 493–519. [doi]. 112

[95] D.G. Luenberger (1973). *Introduction to Linear and Nonlinear Programming*. Addison-Wesley, Reading, USA. 90

[96] O. Mancino, G. Stampacchia (1972). Convex programming and variational inequalities. *Journal of Optimization Theory and Applications*, 9, 3–23. 112
[97] O.L. Mangasarian, S. Fromovitz (1967). The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. *Journal of Mathematical Analysis and Applications*, 17, 37–47. [doi]. 38

[98] E. Marchand, T. Müller, P. Knabner (2012). Fully coupled generalised hybrid-mixed finite element approximation of two-phase two-component flow in porous media. Part II: numerical scheme and numerical results. *Computational Geosciences*, 16(3), 691–708. [doi]. 129

[99] E. Marchand, T. Müller, P. Knabner (2013). Fully coupled generalised hybrid-mixed finite element approximation of two-phase two-component flow in porous media. Part I: formulation and properties of the mathematical model. *Computational Geosciences*, 17(2), 431–442. [doi]. 129

[100] R. Mifflin (1977). Semismooth and semiconvex functions in constrained optimization. *SIAM Journal on Control and Optimization*, 15, 959–972. [doi]. 124, 128

[101] R.D.C. Monteiro (2003). First- and second-order methods for semidefinite programming. *Mathematical Programming*, 97, 209–244. [doi]. 170

[102] R.D.C. Monteiro, M. Todd (2000). Path-following methods. In H. Wolkowicz, R. Saigal, L. Vandenberghe (editors), *Handbook of Semidefinite Programming – Theory, Algorithms, and Applications*, volume 27 of *International Series in Operations Research & Management Science*, chapter 10, pages 267–306. Kluwer Academic Publishers. 170

[103] K.G. Murty (1988). *Linear Complementarity, Linear and Nonlinear Programming* (Internet edition, prepared by Feng-Tien Yu, 1997). Heldermann Verlag, Berlin. 128

[104] K.G. Murty, S.N. Kabadi (1987). Some NP-complete problems in quadratic and non-linear programming. *Mathematical Programming*, 39, 117–129. 90

[105] Y.E. Nesterov, A.S. Nemirovskii (1994). *Interior-Point Polynomial Algorithms in Convex Programming*. SIAM Studies in Applied Mathematics 13. SIAM, Philadelphia, PA, USA. 170

[106] J.M. Ortega, W.C. Rheinboldt (1970). *Iterative Solution of Nonlinear Equations in Several Variables*. Academic Press, New York. Reprinted in 2000 by SIAM, Classics in Applied Mathematics 30, [doi]. 45

[107] J.-S. Pang (1995). Complementarity problems. In R. Horst, P.M. Pardalos (editors), *Handbook of Global Optimization*, volume 2 of *Nonconvex Optimization and Its Applications*, pages 271–338. Kluwer, Dordrecht. [doi]. 128, 129

[108] P.A. Parrilo (2000). On a decomposition for multivariable forms via LMI methods. In *Proceedings of the American Control Conference*. 160

[109] J.-P. Penot (1982). On regularity conditions in mathematical programming. *Mathematical Programming Study*, 19, 167–1999. 80

[110] J.-P. Penot (1994). Optimality conditions in mathematical programming and composite optimization. *Mathematical Programming*, 67, 225–245. [doi]. 53

[111] G. Pólya, G. Szegő (1976). *Problems and Theorems in Analysis II*. Springer-Verlag, Berlin. 170

[112] L. Qi (1993). Convergence analysis of some algorithms for solving nonsmooth equations. *Mathematics of Operations Research*, 18, 227–244. [doi]. 128

[113] L. Qi, J. Sun (1993). A nonsmooth version of Newton's method. *Mathematical Programming*, 58, 353–367. [doi]. 128

[114] L. Qi, X. Xiao, L. Zhang (2016). A parameter-self-adjusting Levenberg-Marquardt method for solving nonsmooth equations. *Journal of Computational Mathematics*, 34(3), 317–338. [doi]. 127

[115] H. Rademacher (1919). Über partielle und totale differenzierbarkeit. *I. Math. Ann.*, 89, 340–359. 31

[116] J. Renegar (2001). *A Mathematical View of Interior-Point Methods in Convex Optimization*. MPS-SIAM Series on Optimization 3. SIAM. 155
[117] S.M. Robinson (1974). Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear-programming algorithms. *Mathematical Programming*, 7, 1–16. 152

[118] S.M. Robinson (1975). Stability theory for systems of inequalities, part I: linear systems. *SIAM Journal on Numerical Analysis*, 12, 754–769. [doi]. 155

[119] S.M. Robinson (1976). Stability theory for systems of inequalities, part II: differentiable nonlinear systems. *SIAM Journal on Numerical Analysis*, 13, 497–513. [doi]. 57

[120] S.M. Robinson (1980). Strongly regular generalized equations. *Mathematics of Operations Research*, 5, 43–62. [doi]. 98, 112

[121] S.M. Robinson (1982). Generalized equations and their solutions, Part II: Applications to nonlinear programming. *Mathematical Programming Study*, 19, 200–221. 92, 96

[122] S.M. Robinson (1987). Local structure of feasible sets in nonlinear programming, part III: stability and sensitivity. *Mathematical Programming Study*, 30, 45–66. [doi]. 118

[123] S.M. Robinson (1992). Normal maps induced by linear transformations. *Mathematics of Operations Research*, 17, 691–714. 113

[124] S.M. Robinson (2003). Variational conditions with smooth constraints: structure and analysis. *Mathematical Programming*, 97(1-2), 245–265. [doi]. 99

[125] R.T. Rockafellar (1970). *Convex Analysis*. Princeton Mathematics Ser. 28. Princeton University Press, Princeton, New Jersey. 12, 26, 155

[126] R.T. Rockafellar, R. Wets (1998). *Variational Analysis*. Grundlehren der mathematischen Wissenschaften 317. Springer. iii, 99

[127] A. Shapiro (1990). On concepts of directional differentiability. *Journal of Optimization Theory and Applications*, 66, 477–487. [doi]. 143

[128] A. Shapiro (1994). Directionally nondifferentiable metric projection. *Journal of Optimization Theory and Applications*, 1, 203–204. 20, 126

[129] A. Shapiro (1997). On uniqueness of Lagrange multipliers in optimization problems subject to cone constraints. *SIAM Journal on Optimization*, 7, 508–518. 27, 74, 82

[130] M. Slater (1950). Lagrange multipliers revisited: a contribution to non-linear programming. Cowles Commission Discussion Paper, Math. 403. 38

[131] G. Stampacchia (1969). Variational inequalities. In *Theory and Applications of Monotone Operators* (Proc. NATO Advanced Study Inst., Venice, 1968), pages 101–192. Edizioni Oderisi, Gubbio. 112

[132] M.J. Todd (2001). Semidefinite optimization. In *Acta Numerica 2001*, pages 515–560. Cambridge University Press. [doi]. 170

[133] P. Tseng (1996). Global behaviour of a class of merit functions for the nonlinear complementarity problem. *Journal of Optimization Theory and Applications*, 89, 17–37. 131

[134] K. Ueda, N. Yamashita (2012). Global complexity bound analysis of the Levenberg-Marquardt method for nonsmooth equations and its application to the nonlinear complementarity problem. *Journal of Optimization Theory and Applications*, 152, 450–467. [doi]. 127

[135] L. Vandenberghe, S. Boyd (1996). Semidefinite programming. *SIAM Review*, 38, 49–95. [doi]. 170

[136] H. Wolkowicz, R. Saigal, L. Vandenberghe (editors) (2000). *Handbook of Semidefinite Programming – Theory, Algorithms, and Applications*, volume 27 of *International Series in Operations Research & Management Science*. Kluwer Academic Publishers. 170

[137] E.H. Zarantonello (1971). Projections on convex sets in Hilbert space and spectral theory. I: Projections on convex sets. In *Contributions to Nonlinear Functional Analysis*, pages 237–341. Academic Press, New York. Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1971. 20

[138] G. Zoutendijk (1970). Nonlinear programming, computational methods. In J. Abadie (editor), *Integer and Nonlinear Programming*, pages 37–86. North-Holland, Amsterdam. 48
<figure><img src="image_56.png" /></figure>
Index

affine hull, 11

- of a convex polyhedron, 26

algorithm

- gradient, 48

- JN (Joseph-Newton), 102, 108

- semismooth Newton, 126

- SQP, 137, 150

- SQP for (P<sub>G</sub>), 154

- steepest descent, 48

B-differential

- definition, 118

Banach

- perturbation lemma, 120

bidual cone, 15

- expression, 17

binary relation, 30

C-differential

- definition, 118

- regular, 120

C-function, 131

- definition, 114

- Fischer, 115

- min, 115

C-regular point, 120

circular cone, 16

closed function, 28

closure, 10

complementarity condition, 39

- strict, see strict complementarity

complementarity problem, 128

- linear, 128

- mixed, 129

cone, 12

- asymptotic, 20, 23, 26

- bidual, see bidual cone

- circular, see circular cone

- critical, see critical cone

- dual, see dual cone

- feasible directions, 17

- linearizing, 38, 53

- normal, see normal cone

- tangent, see tangent cone

conification, 155

constraint

- active, 37

constraint qualification

- affinity (CQ-A), 38, 90

- for representing X<sub>E</sub>, 35

- for representing X<sub>EI</sub>, 38

- for representing X<sub>G</sub>, 54

- linear independence (CQ-LI), 38, 90

- Mangasarian-Fromovitz (CQ-MF), 38,
57, 80, 87, 88

- Robinson (CQ-R), 57

- Slater (CQ-S), 38

convergence to zero, equivalently, 45

convex optimization problem

- (P<sub>comp</sub>), 78

- (P<sub>E</sub>), 35

- (P<sub>EI</sub>), 37

- (P<sub>G</sub>), 52

convex polyhedron, 13

- addition, 13

- affine hull, 26

- dual form, 13

- linear transformation: 13

- normal cone, 19

- relative interior, 26

- tangent cone, 19

- upper semi-continuity of the set of ac-
tive inequalities, 13

convex set, 10

critical cone

- for (P<sub>EI</sub>), 84

degree of a monomial, 160

derivative, 28

differentiability
- directional, see directional differentiability

- Fréchet, 28

differential quotient, 24

direction

- critical, 84

- feasible, 18

directional differentiability, 22

- composition, 143

- in the sense of Hadamard, 143

distance to a set, 10

dual cone, 15

- inclusion, 17

- negative, 15

- of a Cartesian product, 17

- of a convex hull, 17

- of a sum, 17

- of a union, 17

- of an intersection of cones, 17

- self-dual, 15

duality gap, 42

epigraph of a function, 21

error bound

- and semi-stability, 103

- definition, 58

- Robinson for $X_G$, 58

feasible direction, see direction

feasible point, 32

feasible set, 32

- $X_E$ of ($P_E$), 35

- $X_{EI}$ of ($P_{EI}$), 37

- $X_G$ of ($P_G$), 52

Finsler lemma, 158

Fréchet, 28

function

- closed, 21

- convex, 21

- domain, 21

- epigraph, 21

- Lipschitz (continuous), 143

- piecewise affine, 124

- piecewise semismooth, 124

- proper, 21

- r-steep, 66

- semismooth, 122

- strongly semismooth, 122

- subcontinuous, 66

- subdifferentiable, 25

functional inclusion, 98

- hemi-stable solution, 111

- semi-stable solution, 103

- strongly regular solution, 108

global convergence

- of the SQP algorithm with line-search, 150

gradient, 10

homogenization, 155

hull

- affine, see affine hull

- closed convex, 12

- conical, 12

- convex, 12

- vector, see vector hull

index set

- active constraint, 37

- inactive constraint, 37

indicator function, 21

interior, 10

interval, 9

isolated solution

- of a functional inclusion, 103

- of the optimization problem ($P_G$), 92

Kronecker symbol, 156

Lagrangian

- equality and inequality constrained optimization problem, 39

- equality constrained optimization problem, 35

- general optimization problem, 56

- semidefinite optimization problem, 159

Lagrangian dual

- linear optimization, 43

lemma

- Banach perturbation, 120

linear map

- adjoint, 10

- of a relative interior, 14

linear preimage

- of a relative interior, 15

linearization

- JN (Josephy-Newton), 102

lower semi-continuous function, 27

Lyusternik, 67

machine-epsilon, 149

matrix

- copositive, 90
minimizing sequence, 32

Minkowski sum, 9

monomial, 160

- degree, 160

multifunction

- closed, 31

- convex, 30

- definition, 29

- domain, 30

- graph, 30

- image, 30

- inverse, 30

- metric regular, 61

- multiplier, 95

- open, 61

- range, 30

- stationary point, 96

- upper semi-continuous at a point, 31

multiplier set

- boundedness for ($P_{EI}$), 40

- boundedness for ($P_G$), 74

- boundedness for ($P_{Q,G}$), 77

- uniqueness for ($P_{EI}$), 40

$\mathcal{N}(x)$, family of neighborhoods of $x$, 28

Necessary optimality condition

- first order

- for ($P_E$) (Lagrange), 35

- for ($P_{EI}$) (Karush-Kuhn-Tucker), 39

- for ($P_X$) (Peano-Kantorivich), 34

- for unconstrained optimization (Fermat), 33

neighborhood, 10

norm

- dual, 144

normal

- map, 113

normal cone

- intersection, 18

- map, 99

- product, 18

- to a convex set, 18

- to a nonconvex set, 33

- to $S_+^n$, 158

normal-cone-intersection, 18

normal-cone-product, 18

optimal multiplier

- for ($P_E$), uniqueness, 36

- for ($P_{EI}$), bounded, 40

- for ($P_{EI}$), uniqueness, 40

optimality conditions for ($P_{comp}$)

- necessary of the first order (SC1), 79

- sufficient of the first order (SC1), 79

optimality conditions for ($P_{EI}$)

- necessary

- of the second order (NC2), 88, 90

- of the second order (NC2), semi-strong, 85, 90

- of the second order (NC2), strong, 85, 90

- of the second order (NC2), weak, 86, 90

- sufficient

- of the second order (SC2), 91

- of the second order (SC2), semi-strong, 92

- of the second order (SC2), strong, 92

- of the second order (SC2), weak, 92

optimality conditions for ($P_G$)

- necessary of the first order (NC1), 55

- sufficient of the first order (SC1), 56

optimality conditions for ($P_{Q,G}$)

- necessary of the first order (SC1), 77

- sufficient of the first order (SC1), 77

optimization problem

- bounded, 32

- conic, 155

- convex, see convex optimization problem

- equality and inequality constrained, 37

- equality constrained, 34

- linear, 43

- nonlinear, 37

- ($P_E$), 35

- ($P_{EI}$), 37, 52, 133

- ($P_{E[l,u]}$), 52

- ($P_G$), 51

- ($P_L$), 43

- ($P_{Q,G}$), 76

- semidefinite, 52

- unbounded, 32

pairing function, 41

- in linear optimization, 44

polynomial

- SOS, 161

power set, 29

problem

- complementarity ($P_{CP}$), 100

- reformulation as nonsmooth equation, 114

- functional inclusion ($P_{EI}$), 98

- optimization, see optimization problem
- variational inequality

- reformulation as nonsmooth equation, 115

- variational inequality ($P_{vi}$), 113

- variational inequality ($P_{vi}$), 99

- variational ($P_v$), 99

projection

- contraction, 20

- monotonicity, 20

projector, 19

- Cartesian, 30

quadratic convergence

- definition, 45

- of Newton's method for equations, 46

- of the JN algorithm, 109–111

- of the semismooth Newton algorithm, 126

quadratic growth property, 91, 92

reformulation

- normal map, 113

relative interior, 13

- of a convex polyhedron, 26

saddle-point, 42

Schur complement, 160

segment, 10

semi-continuity

- upper, see upper semi-continuity

set-valued function/map/mapping, see multifunction

simplex

- unit - of $\mathbb{R}^n$, 11

small $o$, 29

$S_+^n$, 11

$S_{++}^n$, 11

solution

- hemi-stable of ($P_{EI}$), 138

- improper, 43

- semi-stable of ($P_{EI}$), 138

speed of convergence

- linear, 45

- quadratic, see quadratic convergence

- superlinear, see superlinear convergence

stability

- of a set with respect to small perturbations, 59

stationary point

- for ($P_E$), 35

- for ($P_{EI}$), 39

- for ($P_G$), 56

strict complementarity, 40

- for an $S_+^n$-valued constraint, 82

strong duality

- in linear optimization, 44

subdifferentiability, 25

subdifferential, 25

subgradient, 25

superlinear convergence

- and equivalent sequences, 45

- definition, 45

- Dennis and Moré criterion, 47

- of Newton's method for equations, 46

- of the JN algorithm, 109–111

- of the semismooth Newton algorithm, 126

tangent cone

- to a convex set, 18

- to a nonconvex set, 33

- to $S_+^n$, 158

theorem

- mean value, 29

- open mapping, 80

trace of a matrix, 156

upper semi-continuity

- of a multifunction, 31

- of the C-differential, 119

- of the set of active inequalities, 13

- of the subdifferential of a convex function, 31

vector hull, 11

weak duality inequality, 42

- in linear optimization, 44

zero of a function, 46

Zoutendijk condition, 48