Why is it necessary to have convexity outside the feasible region?

In the book "convex optimization" by Prof. Boyd and Prof. Vandenberghe, a convex problem is defined as,

$$ \begin{equation}\label{op_prob_gen_equivalent} \begin{aligned} & {\text{minimise}} & & \ f_0(x) \\ & \text{subject to} & & f_i(x) \leqslant 0 \ , \ \quad \forall i \in \{1,2,...,m\}\\ &&& a_i^Tx=b_i \ , \ \quad \forall i \in \{1,2,...,p\}\\ \end{aligned} \quad , \end{equation} $$ where $f_0(x) \ , \ f_1(x) \ , \ ... \ , \ f_m(x)$ are convex.

Let $X$ be the feasible set defined as $X=\{x| x \in \mathbb{R}^n, \ f_i(x) \leqslant 0 \ \forall i =1,2,...,m , \ a_i^Tx=b_i \ , \ \forall i =1,2,...,p \}$.

My question is, why is it necessary for $f_0(x) \ , \ f_1(x) \ , \ ... \ , \ f_m(x)$ to be convex outside $X$?

Solution 1:

Frankly, it's for largely practical reasons, though as LinAlg points out below, even some theoretical results depend on convexity outside of the feasible region.

One of the most important reasons that we care about convex optimization problems is that they are theoretically tractable, and can be readily solved in practice. So now let's consider how we go about solving them.

One of the distinctions that we often make when classifying algorithms that solve convex programs is between feasible methods and infeasible methods. A feasible method is guaranteed to consider only points within the feasible region; an infeasible method makes no such guarantee. Infeasible algorithms can be easier to work with, but of course they do require convexity outside of the feasible region. On the other hand, a feasible algorithm doesn't care if your constraint functions are convex outside of the feasible region. Or does it?

The complication is that a feasible method must be initialized with a feasible point. If you happen to know one, you win. But if not, you must employ a two-phase approach. The first phase is used to find a feasible starting point for the second phase. One way to do it is to solve a model like this:

\begin{array}{lll} \text{minimize} & z \\ \text{subject to} & f_i(x) \leq z & i= 1,2,\dots,m \\ & a_i^T x = b & i=1,2,\dots, p \\ & z \geq 0 \end{array}

The good news is that it's easy to find a feasible initial point for this problem: just choose any $x$ that satisfies the equality constraints, and set $z_i=f_i(x)$, $i=1,2,\dots, m$. With that point, you can use your standard feasible optimization method to solve this problem; and once you achieve $z=0$, you can stop and transition to phase 2.

The bad news is that, if $z>0$, you're starting outside the original feasible region. So you can't rely on the fact that the functions are convex just within the feasible region; they must be convex outside of that region, too. Indeed, we now have to guarantee that the functions are convex for all $x$ satisfying the equality constraints.

In limited circumstances, you might be able to find a way to expand your search space carefully to avoid regions of non-convexity. But the point remains that it is not sufficient to have convexity simply within the feasible region.