Optimization: Theory, Algorithms, Applications

1 optimization : theory , Algorithms, Applications MSRI - Berkeley SAC, Nov/06. Henry Wolkowicz Department of Combinatorics & optimization University of Waterloo optimization : theory , Algorithms, Applications Outline Why are we here? (What is optimization ?). History of optimization Main Players Most important Open Problems Different Areas for connections Resources/References optimization : theory , Algorithms, Applications What is optimization ? Two quotes from Tjalling C. Koopmans, Nobel Memorial Lecture: [22]. best use of scarce resources.

2 Mathematical Methods of Organizing and Planning of Production", [18]. - (Kantorovich and K.: joint winners Nobel Prize Economics 1975, "for their contributions to the theory of optimum allocation of resources"). optimization : theory , Algorithms, Applications History Virgil's Aeneid 19 BCE, Legend of Carthage Queen Dido's Problem: Queen fled to African coast after husband killed; she begged King Jambas (local ruler). for land; he granted only as much as she could enclose within a bull's hide; she sliced the hide into strips; used the strips to surround a large area.

3 Optimal shape was ? - In 3-dimensions: soap bubbles and films are examples of minimal surface areas. optimization : theory , Algorithms, Applications The Brachistochrone Problem cycloid or curve of fastest descent;. stationary body starts at first point and passes down along curve to second point, under action of constant gravity, ignoring friction. Bernoulli (1696)/Calculus of Variations Figure 1: Cycloid optimization : theory , Algorithms, Applications History of Math. Progr., 1991 [26]. remarkably short - rooted in Applications 1940's - driven by Applications (war time - moving men and machinery).

4 Dantzig (Pentagon - Stanford) and Kantorovich (Leningrad). Others: Hitchcock, Koopmans, Arrow, Charnes, Gale, Goldman, Hoffman, Kuhn, von Neumann (game theory , duality, computers) optimization : theory , Algorithms, Applications Dantzig/Linear Programming, LP. Planning problems: Assign 70 men to 70 jobs; vij benefit of man i assigned to job j (Linear Assignment Problem, LAP). but 70! > 10100 (a googol). Dantzig visited Von Neumann - Oct 3, 1947 - learned about Farkas' Lemma, Duality (game theory ) - SIMPLEX METHOD for LP. - Hotteling: But we all know the world is nonlinear.

5 Von Neumann: .. if linear application .. use it optimization : theory , Algorithms, Applications Unreasonable Success of Simplex LP min cT x Ax = b, x 0. Klee-Minty 1970: exponential time example for simplex method. But, linear time in practice. SIAM 70s computer survey: 70% of (world). computer time spent on LP/simplex Is LP in class P (easy) or class NP (hard)? Russian Mathematician Khachian 1978: LP. algorithm based on ellipsoids/duality/inequalities showed LP is in P. (NYT frontpage stories/fables). Hungarian method for LAP in O(n3 ) time, [23, 31]; BUT - still no known strongly polynomial method for general LP.

6 optimization : theory , Algorithms, Applications A First Meeting Figure 2: George B. Dantzig and Leonid Khachiyan, meeting for the first time, February 1990, Asilomar, Cali- fornia, at the SIAM-organized workshop Progress in Math- ematical Programming. 2005: Khachiyan died Apr 29 (age 52). Dantzig died May 13 (age 90). optimization : theory , Algorithms, Applications Lagrange Multiplier Extensions NLP: MOTIVATED by LP Success [24]. [25] 1951: Kuhn-Tucker optimality conditions for nonlinear programming (NLP). [20] 1939: Karush, Masters Thesis, Math.

7 , Univ. Chicago (Same constraint qualification). [17] 1948: Fritz John, Extremum problems with optimization : theory , Algorithms, Applications K-K-T Conditions NLP min f (x) g(x) 0, h(x) = 0. CQ: Geometry (cone of tangents) coincides with algebra (linearization) (modern opt cond). f (x ) + g (x ) + h (x ) = 0, 0, dual feas h(x ) = 0, g(x ) 0, primal feas. g(x )T = 0, compl. slack. Proof: Apply Farkas' Lemma, 1902, to local linearization. (modern: use hyperplane separation 's geometric Hahn-Banach Theorem.). optimization : theory , Algorithms, Applications Further Extensions Infinite (Cone) Programs, Duffin, 1956 [6].

8 optimization with respect to partial orders, [15, 36, 16, 28, 14]. Optimal Control (Pontryagin Maximum Principle). Discrete/Combinatorial optimization FIRST CHANCES. - QUESTIONS? DISCUSSION? optimization : theory , Algorithms, Applications NEOS/Argonne/Solvers Figure 3: optimization Tree, optimization : theory , Algorithms, Applications Quasi-Newton Methods For Unconstrained optimization : Least Change Secant Methods, Variable Metric Methods Davidon'59[5]/Fletcher-Powell'63[10]. (DFP), and Broyden[4]/Fletcher[9]/Goldfarb[13]/Shan no[34].

9 '70/(BFGS). rank-two updates of Hessian, maintains positive definite Hessian approximations But: automatic differentiation Griewank-Corliss'91 differentiates the code efficiently. optimization : theory , Algorithms, Applications Power of Duality Find optimal trajectory/control (for rocket). 1 2. R. 1 t1 2. 0 = min J(u) = 2 ku(t)k = 2 t0 u (t)dt x (t) = A(t)x(t) + b(t)u(t). x(t0 ) = x0 , x(t1 ) c. Using fundamental solution matrix . Z t1. x(t1 ) = (t1 , t0 )x(t0 ) + (t1 , t)u(t)b(t)dt t0. | {z }. integral oper. Ku optimization : theory , Algorithms, Applications Duality (.)

10 Min J(u) = 21 ku(t)k2. Convex Pgm Ku d Lagrangian dual (best lower bound) is 0 = max 0 minu {J(u) + T (d Ku)}. = max 0 T Q + T d simple FIN. dim. QP. R. 1 t1. where Q = 2 t0 (t1 , t)b(t)b(t)T (t1 , t)dt u (t) = T (t1 , t)b(t). optimization : theory , Algorithms, Applications Convex Analysis Lies behind results in optimization Classic '70 text by Rockafellar (UofW, Seattle), [33];. Nonsmooth Analysis: Clarke, Borwein (Smooth Variational Principle), Mordukhovich, Lewis Variational Principles (powerful optimality conditions, extensions to nonconvex case).