# Minmax problem with linear objective and linear restrictions

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.

• 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. Jun 16, 2020 at 14:06
• 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. Jun 16, 2020 at 14:28
• What dimensions are we talking about? Jun 16, 2020 at 15:32
• $x_1 \in R^5$, $x_2 \in R^{20}$ Jun 16, 2020 at 17:02
• and the dimension of $A$, i.e. the number of constraints? Jun 17, 2020 at 5:16

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

• Very bad news, thank you very much! :) Jun 17, 2020 at 15:05