What method do you suggest to solve this minimax, quadratic in both variables problem?

Question

I have a problem of the form, \begin{align} minimize_{y} maximize_{x}&\quad x^T y - y^T (B\odot x x^T) y\\ s.t. &x\in [l,u]\\ &Ay=b \end{align} How to efficiently solve this problem? $B$ is a semidefinite matrix. What I have done: you can dual the inner problem, and get a semidefinite problem with two sdp variables. But this approach is too slow, and most of the solvers are unable to warmstart, which I need. I want a rapid method with warmstart ability, i.e. when I add a simple constraint, I can use the previous iteration results and not start from scratch.

EDIT:Unfortunately, I have some additional difficulties, $y$ is integer. Although I relax it to values between $[-1,1]$. If I use the semidefinite relaxation, for $y$, is there any efficient algorithm for this problem? In this way, the nonconvexity of function for a fixed $x$ which @Brian Borchers mentioned, will be resolved. This method, is good for my application, since, I can at least use warmstart for $x$. What do you suggest?

Answer 1

You can write your inner problem as

$ \max_{x} x^{T}y - x^{T}Cx $

subject to

$ x \in [l,u] $

where $C=\mathrm{diag}(y)B\mathrm{diag}(y)$. This is a box constrained QP.

Since $C=\mathrm{diag}(y) B \mathrm{diag}(y)$, $C$ is also positive semidefinite, so the inner problem is a concave maximization problem.

You can easily solve the inner problem using a variety of methods (e.g. an active set method.) You can also compute the sensitivity of the optimal value to changes in $y$. With those sensitivities, you could then apply a first order method to solve the outer minimization problem.

There are a variety of algorithms for solving convex-concave minimax problems

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

where $f$ is a function that is concave in $x$ for fixed $y$ and convex in $y$ for fixed $x$. See for example chapter 3 in the book by Rustem and Howe, Algorithms for Worst-Case Design and Applications to Risk Management. These algorithms can work with just about any method for solving the inner problem as a subroutine.

In your case, $f$ is not convex as a function of $y$ with $x$ fixed. You also have additional complicating constraints. You can still try this general approach, but the conventional analysis won't ensure convergence.

Answer 2

With integer variables, the whole problem can be cast as a MILP after some tricks from integer and quadratic programming. Perhaps not what you want to do in your case, but at least this is a guaranteed global approach

1. Multiplication between binary and continuous can be written using linear constraints and auxiliary variables.

2. Polynomials of binaries can be written using linear constraints and auxilliary variables.

3. Bounded integer variables can be written using binary variables.

4. The optimal solution to the inner QP can be written using KKT conditions, involving products between $y$ and $x$, and complementarity.

5. Complementarity constraints can be handled using additional binary variables and constraints.

First normalize the notation and assume the inner program is to minimize $c^T(y)x + \frac{1}{2}x^TQ(y)x$, subject to constraints $Ex\leq f$. The optimal solution is defined by the KKT conditions $$Q(y)x + c(y) + E^T\lambda=0\\ \lambda^T(f - Ex) = 0\\\lambda\geq 0\\f-Ex\geq 0$$

In any point satisfying the optimality conditions, the objective is equal to $\frac{1}{2}(c(y)^Tx-f^T\lambda)$.In the outer program where we wish to minimize the objective, we thus want to minimize $-\frac{1}{2}(c(y)^Tx-f^T\lambda)$.

We note that we have an equality involving a quadratic function of $y$ multiplied with $x$ (thus linearizable), a complementarity condition (linearizable) and a bilinear term in the objective (linearizable).

Quite a bit of different things to put together. In the code below, I will use the MATLAB Toolbox YALMIP (disclaimer: developed by me) to test this. It has built-in functionality for the linearizations, and MILP-modelling of the complementarity.

% Define a random problem
n = 4;
B = randn(n);
B = B*B';
A = ones(1,n);
b = 1;
U = rand(n,1);
L = -rand(n,1);
E = [eye(n);-eye(n)];
f = [U;-L];

% Define decision variables
x = sdpvar(n,1);
% y is modelled as a selection from possible values
PossibleY = [-1;0;1];
Selector = binvar(n,length(PossibleY),'full');
y = Selector*PossibleY;
ConstrainSelection = sum(Selector,2) == 1

% Inner problem min_x c(y)'*x + .5*x'*Q(y)*x
lambda = sdpvar(length(f),1);
c = -y;
Q = 2*(B.*(y*y'));

Stationary = Q*x+c+E'*lambda == 0;
Complementarity = complements(lambda>=0, f - E*x>=0);
Objective = 0.5*(c'*x - f'*lambda);

% Objective we actually maximized in inner and whish o minimize in
% the outer problem
OuterObjective = -Objective;
% Linearize binary*binary and binary*continuous 
LinearizedStationary = binmodel([Stationary,[L<=x<=U]]);
[LinearizedObjective,Cuts] =  binmodel(OuterObjective,[L<=x<=U]);
% Solve the problem
optimize([LinearizedStationary, 
          Complementarity,
          Cuts,
          A*y == b,ConstrainSelection],LinearizedObjective)
% Check that the linearization actually worked
[value(LinearizedObjective) -value(c'*x + .5*x'*Q*x)]

% Small sanity check. Check by solving everything for fixed x, keeping
% kkt conditions, to ensure the new y still renders x optimal.
Objective = value(x)'*y - y'*(B.*(value(x*x')))*y;
[LinearizedObjective,Cuts] =  binmodel(Objective);
LinearizedStationary = binmodel([Q*value(x)+c+E'*lambda == 0]);
optimize([Cuts,A*y == b,lambda>=0, lambda'*(f - E*value(x))==0,LinearizedStationary],LinearizedObjective)
value(Objective)