Optimization on low rank nonconvex structures

Authors Hiroshi Konno, Phan Thien Thach, Hoang Tuy

Publication date 29 April 1997

Published in Nonconvex Optimization and Its Applications (Search for Journal in Brave)

This monograph gives an extensive presentation of theory, algorithms and applications of nonconvex optimization problems whose nonconvexity is caused by a comparatively small number of variables. To formalize this idea, two basic notions are considered: the nonconvexity rank and the nonconvexity index. The nonconvexity rank of \(f:\mathbb{R}^n\to\mathbb{R}\) is defined as the smallest number \(k\) such that, for some linear isomorphism \(B:\mathbb{R}^n\to\mathbb{R}\), the composition \(f\circ B\) is convex when the values of its first \(k\) arguments are fixed. The nonconvexity index of a d.c. (difference of convex) function \(f:\mathbb{R}^n\to \overline\mathbb{R}\) is the smallest rank of a convex function \(h:\mathbb{R}^n\to \mathbb{R}\) such that \(f+h\) is convex, the rank of a convex function \(h\) meaning the dimension of the affine subspace spanned by \(\text{dom}(f)=\{x\in\mathbb{R}^n|f(x)<+\infty\}\) minus the dimension of the space of all \(y\in\mathbb{R}^n\) such that, for some \(\alpha(y)\), one has \(f(x+\lambda y)=f(x)+\lambda\alpha(y)\), \(\forall\lambda\in\mathbb{R}^n\), \(\forall x\in \mathbb{R}^n\). Both the nonconvexity rank and the nonconvexity index can be regarded as measures of nonconvexity. It turns out that many global optimization problems arising in applications have objective functions and constraints with low convexity ranks or indices and that there are some rather efficient algorithms for solving classes of problems possessing such a structure. The book consists of three parts: I. Foundations. II. Methods and Algorithms. III. Selected Applications. Part I is divided into six chapters. Chapter 1 is an introduction to global optimization. Various special models of global optimization problems are presented: concave minimization, reverse convex programming and d.c. programming. The latter class of problems is rather general, as any problem of minimizing a lower semicontinuous function over a closed set can be reformulated as the minimization of a linear function subset to a d.c. constraint. Chapter 2 is devoted to quasi-convex functions. In contrast with earlier monographs on global optimization or generalized convexity, quasi-convex conjugation and quasi-subdifferentials are studied here in detail. Chapter 3 introduces d.c. functions and d.c. sets. Toland-Singer duality for the minimization of d.c. functions is discussed in Chapter 4, together with other nonconvex duality models. The nonconvexity rank and the nonconvexity index are introduced and studied in Chapter 5; these concepts are used to analyze the lack of convexity of optimization problems. The last chapter of Part I describes the basic search strategies for global minimization: outer approximation, successive partition and dualization. Part II consists of Chapter 7-11, in which numerical methods that take advantage of low rank nonconvexity are presented in detail. These algorithms are specific to specially structured problems like, e.g., multiplicative, fractional or bilinear programming problems, which are studied in Chapters 7 and 8. In Chapter 9, solution methods for problems enjoying a monotonicity property are proposed. Chapter 10 is devoted to decomposition methods of the Dantzig-Wolfe and Benders types for reverse convex optimization. Dynamic programming algorithms for production and inventory problems with a multi-echelon structure and for some special multi-stage d.c. minimization problems are studied in Chapter 11. Applications are the subject of Part III. Quadratic problems with low nonconvexity rank are considered in Chapter 12. Chapter 13 discusses continuous location problems. Chapter 14 is devoted to the design centering and other related problems consisting of finding optimal balls or convex bodies that satisfy certain geometric properties. The last chapter of the book analyzes multiobjective optimization and bilevel linear programming problems. This monograph constitutes a significant contribution to the existing literature on global optimization. Since the appearance of the first book on the subject [\textit{R. Horst} and \textit{H. Tuy}: Global optimization. Deterministic approaches', Springer-Verlag (1990; Zbl 0704.90057)], intensive research has been carried out in this field, and it has become evident that one cannot expect a universal algorithm to exist for efficiently solving all kinds of nonconvex optimization problems. Therefore, any reasonable approach to global optimization must concentrate on specially structured problems. This book identifies one such particular structure, namely, the low rank nonconvexity, which allows for efficient algorithms and is general enough to encompass a wide range of problems arising in practical applications. Researchers in and users of nonconvex optimization will certainly benefit from this monograph.

Recommendations

Cited in

(62)

This page was built for publication: Optimization on low rank nonconvex structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1353375)