Understanding Convex Optimization: Functions, Gradient, and Chain Rule
Explore the fundamentals of convex optimization, including function properties, gradients, chain rule, Jensen's inequality, first and second-order conditions. Learn about continuity, closed functions, derivatives, gradients, and the chain rule in convex functions theory.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 203B: Convex Optimization Week 3 Discuss Session Xinyuan Wang 01/23/2019 1
Contents Related Mathematics (Ref. Appendix A4) Function properties Gradient and chain rule Convex functions (Ref. Chap.3) Jensen s inequality and its extensions First order condition Second order condition 2
Functions and Related Properties For ?:? ? we say that ? is a function on the set dom ? ? into the set ?. ?:?? ??means that the function maps some n-vectors into m-vectors; the dom ? is a subset of ??but not necessarily covers the whole space. Continuity A function ?:?? ??is continuous at ? dom ? if for all ? > 0 there exists a ? such that ? dom ?, ? ? 2 ? Closed function A function ?:?? ? is closed if for each ? ?, the sublevel set ? ??? ? ? ? ?} is closed. Open and closed set: a set ? is open if ? = ??? ?; a set ? ??is closed if its complement ??\? is open. ? ? ? ? 2 ? 3
Derivative and Gradient Suppose ?:?? ??and ? int dom ?. The function ? is differentiable at ? if there exists a matrix ?? ? ?? ?that satisfies ||? ? ? ? ??(?)(? ?)|| lim = 0. ? ? ? dom ?,? ?,? ? 2 - First-order approximation We call ?? ? the derivative (Jacobian) of ? at ? where ?? ???=???(?) , ? = 1, ,?, ? = 1, ,?. ??? The function ? is differentiable if dom ? is open, and differentiable at ? dom ?. Gradient: transpose of derivative (row -> column) ??(?) = ?? ?? first-order approximation ? ? = ? ? + ?? ??(? ?) 4
Derivative and Gradient Suppose ?:?? ? and second-order differentiable ?? ??1 ?? ??? second-order approximation ? ? = ? ? + ?? ??? ? +1 ?2? ??1 ?2? ?2? 2 ??1??? ?2? ??? , Hessian ?2?(?) = Gradient: ??(?) = 2 ?????1 2? ???2?(?)(? ?) Example: calculate the gradient and Hessian of a quadratic function ? ? =1 ??? + ?, where ? ??,? ??,? ?. derivative ?? ? = ??? + ??, gradient ?? ? = ?? + ? Hessian ?2?(?) =??? ? = ? 2???? + 5
Chain Rule Suppose ?:?? ??is differentiable at ? int dom ? and ?:?? ??is differentiable at ?(?) int dom ?. Define the composition :?? ?? ? = ? ? ? . Then is differentiable at ? ? ? = ?? ? ? ??(?) Example: prove the convexity of ? ? = ?(?? + ?) with ??? ? = ? ?? + ? ??? ?}. It is a composition with affine function discussed in class. By the chain rule: ?? ? = ?? ?? + ? ? the gradient ?? ? = ????(?? + ?) the Hessian ?2? ? = ??? ? = ???2? ?? + ? ? 6
Definition of Convex Functions A function ?:?? ? is convex if dom ? is a convex set and if for all ?,? dom ? and 0 ? 1 ? ?? + 1 ? ? ?? ? + 1 ? ?(?) Review the proof in class: necessary and sufficiency sometimes called Jensen s inequality Strict convexity:? ?? + 1 ? ? < ?? ? + 1 ? ? ? ,? ?,0 < ? < 1 Concave functions: ? is convex (?? + 1 ? ?,??(?) + ? ? ?(?)) 7
Example: convexity of functions with definition Necessary: suppose ? is convex, then ? satisfies the basic inequality ? ? + ? ? ? i. ? ? + ?(? ? ? ? ) for 0 ? 1. Integrating both sides from 0 to 1 on ? 1 ? ? + ? ? ? ?? 1 ? ? + ? ? ? ? ??? =? ? + ?(?) 2 0 0 Sufficiency: suppose ? is not convex, then there exists 0 ? 1 and ii. ? ? + ? ? ? > ? ? + ?(? ? ? ? ) ? ? there exist ?,? [0,1] so that in the interval [?,?] the above ? inequality always holds, which contradicts the given inequality. 8
First-order Condition Suppose ? is differentiable (??? ? is open and ?? exists at ? ??? ?), then ? is convex iff dom ? is convex and for all ?,? ??? ? ? ? ? ? + ?? ??(? ?) Review the proof in class: necessary and sufficiency Strict convexity: ? ? > ? ? + ?? ??? ? ,? ? Concave functions: ? ? ? ? + ?? ??(? ?) a global underestimator 9
Second Order Condition Suppose ? is twice differentiable (??? ? is open and its Hessian exists at ? ??? ?), then ? is convex iff dom ? is convex and for all ?,? ??? ? ?2? ? 0 (positive semidefinite) Review the proof in class: necessary and sufficiency Strict convexity:?2? ? 0 Concave functions: ?2? ? 0 10
Example of Convex Functions Quadratic over linear function ? ?,? =?2 ?,for ? > 0 2? ? ?2 ?2 ?? ?? ?? ?? Its gradient ?? ? = = ?2? ??2 ?2? ???? ?2? ???? ?2? ??2 ?2 ?? ?? ?2 2 Hessian ?2? ? = = 0 convex ?3 T, for any ? ?2,?????? = ??????? = ? ? Positive semidefinite? ??? 2 ? ? 2 0. 11
Restriction of a convex function to a line A function ?:?? ? is convex if and only if the function ?:? ?, ? ? = ? ? + ?? , dom ? = ? ? + ?? dom ?} is a convex on its domain for ? dom ?,? ??. The property can be useful to check the convexity of a function ? Example: Prove ? ? = logdet?,dom ? = ?++ is concave. 12
Restriction of a convex function to a line ? Example: Prove ? ? = logdet?,dom ? = ?++ is concave. ?,? ??. Define ? ? = Consider an arbitrary line ? = ? + ??, where ? ?++ ? ? + ?? and restrict ? to the interval values of ? for ? + ?? 0. We have 1 2 ? + ?? 1 2?? 1 2 ?1/2) ? ? = logdet(? + ??) = logdet(? ? The property of eigenvalues det? = ?=1 = log 1 + ??? + logdet? ? ?? ?=1 where ??are the eigenvalues of ? 1 2?? 1 2. So we have ? ? 2 ?? ?? ? ? = ? ? = , 2 0 1 + ??? 1 + ??? ?=1 ?=1 ? ? is concave. For more practice, see Exercise 3.18. 13
Extension of Jensens Inequality The basic inequality can be extended to convex combinations of more than two points. ? ?1?1+ + ???? ?1? ?1 + + ???(??) if ? is convex ?1, ,?? dom ?,?1, ,?? 0 ??? ?1+ + ??= 1. Consider infinite sums and integral ? ? ? ??? ? ? ?(?)?? ? ? where ? ? 0 ?? ? ??? ?, ?? ? ?? = 1. Example with expectation from class ? ?? ??(?) 14
Operations that preserve convexity Practical methods for establishing convexity of a function Verify definition ( often simplified by restricting to a line) For twice differentiable functions, show ?2?(?) 0 Show that ? is obtained from simple convex functions by operations that preserve convexity (Ref. Chap. 3.2) Nonnegative weighted sum Composition with affine function Pointwise maximum and supremum Composition Minimization Perspective 15
