Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector.
Show that this problem
$$\max_{x \ge 0} \min_{y \ge 0} (c^T x – y^T Ax + b^Ty)$$
can be reduced to a linear programming problem.
[Math] How to convert max min problem into a linear programming problem
linear algebralinear programmingmatricesoperations researchoptimization
Related Solutions
The problem is trivial I think. I assume $A,B,C$ are linearly independent. Let's write the solution in this form $t_*=aA+bB+cC+dD$, here $a,b,c,d$ are unknowns and also $D$ is a vector that is orthogonal to the basis $\{A,B,C\}$, in other words if we construct the matrix $M=[A\; B \;C]\in \mathbb{R}^{K\times3}$ then $D\in N(M)$ or $D$ is in the nullspace of $M$. Here for a general $t$ the problem
$$\max_{x_1\in \mathbb{R},x_2\in \mathbb{R}} [t_*^TA+x_1t_*^TB+x_2 t_*^TC]=\\\max_{x_1\in \mathbb{R},x_2\in \mathbb{R}} [\text{something}+x_1(b\Vert B\Vert_2^2+aA^TB+cC^TB)+x_2(aA^TC+bB^TC+c\Vert C\Vert_2^2) ]$$
which is unbounded above unless $\begin{cases}b\Vert B\Vert_2^2+aA^TB+cC^TB = 0\\aA^TC+bB^TC+c\Vert C\Vert_2^2=0\end{cases}$ we can extract $b,c$ as a function of $a$ from above equations
$$\begin{cases}b = \frac{\frac{A^TB}{\Vert B\Vert_2^2}-\frac{(A^TC)(C^TB)}{\Vert C\Vert_2^2\Vert B\Vert_2^2}}{1-\frac{(C^TB)(B^TC)}{\Vert B\Vert_2^2\Vert C\Vert_2^2}}a=m_1a\\c = \frac{\frac{A^TC}{\Vert C\Vert_2^2}-\frac{(A^TB)(B^TC)}{\Vert B\Vert_2^2\Vert C\Vert_2^2}}{1-\frac{(C^TB)(B^TC)}{\Vert B\Vert_2^2\Vert C\Vert_2^2}}a=m_2a\end{cases}$$
If these conditions being fulfilled, the outer optimization tier will be
$$\min_{t\geq 0_{K}} (a\Vert A \Vert^2+m_1aA^TB+m_2aA^TC)=\begin{cases}\min a &\text{if} \quad \Delta \ge 0 \\ \max a &\text{if} \quad \Delta < 0 \end{cases}$$
where $\Delta = \Vert A \Vert^2+m_1A^TB+m_2A^TC$. To solve the original problem. first we compute $m_1,m_2$ and then we compute $\Delta$. Then we solve the following feasibility problem
$$\text{find} \quad a\in\mathbb{R},n \in\mathbb{R}^K \\ \text{s.t.}\quad a(A+m_1B+m_2C)+n^T(I-M(M^TM)^{-1}M^T) \in\mathbb{R}_+^K$$
If this problem is feasible and has the solution $v$, since $\mathbb{R}_+^K$ is a convex cone then any $ev,e\in \mathbb{R}_+$ is also a solution. Thus if $\Delta\ge 0$, The optimum solution will zero. If $\Delta <0$ the problem will be unbounded below. If the feasibility problem is infeasible, then the original problem is unbounded above.
It is called a bilevel program. There is no convenient way of solving it, if you by convenient mean fast in the general case. It is an intractable problem class theoretically.
The basics of a standard approach is to replace the optimality constraint with the resulting KKT conditions, which means adding complementarity constraints to the model (i.e. non-convex constraints). That in combination with the outer objective which is bilinear in $f$ and $h$ means the resulting problem is a non-convex quadratic problem.
This is one way of modelling it in the MATLAB toolbox YALMIP. To solve it you will either have to have an external non-convex quadratic solver such as Gurobi, or hope that the internal global non-convex solver manages it.
f = sdpvar(n,1);
h = sdpvar(n,1);
OuterObj = -f'*A*h
Outer_C = [R1*h<=b1];
InnerObj = -f'*B*h;
Inner_C = R2*f<=b2;
K = kkt(Inner_C,InnerObj,h);
optimize([Outer_C,K],OuterObj)
Best Answer
Consider that the following problem ($*$) \begin{alignat}{3} \min_y && b^\top y \tag{$*$}\\ &&A^\top y \geq c\\ &&y\geq0 \end{alignat} has the Lagrangian (with dual variables $x$) \begin{align} L(y;x) := b^\top y + x^\top (c-A^\top y). \end{align} Then the dual function is defined as \begin{align} d(x) := \min_y L(y;x) := \min_y \left\{ b^\top y + x^\top (c-A^\top y) \right\} \end{align} and the dual problem is \begin{alignat}{3} \max_x && d(x) \tag{$**$}\\ &&x\geq0 \end{alignat} or $$ \max_{x\geq0}\min_{y\geq0} \left\{ b^\top y + c^\top x -y^\top A x \right\} \tag{$**$$*$}. $$ Provided that both are feasible, strong duality says that ($*$) has the same objective value as ($**$), so we have shown that ($**$$*$) can be expressed as ($*$).
Or, again using strong duality, we can express ($**$$*$) as a feasibility problem (simplified LP) \begin{alignat}{3} \min_{x,y} && 0\\ && \begin{bmatrix} A^\top & 0\\ 0 & -A\\I&0\\0&I \end{bmatrix} \begin{bmatrix} y\\x \end{bmatrix} \geq \begin{bmatrix} c\\-b\\0\\0 \end{bmatrix} \end{alignat}