Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In lecture 3 of the course Convex Optimization conducted by Stephen Boyd at 21 minutes mark he says that a function is convex if its convex when we restrict it to a line. What does he mean by restricting a function to a line?

Secondly his exact statement is that a function $f:R^n\to R$ is convex if $g:R\to R$ is convex where $$ g(t) = f(x+tv), \{x \in dom(f), t \in dom(g),v \in R^n\} $$

My doubt regarding this is that won't any function on real space be convex since it would just be a line?

Please correct me if I am wrong.

share|improve this question
1  
Try an example: Let $f(x)=x_1^2+x_2^2$. Start your line from $x=(1,0)$ in the direction $v=(0,1)$. What is $g(t) = f(x+tv)$? Do you think it is a line? –  Rahul Feb 2 '13 at 9:17
    
@R^n: I get your point now. Thank you.... –  shaunshd Feb 5 '13 at 4:33

2 Answers 2

up vote 1 down vote accepted

1] By restricting it to a line means, basically, you draw line in the domain of the function; then you evaluate your function only along that line.

2] Imagine a paraboloid $f:\mathbb{R}\times\mathbb{R} \mapsto \mathbb{R}$ defined by $f(x,y) = \frac{x^2}{a^2} + \frac{y^2}{b^2}$.

$\hskip2in$ Paraboloid

Now, if you draw a line in the domain and evaluate this paraboloid only along that line, it would look like a parabola. Analytically, if you want to check how the function would be along the x-axis, then substitute y = 0 in the equation above and you get $f(x,y) = \frac{x^2}{a^2}$ which you might know is the equation for the parabola. Now, a parabola is convex and since every line in the domain here would give you a parabola, a paraboloid is convex. On the other hand, if you take a hyperbolic paraboloid:

$\hskip2in$ hyperbolicparaboloid

You draw a line in the domain in one direction, it would look like a parabola and you draw a line in the domain in another direction, it would look like an inverted parabola. Now, inverted parabolas are concave and not convex. Therefore, hyperbolic paraboloids are not convex.

  • Images have been borrowed from the internet.
share|improve this answer

The function $g(t)$ represent a "section" of the function $f$ along a line. What Boyd is saying is that a function $f$ (a function of several variables) is convex if every restriction on a line is a convex function of one variable.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.