NOWPAC: A provably convergent derivative-free nonlinear optimizer with path-augmented constraints

F. Augustin, Youssef MarzoukarXiv 2014 · DOI · arXiv

Abstract

This paper introduces NOWPAC (Nonlinear Optimization With Path-Augmented Constraints), a derivative-free optimization (DFO) algorithm designed for complex engineering problems where objective and constraint functions are "black boxes." NOWPAC utilizes a trust-region framework with fully linear models and a novel inner boundary path (IBP) scheme to ensure feasible trial steps. We provide a rigorous proof of convergence to first-order critical points and introduce a noise indicator to handle numerical errors in simulation data.

Introduction: The Challenge of Black-Box Optimization

In modern engineering, performance evaluation often relies on high-fidelity simulations. These simulations are typically "black boxes": they provide outputs $f(x)$ and constraint values $c(x)$ for given inputs $x$, but offer no gradient information. This presents two significant hurdles:

  1. Lack of Derivatives: Standard gradient-based optimization cannot be applied directly.
  2. Numerical Noise: Simulations often contain small numerical errors. As an optimizer approaches a solution, these "wiggles" can be misinterpreted as local optima, causing the algorithm to fail.

While various DFO methods exist, few provide the mathematical guarantees of convergence required for reliable industrial application, especially under general nonlinear constraints.

Methodology: The NOWPAC Framework

NOWPAC operates using a trust-region framework. At each iteration, it constructs local surrogate models (linear or quadratic approximations) of the objective and constraints based on sampled simulation data.

The Inner Boundary Path (IBP)

The defining feature of NOWPAC is the Inner Boundary Path (IBP). Rather than simply attempting to satisfy constraints, NOWPAC introduces an adaptive offset that pushes the search into the interior of the feasible set.

The Inner Boundary Path (IBP) construction at different points within the feasible region X.

This mechanism serves two purposes:

  • Local Convexification: It smooths the feasible region, facilitating the identification of valid search directions.
  • Feasibility Buffer: By maintaining a distance from the boundaries, it ensures that trial steps remain "safe," preventing simulation crashes caused by infeasible inputs.
The IBP effectively handles complex boundary geometries, such as sharp corners, ensuring robust convergence.

Noise Detection via Hessian Monitoring

To address numerical noise, NOWPAC monitors the curvature (Hessian) of its surrogate models. An unnatural spike in the Hessian norm relative to the trust-region size indicates that the algorithm is "fitting the noise." This trigger allows the solver to terminate or adjust its precision, preventing it from wasting computational resources on spurious data features.

Experimental Evaluation

The authors validated NOWPAC across a diverse set of problems:

  • Analytical Benchmarks: Testing on the Rosenbrock function and constrained anisotropic exponential problems.
  • Schittkowski Library: A comprehensive suite of over 300 nonlinear programming problems.
  • Industrial Case Study: A simulation of a tar removal process in a biomass-to-liquid plant, characterized by expensive evaluations and inherent numerical noise.

Key Results

  • Superior Efficiency: On the Schittkowski benchmarks, NOWPAC required significantly fewer function evaluations than established solvers like COBYLA, NOMAD, and GSS-NLC.
  • Strict Feasibility: In the industrial tar removal study, NOWPAC identified more efficient designs than COBYLA while strictly adhering to safety constraints—a task where COBYLA occasionally failed.
  • Robustness: The noise indicator successfully prevented the algorithm from "chasing ghosts" in noisy environments, ensuring reliable termination at the limits of simulation precision.

Conclusion and Future Work

NOWPAC offers a mathematically rigorous and computationally efficient solution for constrained black-box optimization. By combining an innovative IBP scheme with robust noise detection, it bridges the gap between theoretical convergence and practical engineering needs. Future research will focus on extending NOWPAC to global optimization and stochastic settings where objective functions are subject to random variation.

Summary updated

Abstract

This paper proposes the algorithm NOWPAC (Nonlinear Optimization With Path-Augmented Constraints) for nonlinear constrained derivative-free optimization. The algorithm uses a trust region framework based on fully linear models for the objective function and the constraints. A new constraint-handling scheme based on an inner boundary path allows for the computation of feasible trial steps using models for the constraints. We prove that the iterates computed by NOWPAC converge to a first-order critical point. We also discuss the convergence of NOWPAC in situations where evaluations of the objective function or the constraints are inexact, e.g., corrupted by numerical errors. We determine a rate of decay that the magnitude of these numerical errors must satisfy, while approaching the critical point, to guarantee convergence. In settings where adjusting the accuracy of the objective or constraint evaluations is not possible, as is often the case in practical applications, we introduce an error indicator to detect these regimes and prevent deterioration of the optimization results.
BibTeX
@misc{augustin2014nowpac,
  author = {F. Augustin and Youssef Marzouk},
  title = {{NOWPAC: A provably convergent derivative-free nonlinear optimizer with path-augmented constraints}},
  year = {2014},
  eprint = {1403.1931},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.1931},
}
Figure