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.


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

  • 7
    $\begingroup$ What does solvable mean? $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.