# Stationarity Results for Generating Set Search for Linearly Constrained Optimization

### Abstract

We present a new generating set search (GSS) approach for minimizing functions subject to linear constraints. GSS is a class of direct search optimization methods that includes generalized pattern search. One of our main contributions in this paper is a new condition to define the set of conforming search directions that admits several computational advantages. For continuously differentiable functions we also derive a bound relating a measure of stationarity, which is equivalent to the norm of the gradient of the objective in the unconstrained case, and a parameter used by GSS algorithms to control the lengths of the steps. With the additional assumption that the derivative is Lipschitz, we obtain a big-O bound. As a consequence of this relationship, we obtain subsequence convergence to a KKT point, even though GSS algorithms lack explicit gradient information. Numerical results indicate that the bound provides a reasonable estimate of stationarity.

Type
Publication
SIAM Journal on Optimization
Date
Tags
Citation
T. G. Kolda, R. M. Lewis, V. Torczon. Stationarity Results for Generating Set Search for Linearly Constrained Optimization. SIAM Journal on Optimization, Vol. 17, No. 4, pp. 943-968, 2006. https://doi.org/10.1137/S1052623403433638

### Keywords

constrained optimization, linear constraints, global convergence analysis, direct search, generating set search, generalized pattern search, derivative-free methods, stopping criteria

### BibTeX

@article{KoLeTo06,
author = {Tamara G. Kolda and Robert Michael Lewis and Virginia Torczon},
title = {Stationarity Results for Generating Set Search for Linearly Constrained Optimization},
journal = {SIAM Journal on Optimization},
volume = {17},
number = {4},
pages = {943--968},
month = {November},
year = {2006},
doi = {10.1137/S1052623403433638},
}