Nonlinearly-constrained Optimization Using Heuristic Penalty Methods and Asynchronous Parallel Generating Set Search

Abstract

Many optimization problems are characterized by expensive objective and/or constraint function evaluations paired with a lack of derivative information. Direct search methods such as generating set search (GSS) are well understood and efficient for derivative-free optimization of unconstrained and linearly-constrained problems. This paper presents a study of heuristic algorithms that address the more difficult problem of general nonlinear constraints where derivatives for objective or constraint functions are unavailable. We focus on penalty methods that use GSS to solve a sequence of linearly-constrained problems, numerically comparing different penalty functions. A classical choice for penalizing constraint violations is \ell_2^2, the squared \ell_2 norm, which has advantages for derivative-based optimization methods. In our numerical tests, however, we show that exact penalty functions based on the \ell_1, \ell_2, and \ell_{\infty} norms converge to good approximate solutions more quickly and thus are attractive alternatives. Unfortunately, exact penalty functions are nondifferentiable and consequently degrade the final solution accuracy, so we also consider smoothed variants. Smoothed-exact penalty functions are attractive because they retain the differentiability of the original problem. Numerically, they are a compromise between exact and \ell_2^2, i.e., they converge to a good solution somewhat quickly without sacrificing much solution accuracy. Moreover, the smoothing is parameterized and can potentially be adjusted to balance the two considerations. Since our focus is on optimization problems that are characterized by expensive function evaluations, reducing the number of function evaluations is paramount, and the numerical results of this paper suggest that exact and smoothed-exact penalty functions are well-suited to this task.

@article{GrKo10,  
author = {Joshua D. Griffin and Tamara G. Kolda}, 
title = {Nonlinearly-constrained Optimization Using Heuristic Penalty Methods and Asynchronous Parallel Generating Set Search}, 
journal = {Applied Mathematics Research eXpress}, 
volume = {25}, 
number = {5}, 
pages = {36--62}, 
month = {October}, 
year = {2010},
doi = {10.1093/amrx/abq003},
}