Can I use CVX to solve a minimax optimization problem?

Nonconvex
#1

Hi. I need to solve a problem like this

\begin{align} \min_x \max_y \ & \ f(x,y) \\ \mathrm{subject \ to} \ & \ Ax = b, \ Cy = d \end{align}

where the continous function f(x,y) is concave to y and is convex to x.
This problem can be solved following from the KKT condition

\begin{aligned} & \nabla_x f(x,y)+A^T \lambda = 0, \ Ax = b, \\ & \nabla_y f(x,y)+C^T \nu= 0, \ Cy = d. \\ \end{aligned}

I hope to use optimization softwares like CVX to solve the optimization or the KKT equations, but I have no idea how to make it.

#2

You haven;t told us what the function f is. Most likely, formulating and solving the KKT conditions is not the best way of solving it with CVX.

CVX can be used to solve some, but not all, minimax problems.

#3

The complete expression of the optimization is

\begin{aligned} \min_{\mathbf{Q}} \max_{\mathbf{{d}} } \ & \ \sum _ {k=1} ^ K \mu_k \log \frac{ \det (\mathbf{Q}+ \sum_{i=1}^k d_i \mathbf{h}_i \mathbf{h}_i ^ H )} { \det (\mathbf{Q}+ \sum_{i=1}^{k-1} d_i \mathbf{h}_i \mathbf{h}_i ^ H )} \\ \mathrm{subject \ to} \ & \ \sum_{k=1}^K d_k = P, \ \mathbf{d} \geq 0, \ \mathrm{tr}(\mathbf{R} \mathbf{Q}) = \mathrm{tr} (\mathbf{R}),\ \mathbf{Q} \succeq 0, \ \mathbf{Q} \ \mathrm{is \ diagonal} \end{aligned}

where \mu_1 \geq \mu_2 \cdots \geq \mu_K. The optimization variables include \mathbf{d} = [d_1, \ldots, d_K] ^ T and \mathbf{Q}. The function is concave to \mathbf{d} and is convex to \mathbf{Q}.

#4

That doesn’t look like a convex optimization problem to me.

#5

The problem is indeed convex if \mu_1 \geq \mu_2 \ldots \geq \mu_K \geq 0.
First, the expression

\log \frac{ \det (\mathbf{Q}+ \sum_{i=1}^k d_i \mathbf{h}_i \mathbf{h}_i ^ H )} { \det (\mathbf{Q}+ \sum_{i=1}^{k-1} d_i \mathbf{h}_i \mathbf{h}_i ^ H )} = \log \det \left( \mathbf{I} + \left(\mathbf{Q} + \sum_{i=1}^{k-1} d_i \mathbf{h}_i \mathbf{h}_i ^ H \right)^{-1} d_k \mathbf{h}_k \mathbf{h}_k ^ H \right)

is convex to \mathbf{Q}, so the function is convex to \mathbf{Q}.
To show that the function is concave to \mathbf{d}, we can use the following equation

\log \frac{ \det (\mathbf{Q}+ \sum_{i=1}^k d_i \mathbf{h}_i \mathbf{h}_i ^ H )} { \det (\mathbf{Q}+ \sum_{i=1}^{k-1} d_i \mathbf{h}_i \mathbf{h}_i ^ H )} = \log \det (\mathbf{Q}+ \sum_{i=1}^k d_i \mathbf{h}_i \mathbf{h}_i ^ H ) - \log \det (\mathbf{Q}+ \sum_{i=1}^{k-1}d_i \mathbf{h}_i \mathbf{h}_i ^ H ),

and rewrite the function to be

\sum_{k=1} ^ {K-1} (\mu_k - \mu_{k+1}) \log \det (\mathbf{Q}+ \sum_{i=1}^k d_i \mathbf{h}_i \mathbf{h}_i ^ H) + \mu_K \log \det ( \mathbf{Q}+ \sum_{i=1}^K d_i \mathbf{h}_i \mathbf{h}_i ^ H ) - \mu_1 \log \det (\mathbf{Q}).
#6

You need the maximum (objective value) with respect to d to be convex with respect to Q. Otherwise, it is not a convex optimization problem.I.e., you need the objective function of the outer minimization to be jointly convex in d and Q.

#7

Thanks for your reply. For now I can’t prove the convexity of the outer minimization.
Perhaps I need to implement a primal-dual algorithm myself to solve it.

As you mentioned that CVX can be used to solve some, I am interested in what kinds of minimax problems can be solved with CVX.

#8

Convex optimization problems which are DCP-representable.

For example, if x is a variable, minimize(max(exp(2*x),x^2)). That is a mininax problem and follows CVS’s rules.

#9

Ok. Now I know that CVX cannot be used to solve the minimax or saddle point problem of a continous convex-concave function f(x,y), unless the problem can be converted to a standard convex (or conic) problem.