1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Brian Borchers May 1 '17 at 15:02
  • $\begingroup$ 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? $\endgroup$ – user85361 May 1 '17 at 15:06
  • $\begingroup$ My point was simply that the problem you've stated doesn't fit into the standard theory. $\endgroup$ – Brian Borchers May 1 '17 at 15:17
  • $\begingroup$ What is the definition of "convex-concave" problem ? How do constraints incorporate play role in definition of a "convex-concave" problem? $\endgroup$ – Red shoes Jun 3 '17 at 19:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much. Simple and elegant. Do you have any hint for me on how to approximate it with a convex set? $\endgroup$ – user85361 May 2 '17 at 13:13
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo May 2 '17 at 14:04
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.