Objective-derivative-free methods for constrained optimization

We propose feasible descent methods for constrained minimization that do not make explicit use of the derivative of the objective function. The methods iteratively sample the objective function value along a finite set of feasible search arcs and decrease the sampling stepsize if an improved objective function value is not sampled. The search arcs are obtained by projecting search direction rays onto the feasible set and the search directions are chosen such that a subset approximately generates the cone of first-order feasible variations at the current iterate. We show that these methods have desirable convergence properties under certain regularity assumptions on the constraints. In the case of linear constraints, the projections are redundant and the regularity assumptions hold automatically. Numerical experience with the methods in the linearly constrained case is reported.

Authors and Affiliations

1. Università di Roma “La Sapienza”, Dipartimento di Informatica e Sistemistica, Via Buonarroti 12, 00185 Roma, Italy, e-mail: lucidi@dis.uniroma1.it, , , , , , IT

   S. Lucidi

2. Istituto di Analisi dei Sistemi ed Informatica, Consiglio Nazionale delle Ricerche, Viale Manzoni 30, 00185 Roma, Italy, e-mail: sciandro@iasi.rm.cnr.it, , , , , , IT

   M. Sciandrone

3. Department of Mathematics, University of Washington, Seattle, Washington 98195, USA, e-mail: tseng@math.washington.edu, , , , , , US

   P. Tseng

Received: November 12, 1999 / Accepted: April 6, 2001¶Published online October 26, 2001

Reprints and permissions