# 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