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$?
Best Answer
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.