Nonlinearly-constrained optimization using asynchronous parallel generating set search.

Joshua Griffin, Tamara G. Kolda2007 · DOI

TL;DR

This paper tackles the challenge of optimizing complex, real-world problems in science and engineering where function evaluations are expensive and derivatives are unavailable. The authors propose using "exact" and "smoothed-exact" penalty functions with a derivative-free search method (GSS) to achieve feasible solutions more efficiently than traditional methods.

What Problem Does This Paper Address?

Many optimization problems in computational science and engineering (CS&E) are characterized by computationally expensive objective and constraint function evaluations. Furthermore, these problems often lack derivative information, making standard gradient-based optimization techniques unsuitable. Direct search methods like Generating Set Search (GSS) are effective for unconstrained or linearly constrained problems, but extending them to general nonlinear programming (NLP) with unavailable derivatives is a significant challenge. The core problem is to find optimization methods that are both efficient (requiring fewer expensive function evaluations) and effective at handling nonlinear constraints, prioritizing feasibility over finding a perfect KKT point.

Methods

The paper adapts the Generating Set Search (GSS) method, a derivative-free optimization technique, to handle general nonlinear programming problems. The core idea is to transform the NLP into a sequence of linearly constrained subproblems using penalty functions. The authors compare several penalty functions:

  • $\ell_2^2$ penalty function: A standard, smooth penalty function.
  • Exact penalty functions ($\ell_1, \ell_2, \ell_\infty$): These functions offer the theoretical advantage of converging to a solution of the original problem with a finite penalty parameter. However, they are non-smooth, which can pose theoretical challenges for GSS.
  • Smoothed-exact penalty functions: These are variants of the exact penalty functions that are made smooth. This smoothing aims to retain the theoretical benefits of exact penalties while ensuring the differentiability required for GSS convergence guarantees. A smoothing parameter ($\alpha$) is introduced, allowing a trade-off between accuracy and efficiency.

The GSS subproblems are solved using an asynchronous parallel implementation (APGSS) to leverage parallel computing and handle potential variations in evaluation times.

Datasets

The authors evaluated their methods on a collection of 145 CUTEr test problems with nonlinear constraints. They specifically focused on problems with up to ten variables and between one and ten nonlinear constraints. The results are presented for a subset of 98 problems that all tested methods could successfully solve.

Key Insights and Ideas

  • Exact penalty functions offer a significant efficiency boost: Despite their non-smoothness, exact penalty functions ($\ell_1, \ell_2, \ell_\infty$) dramatically reduced the number of function evaluations needed to reach a feasible solution compared to the standard $\ell_2^2$ penalty. This is crucial for expensive CS&E simulations.
  • Smoothness is a double-edged sword: While the $\ell_2^2$ penalty is smooth and theoretically well-behaved, it requires many more function evaluations. Exact penalties are efficient but can lead to convergence issues at non-differentiable points. Smoothed-exact penalties offer a compromise, balancing efficiency with improved solution quality.
  • Feasibility is paramount in CS&E: The paper emphasizes that for many CS&E applications, a "usable" feasible solution is more valuable than an infeasible but theoretically optimal (KKT) point. This perspective justifies prioritizing methods that quickly achieve constraint satisfaction.
  • The smoothing parameter offers flexibility: The parameter $\alpha$ in smoothed-exact penalty functions allows users to tune the method's behavior, balancing the desire for a more accurate solution against the need for fewer function evaluations.

Key Results

  • Efficiency Gains: Exact penalty functions allowed approximately 80% of problems to exit successfully within 1000 function evaluations, compared to about 60% for the $\ell_2^2$ penalty. Smoothed-exact penalties achieved this for about 73% of problems.
  • Solution Quality: While exact penalties sometimes yielded slightly worse objective function values than $\ell_2^2$, 84% of problems were no more than 10% worse. Smoothed-exact penalties further improved this, with 96% of problems achieving objective values no more than 10% worse than $\ell_2^2$.
  • Constraint Satisfaction: All methods were compared based on their ability to achieve sufficient feasibility ($\eta(x) < \eta^* = 10^{-3}$). The focus was on methods that successfully met this criterion.

Limitations and Future Work

  • Non-smoothness of Exact Penalties: The paper acknowledges that exact penalty functions are non-smooth, which can theoretically lead GSS to converge to points of non-differentiability rather than true stationary points. While numerical results were strong, this remains a theoretical concern.
  • Parameter Tuning: The paper uses a simple scheme for updating penalty and smoothing parameters. The authors suggest that more sophisticated strategies for controlling these parameters could potentially further balance accuracy and efficiency.
  • Future Work: The authors mention that other promising penalty functions exist and could be explored for specific application domains. Further investigation into these alternative penalty functions is suggested.

Summary updated

Abstract

Many optimization problems in computational science and engineering (CS&E) 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 addresses the more difficult problem of general nonlinear programming where derivatives for objective or constraint functions are unavailable, which is the case for many CS&E applications. We focus on penalty methods that use GSS to solve the linearly-constrained problems, comparing different penalty functions. A classical choice for penalizing constraint violations is {ell}{sub 2}{sup 2}, the squared {ell}{sub 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}{sub 1}, {ell}{sub 2}, and {ell}{sub {infinity}} norms converge to good approximate solutions more quickly and thus are attractive alternatives. Unfortunately, exact penalty functions are discontinuous and consequently introduce theoretical problems that degrade the final solution accuracy, so we also consider smoothed variants. Smoothed-exact penalty functions are theoretically attractive because they retain the differentiability of the original problem. Numerically, they are a compromise between exact and {ell}{sub 2}{sup 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 many CS&E optimization problems are characterized by expensive function evaluations, reducing the number of function evaluations is paramount, and the results of this paper show that exact and smoothed-exact penalty functions are well-suited to this task.
BibTeX
@misc{griffin2007nonlinearly,
  author = {Joshua Griffin and Tamara G. Kolda},
  title = {{Nonlinearly-constrained optimization using asynchronous parallel generating set search.}},
  year = {2007},
  doi = {10.2172/909393},
}
Figure