Nondifferentiable optimization and polynomial problems (Q1384595)

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.