1. WHAT IS OPTIMIZATION?

1 1. 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, minimal error, optimal design,optimal management, variational of the subject:The understanding ofModeling issues What to look for in setting up an optimization problem?What features are advantageous or disadvantageous?What devices/tricks of formulation are available?How can problems usefully be categorized?Analysis of solutions What is meant by a solution?

2 When do solutions exist, and when are they unique?How can solutions be recognized and characterized?What happens to solutions under perturbations?Numerical methods How can solutions be determined by iterative schemes of computation?What modes of local simplification of a problem are convenient/appropriate?How can different solution techniques be compared and evaluated?Distinguishing features of optimization as a mathematical discipline:descriptive prescriptiveequations inequalitieslinear/nonlinear convex/nonconvexdifferential calculus subdifferential calculus1 Finite-dimensional optimization :The case where a choice corresponds to selectingthe values of a finite number of real variables, calleddecision variables.

3 For generalpurposes the decision variables may be denoted byx1, .. , xnand each possible choicetherefore identified with a pointx= (x1, .. , xn) in the spaceIRn. This is what we llbe focusing on in this set:The subsetCofIRnrepresenting the allowable choicesx= (x1, .. , xn).Objective function:The functionf0(x) =f0(x1, .. , xn) that is to be maximized orminimized :Side conditions that are used to specify the feasible constraints:Conditions of the formfi(x) =cifor certain functionsfionIRnand constraints:Conditions of the formfi(x) ciorfi(x) cifor certainfunctionsfionIRnand constraints:Conditions restricting the values of some decision variables to liewithin certain closed intervals ofIR.

4 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:Range constraints or conditions of the formfi(x) =ci,fi(x) ci,orfi(x) ci, in which the function islinearin the standard sense of beingexpressible as sum of constant coefficients times the variablesx1, .. , parameters:General problem statements usually involve not only decision vari-ables but symbols designating known coefficients, constants, or other data ele-ments. Conditions on such elements, such as the nonnegativity of a particularcoefficient, arenotamong the constraints in a problem of optimization , sincethe numbers in question are supposed to be given and aren t subject to programming:A traditional synonym for finite-dimensional optimiza-tion.]

5 This usage predates computer programming, which actually arose from earlyattempts at solving optimization problems on computers. Programming, with themeaning of optimization , survives in problem classifications such as linear program-ming, quadratic programming, convex programming, integer programming, 1: Engineering DesignGeneral 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.

6 Among the choices of the designparameters that meet certain performance specifications, which is the best bysome criterion?Particular case: optimal proportions of a cylindrical can of a givenvolumeV0is to be proportioned in such a way as to minimize the total cost ofthe material in a box of 12 cans, arranged in a 3 4 pattern. The cost expressiontakes the formc1S1+c2S2, whereS1is the surface area of the 12 cans andS2is the surface area of the box. (The coefficientsc1andc2are positive.) A siderequirement 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 (!)

7 Design choices that are available can be identified with the setCconsisting of all the pairs (r, h) IR2that satisfy the conditionsr 0, h 0,8r D0,6r D0, h D0, r2h= this set we wish to minimize the functionf0(r, h) =c1[24 r(r+h)]+c2[4r(24r+ 7h)]=d1r2+d2rh,whered1= 24 c1+ 96c2andd2= 24 c1+ example illustrates several features that are quite typically foundin problems of constraints:It is obvious that the condition 6r D0is implied by theother constraints and therefore could be dropped without affecting the prob-lem. But in problems with many variables and constraints such redundancymay be hard to recognize. From a practical point of view, the elimination ofredundant constraints could pose a challenge as serious as that of solving theoptimization problem constraints:It could well be true that the optimal pair (r, h) (unique?)

8 ?)is such that either the condition 8r D0or the conditionh D0is satisfiedas a strict inequality, or both. In that case the constraints in question areinactive in the local characterization of optimal point, although they do affectthe shape of the setC. Again, however, there is little hope, in a problem withmany variables and constraints, of determining by some preliminary procedurejust which constraints will be active and which will not. This is the crux ofthe difficulty in many numerical variables:It would be possible to solve the equation r2h=V0forhin terms ofrand thereby reduce the given problem to one in terms of justr,rather than (r, h). Fine but besides being a technique that is usable only inspecial circumstances, the elimination of variables from (generally nonlinear)systems of equations is not necessarily helpful.

9 There may be a trade-offbetween the lower dimensionality achieved in this way and other versus equations :The constraint r2h=V0could be written in theform r2h V0without affecting anything about the solution. This is becauseof the 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 to be superior in thepresent case because the setC happens to be convex, whereasCisn :This problem is not fully of convex type in itself, despite the pre-ceding remark.

10 Nonetheless, it can be made convex by a certain change ofvariables, as will be seen later. The lesson is that the formulation of a prob-lem of optimization can be quite subtle, when it comes to bringing out crucialfeatures like 2: Management of SystemsGeneral sequence of decisions must be made in discrete time whichwill affect the operation of some kind of system, often of an economic decisions, each in terms of choosing the values of a number of variables, haveto respect various limitations in resources. Typically the desire is to minimizecost, or maximize profit or efficiency, say, over a certain time case: an inventory warehouse with total capacitya(in unitsof volume) is to be operated over time periodst= 1.