Proving characterization of convexity as “first order Taylor approximation is a global underestimate”
up vote
1
down vote
favorite
From Boyd and Vanderbei's Convex Optimization, a differentiable function $f$ is convex iff $dom f$ is convex and for all $x,yin dom f$,
$$f(y)ge f(x)+nabla f(x)^T(y-x).$$
I am having trouble following their proof that this latter condition implies convexity, assuming $f$ is a single variable function. I will outline their argument and explain where I fall off:
They start out by picking $thetain[0,1]$, and $x,yin dom f$. If $f$ is a single-variable function, the assumed equality tells us that $theta f(x)ge theta f(z)+theta f'(z)(x-z)$ and $(1-theta)f(y)ge (1-theta) f(z)+(1-theta)f'(z)(y-z)$. We are supposed to add these inequalities to show $f$ is convex, i.e. $theta f(x)+(1-theta) f(y)ge f(z)$. So it must be the case that $theta f'(z)(x-z)+(1-theta)f'(z)(y-z)ge 0$. I'm not able to show this.
Any help is greatly appreciated. Thanks in advance.
real-analysis convex-optimization
add a comment |
up vote
1
down vote
favorite
From Boyd and Vanderbei's Convex Optimization, a differentiable function $f$ is convex iff $dom f$ is convex and for all $x,yin dom f$,
$$f(y)ge f(x)+nabla f(x)^T(y-x).$$
I am having trouble following their proof that this latter condition implies convexity, assuming $f$ is a single variable function. I will outline their argument and explain where I fall off:
They start out by picking $thetain[0,1]$, and $x,yin dom f$. If $f$ is a single-variable function, the assumed equality tells us that $theta f(x)ge theta f(z)+theta f'(z)(x-z)$ and $(1-theta)f(y)ge (1-theta) f(z)+(1-theta)f'(z)(y-z)$. We are supposed to add these inequalities to show $f$ is convex, i.e. $theta f(x)+(1-theta) f(y)ge f(z)$. So it must be the case that $theta f'(z)(x-z)+(1-theta)f'(z)(y-z)ge 0$. I'm not able to show this.
Any help is greatly appreciated. Thanks in advance.
real-analysis convex-optimization
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
From Boyd and Vanderbei's Convex Optimization, a differentiable function $f$ is convex iff $dom f$ is convex and for all $x,yin dom f$,
$$f(y)ge f(x)+nabla f(x)^T(y-x).$$
I am having trouble following their proof that this latter condition implies convexity, assuming $f$ is a single variable function. I will outline their argument and explain where I fall off:
They start out by picking $thetain[0,1]$, and $x,yin dom f$. If $f$ is a single-variable function, the assumed equality tells us that $theta f(x)ge theta f(z)+theta f'(z)(x-z)$ and $(1-theta)f(y)ge (1-theta) f(z)+(1-theta)f'(z)(y-z)$. We are supposed to add these inequalities to show $f$ is convex, i.e. $theta f(x)+(1-theta) f(y)ge f(z)$. So it must be the case that $theta f'(z)(x-z)+(1-theta)f'(z)(y-z)ge 0$. I'm not able to show this.
Any help is greatly appreciated. Thanks in advance.
real-analysis convex-optimization
From Boyd and Vanderbei's Convex Optimization, a differentiable function $f$ is convex iff $dom f$ is convex and for all $x,yin dom f$,
$$f(y)ge f(x)+nabla f(x)^T(y-x).$$
I am having trouble following their proof that this latter condition implies convexity, assuming $f$ is a single variable function. I will outline their argument and explain where I fall off:
They start out by picking $thetain[0,1]$, and $x,yin dom f$. If $f$ is a single-variable function, the assumed equality tells us that $theta f(x)ge theta f(z)+theta f'(z)(x-z)$ and $(1-theta)f(y)ge (1-theta) f(z)+(1-theta)f'(z)(y-z)$. We are supposed to add these inequalities to show $f$ is convex, i.e. $theta f(x)+(1-theta) f(y)ge f(z)$. So it must be the case that $theta f'(z)(x-z)+(1-theta)f'(z)(y-z)ge 0$. I'm not able to show this.
Any help is greatly appreciated. Thanks in advance.
real-analysis convex-optimization
real-analysis convex-optimization
asked Nov 19 at 20:02
manofbear
1,554514
1,554514
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
The estimates are applied to $x, y$, and $z= theta x + (1-theta) y$.
Adding the inequalities gives
$$
theta f(x) + (1-theta) f(y)ge f(z) + bigl(underbrace{theta (x-z) + (1-theta) (y-z)}_{=0}bigr) f'(z) = f(z) , .
$$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
The estimates are applied to $x, y$, and $z= theta x + (1-theta) y$.
Adding the inequalities gives
$$
theta f(x) + (1-theta) f(y)ge f(z) + bigl(underbrace{theta (x-z) + (1-theta) (y-z)}_{=0}bigr) f'(z) = f(z) , .
$$
add a comment |
up vote
2
down vote
accepted
The estimates are applied to $x, y$, and $z= theta x + (1-theta) y$.
Adding the inequalities gives
$$
theta f(x) + (1-theta) f(y)ge f(z) + bigl(underbrace{theta (x-z) + (1-theta) (y-z)}_{=0}bigr) f'(z) = f(z) , .
$$
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
The estimates are applied to $x, y$, and $z= theta x + (1-theta) y$.
Adding the inequalities gives
$$
theta f(x) + (1-theta) f(y)ge f(z) + bigl(underbrace{theta (x-z) + (1-theta) (y-z)}_{=0}bigr) f'(z) = f(z) , .
$$
The estimates are applied to $x, y$, and $z= theta x + (1-theta) y$.
Adding the inequalities gives
$$
theta f(x) + (1-theta) f(y)ge f(z) + bigl(underbrace{theta (x-z) + (1-theta) (y-z)}_{=0}bigr) f'(z) = f(z) , .
$$
answered Nov 19 at 20:11
Martin R
26.1k33047
26.1k33047
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005445%2fproving-characterization-of-convexity-as-first-order-taylor-approximation-is-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown