Nondifferentiable optimization and polynomial problems
type: Item
instance of: scholarly article
title: Nondifferentiable optimization and polynomial problems
zbMATH Open document ID: 0901.49015
author: N. Z. Shor
published in: Nonconvex Optimization and Its Applications
publication date: 1998-04-19T00:00:00Z
review text: This book presents many results on nonsmooth optimization algorithms, originally published in Russian, and perhaps not easily accessible to English speaking people. There is an extensive bibliography. Various algorithms of subgradient type are analyzed, applicable to minimization of convex functions which need not be differentiable. These include especially \(\varepsilon\)-subgradient methods, and combinations of subgradient methods with space dilatation in the direction of the subgradient. The ellipsoid method is a particular case. Convergence theorems are given. Complexity theory is discussed, for algorithms where the objective and constraint functions are polynomials. In particular, Khachiyan's algorithms, and some other interior-point methods, are analyzed. Decomposition schemes, where the set of constraints or the set of variables may be decomposed, are approached using algorithms for nonsmooth optimization. Some linear and convex programming structure problems can be solved by algorithms of subgradient type. Dual problems, and nonsmooth penalty functions, are used to construct optimal ellipsoids circumscribing a given finite set in \(n\) dimensions. This leads to an inscribed ellipsoid method for convex minimization. The computational complexity is analyzed. Algorithms are given, for obtaining dual bounds to quadratic problems arising in some multidimensional combinatorial problems in graph theory, such as maximal cut, and some partitioning problems. A global minimization problem for polynomial functions is reduced to a quadratic problem with additional constraints. Lagrangian relaxation is applied to obtain lower bounds. There is a connection with Hilbert's 17th problem.
Mathematics Subject Classification ID: 49J52
Mathematics Subject Classification ID: 49-02
Mathematics Subject Classification ID: 90-02
zbMATH DE Number: 1142762
zbMATH Keywords: nondifferentiable optimization
zbMATH Keywords: space dilatation
zbMATH Keywords: polynomial extremal problems
zbMATH Keywords: extremal graph problems
zbMATH Keywords: nonsmooth optimization
zbMATH Keywords: algorithms of subgradient
zbMATH Keywords: computational complexity
zbMATH Keywords: global minimization
zbMATH Keywords: Hilbert's 17th problem
reviewed by: B. D. Craven
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1142762