I am trying to understand whether the following problem is a convex optimization problem:

\begin{align} \min 1 \\ s.t. \\ & -x \le 0 \\ & -y \le 0 \\ & -xy \le 0, \end{align}

The objective is constant, hence it is a convex function. $-x$ and $-y$ are linear hence they are convex functions. However, $-xy$ is neither convex nor concave.

According to Boyd's book on convex optimization, the definition of a convex optimization (Equation (1.8) in the book) requires that the objective and all functions above on the lhs of each inequality will all be convex. So it appears that the above is not a convex optimization.

However, it seems to me that the feasible domain of the above problem is: \begin{align} & x \ge 0 \\ & y \ge 0, \\ \end{align} which is a convex domain, hence intuitively, this should be a convex problem as it minimizes a convex objective over a convex domain.

  • 1
    $\begingroup$ There is nothing earth-shattering that would happen if you decide the convention should be "yes" or "no." That constraint $-xy\leq 0$ does not specify a convex subset of $\mathbb{R}^2$. However, given the other constraints, that constraint is redundant and can be removed. A computer that expects the convex program to be in standard form would likely want you to remove that constraint yourself, else it would give you an error. $\endgroup$ – Michael Nov 2 '16 at 12:49
  • $\begingroup$ Another example would be to minimize $-x$ subject to $x\leq 0$ and $x \in \{0,1\}$. This last "binary" constraint is nonconvex but the result of both constraints is the convex set consisting of one point. $\endgroup$ – Michael Nov 2 '16 at 13:02

This is a matter of definitions. Let us consider the problem \begin{align*} \text{Minimize} \quad & f(x) \\ \text{such that} \quad & g(x) \le 0. \end{align*} Here, $f : \mathbb{R}^n \to \mathbb{R}$, $g : \mathbb{R}^n \to \mathbb{R}^m$ and the inequality constraint $g(x) \le 0$ is considered coefficient-wise.

The feasible set is \begin{equation*} \Omega = \{ x \in \mathbb{R}^n \mid g(x) \le 0\}. \end{equation*}

Now, there are two notions of convexity for the above problem:

  • $f$ and all components of $g$ are convex.
  • $f$ and $\Omega$ are convex.

It is easy to see that the first notion implies the second one but note vice-versa (see your example).

However, it is more reasonable to use the first definition, since we are working explicitly with the functions $g$.

| cite | improve this answer | |
  • $\begingroup$ I understand that it is a matter of definition but a convex problem is a well established concept. Since the two possible definitions are NOT equivalent, there is some confusion. I wonder if the inconsistency for the specific example above is only due to the fact that the third condition is redundant. In other words, assuming that there is a single inequality constraint g(x)<0, x \in R^n, is it true that the domain is convex if and only if g(x) is a convex function? Or can one find example of nonconvex g(x) such that g(x)<0 is still convex? $\endgroup$ – Wazowski Nov 2 '16 at 15:15
  • 1
    $\begingroup$ Take $g(x) = x^3 - 1$, then $\{x : g(x) < 0\}$ is convex, yet $g$ is not convex. In optimization we like all $g$ to be convex since then our nice theorems (like KKT) apply. $\endgroup$ – LinAlg Nov 2 '16 at 16:41
  • $\begingroup$ Thanks. That was a very useful simple example to illustrate what I wanted. $\endgroup$ – Wazowski Nov 6 '16 at 13:42

I must gently disagree with @Michael's first comment. There would certainly be a significant shift in what we could say about convex optimization problems if we relax the definition as the OP suggests we might: we suddenly would not be able to claim that convex optimization problems, as a class, are tractable.

The most important reason we study convex models is that, unlike the larger class of mathematical models, they admit a variety of tractable numerical methods for solving them. And if I'm going to get beyond a theoretical paper to the actual solution of a given class of problems, I'm going to need describe them in a computer-friendly manner. For instance, I might write code to compute the values and derivatives of the objective and constraint functions. I might express the problem in conic form and use a barrier or scaling point method. Or I could rely on a cutting plane oracle or barrier function to describe the constraint set.

But if I were start to allow any sort of constraint combination you wish, then the likelihood that I will find such a computational description drops considerably. Consider the constraint $x^2 \geq 1$---it has no cutting plane oracle, and its barrier method is not convex; heck, the set it describes isn't even connected. But wait, if I also happen to know that $x\geq 0$, then I still have a convex problem, right? Well, sure, but of course the first thing I will do is transform my problem into a solvable form by replacing $x^2\geq 1$ with $x\geq 1$. I'm back to my comfortable Boyd-convex domain.

Sure, there are going to be some examples where a "non-convex" description of the problem still admits a tractable solution method. But hopefully we would agree that exceptional cases do not provide a useful foundation on which to build an entire practice.

| cite | improve this answer | |

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.