9

Let $c \in \mathbb{R}^n$, $M \subseteq \mathbb{R}^n$ such that the problem \begin{align}P:\quad\min_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \in M\end{align} is solvable.

If a subset $X \subseteq M$ is nonempty, closed and convex, does it follow that the subproblem \begin{align}P:\quad\min_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \in X\end{align} is also solvable?

Thoughts: I know this is not true if $X$ is only assumed to be closed: an epigraph reformulation of this is a counterexample.

Edit:

By solvable I mean that the problem is feasible and the infimum is achieved.

zxmkn
  • 213
  • 1
  • 6

1 Answers1

8

In your question, you call a problem 'solvable' if there exists an $\hat{x} \in M$ such that

\begin{align}c^\top\hat{x} = \inf_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \in M.\end{align}

The following example shows that the answer to your question is no.

Let $n = 2$ and take $c = (0,1)^\top$. Furthermore, let $$M = \{x \in \mathbb{R}^2 ~\vert~ x_2 \ge 0\}$$ and $$X = \{x \in \mathbb{R}^2 ~\vert~ x_2 \ge e^{x_1}\}.$$

Note that indeed $X \subseteq M$, because $x_2 \ge e^{x_1}$ implies that $x_2 \ge 0$. Furthermore, it is easy to verify that $X$ is closed and convex.

The minimization problem over $M$ is given by \begin{align}\inf_{x \in \mathbb{R}^2}&\quad x_2\\\textrm{s.t.}&\quad x_2 \ge 0.\end{align} Clearly, the minimum is attained by $\hat{x} = (0,0)^\top$, for example.

For the other optimization problem, we have \begin{align}\inf_{x \in \mathbb{R}^2}&\quad x_2\\\textrm{s.t.}&\quad x_2 \ge e^{x_1}.\end{align} The infimum is equal to zero, which results from taking the limit $x_1 \rightarrow -\infty$ and setting $x_2 = e^{x_1}$. However, this value cannot be attained by any $\hat{x} \in X$.

Final note: if you additionally assume that $X$ is bounded (or $M$ is bounded), then the Weierstrass theorem ensures that the minimum can be attained. No convexity is necessary.

Kevin Dalmeijer
  • 6,167
  • 1
  • 17
  • 48