3
$\begingroup$

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.

$\endgroup$
2
  • 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, 2016 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, 2016 at 13:02

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
5
  • $\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, 2016 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, 2016 at 16:41
  • $\begingroup$ Thanks. That was a very useful simple example to illustrate what I wanted. $\endgroup$
    – Wazowski
    Nov 6, 2016 at 13:42
  • $\begingroup$ @gerw Could I have a question? I have the following nonlinear problem: $$\min f(x)\\g(x)\le 0\\h(x)=0.$$ I have found two definition of a convex problem in sources on the internet. $1.$ Problem is convex if function $f$ and all components of $g$ are convex and all components of $h$ are affine. $2.$ The feasible set $\{x\in\mathbb{R}^{n}:g(x)\le 0,h(x)=0\}$ is convex. Of course $1$ implies $2$, but $2$ does not imply $1$. This is clear, however which definition is correct, if they are not equivalent? $\endgroup$
    – Laura
    Jan 17, 2021 at 13:30
  • $\begingroup$ @gerw For example $$\min (x+2)^{2}+(y+2)^{2}$$ $$ xy\ge 4\\ x\le 4\\ y\ge 2.$$ According to the definition $1.$ it is not convex, because function $4-xy$ is not convex, but according to the definition $2.$ it is convex. I am confused with these diferent definitions. What is right? Thank you for your answer. $\endgroup$
    – Laura
    Jan 17, 2021 at 13:31
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .