What does it mean to minimize a convex function with "less than or equal to" inequality constraints? Why?

Question

What does mean to minimize objective function with "less than" inequality constraints? Aren't you suppose to minimize with "greater than" constraints, like in example 1?

Example 1 (understand this) $$\begin{align} \text{max } x_1 & +5 x_2 \\ \text{s.t. } x_1 & \le 150 \\ x_2 &\le 350 \\ x_1+x_2 &\le 400 \\ x_1 , x_2 &\ge 0 \end{align}$$

I get this: the objective function wants to be as large as possible, but the constraints put an upper bound on $x_1, x_2$.

Example 2 (don't understand this) $$\begin{align} \text{min } & f_0(x) \\ \text{s.t. } & f_i \le 0 \text{ } i=1,...,m \\ \end{align}$$ where $f_0,..,f_m$ are convex functions. (Eq. 4.15 Convex Optimization)

This seems unbounded below. But since it's convex, it's bounded below? So, you are minimizing a convex function that satisfies a bunch of other convex functions.

Am I understanding this correctly? What's the point of this? Can someone provide a numerical example?

Thanks in advance!

=============================DIVIDER LINE===========================

Follow up question:

Generally, $f_i(x)$ need not to be convex for $i=1,...,m$ $$\begin{align} \text{min } & f_0(x) \\ \text{s.t. } & f_i \le 0 \text{ } i=1,...,m \\ \end{align}$$

This is unbounded below. Isn't the solution $-\infty$?

Answer 1

Notice that $x^2-1$ is a convex function. If we consider $x^2-1 \ge 0$, we have $x \ge 1$ or $x \le -1$. That is the feasible set is not a convex set.

However, notice that $x^2-1 \le 0$ is equivalent to $-1 \le x \le 1$ is convex.

In general, we know that $\{ x \mid f_i(x) \le 0\}$ is a convex set and their intersection, that is the feasible set that you have written down is a convex set. It is a desirable property to minimize a convex objective function over a convex set, in particular, we know that a local minimum is a global minimum.

Also, notice that the first example is a special case of the general form.

$$\begin{align} \text{max } x_1 & +5 x_2 \\ \text{s.t. } x_1 & \le 150 \\ x_2 &\le 350 \\ x_1+x_2 &\le 400 \\ x_1 , x_2 &\ge 0 \end{align}$$

Is actually equivalent to

$$\begin{align}- \min -x_1 & -5 x_2 \\ \text{s.t. } x_1 & \le 150 \\ x_2 &\le 350 \\ x_1+x_2 &\le 400 \\ -x_1 &\le 0 \\ -x_2 &\le 0 \end{align}$$

Here $f_0$ is just $-x_1-5x_2$ and the $f_i$ are just the LHS of the constraint.

We can flip the inequality by multiplying a negative sign and in fact the general form even include the first form. The general form doesn't tell us whether $x_i$ is bounded above or below since linear functions are convex and we can flip the inequality signs. The crucial propery here is convexity.

For the follow up question:

Even if $f_i$ is not convex, it is still possible for the feasible region to be bounded. In fact, in special cases, it is even possible for it to be convex. As an example

Consider $$x^3-1 \le 0$$

Even thought the function $x^3-1$ is not convex, the feasible region is just $x \le 1$.

Imposing $f_i$ to be convex explicitly gives us a convenient way to construct a convex set and also use its properties in deriving algorithms or investigate property of this form of problems.

Answer 2

I think Siong Thye Goh's answer is very good--I'm adding this answer to try to clarify some confusion you expressed in the comments.

I'm not positive, but I think the confusion is that you're mixing up the hypograph of a function with the sublevel sets of a function. The hypograph of a function $f:\mathbb{R}^n\to\mathbb{R}$ is the set $$\big\{(x,y)\in\mathbb{R}^{n+1}\;|\;y\leqq{f(x)}\big\}.$$ By contrast, the sublevel sets (at a value $c\in\mathbb{R}$) is the set $$\big\{x\in\mathbb{R}^n\;|\;f(x)\leqq{c}\big\}.$$ Notice that these two sets are fundamentally different (in particular, one is a subset of $\mathbb{R}^{n+1}$, while the other is a subset of $\mathbb{R}^n$).

Inequality constraints $g(x)\leqq0$ define a feasible region through sublevel sets. Let's consider a function $g:\mathbb{R}\to\mathbb{R}$, like $g(x)=x-1$. The sublevel set of this function (for $c=0$) is shown in red here:

If we multiply this constraint by $-1$, then we get:

Note that even though the line flipped upside down, the set of feasible solutions is exactly the same!

In contrast, the hypograph of the function $g(x)=x-1$ is

(the hyprograph is the set shaded in light blue). Note that the dimension of the hypograph is one dimension higher than the dimension of the sublevel set (red line) above. The hypograph of $g$ really has nothing to do with the constraint $g(x)\leqq0$.

Two Final Points

1. In the example above, we can see that the hypograph of $g$ is the exact same set as the sublevel set (at $c=0$) of the function $h:\mathbb{R}^2\to\mathbb{R}$ given by $h(x_1,x_2)=x_2-x_1+1$. In general, the hypograph of a function $g:\mathbb{R}^n\to\mathbb{R}$ equals the sublevel sets for $c=0$ of the function $h:\mathbb{R}^{n+1}\to\mathbb{R}$ given by $h(x,y)=y-g(x)$. I think this connection is causing confusion.
2. The sublevel sets of a function $g$ (for $c=0$) are the same as the superlevel sets of the function $-g$ (for $c=0$). However, the hypograph of a function $g$ is not the epigraph of the the function $-g$ (see linked Wiki articles for defintions of superlevel set and epigraph). Multiplying by $-1$ affects function graphs, but not feasible regions.