NUMERICAL OPTIMIZATION
CHAPTER 1 INTRODUCTION 1 CHAPTER 2 FUNDAMENTALS OF UNCONSTRAINED OPTIMIZATION 11 CHAPTER 3 LINE SEARCH METHODS 34 CHAPTER 4 TRUST REGION METHODS 64 CHAPTER 5 CONJUGATE GRADIENT METHODS 100 CHAPTER 6 PRACTICAL NEWTON METHODS 134 CHAPTER 7 CALCULATING DERIVATIVES 164 CHAPTER 8 QUASI NEWTON METHODS 192 CHAPTER 9 LARGE SCALE QUASI NEWTON AND PARTIALLY SEPARABLE OPTIMIZATION 222 CHAPTER 10 NONLINEAR LEAST SQUARES PROBLEMS 250 CHAPTER 11 NONLINEAR EQUATIONS 276 CHAPTER 12 THEORY OF CONSTRAINED OPTIMIZATION 313 CONTENTS CHAPTER 13 LINEAR PROGRAMMING THE SIMPLEX METHOD 359 CHAPTER 14 LINEAR PROGRAMMING INTERIOR POINT METHODS 391 CHAPTER 15 FUNDAMENTALS OF ALGORITHMS FOR NONLINEAR CONSTRAINED OPTIMIZATION 417 CHAPTER 16 QUADRATIC PROGRAMMING 437 CHAPTER 17 PENALTY BARRIER AND AUGMENTED LAGRANGIAN METHODS 486 CHAPTER 18 SEQUENTIAL QUADRATIC PROGRAMMING 524 INTRODUCTION PEOPLE OPTIMIZE AIRLINE COMPANIES SCHEDULE CREWS AND AIRCRAFT TO MINIMIZE COST INVESTORS SEEK TO CREATE PORTFOLIOS THAT AVOID EXCESSIVE RISKS WHILE ACHIEVING A HIGH RATE OF RETURN MANUFACTURERS AIM FOR MAXIMUM EF CIENCY IN THE DESIGN AND OPERATION OF THEIR PRODUCTION PROCESSES NATURE OPTIMIZES PHYSICAL SYSTEMS TEND TO A STATE OF MINIMUM ENERGY THE MOLECULES IN AN ISOLATED CHEMICAL SYSTEM REACT WITH EACH OTHER UNTIL THE TOTAL POTENTIAL ENERGY OF THEIR ELECTRONS IS MINIMIZED RAYS OF LIGHT FOLLOW PATHS THAT MINIMIZE THEIR TRAVEL TIME OPTIMIZATION IS AN IMPORTANT TOOL IN DECISION SCIENCE AND IN THE ANALYSIS OF PHYSICAL SYSTEMS TO USE IT WE MUST RST IDENTIFY SOME OBJECTIVE A QUANTITATIVE MEASURE OF THE PER FORMANCE OF THE SYSTEM UNDER STUDY THIS OBJECTIVE COULD BE PRO T TIME POTENTIAL ENERGY OR ANY QUANTITY OR COMBINATION OF QUANTITIES THAT CAN BE REPRESENTED BY A SINGLE NUMBER THE OBJECTIVE DEPENDS ON CERTAIN CHARACTERISTICS OF THE SYSTEM CALLED VARIABLES OR UNKNOWNS OUR GOAL IS TO ND VALUES OF THE VARIABLES THAT OPTIMIZE THE OBJECTIVE OFTEN THE VARIABLES ARE RESTRICTED OR CONSTRAINED IN SOME WAY FOR INSTANCE QUANTITIES SUCH AS ELECTRON DENSITY IN A MOLECULE AND THE INTEREST RATE ON A LOAN CANNOT BE NEGATIVE THE PROCESS OF IDENTIFYING OBJECTIVE VARIABLES AND CONSTRAINTS FOR A GIVEN PROBLEM IS KNOWN AS MODELING CONSTRUCTION OF AN APPROPRIATE MODEL IS THE RST STEP SOMETIMES THE CHAPTER1 1 MOST IMPORTANT STEP IN THE OPTIMIZATION PROCESS IF THE MODEL IS TOO SIMPLISTIC IT WILL NOT GIVE USEFUL INSIGHTS INTO THE PRACTICAL PROBLEM BUT IF IT IS TOO COMPLEX IT MAY BECOME TOO DIF CULT TO SOLVE ONCE THE MODEL HAS BEEN FORMULATED AN OPTIMIZATION ALGORITHM CAN BE USED TO ND ITS SOLUTION USUALLY THE ALGORITHM AND MODEL ARE COMPLICATED ENOUGH THAT A COMPUTER IS NEEDED TO IMPLEMENT THIS PROCESS THERE IS NO UNIVERSAL OPTIMIZATION ALGORITHM RATHER THERE ARE NUMEROUS ALGORITHMS EACH OF WHICH IS TAILORED TO A PARTICULAR TYPE OF OPTIMIZATION PROBLEM IT IS OFTEN THE USER S RESPONSIBILITY TO CHOOSE AN ALGORITHM THAT IS APPROPRIATE FOR THEIR SPECI C APPLICATION THIS CHOICE IS AN IMPORTANT ONE IT MAY DETERMINE WHETHER THE PROBLEM IS SOLVED RAPIDLY OR SLOWLY AND INDEED WHETHER THE SOLUTION IS FOUND AT ALL AFTER AN OPTIMIZATION ALGORITHM HAS BEEN APPLIED TO THE MODEL WE MUST BE ABLE TO RECOGNIZE WHETHER IT HAS SUCCEEDED IN ITS TASK OF NDING A SOLUTION IN MANY CASES THERE ARE ELEGANT MATHEMATICAL EXPRESSIONS KNOWN AS OPTIMALITY CONDITIONS FOR CHECKING THAT THE CURRENT SET OF VARIABLES IS INDEED THE SOLUTION OF THE PROBLEM IF THE OPTIMALITY CONDITIONS ARE NOTSATIS ED THEYMAYGIVEUSEFULINFORMATIONONHOWTHECURRENTESTIMATEOFTHESOLUTIONCAN BE IMPROVED FINALLY THE MODEL MAY BE IMPROVED BY APPLYING TECHNIQUES SUCH AS SENSITIVITY ANALYSIS WHICH REVEALS THE SENSITIVITY OF THE SOLUTION TO CHANGES IN THE MODEL AND DATA MATHEMATICAL FORMULATION MATHEMATICALLY SPEAKING OPTIMIZATION IS THE MINIMIZATION OR MAXIMIZATION OF A FUNCTION SUBJECT TO CONSTRAINTS ON ITS VARIABLES WE USE THE FOLLOWING NOTATION X IS THE VECTOR OF VARIABLES ALSO CALLED UNKNOWNS OR PARAMETERS F IS THE OBJECTIVE FUNCTION A FUNCTION OF X THAT WE WANT TO MAXIMIZE OR MINIMIZE C IS THE VECTOR OF CONSTRAINTS THAT THE UNKNOWNS MUST SATISFY THIS IS A VECTOR FUNCTION OF THEVARIABLESX THENUMBEROFCOMPONENTSINC ISTHENUMBEROFINDIVIDUALRESTRICTIONS THAT WE PLACE ON THE VARIABLES THE OPTIMIZATION PROBLEM CAN THEN BE WRITTEN AS MIN X IRN F X SUBJECT TO CI X 0 I E CI X 0 I I 1 1 HERE F AND EACH CI ARE SCALAR VALUED FUNCTIONS OF THE VARIABLES X AND I E ARE SETS OF INDICES AS A SIMPLE EXAMPLE CONSIDER THE PROBLEM MIN X1 2 2 X2 1 2 SUBJECT TO X2 1 X2 0 X1 X2 2 1 2 2 X F C1 C2 CONTOURS OF X X1 FEASIBLE REGION 2 FIGURE 1 1 GEOMETRICAL REPRESENTATION OF AN OPTIMIZATION PROBLEM WE CAN WRITE THIS PROBLEM IN THE FORM 1 1 BY DE NING F X X1 2 2 X2 1 2 X X1 X2 C X C1 X C2 X X2 1 X2 X1 X2 2 I 1 2 E FIGURE 1 1 SHOWS THE CONTOURS OF THE OBJECTIVE FUNCTION I E THE SET OF POINTS FOR WHICH F X HAS A CONSTANT VALUE IT ALSO ILLUSTRATES THE FEASIBLE REGION WHICH IS THE SET OF POINTS SATISFYING ALL THE CONSTRAINTS AND THE OPTIMAL POINT X THE SOLUTION OF THE PROBLEM NOTE THAT THE INFEASIBLE SIDE OF THE INEQUALITY CONSTRAINTS IS SHADED THE EXAMPLE ABOVE ILLUSTRATES TOO THAT TRANSFORMATIONS ARE OFTEN NECESSARY TO EXPRESS AN OPTIMIZATION PROBLEM IN THE FORM 1 1 OFTEN IT IS MORE NATURAL OR CONVENIENT TO LABEL THE UNKNOWNS WITH TWO OR THREE SUBSCRIPTS OR TO REFER TO DIFFERENT VARIABLES BY COMPLETELY DIFFERENT NAMES SO THAT RELABELING IS NECESSARY TO ACHIEVE THE STANDARD FORM ANOTHER COM MON DIFFERENCE IS THAT WE ARE REQUIRED TO MAXIMIZE RATHER THAN MINIMIZE F BUT WE CAN ACCOMMODATE THIS CHANGE EASILY BY MINIMIZING F IN THE FORMULATION 1 1 GOOD SOFTWARE SYSTEMS PERFORM THE CONVERSION BETWEEN THE NATURAL FORMULATION AND THE STANDARD FORM 1 1 TRANSPARENTLY TO THE USER 3