0
$\begingroup$

I'm trying to solve a linear minmax problem very similar to KKT Conditions for Minmax Problem (and hopefully with a simpler solution).

Let vector $x$ be a concatenation of two vectors $x_1$ and $x_2$. I then want to find

$$ \min_{x_1} \max_{x_2} c^Tx $$

constrained by

$$ Ax \leq b \\ x \geq 0. $$

By replacing the inner maximization with it's dual, I can reduce this problem to a QP problem, but, unfortunately, the Q matrix of that QP is not necessarily positively defined.

Is there a better route, that would allow me to reduce this to a more tractable problem?

Edit

Even the idea of replacing the inner maximization with it's dual does not work - depending on the values of $x_1$ the inner maximization can become infeasible, and it's dual unbounded, so the QP becomes unbounded as well. And I don't think it is possible to add restrictions on $x_1$ to avoid this.

$\endgroup$
6
  • $\begingroup$ Perhaps you can replace $x_2 \geq 0$ with a finite set for $x_2$, and alternatingly optimize over $x_1$ and $x_2$ where you extend the finite set by one element in each iteration. $\endgroup$
    – LinAlg
    Jun 16, 2020 at 14:06
  • $\begingroup$ Hmm, discretized set for $x_2$ is too large in my case. But I understand from your comment, that you don't see a tractable reduction of this, which is helpful by itself. $\endgroup$
    – psarka
    Jun 16, 2020 at 14:28
  • $\begingroup$ What dimensions are we talking about? $\endgroup$ Jun 16, 2020 at 15:32
  • $\begingroup$ $x_1 \in R^5$, $x_2 \in R^{20}$ $\endgroup$
    – psarka
    Jun 16, 2020 at 17:02
  • $\begingroup$ and the dimension of $A$, i.e. the number of constraints? $\endgroup$ Jun 17, 2020 at 5:16

1 Answer 1

1
$\begingroup$

I don't see why this would be possible to solve any faster than a general bilevel linear programming problem , i.e. accepting the intractable nonconvex nature of the problem (although I absolutely could be wrong there).

Just for fun, I set up the problem as a bilevel problem (with a MILP-representation of the nonconvex complementarity constraints) with the dimensions you listed, and random instances were solved in anything from 5 seconds to 5 minutes with an efficient MILP solver (Gurobi in my tests). To setup the bilevel program, I used the MATLAB Toolbox YALMIP (disclaimer, developed by me)

n1 = 5;
n2 = 20;
m = 20;
A = randn(n2*5,n1+n2);
b = 10*rand(n2*5,1);
c = randn(n1+n2,1);

x1 = sdpvar(n1,1);
x2 = sdpvar(n2,1);
x = [x1;x2];
outer_o = c'*x;
inner_o = -c'*x;
outer_c = x1 >= 0;
inner_c = [x2 >= 0, A*x <= b];
solvebilevel(outer_c,outer_o,inner_c,inner_o,x2,sdpsettings('bilevel.algorithm','external'))
$\endgroup$
1
  • $\begingroup$ Very bad news, thank you very much! :) $\endgroup$
    – psarka
    Jun 17, 2020 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .