8
$\begingroup$

The problem $$\min \ x^3 \ \mathrm{s.t.} \ x \geq 0$$ is sometimes said to be a convex optimization problem. $f(x) = x^3$ is not a convex function. However, in the domain of $x\geq 0$ it is convex. So for some definitions this is a convex optimization problem, for others it is not. Could you please help me figure out in which main (books like convex analysis, convex optimization, etc.) source this problem is said to be convex?

I am looking to Rockafellar's convex analysis book, it says the objective function needs to be a proper convex function with domain $\{x \ : x \geq 0\}.$ Well, $x^3 $ is not a proper convex function, and has domain $\{x\ : \ x\geq 0 \}$, however $x^3$ restricted to this domain is a convex function. Which interpretation is correct?

Note: the given example is just a simplified version of a higher-level question, so I don't actually care about minimizing $x^3$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

An objective function which is convex on only part of its unconstrained domain, but which is convex on the constraint set (i.e.., for any feasible point), can be 'convexified" by modifying the objective function to have value $\infty$ for infeasible points.

This is essentially what is done by Disciplined Convex Programming (DCP) systems such as CVX, which has the function pow_p, which can be used as pow_p(x,3) which equals $x^3$ for $ x\ \ge 0$, and $\infty$ for $x < 0$. That is indeed a convex function, and the problem is completely equivalent to the original problem as you stated. It is a convex optimization problem by anyone's definition.

So I would say the answer is yes, your stated problem is convex. Definitely, as a practical matter. And to the extent that anyone disagrees, that is essentially a matter of semantics as to whether my minimal transformation is considered to still be the original problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this answer. If we also have nonconvex constraints, though implied by convex ones, is this still a convex constraint? For example, what if we have a constraint like $x^{100} \geq 0$? This is again philosophically asking: should we check the feasible set given by all constraints, or the constraints one by one? I think the latter, as it is generally very hard to figure redundant nonconvex constraints, and this somehow related to my question. $\endgroup$
    – independentvariable
    Apr 1, 2021 at 3:13
  • 2
    $\begingroup$ I'd say that for a minimization problem, if the constraint set (region) is convex, and the objective function is convex on the constraint set, the problem is convex. All the constraints being individually convex is sufficient, but not necessary for, the constraint region to be convex A rotated Second Order Cone constraint, $\|x\| \le yz, y \ge 0, z \ge 0$ is convex, but $\|x\| \le yz$, without $y \ge 0, z \ge 0$ is not convex So the "individual constraint at a time" definition depends on what's considered to be an individual constraint. My way of viewing it is invariant to that arbitrariness $\endgroup$
    – Mark L. Stone
    Apr 1, 2021 at 11:29
3
$\begingroup$

This is a convex problem under any definition.

From Wikipedia:

If $f$ is a convex function or if a minimum point of $f$ is being sought, then $f$ is called proper if there exists some point $x_0$ in its domain such that:

\begin{aligned} f(x_0)<\infty\\ f(x) > -\infty \end{aligned}

$x^3$ is convex for $x\geq 0$ and it also satisfies the above condition, making it a proper convex function for non-negative $x$.

The same is mathematically true of any function that is only convex in a particular subdomain, when defined in only that subdomain.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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