By adding a bilinear constraint in the form $x^T A y=0$, is this problem still convex-concave?

Question

I have a function $f(x,y)$ which is convex with respect to $x$ and concave to $y$. The problem \begin{align} \min_x \max_y f(x,y)\\ \text{s.t.} x \in \mathcal{C} \end{align} is then convex-concave saddle point. Now I found that I have to add another constraint in the form $x^\mathsf{T}A y=0$, where $A$ is an invertible matrix. Is the following problem still convex-concave? \begin{align} \min_x & \max_y f(x,y)\\ \text{s.t.} &x\in \mathcal{C}\\ &x^\mathsf{T} A y = 0 \end{align} I know that a problem of the form \begin{align} \min_x & \max_y x^\mathsf{T} A y\\ \text{s.t.} &x\in \mathcal{C}\\ \end{align} is convex-concave.

Answer 1

We have the bilinear equation

$$\rm x^{\top} A \, y = 0$$

where $\mathrm A \in \mathbb R^{n \times n}$ is a given invertible matrix. The equation above can be rewritten as follows

$$\begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix}^{\top} \begin{bmatrix} \mathrm O_n & \mathrm A\\ \,\mathrm A^{\top} & \,\mathrm O_n\end{bmatrix} \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix} = 0$$

The characteristic polynomial of the block matrix is

$$\det \begin{bmatrix} s \mathrm I_n & -\mathrm A\\ -\mathrm A^{\top} & s\mathrm I_n\end{bmatrix} = \det \left( s^2 \mathrm I_n - \mathrm A \mathrm A^{\top} \right)$$

Since $\mathrm A$ is invertible, $\mathrm A \mathrm A^{\top}$ is positive definite. Thus, the spectrum of the block matrix contains the positive and negative square roots of the positive eigenvalues of $\mathrm A \mathrm A^{\top}$. Hence,

$$\begin{bmatrix} \mathrm O_n & \mathrm A\\ \,\mathrm A^{\top} & \,\mathrm O_n\end{bmatrix}$$

is indefinite. We then conclude that the set

$$\left\{ \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix} \in \mathbb R^{2n} : \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix}^{\top} \begin{bmatrix} \mathrm O_n & \mathrm A\\ \,\mathrm A^{\top} & \,\mathrm O_n\end{bmatrix} \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix} = 0 \right\}$$

is non-convex.

Answer 2

A standard approach can be used to convert your program into a single level optimization problem.

Start with

$\min_{x} \max_{y} f(x,y)$

subject to

$x \in C$

$x^{T}Ay=0$.

Now, assuming that the Karush-Kuhn Tucker sufficient conditions for the inner maximization are satisfied, we can substitute them into the problem. For any given $x$, the KKT conditions for the inner maximization are:

$\nabla_{y} f(x,y)=\lambda A^{T}x $

$x^{T}Ay=0$.

The original problem can then be written as:

$\min_{x,y,\lambda} f(x,y)$

subject to

$x \in C$

$x^{T}Ay=0$

$\nabla_{y} f(x,y)=\lambda A^{T}x $.

Whether you can solve this will depend on the details of $f$ but it won't be a convex problem.