Confusion related to a convex optimization problem

Question

I was going through Stephen Boyd's lecture on convex optimization. However, I am a bit confused about a problem

Given Minimize $f(x) = x_1^2+x_2^2$

subject to $f_1(x) = \frac{x_1}{1+x_2^2} \leq 0$

How come $f_1(x)$ is not convex?

I was going through Stephen Boyd's book related to convex optimization http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

Here is the exact screenshot of the page

enter image description here

I cant understand you question, what do you want to know? Do you want to know if $f_1$ is convex? — Tomás, Jan 10 '13 at 16:01
Closely related: http://math.stackexchange.com/questions/274837/. — whuber, Jan 10 '13 at 16:19
The constraint only says $x_1 \le 0$. So looks like min is $0$ when $(x_1,x_2)=(0,0)$. — coffeemath, Jan 10 '13 at 17:23
Compare $f(1,0)$ with $\frac12\big(f_1(1,1)+f_1(1,-1)\big)$. Or fix $x_1=1$ and check the sign of $\frac{\mathrm d^2}{\mathrm dx_2^2}f(1,x_2)$. — , Jan 10 '13 at 19:38

score 1 · Answer 1 · answered Jan 10 '13 at 21:27

1

Look at $f_1$ along any "vertical" line $x_1=c$ where $c\neq0$. For positive $c$, you get a failure of convexity near the $x_1$-axis, and for negative $c$ you get a failure of convexity far from the $x_1$-axis.

answered Jan 10 '13 at 21:27

Andreas Blass

71,833

score 0 · Answer 2 · answered Jan 13 '19 at 04:09

A set is convex if contains every convex combination of points within the set. If you plot $f_1$, then you get the following image.

We can see from this image that the set is not convex. In particular, the line segment between a point on the top right of the set and a point on the bottom right of the set is not included in the set.

If you want, you can also use this image to choose points x and y as well as $\lambda \in [0, 1]$ such that $f(\lambda x + (1- \lambda)y) \not\leq \lambda f(x) + (1 - \lambda) f(y)$ -- this will prove that the function is not convex using the definition of a convex function.

Confusion related to a convex optimization problem

2 Answers2