3

According to exercise 3.32 in Boyd & Vandenberghe's Convex Optimization, if both $f$ and $g$ are convex, positive and non-increasing (or non-decreasing) then $fg$ is convex. However, if we let $f(x,y)=x$ and $g(x,y)=y$ then over the non-negative orthant the conditions are fulfilled but the sublevel set for $0.5$ is not convex (which I think should be convex if the function is convex).

Where am I wrong in understanding the meaning of the result presented in this exercise?

Frank Moses
  • 2,718
  • 3
    What does it mean for a 2-variable function to be "increasing" or "decreasing"? I thought those concepts apply to single variable functions only? – Jyrki Lahtonen Jul 19 '18 at 06:26
  • what is the sublevel set for .5? – Jürg W. Spaak Jul 19 '18 at 06:27
  • @JürgMerlinSpaak you can see this sublevel set in Wolfram Alpha website. It is clearly not convex. – Frank Moses Jul 19 '18 at 06:33
  • @JyrkiLahtonen so you mean that the exercise result is only applicable for single variable functions? (Actually I have read in books the statements like "increasing/decreasing in every argument" for multivariable functions but I do not know how it applies here. I think both of the functions that I wrote in my question are non-decreasing in with respect to all the arguments. ) – Frank Moses Jul 19 '18 at 06:36
  • @JürgMerlinSpaak see this https://www.wolframalpha.com/input/?i=xy%3C%3D.5 – Frank Moses Jul 19 '18 at 06:42
  • @Arthur I think you are talking about the epigraph. But I am taking about the sublevel set. For instance if $h(x,y)=x^2$ then the set of values of $(x,y)$ for which $h(x)\leq \alpha$ (this set must be a convex if $h(x,y)$ is convex. Am I wrong?) – Frank Moses Jul 19 '18 at 06:56
  • @Arthur do you agree with my point? – Frank Moses Jul 19 '18 at 08:01
  • Wikipedia says in the first paragraph a function is convex if and only if its epigraph is convex. On the other hand, the subgraph of a convex function is usually not convex, as is evidenced by, for instance, the single variable convex function $h(x) = x^2$. – Arthur Jul 19 '18 at 08:09
  • @Arthur it is well known that every convex function is quasiconvex. And a function is quasiconvex if the sublevel set of that function is convex. (This is given in the convex optimization book, by Stephen Boyd and Vandenberg, page 95 and 96) – Frank Moses Jul 19 '18 at 08:30
  • @Arthur I know that epigraph of the convex function is convex. But I am saying that the sublevel set should also be convex (since a convex function is always quasiconvex), which in this case is not. – Frank Moses Jul 19 '18 at 08:32
  • No, you're right, I've not been thinking straight. $f(x, y)$ is not a convex function. Take, for instance, the line segment between $(0,1,f(0,1)) = (0,1,0)$ and $(1,0,f(1,0)) = (1,0,0)$. That segment does not lie above the graph. – Arthur Jul 19 '18 at 08:35
  • @Arthur but it does satisfy the properties described in exercise 3.32 of convex optimization book (Stephen Boyd and Vandenberg). And therefore it should be convex. Right? – Frank Moses Jul 19 '18 at 08:39
  • 4
    Your reply to Jyrki has it right: the result in the exercise only applies to functions of one variable. –  Jul 19 '18 at 08:44
  • 2
    I'll confirm Jyrki and Rahul's comment. This is a very common misinterpretation of the claim in B&V. I cannot tell you how many people claim that $xy$ or $x/y$ is convex because of this. – Michael Grant Jul 19 '18 at 14:41
  • @MichaelGrant thank you for your comment. I think it will be better if they mentioned it in the book that they are only talking about the functions that are of single variable. – Frank Moses Jul 19 '18 at 23:08
  • 1
    Perhaps, but I would argue that the way the question is worded it is simply not correct to assume it can be extended to the multivariate case. It's just that many people, frankly, don't think rigorously enough about these things. – Michael Grant Jul 19 '18 at 23:15

2 Answers2

2

To summarize the comments:

The theorem about the product of two positive non-decreasing convex functions being convex applies only to functions of one real variable.

For example, we can use it to conclude that $x e^x$ is convex for $x\ge 0$. We cannot use it to conclude that $xe^y$ is convex over $x, y\ge 0$.

0

Look at the Hessian $H$ of $xy$:

$$H = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$

$|H| = -1 < 0$, and so $xy$ is concave.

Johnny Que
  • 315