I have the following min-max problem
$$
\min_{t\geq 0_{K}} \max_{x_1\in \mathbb{R},x_2\in \mathbb{R}} [t'A+x_1t'B+x_2 t'C]
$$
where $t$ is a $K\times 1 $ vector, $0_K$ is $K\times 1$ vector of zeros, $A,B,C$ are $K\times1$ vectors of known numbers.
I would like your help to understand if there is a way to simplify this problem. For example, is there a way to transform it into a unique minimisation problem?
Best Answer
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.