1
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ I'm definitely not an expert on that subject, but minimizing $x$ st $x^2+5x+6 \leq 0$ makes sense to me. The minimum is $x=-3$ which can be seen by plotting the constraint. $\endgroup$ – FormerMath Feb 23 '19 at 4:12
  • $\begingroup$ The direction of the inequalities is immaterial, as we can always flip them by multiplying by $-1$. It certainly feels intuitive to have lower bound constraints when minimizing, but we can always flip them by multiplying with $-1$. $\endgroup$ – David M. Feb 24 '19 at 3:31
  • $\begingroup$ @DavidM. I tried to think that way. But if you graph the constraints, it's still upper bounded though. The feasible set is below the graph. $\endgroup$ – user13985 Feb 24 '19 at 3:52
  • 1
    $\begingroup$ I just added an answer to try to address your confusion--sorry if I'm way off base! $\endgroup$ – David M. Feb 24 '19 at 4:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I added a follow up question. What if constrains are not convex? Isn't the solution equal to $-\infty$? Can you explain this in your post? Thank you! $\endgroup$ – user13985 Feb 23 '19 at 17:20
  • $\begingroup$ I think what I was really missing was the definition that: the inequality constraint functions must be convex. $\endgroup$ – user13985 May 8 '19 at 17:43
1
$\begingroup$

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:

1D example

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

Multiplied by negative 1

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

hypograph of g

(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.
$\endgroup$

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.