Optimization Online


On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods

Amir Beck (becka***at***tauex.tau.ac.il)
Nadav Hallak (Nadav_Hallak***at***outlook.com)

Abstract: We study the class of nonsmooth nonconvex problems in which the objective is to minimize the difference between a continuously differentiable function (possibly nonconvex) and a convex (possibly nonsmooth) function over a convex polytope. This general class contains many types of problems, including difference of convex functions (DC) problems, and as such, can be used to model a variety of applications. Our goal is to attain a point satisfying the stationarity necessary condition, defined as the lack of feasible descent directions. Although elementary in smooth optimization, this condition is nontrivial when the objective function is nonsmooth, and correspondingly there are very few methods that obtain stationary points in similar settings to the one we study. In this paper we prove that stationarity in our model can be characterized by a finite number of directions that positively span the set of feasible directions. We then use the latter to develop two methods, one deterministic and one random, whose accumulation points are proved to be stationary points. Supplementing discussion on positively spanning sets, and corresponding methods to obtain members of such sets, are also presented. Numerical experiments illustrate the appeal of obtaining a stationary point and the advantage of using the random method to do so.

Keywords: nonsmooth, nonconvex, random method,

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 10/21/2018
Entry Accepted: 10/21/2018
Entry Last Modified: 06/16/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society