4
$\begingroup$

Although this sounds like a standard minimax problem, I'm not sure how to deal with feasibility issues.

Consider a maximin linear program

\begin{align}\max_x\min_y&\quad c^\top y\\\text{s.t.}&\quad Ay\leq b\\&\quad Cy\leq x\\&\quad Dx\leq f.\end{align}

Under what conditions can I swap the maximin to minimax and is there any duality theory that applies to this?

Note that y and x must be chosen to be feasible and we can assume that for any feasible x, there exists a feasible y. (We are not allowing infeasibility to count an $-\infty$.)

EDIT: changed minimax to maximin to clarify and added a condition.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your inner problem is actually trivial. For fixed $x$ satisfying $Ax\le b$, either $y \ge Cx$ and the inner problem has value $c'x$ or $y \not \ge Cx$ and the inner problem (using the usual convention for infeasibility in a max problem) has value $-\infty$. Since there are no other constraints on $y$, selecting $y=Cx$ is optimal in the inner problem, with value $c'x$.

So you are now left with a simple LP:\begin{align*} \min\ & c'x\\ \textrm{s.t. }\ & Ax\le b. \end{align*}

$\endgroup$
1
  • $\begingroup$ Thanks, but I'm not using that convention for infeasibility. The challenge seems to be maintaining feasibility throughout the process. I'll edit the question to add that. $\endgroup$
    – ericf
    Commented Jan 22, 2022 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.