1
$\begingroup$

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

$\endgroup$

migrated from stats.stackexchange.com Jan 10 '13 at 15:40

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • 1
    $\begingroup$ I cant understand you question, what do you want to know? Do you want to know if $f_1$ is convex? $\endgroup$ – Tomás Jan 10 '13 at 16:01
  • $\begingroup$ Closely related: math.stackexchange.com/questions/274837. $\endgroup$ – whuber Jan 10 '13 at 16:19
  • $\begingroup$ The constraint only says $x_1 \le 0$. So looks like min is $0$ when $(x_1,x_2)=(0,0)$. $\endgroup$ – coffeemath Jan 10 '13 at 17:23
  • $\begingroup$ 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)$. $\endgroup$ – Rahul Jan 10 '13 at 19:38
  • $\begingroup$ @Tomás. Yeah I want to know why $f_1(x)$ is not convex? $\endgroup$ – user34790 Jan 10 '13 at 19:43
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

enter image description here

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.

$\endgroup$

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.