Optimization Online


Direct search based on probabilistic feasible descent for bound and linearly constrained problems

S. Gratton(serge.gratton***at***enseeiht.fr)
C. W. Royer(croyer2***at***wisc.edu)
L. N. Vicente(lnv***at***mat.uc.pt)
Z. Zhang(zaikun.zhang***at***polyu.edu.hk)

Abstract: Direct search is a methodology for derivative-free optimization whose iterations are characterized by evaluating the objective function using a set of polling directions. In deterministic direct search applied to smooth objectives, these directions must somehow conform to the geometry of the feasible region and typically consist of positive generators of approximate tangent cones (which then renders the corresponding methods globally convergent in the linearly constrained case). One knows however from the unconstrained case that randomly generating the polling directions leads to better complexity bounds as well as to gains in numerical efficiency, and it becomes then natural to consider random generation also in the presence of constraints. In this paper, we study a class of direct search based on sufficient decrease for solving smooth linearly constrained problems where the polling directions are randomly generated (in approximate tangent cones). The random polling directions must satisfy probabilistic feasible descent, a concept which reduces to probabilistic descent in the absence of constraints. Such a property is instrumental in establishing almost-sure global convergence and worst-case complexity bounds with overwhelming probability. Numerical results show that the randomization of polling directions compares favorably to the classical deterministic approach. In some cases, one can observe a clear superiority of randomization, as it is suggested by our complexity results.

Keywords: Derivative-free optimization, direct-search methods, positive generators, probabilistic feasible descent, bounds, linear constraints

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Category 3: Stochastic Programming

Citation: S. Gratton, C. W. Royer, L. N. Vicente, and Z. Zhang, Direct search based on probabilistic feasible descent for bound and linearly constrained problems, preprint 17-10, Dept. Mathematics, Univ. Coimbra.

Download: [PDF]

Entry Submitted: 02/17/2017
Entry Accepted: 02/17/2017
Entry Last Modified: 02/17/2017

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