Mixing
What is the condition to have a Lipschitz continuous the gradient for convex function?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
According to Prof. Vandenberg's lecture notes [http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf], page 11, a function is called Lipschitz continuous gradient when
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Note that the definition does not assume that $f$ is a convex function.
However, if $f$ is a convex function we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
Can we prove the reverse, i.e., if we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
then
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Hint: using $
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$ we can conclude that $g(x)=fracalpha2|x|_2^2-f(x)$ is convex. Since $g(x)$ is convex, monotonicity of the gradient of $g$ results in
$$
langle nabla f(x) - f(y),y-x rangle leq alpha|y-x|_2^2
$$
but how is possible to get back to the following?
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
I am wondering if the above method is right way to prove it. In addition, is there any other condition that can be applied to the convex function $f(x)$ to have Lipschitz continuous gradient?
convex-analysis convex-optimization
asked Jul 18 at 20:47
Saeed
887
add a comment |Â
up vote
0
down vote
favorite
According to Prof. Vandenberg's lecture notes [http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf], page 11, a function is called Lipschitz continuous gradient when
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Note that the definition does not assume that $f$ is a convex function.
However, if $f$ is a convex function we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
Can we prove the reverse, i.e., if we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
then
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Hint: using $
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$ we can conclude that $g(x)=fracalpha2|x|_2^2-f(x)$ is convex. Since $g(x)$ is convex, monotonicity of the gradient of $g$ results in
$$
langle nabla f(x) - f(y),y-x rangle leq alpha|y-x|_2^2
$$
but how is possible to get back to the following?
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
I am wondering if the above method is right way to prove it. In addition, is there any other condition that can be applied to the convex function $f(x)$ to have Lipschitz continuous gradient?
convex-analysis convex-optimization
asked Jul 18 at 20:47
Saeed
887
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
According to Prof. Vandenberg's lecture notes [http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf], page 11, a function is called Lipschitz continuous gradient when
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Note that the definition does not assume that $f$ is a convex function.
However, if $f$ is a convex function we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
Can we prove the reverse, i.e., if we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
then
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Hint: using $
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$ we can conclude that $g(x)=fracalpha2|x|_2^2-f(x)$ is convex. Since $g(x)$ is convex, monotonicity of the gradient of $g$ results in
$$
langle nabla f(x) - f(y),y-x rangle leq alpha|y-x|_2^2
$$
but how is possible to get back to the following?
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
I am wondering if the above method is right way to prove it. In addition, is there any other condition that can be applied to the convex function $f(x)$ to have Lipschitz continuous gradient?
convex-analysis convex-optimization
asked Jul 18 at 20:47
Saeed
887
According to Prof. Vandenberg's lecture notes [http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf], page 11, a function is called Lipschitz continuous gradient when
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Note that the definition does not assume that $f$ is a convex function.
However, if $f$ is a convex function we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
Can we prove the reverse, i.e., if we have
$$
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$$
then
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
Hint: using $
f(y) leq f(x) + langle nabla f(x),y-x rangle + fracalpha2|y-x|_2^2
$ we can conclude that $g(x)=fracalpha2|x|_2^2-f(x)$ is convex. Since $g(x)$ is convex, monotonicity of the gradient of $g$ results in
$$
langle nabla f(x) - f(y),y-x rangle leq alpha|y-x|_2^2
$$
but how is possible to get back to the following?
$$
|nabla f(y)-nabla f(x)|_2 leq alpha|y-x|_2
$$
I am wondering if the above method is right way to prove it. In addition, is there any other condition that can be applied to the convex function $f(x)$ to have Lipschitz continuous gradient?
convex-analysis convex-optimization
asked Jul 18 at 20:47
Saeed
887
asked Jul 18 at 20:47
Saeed
887
asked Jul 18 at 20:47
Saeed
887
asked Jul 18 at 20:47
Saeed
887
887
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
No. Intuitively, a function is Lipschitz means that the derivative is continuous. (It's a bit stronger, even.) Consider the function $f:mathbbRrightarrowmathbbR$ such that $f(x)=|x|$. This function is convex, but its derivative is not continuous, therefore it is not Lipschitz.
answered Jul 18 at 20:52
NicNic8
3,7113922
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
No. Intuitively, a function is Lipschitz means that the derivative is continuous. (It's a bit stronger, even.) Consider the function $f:mathbbRrightarrowmathbbR$ such that $f(x)=|x|$. This function is convex, but its derivative is not continuous, therefore it is not Lipschitz.
answered Jul 18 at 20:52
NicNic8
3,7113922
add a comment |Â
up vote
0
down vote
No. Intuitively, a function is Lipschitz means that the derivative is continuous. (It's a bit stronger, even.) Consider the function $f:mathbbRrightarrowmathbbR$ such that $f(x)=|x|$. This function is convex, but its derivative is not continuous, therefore it is not Lipschitz.
answered Jul 18 at 20:52
NicNic8
3,7113922
add a comment |Â
up vote
0
down vote
up vote
0
down vote
No. Intuitively, a function is Lipschitz means that the derivative is continuous. (It's a bit stronger, even.) Consider the function $f:mathbbRrightarrowmathbbR$ such that $f(x)=|x|$. This function is convex, but its derivative is not continuous, therefore it is not Lipschitz.
answered Jul 18 at 20:52
NicNic8
3,7113922
No. Intuitively, a function is Lipschitz means that the derivative is continuous. (It's a bit stronger, even.) Consider the function $f:mathbbRrightarrowmathbbR$ such that $f(x)=|x|$. This function is convex, but its derivative is not continuous, therefore it is not Lipschitz.
answered Jul 18 at 20:52
NicNic8
3,7113922
answered Jul 18 at 20:52
NicNic8
3,7113922
answered Jul 18 at 20:52
NicNic8
3,7113922
answered Jul 18 at 20:52
NicNic8
3,7113922
3,7113922
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855986%2fwhat-is-the-condition-to-have-a-lipschitz-continuous-the-gradient-for-convex-fun%23new-answer', 'question_page');
);
Post as a guest
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
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
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