The regularized feasible directions method for nonconvex optimization |
| |
Affiliation: | 1. School of Mathematical Sciences, Tel-Aviv University, Ramat-Aviv 69978, Israel;2. Faculty of Industrial Engineering and Management, Technion Israel Institute of Technology, Haifa 3200003, Israel |
| |
Abstract: | This paper develops and studies a feasible directions approach for the minimization of a continuous function over linear constraints in which the update directions belong to a predetermined finite set spanning the feasible set. These directions are recurrently investigated in a cyclic semi-random order, where the stepsize of the update is determined via univariate optimization. We establish that any accumulation point of this optimization procedure is a stationary point of the problem, meaning that the directional derivative in any feasible direction is nonnegative. To assess and establish a rate of convergence, we develop a new optimality measure that acts as a proxy for the stationarity condition, and substantiate its role by showing that it is coherent with first-order conditions in specific scenarios. Finally we prove that our method enjoys a sublinear rate of convergence of this optimality measure in expectation. |
| |
Keywords: | Feasible directions Nonconvex optimization Nonsmooth optimization Constrained optimization Convergence analysis |
本文献已被 ScienceDirect 等数据库收录! |
|