kkt conditions

Let $x \in \mcD$. By convexity of $f$, we have $$ f(x) - f(x^*) \geq \nabla f(x^*)^T (x - x^*). $$

Using the definition of the Lagrangian and the stationarity condition, we obtain $$ \nabla f(x^*) + \sum_{i=1}^n \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^m \mu_j^* \nabla g_j(x^*) = 0, $$ which implies \begin{equation} \label{eq:grad} f(x) - f(x^*) \geq \nabla f(x^*)^T (x - x^*) = - \sum_{i=1}^n \lambda_i^* \nabla h_i(x^*)^T (x - x^*) - \sum_{j=1}^m \mu_j^* \nabla g_j(x^*)^T (x - x^*). \end{equation}

Inequality constraints: $h_i$: by convexity, for any $x \in \mcD$, $$ - \nabla h_i(x^*)^T (x - x^*) \ge h_i(x^*) - h_i(x) \ge h_i(x^*), $$ hence $$ - \sum_{i=1}^n \lambda_i^* \nabla h_i(x^*)^T (x - x^*) \ge \sum_{i=1}^n \lambda_i^* h_i(x^*) = 0. $$

Equality constraints: $g_j$: since $g_j$ is affine and $x \in \mcD$, we have $g_j(x) = g_j(x^*) = 0$, hence $$ \nabla g_j(x^*)^T (x - x^*) = g_j(x) - g_j(x^*)= 0. $$

Combining these relations in \eqref{eq:grad}, we obtain that for any $x \in \mcD$, $$ f(x) - f(x^*) \ge \nabla f(x^*)^T (x - x^*) \ge 0, $$ which proves that $f(x^*) = \inf_{x \in \mcD} f(x)= \mcl(x^*, \lambda^*, \mu^*)$. Since $x \mapsto \mcl(x,\lambda^*,\mu^*)$ is convex, the KKT conditions show that $$ \mcl(x^*, \lambda^*, \mu^*) = \inf_{x\in \Xset} \mcl(x, \lambda^*, \mu^*) \leq \sup_{\lambda \geq 0,\mu} \inf_{x\in \Xset} \mcl(x, \lambda, \mu) $$ which is the converse inequality in \eqref{eq:weak} and the strong duality holds.

By the saddle point property, $$ \sup_{\lambda \geq 0, \mu} \mcl(x^*, \lambda, \mu) \leq \inf_{x \in \Xset} \mcl(x, \lambda^*, \mu^*). $$ Hence, $$ \inf_{x \in \Xset} \sup_{\lambda \geq 0, \mu} \mcl(x, \lambda, \mu) \leq \sup_{\lambda \geq 0, \mu} \mcl(x^*, \lambda, \mu) \leq \inf_{x \in \Xset} \mcl(x, \lambda^*, \mu^*) \leq \sup_{\lambda \geq 0, \mu} \inf_{x \in \Xset} \mcl(x, \lambda, \mu). $$

This chain of inequalities implies strong duality (see \eqref{eq:weak} for the reverse inequality).

Moreover, the upper bound in the saddle point property, which holds for all $\lambda \geq 0, \mu$, implies that $\sup_{\lambda \geq 0, \mu} \mcl(x^*, \lambda, \mu) <\infty$ and hence $h_i(x^*) \leq 0$ and $g_j(x^*) = 0$.

Finally, choosing $\lambda = 0$ and $\mu = 0$, we obtain $$ f(x^*) = \mcl(x^*, 0, 0) \le \sup_{\lambda \geq 0, \mu} \mcl(x^*, \lambda, \mu) = \inf_{x \in \Xset} \mcl(x, \lambda^*, \mu^*) \le \mcl(x, \lambda^*, \mu^*) \le f(x), \quad \forall x \in \mcD, $$ which shows that $x^*$ minimizes $f$ over $\mcD$ and that $\lambda_i^* h_i(x^*) = 0$ for all $i$ where the last identity follows from the above inequality with $x=x^*$.

Recall that $$ g_j(x) = a_j^T x - b_j, \quad j=1,\dots,m. $$ Without loss of generality, we assume that $(a_j)_{1\leq j \leq m}$ are linearly independent. We define the set $U$ as $$ U = \{ u = (u_0, u_1, \dots, u_n, u_{n+1}, \dots, u_{n+m}) \in \rset^{n+m+1}: \exists x \in \Xset, f(x) < u_0, h_i(x) \le u_i, g_j(x) = u_{n+j} \}. $$

First note that the condition $\{x \in \mcD : f(x) < 0\} = \emptyset$ is equivalent to $0 \notin U$. Since $U$ is convex, a separation argument shows that $0 \notin U$ if and only if there exists a nonzero vector $\phi \in \mathbb{R}^{n+m+1}$ such that $$ \phi^T u \ge 0, \quad \forall u \in U. $$

Take an arbitrary $i \in [0:n]$. If $u\in U$ then $u+t e_i \in U$ where $t>0$ and $e_i=(\indiacc{k=i})_{k \in [0:n+m]} \in \rset^{n+m+1}$. The previous inequality implies $\phi^T (u+t e_i)=\phi^T u + t\phi_i \geq 0$ for all $t>0$, therefore $\phi_i\geq 0$ for any $i \in [0:n]$. Now, since $\phi^T u\geq 0$ for all $u \in U$, a simple limiting argument yields for all $x\in \Xset$, $$ \phi_0 f(x)+\sum_{i=1}^n \phi_i h_i(x) +\sum_{j=n+1}^{n+m} \phi_j g_j(x)\geq 0 $$ To conclude, and since we already know that $\phi_i\geq 0$ for all $i \in [0:n]$, it only remains to prove that $\phi_0 \neq 0$ and to set in that case $\lambda^*_i=\frac{\phi_i}{\phi_0}$ for $i\in \lrcb{1,\ldots,n}$ and $\mu_j^*=\frac{\phi_{n+j}}{\phi_0}$ for $j \in \lrcb{1,\ldots,m}$. The rest of the argument is by contradiction. If $\phi_0=0$, then the previous inequality on a Slater point $x=\tilde x \in \mcD $ yields $\sum_{i=1}^n \phi_i h_i(\tilde x) \geq 0$ but since $h_i(\tilde x)<0$ for all $i \in [1:n]$, we finally get $\phi_i=0$ for all $i \in [1:n]$. Then the previous inequality becomes for any $x\in \Xset$, $$ \sum_{j=n+1}^{n+m} \phi_j g_j(x)= \lr{\sum_{j=n+1}^{n+m} \phi_j a_j}^T x + \sum_{j=n+1}^{n+m} \phi_j b_j\geq 0 $$ which in turn implies that $\sum_{j=n+1}^{n+m} \phi_j a_j=0$ and since $(a_j)_{n+1\leq j \leq n+m}$ are linearly independent, we deduce that $\phi_j=0$ for any $j\in [n+1:n+m]$. Finally all the components of $\phi$ are null and we are face to a contradiction. The proof is completed.

Assume that $f(x^*)=\inf_{x\in \mcD} f(x)$ for some $x^* \in \mcD$. Then $\{f-f(x^*)<0\} \cap \mcD = \emptyset$. By the Farkas lemma, there exist $\lambda^* \geq 0$ and $\mu^* \in \mathbb{R}^m$ such that for all $x\in \Xset$, $$ f(x)-f(x^*)+\sum_{i=1}^n \lambda^*_i h_i(x) + \sum_{j=1}^m \mu_j^* g_j(x)\geq 0. $$

This implies that $(x^*,\lambda^*,\mu^*)$ is a saddle point. Indeed, for all $\lambda \geq 0$, $\mu \in \rset^m$ and $x \in \Xset$, $$ f(x^*)+\sum_{i=1}^n \lambda_i h_i(x^*) + \sum_{j=1}^m \mu_j g_j(x^*)\leq f(x^*) \leq f(x)+\sum_{i=1}^n \lambda^*_i h_i(x) + \sum_{j=1}^m \mu_j^* g_j(x) $$

Therefore, $(x^*,\lambda^*,\mu^*)$ is a saddle point, which implies strong duality (as shown previously). This concludes the proof.

In order to prove the proposition, we will show that $$ \mathrm{argmin}\left\{ \sum_{i,j=1}^n p_{ij} |X_i- Y_j|^p \,: \forall i,j,\ p_{ij} \geq 0, \forall i, \sum_{j} p_{ij}=\frac{1}{N} , \forall j, \sum_{i} p_{ij}=\frac{1}{N} \right\}= \left[ \frac{1}{N} \mathsf{1}(i=j) \right]_{1\leq i,j \leq n}. $$

The function $p \mapsto \sum_{i,j} p_{ij}|X_i-Y_j|^p$ is linear, hence convex. Moreover, the constraints are affine: for all $i\in [1:n]$, $\sum_{j=1}^n p_{ij}=\frac{1}{N}$ and for all $j\in [1:n]$, $\sum_{i=1}^n p_{ij}=\frac{1}{N}$, together with inequality constraints $\forall i,j \in [1:n],\ -p_{ij} \leq 0$.

Therefore, we can apply the KKT theorem. We seek $p\in \rset^{n\times n}$, $\alpha,\beta \in \rset^n$, and $\gamma \in \rset^{n \times n}$ such that, defining $$ \mathcal{L}(p,\alpha,\beta,\gamma)=\sum_{i,j=1}^n p_{ij}|X_i-Y_j|^p - \gamma_{ij} p_{ij}+\sum_{i=1}^n \alpha_i \lr{\sum_{j=1}^n p_{ij}- \frac 1 N} +\sum_{j=1}^n \beta_j \lr{\sum_{i=1}^n p_{ij}- \frac 1 N}, $$ we have $\nabla_p \mathcal{L}(p,\alpha,\beta,\gamma)=0$, together with the conditions $\gamma_{ij} p_{ij}=0$ for all $i,j \in [1:n]$ and $\sum_{j=1}^np_{ij}=\sum_{i=1}^n p_{ij}=1/N$.

We already know that $p_{ij}=\frac 1 N \indi{i=j}$ is a solution. It therefore remains to find $\alpha,\beta,\gamma$ such that the KKT conditions are satisfied for this choice of $p$. These conditions can be written as:

• for all $i,j \in [1:n]$, $\partial_{p_{ij}} \mathcal{L}(p,\alpha,\beta,\gamma)=|X_i-Y_j|^p - \gamma_{ij} +\alpha_i +\beta_j=0$,
• for all $i,j \in [1:n]$, $\gamma_{ij} \geq 0$ and $\gamma_{ij} p_{ij}=0$.

The complementarity condition reduces to $\gamma_{ii}=0$, since $p_{ij}=\frac 1 N \indi{i=j}$. Hence, the KKT conditions are equivalent to: for all $i,j \in [1:n]$, $\gamma_{ij}=\alpha_i+\beta_j + |X_i-Y_j|^p \geq 0$ and $\gamma_{ii}=\alpha_i+\beta_i + |X_i-Y_i|^p=0$.

This is in turn equivalent to the existence of $\beta \in \rset^n$ such that

• $\forall i,j \in [1:n], \ \beta_j - \beta_i \geq |X_i-Y_i|^p-|X_i-Y_j|^p$.

Set $\beta_1=0$ and, for all $i\in [1:n-1]$, define $\beta_j=\sum_{\ell=1}^{j-1} \lrcb{|X_\ell-Y_\ell|^p - |X_\ell - Y_{\ell+1}|^p}$. Then, $$ \beta_j - \beta_i=\sum_{\ell=i}^{j-1} \lrcb{|X_\ell-Y_\ell|^p - |X_\ell - Y_{\ell+1}|^p}. $$

Since $u \mapsto |u|^p$ is convex, we have $|a+c|^p-|a|^p \geq |b+c|^p-|b|^p$ for all $a \geq b$ and $c\geq 0$. We set $a=X_\ell -Y_{\ell+1}$, $b=X_i-Y_{\ell+1}$, and $c=Y_{\ell+1}-Y_\ell$. For $\ell \geq i$, we have $a \geq b$ and $c\geq 0$. Hence, for any $\ell \geq i$, the inequality can be rewritten as $$ |X_\ell-Y_\ell|^p - |X_\ell - Y_{\ell+1}|^p \geq |X_i-Y_\ell|^p - |X_i - Y_{\ell+1}|^p. $$

Finally, plugging into the previous identity yields $$ \beta_j-\beta_i \geq \sum_{\ell=i}^{j-1} |X_i-Y_\ell|^p - |X_i - Y_{\ell+1}|^p = |X_i-Y_i|^p - |X_i - Y_j|^p. $$

This proves the KKT conditions, and the proof is complete.