Lagrangian saddle-point set is compact?

81 Views Asked by At

Let $f: \mathbb R^n \to \mathbb R$ be a convex, continuously differentiable function. Let $\mathcal X \subset \mathbb R^n$ denote the set of solutions to the problem $$ \min_{x \in \mathbb R^n} f(x) \quad \text{s.t.} \quad g(x) = 0, $$ where $g: \mathbb R^n \rightarrow \mathbb R^p$ is a linear map with $p \leq n$. Assume that $\mathcal X$ is non-empty and compact.

Define $L: \mathbb R^n \times \mathbb R^p \rightarrow \mathbb R$ to be $L(x, \lambda) = f(x) + \lambda^T g(x)$, and denote the set of min-max saddle points of $L$ by $$\mathcal S_L = \{(x^*, \lambda^*) \in \mathbb R^n \times \mathbb R^p: \; L(x^*, \lambda) \leq L(x^*, \lambda^*) \leq L(x, \lambda^*) \; \forall (x, \lambda) \in \mathbb R^n \times \mathbb R^p\}.$$ Under what condition(s) is $\mathcal S_{L}$ compact?

2

There are 2 best solutions below

3
On BEST ANSWER

Note that since $g$ is linear, $g(x) = Ax$ for some $A$, and $Dg(x) = A$.

Note that $x \mapsto L(x, \lambda)$ is convex, hence $x'$ is a minimiser of $x \mapsto L(x, \lambda)$ iff $Df(x')+\lambda^T A = 0$.

Note that if $n^T A = 0$ then $L(x,\lambda) = L(x,\lambda+tn)$ for all $t$.

Suppose $(x^*,\lambda^*) \in S_L$, then since $L(x^*,\lambda) \le L(x^*,\lambda^*)$ for all $\lambda$ we must have $g(x^*) = 0$.

Since $f(x^*)=L(x^*,\lambda^*) \le L(x,\lambda^*)$ for all $x$, we see that if $g(x) = 0$ then $f(x^*) \le L(x,\lambda^*) = f(x)$ and so $x^* \in {\cal X}$.

We also see that $x^*$ is a minimiser of $x \mapsto L(x,\lambda^*)$ and so $Df(x^*)+ {\lambda^*}^T A = 0$.

If $\ker A^T = \{0\}$ then we see that $\lambda^* = -(AA^T)^{-1}A Df(x^*)^T$, in particular, since $x \mapsto (x, -(AA^T)^{-1}ADf(x)^T)$ is continuous, we see that $S_L$ is compact since ${\cal X}$ is.

If $A^Tn = 0$ for some $n \neq 0$, we see that $(x^*,\lambda^*+tn) \in S_L$ for all $t$, hence $S_L$ is unbounded.

1
On

If you write $g(x) = A \, x + b $, the matrix $A$ should have full rank. This condition is necessary and sufficient.