Skip to main content
main-content

Über dieses Buch

This book presents state-of-the-art results and methodologies in modern global optimization, and has been a staple reference for researchers, engineers, advanced students (also in applied mathematics), and practitioners in various fields of engineering. The second edition has been brought up to date and continues to develop a coherent and rigorous theory of deterministic global optimization, highlighting the essential role of convex analysis. The text has been revised and expanded to meet the needs of research, education, and applications for many years to come.

Updates for this new edition include:

· Discussion of modern approaches to minimax, fixed point, and equilibrium theorems, and to nonconvex optimization;

· Increased focus on dealing more efficiently with ill-posed problems of global optimization, particularly those with hard constraints;

· Important discussions of decomposition methods for specially structured problems;

· A complete revision of the chapter on nonconvex quadratic programming, in order to encompass the advances made in quadratic optimization since publication of the first edition.

· Additionally, this new edition contains entirely new chapters devoted to monotonic optimization, polynomial optimization and optimization under equilibrium constraints, including bilevel programming, multiobjective programming, and optimization with variational inequality constraint.

From the reviews of the first edition:

The book gives a good review of the topic. …The text is carefully constructed and well written, the exposition is clear. It leaves a remarkable impression of the concepts, tools and techniques in global optimization. It might also be used as a basis and guideline for lectures on this subject. Students as well as professionals will profitably read and use it.—Mathematical Methods of Operations Research, 49:3 (1999)

Inhaltsverzeichnis

Frontmatter

Convex Analysis

Frontmatter

Chapter 1. Convex Sets

This chapter summarizes the basic concepts and facts about convex sets. Affine sets, halfspaces, convex sets, convex cones are introduced, together with related concepts of dimension, relative interior and closure of a convex set, gauge and recession cone. Caratheodory’s Theorem and Shapley–Folkman’s Theorem are formulated and proven. The first and second separation theorems are presented and on this basis the geometric structure of a convex set is studied via its supporting hyperplanes, faces, and extreme points. Polars of convex sets and particularly of polyhedral convex sets are introduced and the basic theorem on representation of a polyhedron in terms of its extreme points and extreme directions is established. The chapter closes by a study of systems of convex sets, including a proof of Helly’s Theorem.
Hoang Tuy

Chapter 2. Convex Functions

This chapter presents the basic concepts and facts about convex functions. After standard definitions, we discuss the basic operations that preserve convexity, including a theorem on the concavity of the geometric mean of m concave positive functions. Theorems on consistent and inconsistent systems of convex inequalities are then established, to provide the foundation for the study of differential properties of convex functions, subdifferential calculus, and conjugate functions. Further, extremal properties of convex functions are discussed, in particular necessary and sufficient conditions for the minimizer or maximizer of a convex function over a convex set. Especially, an important place is given to the proof of the classic minimax theorem in its strongest version together with its application to the theory of optimality conditions and Lagrange duality for convex and generalized convex optimization, including conic optimization and semidefinite programming.
Hoang Tuy

Chapter 3. Fixed Point and Equilibrium

This chapter summarizes the modern theory of fixed point and equilibrium. Based on the concept of ɛ-approximate minimum, Ekeland variational principle is established first, along with Caristi fixed point theorem, and Nadler contraction theorem for set-valued maps. The next central result is a general equilibrium theorem from which virtually all important fixed point and equilibrium propositions can be derived in a simple unified manner: Ky Fan inequality, Brouwer and Kakutani fixed point theorems, Nash equilibrium theorem, and also the basic solvability theorem for variational inequalities.
Hoang Tuy

Chapter 4. DC Functions and DC Sets

A dc function is a function which can be expressed as the difference of two convex functions. A dc set is a set which can be expressed as the difference of two convex sets. Several important properties of dc functions and dc sets are discussed, among them: (1) any continuous function can be approximated as closely as desired by a dc function; (2) any closed set in \(\mathbb{R}^{n}\) is the projection of a dc set from \(\mathbb{R}^{n+1}\); (3) the class of dc functions is stable under linear operations and under finite upper or lower envelope. Due to the latter property, any finite system of dc inequalities can be rewritten equivalently as a single dc inequality. This permits a classification of dc optimization problems into a few basic classes, which is very convenient for their systematic study. The following questions are discussed next: which functions are dc; how to find an effective representation of a dc function, and how to recognize a minimizer of a dc function on \(\mathbb{R}^{n}\). In the last section Toland duality relation in dc minimization problems is presented.
Hoang Tuy

Global Optimization

Frontmatter

Chapter 5. Motivation and Overview

The concept of global optimum is discussed versus that of local optimum. Many functions encountered in the applications possess multiple local minimizers (or maximizers) with distinct function values. Finding the global minimizer (or global maximixer) in such cases is often of considerable interest and at the same time a great challenge. Fortunately, most global optimization problems of practical interest fall into two basic classes: dc optimization, which deals with problems described by dc functions, and monotonic optimization, which is concerned with problems described by functions representable as differences of increasing functions. The study of these two basic classes of problems is the main theme of modern deterministic global optimization.
Hoang Tuy

Chapter 6. General Methods

Methods for solving global optimization problems combine in different ways some basic techniques of partitioning, bounding, cutting, and approximation by relaxation or restriction. This chapter presents two most popular general methods: branch and bound (BB) and outer approximation (OA). Section 6.1 discusses the theoretical foundations of three basic types of partitioning processes: simplicial, conical, and rectangular, with a focus on the basic property of exhaustiveness which is crucial for the convergence of methods using partitioning. Section 6.2 presents a prototype BB procedure along with its convergence condition expressed in terms of the partitioning and bounding operations. Finally Sect. 6.3 presents a prototype outer approximation procedure. The latter consists in iteratively building a sequence of cuts determining a sequence of relaxed problems whose global optimal solutions will eventually converge to a global optimal solution of the original problem.
Hoang Tuy

Chapter 7. DC Optimization Problems

This chapter presents methods and algorithms for solving the basic dc optimization problems: concave minimization under linear constraints (Sect. 7.1), concave minimization under convex constraints (Sect. 7.2), reverse convex programming (Sect. 7.3), general canonical dc optimization problem (Sect. 7.4), general robust approach to dc optimization (Sect. 7.5), and also applications of dc optimization in various fields (Sects. 7.6–7.8) such as design calculations, location, distance geometry, and clustering. An important new result in this chapter is a surprisingly simple proof of the convergence of algorithms using ω-subdivision—a question which had remained open during two decades before being settled with quite sophisticated proofs by Locatelli (Math Program 85:593–616, 1999), Jaumard and Meyer (J Optim Theory Appl 110:119–144, 2001), and more recently Kuno and Ishihama (J Glob Optim 61:203–220, 2015). In addition, the new concept of ω-bisection by Kuno–Ishihama is introduced as a substitute for ω-subdivision.
Hoang Tuy

Chapter 8. Special Methods

Many problems have a special structure which should be exploited appropriately for their efficient solution. This chapter presents in the first part special methods adapted to special problems of dc optimization and extensions: polyhedral annexation for concave minimization and reverse convex programming, decomposition method for convex problems depending upon a multivariate parameter, including decomposition of partly convex problems by reducing the duality gap, and optimal visible point method for a particular class of problems with a visibility assumption. The second part of the chapter is devoted to the quasi-gradient duality method for global optimization and the relief indicator method for continuous optimization problems with no special structure.
Hoang Tuy

Chapter 9. Parametric Decomposition

A partly convex problem can also be viewed as a convex optimization problem depending upon a parameter \( x \in \mathbb{R}^{n}. \) In the preceding chapter, for solving this parametric convex optimization problem, a BB Algorithm has been proposed which branches upon the space of the parameter x and operates basically as a decomposition method that reduces the problem to a sequence of easier subproblems. The present chapter deals with the important case when n is small. It turns out that in that case the problem can be solved by streamlined decomposition methods of parametric programming.
Hoang Tuy

Chapter 10. Nonconvex Quadratic Programming

Nonconvex quadratic programming deals with optimization problems described by means of linear and quadratic functions, i.e., functions with lowest degree of nonconvexity. One of the earliest significant results in this area is the celebrated S-Lemma of Yakubovich which plays a major role in the development of quadratic optimization. In this chapter, a study of nonconvex quadratic programming is provided that starts with a generalized S-Lemma established on the basis of a special minimax theorem. In particular a thorough study, including most recent results, is presented of quadratic programming with single quadratic constraint and quadratic programming under linear constraints.
Hoang Tuy

Chapter 11. Monotonic Optimization

This chapter presents a mathematical framework for monotonic optimization—an important new field of global optimization which has been emerged in the last 15 years. The basic concepts are introduced, then the basic polyblock algorithm along with the SIT (Successive Incumbent Transcending) Algorithm for canonical monotonic optimization is described. Finally some important applications in economics and engineering, particularly in communication and networking systems, are discussed.
Hoang Tuy

Chapter 12. Polynomial Optimization

Polynomial optimization is concerned with optimization problems described by multivariate polynomials on \(\mathbb{R}_{+}^{n}.\) In this chapter two approaches are presented for polynomial optimization. In the first approach a polynomial optimization problem is solved as a nonconvex optimization problem by a rectangular branch and bound algorithm in which bounding is performed by linear or convex relaxation. In the second approach, by viewing any multivariate polynomial on \(\mathbb{R}_{+}^{n}\) as a difference of two increasing functions, a polynomial optimization problem is treated as a monotonic optimization problem. In particular, the Successive Incumbent Transcending algorithm is developed which starts from a quickly found feasible solution then proceeds to gradually improving it to optimality.
Hoang Tuy

Chapter 13. Optimization Under Equilibrium Constraints

An important class of optimization problems has constraints of a particular type called equilibrium constraints which arise from many applications in natural sciences, engineering, and economics. Up to recently most methods developed for solving these problems have been essentially local optimization methods. Few methods have been concerned with finding a global optimal solution. This chapter presents a global optimality approach to this class of problems in the most important special cases that include: bilevel programming, optimization over the efficient set, and optimization with variational inequality constraint.
Hoang Tuy

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise