FUNDAMENTALS OF OPTIMIZATION 2007

1 FUNDAMENTALS OF OPTIMIZATIONLECTURE NOTES2007R. T. RockafellarDept. of MathematicsUniversity of WashingtonSeattleCONTENTS1. What is OPTIMIZATION ?12. Problem Formulation153. Unconstrained Minimization334. Constrained Minimization495. Lagrange Multipliers656. Games and Duality90X. Exercises1161. WHAT IS OPTIMIZATION ? OPTIMIZATION problem:Maximizing or minimizing some function relative to some set,often representing a range of choices available in a certain situation. The functionallows comparison of the different choices for determining which might be best. Common applications:Minimal cost, maximal profit, best approximation, optimal de-sign, optimal management or control, variational of the subject:Understanding the practical and theoretical aspects of:Modeling issues:What to look for in setting up an OPTIMIZATION problem?

2 What fea-tures are advantageous or disadvantageous? What aids to formulation are avail-able? How can problems usefully be categorized?Analysis of solutions:What is meant by a solution? When do solutions exist, andwhen are they unique? How can solutions be recognized and characterized? Whathappens to solutions under perturbations?Numerical methods:How can solutions be determined by iterative schemes of compu-tation? What modes of local simplification of a problem are appropriate? Howcan different solution techniques be compared and evaluated?Distinguishing features of OPTIMIZATION as a mathematical discipline:Descriptive math prescriptive math:Much of mathematics in the past has beendevoted to describing how systems behave, in the laws of physics. The adventof computers, however, has brought an emphasis on using mathematics to makesystems behave inchosenways, and choices lead to questions of inequalities: OPTIMIZATION typically deals with variables that have to liewithin certain ranges, dictated by the limitations of what choices are allowable,and this leads to a dominance of relationships that are expressed by inequalitiesrather than convex /nonconvex:The familiar division between linearity andnonlinearity is less important in OPTIMIZATION than the one between convexity andnonconvexity, which for its appreciation requires a new investment in calculus subdifferential calculus.

3 The prevalence of inequalities, alongwith the special properties of max and min as operations, raise the need fora methodology that doesn t rely so much as classical mathematics on supposingsurfaces to be smooth and functions to be differentiable OPTIMIZATION :The case where a choice corresponds to selecting thevalues of a finite number of real variables, calleddecision variables. For purposes ofgeneral discussion, such as now, the decision variables may be denoted byx1,..,xnand each allowable choice therefore identified with a pointx= (x1,..,xn) :The pointsxrepresenting allowable choices are said to befeasible. Theyform the subset ofIRnover which the maximization or minimization takes :Conditions on the decision variables that are used to specify the set offeasible and inequality constraints:Conditions of the formfi(x) =ci,fi(x) ciorfi(x) cifor certain functionsfionIRnand constantsciinIR.

4 (Note: Strictinequalities are avoided in constraints, for reasons which will be clear later.)Range constraints:Conditions restricting the values of some decision variables to liewithin certain closed intervals ofIR. Very important in many situations, forinstance, arenonnegativity constraints: some variablesxjmay only be allowedto take values 0; the interval then is [0, ). Range constraints can also arisefrom the desire to keep a variable between certain upper and lower constraints:This covers range constraints and conditionsfi(x) =ci,fi(x) ci,orfi(x) ci, in which the functionfiislinear in the standard sense of beingexpressible as sum of constant coefficients times the variablesx1,.., parameters:Problem statements usually involve not only decision variables butsymbols designating given constants and coefficients.]

5 Conditions on such ele-ments, such as the nonnegativity of a particular coefficient, arenotamong the constraints in a problem of OPTIMIZATION , however crucial they may be fromsome other and unknowns:A good way to think about the important distinction betweendecision variables and data parameters is as follows. This may help you throughconfusing situations where certain parameters might actually be decision variablesand certain variables actually data parameters. In practice, of course, all kinds ofsymbols besidesxget used, and it can get hard to tell things decision variables in an OPTIMIZATION problem are unknowns that are opento manipulation in the process of maximization or minimization, whereas the dataparameters aren t open to manipulation when it comes to solving a particular prob-lem, but instead would be furnished with specific numerical values as inputs to anysolution programming:This is a synonym for finite-dimensional usage predates computer programming, which actually arose from attempts atsolving OPTIMIZATION problems on early computers.

6 Programming, in the senseof OPTIMIZATION , survives in problem classifications such as linear programming,quadratic programming, convex programming, integer programming, and so 1: Engineering designGeneral description:In the design of some object, system or structure, the valuesof certain parameters can be chosen subject to some conditions expressing theirranges and interrelationships. The choice determines the values of a number ofother variables on which the desirability of the end product depends, such ascost, weight, speed, bandwidth, reliability,.. Among the choices of the designparameters that meet certain performance specifications, what s best by someoverall criterion?An illustration, optimal proportions of a can:The following example, althoughtoy-sized, brings out many features of OPTIMIZATION modeling.

7 A cylindrical canof a given volumeV0is to be proportioned in such a way as to minimize the totalcost of the material in a box of 12 cans, arranged in a 3 4 pattern. The costexpression takes the formc1S1+c2S2, whereS1is the surface area of the 12 cansandS2is the surface area of the box. The coefficientsc1andc2are side requirement is that no dimension of the box can exceed a given parameters:r= radius of can,h= height of canvolume constraint: r2h=V0(or V0, see below!)surface area of cans:S1= 12(2 r2+ 2 rh) = 24 r(r+h)box dimensions:8r 6r hsurface area of box:S2= 2(48r2+ 8rh+ 6rh) = 4r(24r+ 7h)size constraints:8r D0,6r D0, h D0nonnegativity constraints:r 0, h 0 (!)Summary:The decision variables arerandh, and the choices that are available canbe identified with the setC IR2consisting of all (r,h) satisfying the conditionsr 0, h 0,8r D0,6r D0, h D0, r2h= first five conditions can be thought of as range constraints and the sixth asan equality constraint onf1(r,h) = r2h.

8 Over the setCwe wish to minimizef0(r,h) =c1[24 r(r+h)]+c2[4r(24r+ 7h)]=d1r2+d2rh,3whered1= 24 c1+ 96c2andd2= 24 c1+ 28c2. The symbolsV0,D0,c1andc2,and ultimatelyd1andd2, are data parameters. Althoughc1 0 andc2 0, thesearen t constraints in the problem. As forS1andS2, they were only introducedas temporary symbols and didn t end up as decision constraints:It is obvious that the condition 6r D0is implied by the otherconstraints and therefore could be dropped without affecting the problem. Butin problems with many variables and constraints such redundancy may be hardto recognize. The elimination of redundant constraints could pose a practicalchallenge as serious as that of solving the OPTIMIZATION problem constraints:It could well be true that the optimal pair (r,h) (unique??) is suchthat either the condition 8r D0or the conditionh D0is satisfied as a strictinequality, or both.

9 In that case the constraints in question are inactive in thelocal characterization of optimal point, although they do affect the shape of thesetC. Again, however, there is little hope, in a problem with many variables andconstraints, of determining by some preliminary procedure just which constraintswill be active and which will not. This is the crux of the difficulty in manynumerical variables:It would be possible to solve the equation r2h=V0forhinterms ofrand thereby reduce the given problem to one in terms of justr, ratherthan (r,h). Fine but besides being a technique that is usable only in specialcircumstances, the elimination of variables from (generally nonlinear) systems ofequations is not necessarily helpful. There may be a trade-off between the lowerdimensionality achieved in this way and other versus equations:The constraint r2h=V0could be written in the form r2h V0without affecting anything about the solution.

10 This is because ofthe nature of the cost function; no pair (r,h) in the larger setC , obtainedby substituting this weaker condition for the equation, can minimizef0unlessactually (r,h) C. While it may seem instinctive to prefer the equation tothe inequality in the formulation, the inequality turns out to be superior in thepresent case because the setC happens to be convex , whereasCisn :Even with the reformulation just suggested, the problem wouldn t be fullyof convex type because the function ofrandhbeing minimized isn t itself con-vex ; further maneuvers might get around that. The lesson is that the formulationof a problem can be subtle, when it comes to bringing out features of importancein OPTIMIZATION . Knowledge and experience play a valuable 2: Utilization of ResourcesGeneral description:Actions are to be taken that hopefully will result in profit, butthese actions, which correspond to selecting the values of a number of variables,draw on some limited resources.