Optimization Techniques in Convex and General Problems
Explore the world of optimization through convex and general problems, understanding the concepts, constraints, and the difference between convex and non-convex optimization. Discover the significance of local and global optima in solving complex optimization challenges.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Convex Optimization Nicholas Ruozzi University of Texas at Dallas
General Optimization min ? ??0(?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? 2
General Optimization min ? ??0(?) ?0 is not necessarily convex subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? 3
General Optimization min ? ??0(?) subject to: Constraints do not need to be linear ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? 4
Example max ? 2 ?1log?1 ?2log?2 subject to: ?1+ ?2= 1 ?1 0 ?2 0 5
Example min ? 2?1log?1+ ?2log?2 subject to: 1 ?1 ?2= 0 ?1 0 ?2 0 6
Convex Optimization min ? ??0(?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? In a convex optimization problem ?0,?1, ,?? must be convex and 1, , ? must be affine, i.e., ?? = ??? + ? 7
Convex Optimization min ? ??0(?) subject to: ??? 0, ?? = 0, ? = 1, ,? ? = 1, ,? The constraints form a convex set: if ?,? ? both satisfy all of the constraints, then so does any ?? + 1 ? ? for ? [0,1] 8
Local and Global Optima Every local optimum of a convex optimization problem is a global optimum: let ? be a local minimum, ? a global minimum, and ? ? > ?(?) ? ? ? 9
Local and Global Optima Every local optimum of a convex optimization problem is a global optimum: let ? be a local minimum, ? a global minimum, and ? ? > ?(?) ? is a local minimum implies that there exists a radius ? such that for all points ? within the ball of radius ? of ?, ? ? ?(? ) ? ? ? 10
Local and Global Optima Every local optimum of a convex optimization problem is a global optimum: let ? be a local minimum, ? a global minimum, and ? ? > ?(?) Let ? = ?? + 1 ? ? ? ? = 2 ? ?2 ? then ? ? ? ? ?2= 1 ? =? ? ?2 2 11
Local and Global Optima Every local optimum of a convex optimization problem is a global optimum: let ? be a local minimum, ? a global minimum, and ? ? > ?(?) By convexity, ? ? ?? ? + 1 ? ? ? < ?(?) ? And ? ? ?(?) ? ? ? So, ? ? < ?(?), a contradiction 12
Local Optima For convex differentiable functions, ? is a local minimum of ?(?) over a convex set ? if the directional is nonnegative along any direction inside the constraint set ? For all ? ?, ? ??? ? 0 Note that if ? ??? ? < 0 for some ? ?, then it must correspond to a descent direction, i.e., if we take a small enough step in this direction, the function will decrease in value 13
Linear Programming Problems For c ?,? ?,A ? ? ? ???? min subject to: ?? ? 14
Quadratic Programming Problems For ? ? ?,c ?,? ?,? ? ? 1 2???? + ??? min ? ? subject to: ?? ? Recall ? must be positive semidefinite for this to be a convex optimization problem 15
Least Squares Regression Given data points ?(1), ,?? and ?(1), ,?? , find the best fit line ? ? 16
Least Squares Regression Given data points ?(1), ,?? and ?(1), ,?? , find the best fit line ? 2 ?? ???+ ? min ?,? ?=1 This is a convex optimization problem, why? 17
Least Squares Regression Given data points ?(1), ,?? and ?(1), ,?? , find the best fit polynomial of degree ? 2 ? ? ????? ?? min ?,? ?=1 ?=0 This is a convex optimization problem, why? 18
Projections Given a set ? ?, the projection of a point ? ? onto ? is the point ? ? such that the distance between ? and ? is less than or equal to the distance between ? and any other ? ? ? ? 19
Projections Given a set ? ?, the projection of a point ? ? onto ? is the point ? ? such that the distance between ? and ? is less than or equal to the distance between ? and any other ? ? min ? ? ? ?2 20
Projections Given a set ? ?, the projection of a point ? ? onto ? is the point ? ? such that the distance between ? and ? is less than or equal to the distance between ? and any other ? ? 2 min ? ? ? ?2 Convex if ? is a convex set, e.g., ? is a line or a plane 21
Projections Given a set ? ?, the projection of a point ? ? onto ? is the point ? ? such that the distance between ? and ? is less than or equal to the distance between ? and any other ? ? 2 min ? ? ? ?2 Can project under different notions of distance as well 22
Smallest Enclosing Ball Find the ball of smallest radius that encloses a collection of points ?(1), ,?? ? 23
Smallest Enclosing Ball Find the ball of smallest radius that encloses a collection of points ?(1), ,?? ? ? ?,? ? min 2 ? for ? = 1, ,? such that ?? ? 2 and ? 0 24
