Interior-point polynomial algorithms in convex programming.

*(English)*Zbl 0824.90112
SIAM Studies in Applied Mathematics. 13. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. ix, 405 p. (1994).

This book presents a rigorous general theory of interior-point polynomial-time methods of convex programming, which explains and extends known methods. The general idea is that these methods are penalty function methods in which the constraints and various associated penalties for constraint violation are incorporated with the objective function into a single unconstrained convex function \(F\), which can be optimized, in particular, by Newton methods.

A fundamental concept is self-concordance, defined as follows: Let \(E\) be a finite-dimensional real vector space, and \(Q\) be an open nonempty convex subset of \(E, F: Q\to {\mathbb R}\) be a function, and \(a> 0\). \(F\) is called self-concordant on \(Q\) with the parameter value \(a\), if \(F\in C^ 3\) is a convex function on \(Q\), and, for all \(x\in Q\) and all \(h\in E\), the following inequality holds: \[ | D^ 3 F(x)[h, h, h]|\leq 2a^{- 1/2}(D^ 2 F(x)[h, h])^{3/2}, \] where \(D^ k F(x)[h_ 1,\dots, h_ k]\) denotes the value of the \(k\)th differential of \(F\) taken at \(x\) along the collection of directions \(h_ 1,\dots, h_ k\). This restriction imposed on certain classes of function \(F\) together with chosen penalties is used to investigate the nature of the convergence of Newton type algorithms. Path-following interior-point methods, potential- reduction interior-point methods, and various specific applications are examined. Algorithms are given, but numerical results are omitted.

A fundamental concept is self-concordance, defined as follows: Let \(E\) be a finite-dimensional real vector space, and \(Q\) be an open nonempty convex subset of \(E, F: Q\to {\mathbb R}\) be a function, and \(a> 0\). \(F\) is called self-concordant on \(Q\) with the parameter value \(a\), if \(F\in C^ 3\) is a convex function on \(Q\), and, for all \(x\in Q\) and all \(h\in E\), the following inequality holds: \[ | D^ 3 F(x)[h, h, h]|\leq 2a^{- 1/2}(D^ 2 F(x)[h, h])^{3/2}, \] where \(D^ k F(x)[h_ 1,\dots, h_ k]\) denotes the value of the \(k\)th differential of \(F\) taken at \(x\) along the collection of directions \(h_ 1,\dots, h_ k\). This restriction imposed on certain classes of function \(F\) together with chosen penalties is used to investigate the nature of the convergence of Newton type algorithms. Path-following interior-point methods, potential- reduction interior-point methods, and various specific applications are examined. Algorithms are given, but numerical results are omitted.

Reviewer: M.A.Hanson (Tallahassee)

##### MSC:

90C51 | Interior-point methods |

90C25 | Convex programming |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |