# Problem solvable $\Rightarrow$ subproblems solvable if feasible region closed, convex?

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.

• What does solvable mean? Jan 4 '20 at 21:34

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.