# min max inside a linear program

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.

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*}