Minmax problem with linear objective and linear restrictions

Question

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.

Answer 1

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'))