Recent Developments in Mathematical Programming

Santosh Kumar

• Publisher: CRC Press
• Year: 2022
• ISBN:
  9781000673340
• Edition: 1
• Topic: Mathematics
• Subtopic: Mathematics General
• Index: Mathematics

This work is concerned with theoretical developments in the area of mathematical programming, development of new algorithms and software and their applications in science and industry. It aims to expose recent mathematical developments to a larger audience in science and industry.

Recent Advances in Global Optimization: A Tutorial Survey

DOI: 10.1201/9780429333439-1

Reiner Horst

University of Trier, Department of Mathematics, Trier, West Germany

Abstract This paper describes the state–of—the—art in important parts of global optimization. By definition, a (multiextremal) global optimization problem seeks at least one global minimizer of a real—valued objective function that possesses (often very many) different local minimizers. The feasible set of (admissible) points in ℝⁿ is usually determined by a system of inequalities. The enormous practical need for solving global optimization problems coupled with a rapidly advancing computer technology has allowed one to consider problems which a few years ago would have been considered computationally intractable. As a consequence we are seeing the creation of a large and increasing number of diverse algorithms for solving a wide variety of multiextremal global optimization problems. It is the purpose of this paper to present in a tutorial way a survey of recent methods and typical applications.

Key Words Global Optimization, Multiextremal Optimization, Nonconvex Programming

1. Introduction and Classification

By definition, a (multiextremal) global optimization problem seeks at least one global minimizer of a real—valued objective function that possesses (often very many) different local minimizers with objective function values that can be substantially different from the global minimum.

It is well known that in practically all disciplines where mathematical models are used there are many real—world problems which can be formulated as multiextremal global optimization problems.

Standard nonlinear programming techniques have not been successful for solving these problems. Their deficiency is due to the intrinsic multiextremality of the formulation and not to the lack of smoothness or continuity. One can observe that local tools such as gradients, subgradients, and second order constructions such as Hessians, cannot be expected to yield more than local solutions. One finds, for example, that a stationary point (satisfying certain first order optimality conditions) is often detected for which there is even no guarantee of local minimality. Moreover, determining the local minimality of such a point is known to be NP—hard in the sense of computational complexity even in relatively simple cases. Apart from this deficiency in the local situation, classical methods do not recognize conditions for global optimality.

For these reasons global solution methods must be significantly different from standard nonlinear programming techniques, and they can be expected to be and are much more expensive computationally.

However, the enormous practical need for solving global optimization problems coupled with a rapidly advancing computer technology has allowed one to consider problems which a few years ago would have been considered computationally intractable. As a consequence, we are seeing the creation of a large and increasing number of diverse algorithms for solving a wide variety of multiextremal global optimization problems. Most of these procedures are designed for special problem types where helpful specific structures can be exploited. Moreover, in many practical global optimizations, the multiextremal feature involves only a small number of variables and additional structure is amenable to large scale solutions. Other methods which have been proposed for solving very general and difficult global problems that possess little additional structure can handle only small problem sizes with sufficient accuracy. However, in these very general cases, the methods often provide useful tools for transcending local optimality restrictions, in the sense of providing valuable information about the global quality of a given feasible point. Typically, such information will give upper and lower bounds for the optimal objective function value and indicate parts of the feasible set where further investigations of global optimality will not be worthwile.

We distinguish between unconstrain...

Table of contents

• Cover Page
• Half-Title Page
• Title Page
• Copyright Page
• Table of Contents
• Preface
• List of Contributors
• PART 1: REVIEW ARTICLES IN MATHEMATICAL PROGRAMMING
• PART 2: MULTICRITERIA OPTIMIZATION
• PART 3: SYSTEM OPTIMIZATION AND HEURISTICS
• PART 4: INTERIOR-POINT APPROACH AND QUADRATIC PROGRAMMING
• PART 5: COMPUTATIONAL EFFICIENCY, METHODS AND SOFTWARE
• PART 6: MATHEMATICAL PROGRAMMING APPLICATIONS
• PART 7: ALGORITHMS, GAMES AND PARADOX
• APPENDICES