Implementing generating set search methods for linearly constrained minimization

doi:10.1137/050635432

Implementing generating set search methods for linearly constrained minimization

2007-01-01

80

OA

AI

R

Robert Michael Lewis *

DOI：10.1137/050635432

Original

Original request for help

Save

Abstract

En 中文

We discuss an implementation of a derivative-free generating set search method for linearly constrained minimization with no assumption of nondegeneracy placed on the constraints. The convergence guarantees for generating set search methods require that the set of search directions possesses certain geometrical properties that allow it to approximate the feasible region near the current iterate. In the hard case, the calculation of the search directions corresponds to finding the extreme rays of a cone with a degenerate vertex at the origin, a difficult problem. We discuss here how state-of-the-art computational geometry methods make it tractable to solve this problem in connection with generating set search. We also discuss a number of other practical issues of implementation, such as the careful treatment of equality constraints and the desirability of augmenting the set of search directions beyond the theoretically minimal set. We illustrate the behavior of the implementation on several problems from the CUTEr test suite. We have found it to be successful on problems with several hundred variables and linear constraints.

Keywords:

nonlinear programming

nonlinear optimization

constrained optimization

linear constraints

degeneracy

direct search

generating set search

generalized pattern search

derivative-free methods

double description algorithm

Implementing generating set search methods for linearly constrained minimization

Abstract

Journal

Organization