Convex Optimization — Boyd & Vandenberghe13. Conclusions• main ideas of the course• importance of modeling in optimization13–1Modelingmathematical optimization• problems in engineering design, data analysis and statistics, economics,management, . . . , can often be expressed as mathematicaloptimization problems• techniques exist to take into account multiple objectives or uncertaintyin the datatractability• roughly speaking, tractability in optimization requires convexity• algorithms for nonconvex optimization find local (suboptimal) solutions,or are very expensive• surprisingly many applications can be formulated as convex problemsConclusions 13–2Theoretical consequences of convexity• local optima are global• extensive duality theory– systematic way of deriving lower bounds on optimal value– necessary and sufficient optimality conditions– certificates of infeasibility– sensitivity analysis• solution methods with pol yn omi al worst-c ase compl exi ty theory(with self-concordance)Conclusions 13–3Practical conseque nces of convexity(most) convex problems can be solved globally and efficiently• interior-point methods require 20 – 80 steps in practice• basic algorithms (e.g., Newton, barrier method, . . . ) are easy toimplement and work well for small and medium size problems (largerproblems if structure is exploited)• more and more high-quality implementations of advanced algorithmsand modeling tools are becoming available• high level modeling tool s like cvx ease modeling and problemspecificationConclusions 13–4How to use convex optimizationto use convex optimization in some applied context• use rapid prototyping, approximate modeling– start with simple models, small problem instances, inefficient solutionmethods– if you don’t like the results, no need to expend further effort on moreaccurate models or efficient algorithms• work out, simplify, and interpret optimality conditions and dual• even if the problem is quite nonconvex, you can use convex optimization– in subproblems, e.g., to find search direction– by repeatedly forming and solving a conv ex approxim ati on at thecurrent pointConclusions 13–5Further topicssome topics we di d n’ t cover:• methods for very large scale probl ems• subgradient calculus, convex analysis• localization, subgradient, and related methods• distributed convex optimization• applications that build on or use convex op ti mi za ti onConclusions 13–6What’s next?• EE364B — conve x optimiz ati on II (Spr 13–14)• MATH301 — advanced topics in convex optimization• MS&E314 — li ne ar and conic optimiza tio n• EE464 — semi defi ni te optimi za ti on and algebrai c techni q ue sConclusions