FUNDAMENTALS OF PRACTICAL MATHEMATICS
CHAPTER 1 INTRODUCTION 1 CHAPTER 2 PRACTICAL MOTIVATIONS 4 CHAPTER 3 OPTIMALITY CONDITIONS 14 CHAPTER 4 MODEL AUGMENTED LAGRANGIAN ALGORITHM 30 CHAPTER 5 GLOBAL MINIMIZATION APPROACH 39 CHAPTER 6 GENERAL AFFORDABLE ALGORITHMS 45 CHAPTER 7 BOUNDEDNESS OF THE PENALTY PARAMETERS 57 CHAPTER 8 SOLVING UNCONSTRAINED SUBPROBLEMS 70 CHAPTER 9 SOLVING CONSTRAINED SUBPROBLEMS 93 CHAPTER 10 FIRST APPROACH TO ALGENCAN 108 CHAPTER 11 ADEQUATE CHOICE OF SUBROUTINES 136 CHAPTER 12 MAKING A GOOD CHOICE OF ALGORITHMIC OPTIONS AND PARAMETERS 145 CHAPTER 13 PRACTICAL EXAMPLES 159 CHAPTER 14 FINAL REMARKS 188 CONTENTS CHAPTER 1 INTRODUCTION CONSTRAINED OPTIMIZATION IS ONE OF THE MATHEMATICAL PROBLEMS THAT MOST FREQUENTLY SERVE FOR MODELING NATURAL PHENOMENA LARGE PROBLEMS OF THIS TYPE APPEAR IN MANY CHALLENGING AREAS OF SCIENCE AND TECHNOLOGY SUCH AS PROTEIN FOLDING ELECTRONIC CALCULATIONS GEOPHYSI CAL PROSPECTING NONLINEAR CONTROL DATA MINING IMAGE PROCESSING AND RECONSTRUCTION AND STRUCTURAL ENGINEERING MANY HUMAN ACTIVITIES GIVE RISE TO THE MINIMIZATION OF FUNCTIONS WITH CONSTRAINTS MAKING DECISIONS USUALLY INVOLVES OPTIMIZATION MAXIMIZING UTILITIES AND PRO TS OR MINIMIZING LOSS RISK ANALYSIS REQUIRES CAREFUL IDENTI CATION OF OBJECTIVES AND RESTRICTIONS AND IN GENERAL EVERY MATHEMATICAL MODEL OF REAL LIFE SYSTEMS REQUIRES TTING PARAMETERS BEFORE ITS ACTUAL APPLICATION ONE OF THE MOST NATURAL IDEAS FOR SOLVING CONSTRAINED MINIMIZATION PROBLEMS CONSISTS OF ADDING TO THE OBJECTIVE FUNCTION A TERM THAT PENALIZES THE LACK OF FUL LLMENT OF THE CON STRAINTS QUADRATIC PENALTY FUNCTIONS MEASURE THE NONSATISFACTION OF EQUALITY CONSTRAINTS HI X 0 BY THEIR SQUARE HI X 2 NONFUL LLMENT OF INEQUALITY CONSTRAINTS GI X 0 IS MEASURED BY MAX 0 GI X 2 MANY OTHER PENALTY FUNCTIONS HAVE BEEN CONSIDERED IN THE OPTIMIZATION LITERATURE BUT THE SIMPLE QUADRATIC PENALTY TERM MAINTAINS ITS ATTRACTIVENESS BECAUSE IT PRESERVES DIFFERENTIABILITY AND PENALIZES LINEAR CONSTRAINTS BY CONVEX QUADRAT ICS OR PIECEWISE CONVEX QUADRATICS WHICH ARE VERY ADEQUATE FOR MINIMIZATION PURPOSES IN THE CASE OF INEQUALITY CONSTRAINTS THE THEORY OF SEMISMOOTH NONLINEAR SYSTEMS HAS REVEALED THAT THE ABSENCE OF CONTINUOUS SECOND DERIVATIVES IS NOT A SERIOUS DRAWBACK AT LEAST FOR THE APPLICATION OF NEWTONIAN AND INEXACT NEWTON STRATEGIES MOREOVER IF ONE USES SLACK VARIABLES INEQUALITY CONSTRAINTS ARE TRANSFORMED INTO EQUALITY CONSTRAINTS AND BOUNDS SO THAT THE PENALTY SUBPROBLEM ASSOCIATED WITH A QUADRATIC PROGRAMMING PROBLEM REDUCES TO THE SEQUENTIAL MINIMIZATION OF QUADRATICS WITH BOUNDS ON THE VARI ABLES CONSTRAINED OPTIMIZATION PROBLEMS MAY BE EXTREMELY DIF CULT AND THEIR SOLVABIL ITY IN THE LARGE SCALE CASE DEPENDS ON CLEVER FORMULATIONS THAT ROUGHLY SPEAKING MAKE THEM SIMILAR TO QUADRATIC PROGRAMMING AT LEAST LOCALLY AS A CONSEQUENCE THE QUADRATIC PENALTY APPROACH REMAINS A USEFUL PRACTICAL CHOICE DOST L 102 RECENTLY PUBLISHED A BOOK RE ECTING HIS RESEARCH IN APPLIED MECHANICAL ENGINEERING IN WHICH HE INTRODUCES THE EMPLOYMENT OF AUGMENTED LAGRANGIANS WITH QUADRATIC PENALTY FUNCTIONS FOR QUADRATIC PROGRAMMING BY MEANS OF THE EMPLOYMENT OF THE QUADRATIC PENALTY METHOD ONE REDUCES THE CON STRAINED OPTIMIZATION PROBLEM TO A SEQUENCE OF SIMPLY CONSTRAINED PERHAPS UNCONSTRAINED MINIMIZATION PROBLEMS IN WHICH THE PENALTY PARAMETERS TEND TO IN NITY GIVING INCREAS ING WEIGHT TO THE CONSTRAINTS WITH RESPECT TO THE OBJECTIVE FUNCTION THIS IS THE MAIN 1 DRAWBACK OF THE PENALTY APPROACH AS THE PENALTY PARAMETERS GROW SUBPROBLEMS BE COME MORE AND MORE DIF CULT IF THE PENALTY PARAMETERS ARE VERY LARGE A POINT CLOSE TO THE SOLUTION OF THE ORIGINAL PROBLEM WITH MODEST INFEASIBILITY MAY BE CONSIDERED AS BEING WORSE THAN AN ALMOST FEASIBLE POINT WITH POOR OBJECTIVE FUNCTION VALUE THAT COULD BE FAR FROM THE SOLUTION TO ALLEVIATE THIS INCONVENIENCE ONE COULD VERY CAUTIOUSLY INCREASE THE PENALTY PARAMETERS SEE 130 WHICH MAY LEAD TO SOLVING AN EXCESSIVELY LARGE NUMBER OF SUBPROBLEMS OR ONE MAY ADOPT THE SHIFTING STRATEGY THAT MOTIVATES THE AUGMENTED LAGRANGIAN APPROACH ACCORDING TO THE SHIFTING IDEA ONE TRIES TO OBTAIN THE SOLUTION OF THE PROBLEM EMPLOY ING A MODERATE VALUE OF THE PENALTY PARAMETERS THE BASIC OBSERVATION IS THAT THE EFFECT OF GETTING A SUBPROBLEM SOLUTION CLOSE TO THE TRUE SOLUTION OF THE CONSTRAINED OPTIMIZA TION PROBLEM CAN BE OBTAINED BY APPLYING PENALIZATION NOT TO THE TRUE CONSTRAINTS BUT TO DISPLACED CONSTRAINTS WHOSE SHIFTING LEVEL CORRESPONDS TO THE INFEASIBILITY AT THE SOLUTION OF THE LAST SUBPROBLEM SOLVED THIS IDEA SEEMS TO BE IMPLICITLY OR EXPLICITLY PRESENT IN THE RST HISTORICAL WORKS IN WHICH THE AUGMENTED LAGRANGIAN APPROACH WITH QUADRATIC PENALIZATION APPEARS 73 136 144 218 229 AUGMENTED LAGRANGIAN METHODS HAVE BEEN USED MANY TIMES IN CONNECTION WITH EN GINEERING PROBLEMS AND FOR GENERAL OPTIMIZATION ITS POPULARITY INCREASED WITH THE INTRO DUCTION OF THE LANCELOT PACKAGE IN THE LATE 1980S 82 83 IN SPITE OF THE PERMANENT INTRODUCTION OF NEW EF CIENT METHODS FOR NONLINEARLY CON STRAINED OPTIMIZATION THERE ARE FAMILIES OF PROBLEMS FOR WHICH THE AUGMENTED LAGRANGIAN APPROACH IS RECOMMENDED ESPECIALLY IN THE LARGE SCALE CASE MANY REASONS SUPPORT THIS POINT OF VIEW 1 THE APPROACH IS MODULAR THE EF CIENCY OF MOST PRACTICAL AUGMENTED LAGRANGIAN METHODS IS LINKED TO THE EF CIENCY OF THE ALGORITHMS USED FOR SOLVING THE SUBPROB LEMS OFTEN THE CONSTRAINTS OF THESE SUBPROBLEMS DE NE AN N DIMENSIONAL BOX BOX CONSTRAINED MINIMIZATION IS A CLASSICAL PROBLEM ON WHICH INTENSIVE RESEARCH CONTINUES ESPECIALLY IN THE LARGE SCALE CASE AS LOCAL OR GLOBAL BOX CONSTRAINT AL GORITHMS ARE DEVELOPED THE EFFECTIVENESS OF THE ASSOCIATED AUGMENTED LAGRANGIAN ALGORITHMS IS INCREASED 2 THE AUGMENTED LAGRANGIAN APPROACH IS APPEALING FOR SITUATIONS IN WHICH IT IS NAT URAL TO DIVIDE THE CONSTRAINTS INTO TWO GROUPS THE CONSTRAINTS TO WHICH ONE AP PLIES PENALIZATION AND SHIFTS BELONG TO THE RST GROUP THE SECOND GROUP CONTAINS CONSTRAINTS THAT REMAIN IN THE SUBPROBLEMS AND ARE NOT PENALIZED OR SHIFTED AT ALL SOMETIMES AS IN THE CASE OF BOXES THESE CONSTRAINTS ARE SIMPLE AND WE KNOW PRACTI CAL METHODS FOR DEALING WITH THEM GENERALLY SPEAKING THE AUGMENTED LAGRANGIAN FRAMEWORK ALLOWS ONE TO HANDLE SPECI C CONSTRAINTS IN A SPECI C WAY WHEN THE AP PROPRIATE TECHNOLOGY FOR THAT PURPOSE EXISTS 3 THE AUGMENTED LAGRANGIAN METHOD MAY BE USED FOR DERIVATIVE FREE OPTIMIZATION PROVIDED THAT DERIVATIVE FREE METHODS FOR SOLVING THE SUBPROBLEMS ARE AVAILABLE 99 164 175 176 4 THE CONVERGENCE TOWARD GLOBAL MINIMIZERS OF CONSTRAINED OPTIMIZATION PROBLEMS DEPENDS IN THE AUGMENTED LAGRANGIAN FRAMEWORK ONLY ON THE GLOBAL MINIMIZA TION PROPERTIES OF THE PROBABLY SIMPLER SUBPROBLEMS 49 58 5 THE APPLICABILITY OF THE AUGMENTED LAGRANGIAN METHOD IS NOT IMPAIRED BY AN EX CESS OF EQUALITY OR INEQUALITY CONSTRAINTS AS FOR OTHER CONSTRAINED MINIMIZATION METHODS FUNDAMENTALS OF PRACTICAL MATHEMATICS 2 6 NATURAL EXTENSIONS OF THE METHOD FOR NONSMOOTH GENERALIZATIONS OF THE CONSTRAINED OPTIMIZATION PROBLEMS EXIST AND INVOLVE MINIMAL MODI CATIONS OF THE BASIC AUG MENTED LAGRANGIAN ALGORITHM 42 7 THE CONVERGENCE THEORY OF THE AUGMENTED LAGRANGIAN METHODS CAN BE USED TO IM PROVE ROBUSTNESS OF ALGORITHMS THAT IN GENERAL ARE NOT CLASSI ED AS AUGMENTED LAGRANGIAN 107 ALTHOUGH DEDICATED TO ENGINEERS SOCIAL SCIENTISTS PHYSICISTS CHEMISTS AND GENERAL PRACTITIONERS THIS BOOK OFFERS A SOLID THEORETICAL BASIS FOR UNDERSTANDING THE RESULTS THAT HELP TO EXPLAIN THE PRACTICAL BEHAVIOR OF ALGORITHMS ALL PROVED THEOREMS MAKE USE OF PLAUSIBLE ASSUMPTIONS WITH CLEAR GEOMETRICAL OR ALGORITHMIC MEANING EVEN WHEN THE USER DOES NOT WISH TO READ THE PROOFS HE OR SHE WILL BE ABLE TO INTERPRET THEIR MEANING THE HYPOTHESES ON WHICH THEY ARE BASED AND THEIR PRACTICAL CONSEQUENCES APPROPRIATE REMARKS WILL EMPHASIZE THESE POINTS THROUGHOUT THE TEXT FUNDAMENTALS OF PRACTICAL MATHEMATICS 3