The Validity of a Family of Optimization Methods

[摘要] A family of iterative optimization methods, which includes most of the well-known algorithms of mathematical programming, is described and analyzed with respect to the properties of its accumulation points. It is shown that these accumulation points have desirable properties under appropriate assumptions on a relevant point-to-set mapping. The conditions under which these assumptions hold are than discussed for a number of algorithms, including steepest descent, the Frank-Wolfe method, feasible direction methods, and some second-order methods. Five algorithms for a special class of nonconvex problems are also analyzed in the same manner. Finally, it is shown that the results can be extended to the case in which the subproblems constructed are only approximately solved and to algorithms which are composites of two or more algorithms.

[发布机构] University of Wisconsin-Madison Department of Computer Sciences