COMPUTATIONAL ISSUES IN HIGH PERFORMANCE SOFTWARE FOR NONLINEAR OPTIMIZATION

By V. LILAA

CONTENTS INTRODUCTION REFERENCES INTERVAL CALCULUS BASICS OF INTERVAL COMPUTATIONS OPERATIONS ON INTERVALS INTERVAL ARITHMETIC INTERVAL ENCLOSURES OF OTHER OPERATIONS AND FUNCTIONS AUXILIARY OPERATIONS PROPERTIES AND FEATURES OF THE INTERVAL CALCULUS INTERVAL EXTENSION OF A FUNCTION MOST COMMON FORMS OF INTERVAL EXTENSIONS HOW TO CONSTRUCT FORMULAE FOR INTERVAL-VALUED FUNCTIONS? COMPARISON OF INTERVALS A METRIC ON THE SPACE OF INTERVALS OPEN OR CLOSED INTERVALS? PURPOSES OF THE INTERVAL CALCULUS BOUNDING DERIVATIVES BY ALGORITHMIC DIFFERENTIATION INTERVAL ALGORITHMS AND DERIVATIVES COMPUTATION BASIC APPROACHES ALGORITHMIC DIFFERENTIATION IMPLEMENTATION OF AD FORWARD AD WITH OPERATOR OVERLOADING FORWARD AD WITH DUAL NUMBERS REVERSE MODE AD STATE-OF-THE-ART LIBRARIES ADHC LIBRARY COMPUTING ARBITRARY MANY DERIVATIVES SUMMARY BRANCH-AND-BOUND-TYPE METHODS PRELIMINARY REMARKS THE SOLUTION SET GENERIC ALGORITHM ANALYSIS OF THE B&BT ALGORITHM THE SECOND PHASE—QUANTI?ER ELIMINATION HERBRAND EXPANSION SHARED QUANTITIES EXISTENTIALLY QUANTI?ED FORMULAE WHEN IS THE SECOND PHASE NOT NECESSARY? NECESSARY CONDITIONS SEEKING LOCAL OPTIMA OF A FUNCTION EXAMPLE HEURISTICS CONCLUSIONS SOLVING EQUATIONS AND INEQUALITIES SYSTEMS USING INTERVAL B&BT METHODS CONSTRAINT SATISFACTION PROBLEMS SOLVING SYSTEMS OF NONLINEAR EQUATIONS INTERVAL NEWTON OPERATORS OTHER VERI?CATION TESTS MIRANDA TEST USING QUADRATIC APPROXIMATION BORSUK TEST COMPUTING TOPOLOGICAL DEGREE OBSTRUCTION THEORY TEST CONSISTENCY ENFORCING HULL-CONSISTENCY BOX-CONSISTENCY HIGHER-ORDER CONSISTENCIES HEURISTICS FOR CHOOSING AND PARAMETERIZING THE TOOLS SOLVING QUANTI?ED PROBLEMS USING INTERVAL METHODS INTERVAL GLOBAL OPTIMIZATION BRANCH-AND-BOUND ALGORITHM PROCESSING A BOX IN INTERVAL GLOBAL OPTIMIZATION PARETO SETS OF MULTICRITRIA PROBLEMS TOOLS GAME SOLUTIONS ALGORITHM PARALLELIZATION OF B&BT ALGORITHMS BASIC IMPLEMENTATION DETAILS DATA STRUCTURES MEMORY MANAGEMENT PARALLELIZATION OF THE B&BT ALGORITHM SHARED MEMORY IMPLEMENTATIONS STORAGE OF L STORAGE OF LVER AND LPOS DISTRIBUTED MEMORY IMPLEMENTATIONS LOAD BALANCING TERMINATION DETECTION ADVANCED ISSUES PARALLELIZATION OF REJECTION/REDUCTION TESTS PARALLELIZATION OF EXISTENCE TESTS MODERN ARCHITECTURES INTERVAL SOFTWARE, LIBRARIES AND STANDARDS MAIN ISSUES IN IMPLEMENTING INTERVAL LIBRARIES IEEE 754 STANDARD C-XSC BASIC TYPES THE USE OF BLAS THE TOOLBOX AND ADDITIONAL SOFTWARE AUTHOR’S SOLVERS AND LIBRARIES OTHER LIBRARIES PROFIL/BIAS BOOST::INTERVAL OTHER PACKAGES GPU LIBRARIES IEEE STANDARD 1788–2015: STANDARD FOR INTERVAL ARITHMETIC APPLICATIONS OF INTERVAL B&BT METHODS ROBOTICS MANIPULATOR KINEMATICS MOBILE ROBOTS PATH PLANNING MEASUREMENTS AND ESTIMATION PARAMETER ESTIMATION STATE ESTIMATION OUTLIERS PROCESSING STATISTICAL SAMPLES UNDER INTERVAL UNCERTAINTY ARTI?CIAL INTELLIGENCE SYSTEMS NEURAL NETWORKS SUPPORT VECTOR MACHINES CONTROL THEORY STABILITY CHECKING DESIGNING A CONTROLLER H1-CONTROL MODEL-PREDICTIVE-CONTROL NONLINEAR DYNAMICS, CHAOS AND DIFFERENTIAL EQUATIONS ECONOMICAL MODELING AND MULTIAGENT SYSTEMS ECONOMY MODELING QUEUEING SYSTEMS DECISION MAKING CHAPTER INTRODUCTION THE GENERIC PROBLEM WE ARE CONSIDERING IN THIS MONOGRAPH CAN BE FORMULATED AS FOLLOWS: FIND ALL X ?X SUCH THAT P(X) IS FUL?LLED (1 1) HERE, P(X) IS A FORMULA WITH A FREE VARIABLE X AND X ?RN THE ABOVE PROBLEM IS UBIQUITOUS AND PRETTY GENERAL; WE CAN THINK OF IT AS SOME GENERALIZATION OF A CONSTRAINT SATISFACTION PROBLEM (CSP) ITS INSTANCES INCLUDE: SYSTEMSOFEQUATIONS—THEN P(X)MEANS“ F (X) = ” OR“ (G(X) ? 0) AND ( F (X) = 0) ”, FOR G : RN ?RM1, F : RN ?RM2; GLOBAL OPTIMIZATION PROBLEMS—THEN P(X) MEANS “(?T ?X) F (X) ?F (T) ”, FOR F : RN ?R; PROBLEMS OF SEEKING PARETO-OPTIMAL POINTS OF A MULTICRITERIA PROBLEM—THEN P(X) MEANS “(?T ?X) (?I = 1, , N) ( FI(X) ?FI(T)) OR (?J ?[1N]) ( F J(X) < F J(T)) ”, FOR F : RN ?RN; AND MANY OTHER PROBLEMS DISCUSSED, I A , IN CHAP 4 (CF ALSO [6, 7]) AS WE CAN EASILY TELL, THE PROBLEM UNDER CONSIDERATION MIGHT BE A DECISION PROBLEM, AN OPTIMIZATION PROBLEM, AN APPROXIMATION PROBLEM OR VIRTUALLY ANY OTHER TYPE OF PROBLEMS ENCOUNTERED IN SEVERAL BRANCHES OF SCIENCE AND ENGINEERING RARELY HAVE SUCH PROBLEMS BEEN CONSIDERED, IN THE PAST TYPICALLY, THE PROBLEM UNDER CONSIDERATION HAS BEEN FORMULATED AS AN OPTIMIZATION PROBLEM OR A CSP, OR AN INSTANCE OF ANOTHER WELL-KNOWN TYPE OF PROBLEMS YET, IN THIS MONOGRAPH, AN APPROACH TO SOLVE THE GENERIC PROBLEM IS PROPOSED WHAT CAN THE FORMULA P BE LIKE, IN GENERAL? IT IS A FORMULA, IN THE ?RST-ORDER LOGIC [1] BUT IN WHAT FORMAL SYSTEM? AS A ?RST-ORDER FORMULA, P CONSISTS OF VARIABLES (RANGING OVER SOME DOMAIN X, OR OVER A FEW DOMAINS), CONSTANTS (WITH NUMERICAL VALUES), COMPARISON SIGNS (=, ?, ?, <, >), LOGICAL CONJUNCTIONS (AND, OR, NOT), LOGICAL QUANTI?ERS (?AND ?;