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

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.

• What exactly do you mean by "convex-conave"? In the well studied subject of convex-concave games, you can have linear (in)equalities involving $x$ and separate (in)equalities involving $y$ but not equilibrium constraints involving both $x$ and $y$. – Brian Borchers May 1 '17 at 15:02
• This is a saddle point problem in machine learning. As said it is convex with respect to one variable and concave with respect to another. This problem is not coming from a game. Can't we reach to an equivalent problem by adding the constraint to objective? – user85361 May 1 '17 at 15:06
• My point was simply that the problem you've stated doesn't fit into the standard theory. – Brian Borchers May 1 '17 at 15:17
• What is the definition of "convex-concave" problem ? How do constraints incorporate play role in definition of a "convex-concave" problem? – Red shoes Jun 3 '17 at 19:57

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( s^2 \mathrm I_n - \mathrm A \mathrm A^{\top} )$$

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.

• Thank you very much. Simple and elegant. Do you have any hint for me on how to approximate it with a convex set? – user85361 May 2 '17 at 13:13
• @user85361 Let $n=1$ and $A = 1$. Then $x y = 0$ implies $x = 0 \lor y = 0$, i.e., the set defined by $x y = 0$ is the union of the two axes, which is clearly non-convex. I do not see in what sense one can approximate the set. – Rodrigo de Azevedo May 2 '17 at 14:04

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

$\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.

• Thank you Brian. So, do you mean the problem is not convex-concave? – user85361 May 2 '17 at 8:32