Maximin optimization

Question

So I have the following optimization problem.

$$\max_{x\in C} \min(f^{\top}x,g^{\top}x)$$

Here $C$ is some bounded constraint set defined by linear inequalities only.

Suppose that $z^{*} = \max_{x\in C} \min(f^{\top}x,g^{\top}x)$. Let $x^{*}\in C$ denote an optimal solution. I was wondering under which conditions the following is true. $$z^{*} = f^{\top}x^{*} = g^{\top}x^{*} \qquad (\triangle)$$

Non-example $1$: $C = \{x \in \mathbb{R}^2: 0 \leq x \leq 1\}$, $f = \begin{pmatrix}1 \\ 1\end{pmatrix}$ and $g = \begin{pmatrix}1 \\ 2\end{pmatrix}$.

<p>Non-example $2$: $C = \{x \in \mathbb{R}^2: 0 \leq x \leq \begin{pmatrix}1 \\ 2\end{pmatrix}\}$, $f = \begin{pmatrix}1 \\ 0\end{pmatrix}$ and $g = \begin{pmatrix}0 \\ 1\end{pmatrix}$</p>

<p>Example $1$: $C = \{x \in \mathbb{R}^2: 0 \leq x \leq 1\}$, $f = \begin{pmatrix}1 \\ 1\end{pmatrix}$ and $g = \begin{pmatrix}1 \\ -1\end{pmatrix}$</p>

Based on these toy examples, I get the feeling that at least one component of $f$ and $g$ should be opposite signed for $(\triangle)$ to be true.

Answer 1

This is an answer to a special case of the problem in question due to the discussion in the comments:

We consider \begin{align} \tag{1} \max \quad \min(f^T x, g^T x) \quad\text{s.t.}\quad x \ge 0, e^T x = 1. \end{align}

Using the KKT conditions or Lagrangian multiplier techniques, you will get a characterization:

We can rewrite the problem equivalently to $$ \tag{2} \max \{ z \mid z \le f^T x, z \le g^T x, x \ge 0, e^T x = 1 \}, $$ which is a convex problem. That is, the KKT conditions are sufficient and necessary. They are $$ \begin{bmatrix} -1 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ -f \end{bmatrix} \lambda + \begin{bmatrix} 1 \\ -g \end{bmatrix} \mu + \begin{bmatrix}0 \\ -I \end{bmatrix} \nu + \begin{bmatrix}0\\ e\end{bmatrix}\rho = 0, $$ $$ z - f^T x \le 0, z - g^T x \le 0, -x \le 0, e^T x - 1 = 0$$ $$ \lambda, \mu, \nu \ge 0, $$ $$ \lambda(z - f^T x) = 0, \mu(z - g^T x) = 0, \nu^T x = 0. $$ Simplify and adding the fact that $f^T x = g^T x$, we obtain $$ \nu = \rho e - \lambda f - (1-\lambda) g, $$ $$ (f-g)^T x = 0, x \ge 0, e^T x = 1, $$ $$ \lambda \in[0,1], \nu \ge 0, $$ $$ \nu^T x = 0. $$ Using $\nu^T x = 0$ and $e^T x = 1$, we obtain $$ \rho = f^T x. $$ That is, we obtain following sufficient condition for a maximizer of (1): $$ f^T x e - \lambda f - (1-\lambda) g \ge 0, $$ $$ (f-g)^T x = 0, e^T x = 1, x \ge 0, \lambda\in [0, 1]. $$

A non example:

Consider $$ C = [0, 1]^2 $$ and $$ f = \begin{bmatrix}-1 \\ 0 \end{bmatrix}, \qquad g = \begin{bmatrix}0 \\ 1 \end{bmatrix}. $$ Then, for $x\in C$ we have $$ \min(f^T x, g^T x) = \min(-x_1, x_2) = -x_1, $$ hence $$ z^* = \max_{x\in C} \min(f^T x, g^T x) = \max_{x_1 \in [0,1]} -x_1 = 0. $$ Now, the set of maximizers is $$ X^* = \{ (0, x_2) \mid x_2 \in [0,1] \}. $$ So, for any $x^*\in X^*\setminus \{ 0 \}$ we have $$ z^* = f^T x^* = 0 < g^T x^*. $$