METHODS
OF NONCONVEX OPTIMIZATION (In Russian)
V.S.Mikhalevich,
A.M.Gupal and V.I.Norkin
Nauka,
Abstract
The
book deals with the finite dimensional problems of nonconvex optimization and their
numerical solution methods. The theory of extremum problem complexity states
that nonconvex problems are an extraordinary challenge for the researches
(efforts to obtain their guaranteed solution grow exponentially with the
increase of the dimension). In spite of the discouraging statement of
complexity, the impotence of those problems to practice gives an impetus to the
elaboration of numerical methods.
Two
families of nonconvex functions are investigated in the book - the so-called
generalized differentiable functions and the locally Lipschitz functions. These
families are sufficiently general and cover the majority of practical demands.
In particular, the functions under consideration may be nonsmooth. The
nonsmooth functions are natural in many practical applications. They often
appear in the theory of extremum problems as a result of using decomposition
methods, exact nonsmooth penalties, duality and others. The classes of
generalized differentiable functions and locally Lipschitz functions include convex and concave functions and
their differences, and they are closed with respect to operations of maximum,
minimum, superposition and mathematical expectation.
The
authors introduce a notion of gradient for generalized differentiable
functions, construct calculus of such gradients and study different properties
of nonconvex problems in terms of these gradients. They extend the theory and
algorithms of the sub-gradient convex optimization (including stochastic
sub-gradient methods) to the optimization problems with the generalized
differentiable functions.
A
technique for optimization of Lipschitz functions is also proposed. Lipschitz
function is approximated by a family of smooth functions. Only some estimates
of these smooth function gradients are used in the solution procedure. The
gradients of the smooth functions are approximated by the stochastic finite
differences. For calculation of stochastic differences, the values of the
original Lipschitz function are used. A similar approach is developed for the
Lipschitz stochastic programming. Different generalizations of the classic
stochastic approximation method are obtained for the solution of Lipschitz
stochastic constrained programming problems.
In
this book attention mainly is paid to the local constrained optimization of
generalized differentiable functions and locally Lipschitz functions, but the
global optimization problem is also discussed. Three approaches to the global
optimization are considered.
(i)
The combined algorithms of nonconvex nonsmooth optimization. According to
this approach, local methods are used for searching local minimums and global
optimization methods are used for going out of the attraction zone of the local
minimum. The convergence conditions of the combined algorithms are
investigated.
(ii)
A generalization of the classic Piyavski method for problems with general
nonlinear constraints. The auxiliary problems arising in this method are
reduced either to concave minimization problems or to reverse convex programming
problems.
(iii)
A smoothing method for solving unconstrained global optimization problems.
The smoothing procedure deletes small local extremums of the original function.
The picture of critical (stationary) points of the smoothed function in the plane
"variable - smoothing parameter" is studied. It appears that in this
plane there exists a continuous curve of critical points which leads exactly to
the global minimum and there is a possibility to sit on this curve and to come
along it to the global minimum.
Besides these three methods efficient
local heavy-ball and ravine-step methods are also considered in the book. The
motion in these methods is made along the valleys of the minimized function.
Since these methods have some inertia properties, they can rush through local
minimums and thus may be used for the global optimization.
Contents
Sec. 1. Generalized Differentiable Functions
Sec.
2. Smoothing of Functions and Main Properties of Lipschitz Functions
Sec.
3. Necessary Extremum Conditions
Sec.
4. Finite Difference Method of Lipschitz Function Optimization
Sec.
5. Construction of Finite Differences for Maximum Functions
Sec.
6. Random Finite Differences
Sec. 7. Efficiency of Finite-Difference Methods
Sec.
8. Convergence Conditions for Iterative Algorithms of Nonlinear Programming
Sec.
9. Generalized Gradient Method
Sec.10.
Generalized Gradient Method in Constrained Optimization Problem
Sec.11.
Construction of Relaxation Methods of Nonconvex Optimization
Sec.12.
Multiextremum Optimization
12.1. Combined Algorithms
12.2. Approximation Method
12.3. Smoothing Method
Sec.13.
Finite-Difference Average Directions Methods
Sec.14.
Average Gradients Methods
Sec.15.
Conditional Gradient Method
Sec.16.
Reduced Gradient Method
Sec.17.
Feasible Directions Method
Sec.18.
Penalty Functions Methods
Sec.19.
Finite-Difference Method of Constrained Lipschitz Function Minimization
Sec.20.
Arrow-Hurwitz Finite-Difference Method
Sec.21.
Measurable Multivalued Mappings
Sec.22.
Random Lipschitz Functions
Sec.23.
Random Generalized Differentiable Functions and Stochastic Generalized
Gradients Calculus
Sec.24.
Methods of Average Stochastic Gradients
Sec.25.
Finite-Difference Methods in Stochastic Programming
Sec.26.
Averaging Operation
Sec.27.
Stochastic Optimization Based on Averaging Operation
Sec.28.
Arrow-Hurwitz Stochastic Finite-Difference Methods
Literature
comments
References