Non Linear Programming 1Linear Programming ModelWhat is a non-linear program?Nonlinear Programs (NLP)Unconstrained Facility LocationAn NLPHere are the objective values for 55 different locations.Facility Location. What happens if P must be within a specified region?The model0-1 integer programs as NLPsSome comments on non-linear modelsVariant of exercise from Bertsimas and FreundPowerPoint PresentationHow long should we keep the machine?Non-linearities Because of TimeNon-linearities in PricingNon-linearities because of congestionNon-linearities because of “penalties”Portfolio OptimizationRisk vs. ReturnExpectations AddVariances do not add (at least not simply)Reducing riskPortfolio Selection (cont’d)Portfolio Selection ExampleSlide 26More on Portfolio SelectionRegressionWriting regression as an NLPSlide 30Slide 31An application of regression to financeRegression, and estimating bSlide 34Solving NLP’s by Excel SolverSummaryMIT and James Orlin © 20031Non Linear Programming 1Nonlinear Programming (NLP)–Modeling ExamplesMIT and James Orlin © 20032Linear Programming Model1 1 2 211 1 12 2 1n n 121 1 22 2 2n n 2m1 1 2 2 mn n mMaximize .....subject to a x + a x + ... +a x ba x + a x + ... +a x b a x + a x + ... +a x b n nmc x c x c xx+ + +���M M M1 2, ,..., 0nx x �ASSUMPTIONS:  Proportionality Assumption–Objective function–Constraints Additivity Assumption–Objective function–ConstraintsMIT and James Orlin © 20033What is a non-linear program?maximize 3 sin x + xy + y3 - 3z + log zSubject to x2 + y2 = 1 x + 4z  2 z  0A non-linear program is permitted to have non-linear constraints or objectives. A linear program is a special case of non-linear programming!MIT and James Orlin © 20034Nonlinear Programs (NLP) Nonlinear objective function f(x) and/or Nonlinear constraints gi(x).Today: we will present several types of non-linear programs.( )1 2 , , , ( ) ( ) , 1, 2, ,ni iLet x x x xMax f xg x b i m= �� " = �MIT and James Orlin © 20035Unconstrained Facility Location0246810121416y0 2 4 6 8 10 12 14 16C(2)(7)BA(19)P ?D (5)x Loc. Dem. A: (8,2) 19B: (3,10) 7C: (8,15) 2D: (14,13) 5P: ?This is the warehouse location problem with a single warehouse that can be located anywhere in the plane. Distances are “Euclidean.”MIT and James Orlin © 20036Costs proportional to distance;known daily demandsAn NLP2 28 2( ) ( )x y- + -d(P,A) =…2 214 13( ) ( )x y- + -d(P,D) =minimize 19 d(P,A) + … + 5 d(P,D)subject to: P is unconstrainedMIT and James Orlin © 20037Here are the objective values for 55 different locations.050100150200250300350valuesfor yObjective valuex = 0x = 2x = 4x = 6x = 8x = 10x = 12MIT and James Orlin © 20038Facility Location. What happens if P must be within a specified region?0246810121416y0 2 4 6 8 10 12 14 16C (2)(7)BA (19)P ?D (5)xMIT and James Orlin © 20039The model2 219 8 2( ) ( )x y- + -2 25 14 13( ) ( )x y- + -+ …+MinimizeSubject to x  7 5  y  11 x + y  24MIT and James Orlin © 2003100-1 integer programs as NLPsminimize j cj xjsubject to j aij xj = bi for all i xj is 0 or 1 for all jis “nearly” equivalent tominimize j cj xj + 106 j xj (1- xj).subject to j aij xj = bi for all i 0  xj  1 for all jMIT and James Orlin © 200311Some comments on non-linear modelsThe fact that non-linear models can model so much is perhaps a bad sign–How can we solve non-linear programs if we have trouble with integer programs?–Recall, in solving integer programs we use techniques that rely on the integrality. Fact: some non-linear models can be solved, and some are WAY too difficult to solve. More on this later.MIT and James Orlin © 200312Variant of exercise from Bertsimas and Freund Buy a machine and keep it for t years, and then sell it. (0  t  10)–all values are measured in $ million–Cost of machine = 1.5–Revenue = 4(1 - .75t) –Salvage value = 1/(1 + t)MIT and James Orlin © 200313Machine values00.511.522.533.544.50.211.82.63.44.255.86.67.48.299.8TimeMillions of dollarsrevenuesalvagetotalMIT and James Orlin © 200314How long should we keep the machine?Work with your partner on how long we should keep the machine, and why?MIT and James Orlin © 200315Non-linearities Because of TimeDiscount ratesdecreasing value of equipment over time –wear and tear, improvements in technologyTax implications (Depreciation)Salvage valueSecondary focus of the previous model(s): Finding the right model can be subtleMIT and James Orlin © 200316Non-linearities in PricingThe price of an item may depend on the number sold –quantity discounts for a small seller–price elasticity for monopolistComplex interactions because of substitutions: –Lowering the price of GM automobiles will decrease the demand for the competitorsMIT and James Orlin © 200317Non-linearities because of congestionThe time it takes to go from MIT to Harvard by car depends non-linearly on the congestion. As congestion increases just to its limit, the traffic sometimes comes to a near halt.MIT and James Orlin © 200318Non-linearities because of “penalties”Consider any linear equality constraint:e.g., 3x1 + 5x2 + 4x3 = 17 Suppose it is a “soft” constraint and we permit solutions violating it. We can then write: 3x1 + 5x2 + 4x3 - y = 17 And we may include a term of –10y2 in the objective function.–This adds flexibility to the solution by discourages violation of our “goals”MIT and James Orlin © 200319Portfolio Optimization In the following slides, we will show how to model portfolio optimization as NLPsThe key concept is that risk can be modeled using non-linear equationsSince this is one of the most famous applications of non-linear programming, we cover it in much more detailMIT and James Orlin © 200320Risk vs. ReturnIn finance, one trades of risk and return. For a given rate of return, one wants to minimize risk. For a given rate of risk, one wants to maximize return.Return is modeled as expected value. Risk is modeled as variance (or standard deviation.)MIT and James Orlin © 200321Expectations AddSuppose that X and Y are random variablesE(X + Y) = E(X) + E(Y)Interpretation: –Suppose that the