1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much. what method do you suggest for solving inner problem which can be used also to compute sensitivity of the optimal values? Is there any code for doing that available? Could you please explain a little or point to somewhere about how to use sensitivities to solve the outer minimization? $\endgroup$ – user85361 Mar 7 '16 at 4:08
  • $\begingroup$ Also, will this method reach global optimal? $\endgroup$ – user85361 Mar 7 '16 at 4:16
  • $\begingroup$ Despite searching and reading a lot I didn't find anything how to do your suggested method. Would you please point me to a link or some hints? Thank you. $\endgroup$ – user85361 Mar 7 '16 at 15:39
  • $\begingroup$ I've edited the answer to include a reference on algorithms for a related class of problems. However, your problem doesn't have the correct convexity, so the approach I've suggested would only be heuristic. $\endgroup$ – Brian Borchers Mar 8 '16 at 1:40
  • $\begingroup$ Is it a good idea to use lifting procedure just for $y$? and use the method you proposed? Please see my edit of question $\endgroup$ – user85361 Mar 9 '16 at 7:08
3
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Wow. Thank you. At the moment, actually I can't understand everything, so I think on it, try your code and let you know. How it obtains minimax point? Is it fast? $\endgroup$ – user85361 Mar 14 '16 at 15:02
  • $\begingroup$ Dear Johan, I don't understand how you solve minimax? Also, your linearization is not obvious to me? would you please give me some hints to understand your approach? Thank you. $\endgroup$ – user85361 Mar 14 '16 at 15:22
  • 1
    $\begingroup$ minimax is handled by replacing the maximization with the corresponding kkt equalities, and then simply minimizing. Linearization of $w=xy$ with binary $x$ and continuous $y$ is done by standard big-M $-Mx \leq w\leq Mx, -M(1-x)\leq w-y\leq M(1-x)$ $\endgroup$ – Johan Löfberg Mar 14 '16 at 21:20
  • $\begingroup$ Is this approach, "minimax is handled by replacing the maximization with the corresponding kkt equalities, and the simply minimizing" is an approach that we can use regardless of your approach for solving integer problem? I mean can I add this as a constraint to min problem and just solve? If it cannot be answered here, Is it good to ask it as a new question? $\endgroup$ – user85361 Mar 17 '16 at 7:55
  • $\begingroup$ In the code, when I change n=4 to n=40, it doesn't complete. $\endgroup$ – user85361 Mar 17 '16 at 7:58

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.