Quasiconvex optimization and location theory
The present book is a slightly enhanced version of the author's Ph.D. thesis ``Quasiconvex optimization and location theory'' [Tinbergen Institute Research Series No. 90, Thesis Publishers, Amsterdam, 1995]. Its aim is to describe improved versions of the ellipsoid method and to apply them for solving convex and quasiconvex location problems. The book starts by reviewing some basic concepts and results of convex analysis that are needed for understanding the text. After that it deals with the ellipsoid method in convex programming. This method is very powerful and originates from papers by \textit{N. Z. Shor}, written in the 70ies. Although it is now acknowledged that the ellipsoid method is far from being a practical way to solve linear programming problems, the author believes that it represents a practical and competitive method in nonlinear programming. He develops an improved ellipsoid method that uses the norm cuts introduced by \textit{J. B. G. Frenk}, \textit{J. Gromicho} and \textit{S. Zhang} [Math. Programming 63A, 83-108 (1994; Zbl 0791.90041)]. The use of these cuts reduces the risk of numerical instability and permits the derivation of very simple and geometrically oriented convergence proofs. The unconstrained version of the new method is applied to solve convex location problems. In the last part of the book, the author derives a variant of the improved version of the ellipsoid method capable of solving problems with a continuous quasiconvex objective function and convex constraints. For this method rate of convergence results are proved that are similar to the convex case. It seems that here for the first time an application of a version of the ellipsoid method to quasiconvex programs is given with a convergence proof.
scientific article; zbMATH DE number 1095212