A trust-region funnel algorithm for gray-box optimization

1. Problem Statement

The paper addresses Grey-Box Optimisation, a class of problems common in process systems engineering where the objective function and constraints are composed of two distinct types of models:

• Glass-Box (Explicit) Models: Algebraic equations with known analytic derivatives (e.g., mass/energy balances).
• Black-Box (Implicit) Models: Expensive simulations or proprietary tools (e.g., CFD, Aspen Plus) that lack analytic derivatives and are computationally costly to evaluate.

Challenges:

• Traditional Nonlinear Programming (NLP) solvers struggle when black-box components are present due to the lack of gradients.
• Existing Trust-Region (TR) Filter methods (the current state-of-the-art) are robust but suffer from:
  • Complexity in tuning multiple parameters (e.g., filter parameters $\lambda_\theta, \lambda_f$).
  • The need to maintain a list of non-dominated pairs (objective vs. infeasibility), which can be computationally heavy.
  • Potential stalling when reduced model (RM) errors dominate the process.
• Other alternatives like DEFT-FUNNEL or ARGONAUT are often algorithmically complex, lack open-source implementations, or rely on global multi-start strategies that are not scalable for large-scale NLPs.

2. Methodology: The Trust-Region Funnel Algorithm

The authors propose a novel Trust-Region (TR) Funnel Algorithm that integrates the robustness of TR methods with a "funnel" mechanism for handling infeasibility, replacing the traditional filter acceptance criterion.

Key Formulation:

• Decoupling: The problem is reformulated by introducing auxiliary variables to separate explicit glass-box equations from implicit black-box mappings $t(w)$.
• Reduced Models (RMs): Local surrogates (linear, quadratic, Taylor series, or Gaussian Processes) are constructed for the black-box components within a specific sampling region ($\sigma^{(k)}$).
• $\kappa$-Fully Linear Property: The RMs are required to satisfy error bounds proportional to the sampling radius, ensuring accuracy near the current iterate.

The Funnel Mechanism:
Instead of a filter that manages a set of (objective, infeasibility) pairs, the funnel method maintains a monotonically non-increasing upper bound (the "funnel width" $\phi^{(k)}$) on the infeasibility measure $\theta(x)$ (the error between the RM prediction and the true black-box response).

• Step Acceptance: A trial step is accepted if it satisfies the funnel condition $\theta(x^{(k)} + s^{(k)}) \leq \phi^{(k)}$.
• Step Types:
  • $f$-type steps: Improve the objective function while satisfying the funnel condition. The funnel width remains unchanged.
  • $\theta$-type steps: Reduce the infeasibility measure. The funnel width is tightened (reduced) according to a specific update rule.
• Globalisation: The algorithm dynamically adjusts the Trust-Region radius ($\Delta^{(k)}$) and the sampling radius ($\sigma^{(k)}$). Crucially, while $\sigma^{(k)}$ contracts to ensure RM accuracy and convergence, $\Delta^{(k)}$ can remain large to allow significant steps in the glass-box variables.

Algorithmic Flow:

1. Criticality Check: Assess proximity to a KKT point. If close, reduce the sampling radius.
2. Compatibility Check: Ensure the local TR subproblem (TRSP) is feasible with the current RM. If not, enter a Restoration Phase.
3. TRSP Solution: Solve the subproblem to find a candidate step.
4. Acceptance Logic:
   • If the step improves the objective ($f$-type) and satisfies Armijo conditions, accept and expand TR.
   • If the step reduces infeasibility ($\theta$-type) and satisfies the funnel decrease condition, accept and shrink the funnel width.
   • Otherwise, reject the step and shrink the TR radius.

3. Key Contributions

1. Novel Algorithm: Introduction of a TR Funnel algorithm specifically designed for grey-box optimisation, replacing the complex filter mechanism with a simpler, single-parameter funnel constraint.
2. Rigorous Convergence Proof: The paper provides a global convergence proof showing that the algorithm converges to a first-order KKT point (stationary point) of the original grey-box problem. The proof relies on the contraction of the sampling radius $\sigma^{(k)}$ rather than the TR radius.
3. Open-Source Implementation: The algorithm is implemented in Pyomo, an open-source Python framework. It supports multiple RM forms (Linear, Quadratic, Taylor, Gaussian Process) and allows users to switch between Filter and Funnel strategies.
4. Simplified Tuning: By removing the need for a filter set and associated heuristic parameters ($\lambda_\theta, \lambda_f$), the method reduces the sensitivity to parameter tuning, making it more accessible for industrial application.

4. Results

The authors benchmarked the TR Funnel algorithm against the classical TR Filter method across seven problems: three numerical benchmarks (Colville, Himmelblau, Loeppky) and four engineering/process design problems (Wing Weight, Welded Beam, Williams-Otto, Biomass Hydrogen).

Key Findings:

• Performance: The TR Funnel method achieved comparable or improved performance relative to the TR Filter.
  • In numerical benchmarks (e.g., Colville with Quadratic RMs), the Funnel method required up to 4–135 times fewer external black-box evaluations and significantly less CPU time.
  • For engineering problems (Wing Weight, Welded Beam), both methods converged to the same optimal values, but the Funnel method often required fewer iterations and evaluations, particularly when using lower-fidelity RMs.
• Step Efficiency: The Funnel method exhibited a higher proportion of $f$-type steps (optimality steps) and fewer $\theta$-type steps (feasibility correction steps) compared to the Filter method. This indicates a smoother convergence trajectory where feasibility is maintained more efficiently.
• Robustness: The algorithm successfully handled highly infeasible starting points (e.g., Welded Beam with initial infeasibility of 9.1) by rapidly reducing infeasibility via restoration and $\theta$-steps before switching to objective minimization.
• Scalability: The method performed well on large-scale process problems (e.g., Biomass Hydrogen with 83 variables and 69 constraints), converging in 193 iterations with stable feasibility enforcement.

5. Significance

This research provides a simpler, extensible, and theoretically sound alternative to the widely used TR Filter method for grey-box optimisation.

• Practical Impact: By reducing the need for manual parameter tuning and lowering the computational cost of expensive black-box evaluations, the method is more suitable for complex industrial process design and optimisation.
• Theoretical Advancement: The derivation of a global convergence proof for the funnel approach in the grey-box context bridges a gap between NLP theory and practical derivative-free optimisation.
• Accessibility: The open-source Pyomo implementation democratizes access to advanced grey-box optimisation techniques, allowing researchers and engineers to easily integrate funnel-based strategies into their workflows.

In conclusion, the TR Funnel algorithm effectively balances the trade-off between feasibility and optimality in grey-box problems, offering a robust tool for large-scale process systems engineering where derivative information is partially unavailable.