Source-linked AI summary
Global Deterministic Optimization with Artificial Neural Networks Embedded
Artur M Schweidtmann, Alexander Mitsos
TL;DR
ANN-embedded optimization needs deterministic global methods because local methods may return suboptimal solutions, while stochastic methods lack global-optimality guarantees. The paper proposes reduced-space McCormick relaxations with activation-function envelopes, implemented in MAiNGO, and evaluates them on four examples against BARON in CPU time. The reported comparison finds favorable computational solution time for the proposed method.
Problem
ANN-embedded optimization requires an efficient deterministic global optimization algorithm because local methods can be suboptimal and stochastic methods cannot guarantee global optimality.
Method
The method optimizes ANN surrogate models in reduced space using McCormick relaxations incorporating convex and concave activation-function envelopes, solved with MAiNGO.
Results
Across four optimization examples, the proposed method is compared with BARON in computational CPU time, with favorable solution time reported.
Takeaways & Limitations
Reduced-space deterministic global optimization provides an approach for globally optimizing problems with established ANN surrogate models.
Takeaways & Limitations
Complete elimination of equality constraints is not always possible when optimizing several MLPs or hybrid formulations, so some constraints and variables may remain.
Abstract
from arXiv · showhide
Artificial neural networks (ANNs) are used in various applications for data-driven black-box modeling and subsequent optimization. Herein, we present an efficient method for deterministic global optimization of ANN embedded optimization problems. The proposed method is based on relaxations of algorithms using McCormick relaxations in a reduced-space [\textit{SIOPT}, 20 (2009), pp. 573-601] including the convex and concave envelopes of the nonlinear activation function of ANNs. The optimization problem is solved using our in-house global deterministic solver MAiNGO. The performance of the proposed method is shown in four optimization examples: an illustrative function, a fermentation process, a compressor plant and a chemical process optimization. The results show that computational solution time is favorable compared to the global general-purpose optimization solver BARON.
2 Introduction
The introduction motivates deterministic global optimization for ANN-embedded problems because local methods can be suboptimal and stochastic methods cannot guarantee global optimality. It presents a reduced-space McCormick-relaxation approach and compares it with BARON on four examples.
- Local optimization can yield suboptimal solutions when ANN-learned input-output relations are multi-modal and activation functions are nonconvex.
- Stochastic global methods such as genetic algorithms and grid search cannot guarantee global optimality.
- The literature identifies a need for an efficient deterministic global optimization algorithm for problems with embedded ANNs.
- The contribution develops deterministic global optimization for given ANN surrogate models using a reduced-space formulation that hides network equations and variables from the optimizer.
- Compared with full-space formulations, reduced-space optimization addresses the large-scale structure caused by network layers, neurons, equations, and relaxation auxiliaries.
- The method is evaluated on four numerical examples and compared with BARON using computational CPU time.
3 Background on Multilayer Perceptrons
The paper describes multilayer perceptrons as feed-forward neural networks represented by layered directed acyclic graphs. Neurons apply affine combinations followed by activation functions, with tanh commonly used in hidden layers and identity in regression outputs.
- A multilayer perceptron is a feed-forward ANN represented as a directed acyclic graph of neuron layers.
- The network contains an input layer, hidden layers, and an output layer, with connections between successive-layer neurons carrying weights.
- Each neuron output is formed from a linear combination of outputs from the preceding layer followed by an activation function.
- The hyperbolic tangent is commonly used in hidden layers, while the identity activation is typically used for regression outputs.
- The proposed method focuses on tanh but can also be applied to other common activation functions such as sigmoid.
4 Method
The method embeds ANN surrogate models in reduced-space deterministic global optimization. It propagates activation-function envelopes through the network using McCormick relaxations, enabling branch-and-bound solution with smooth relaxations under stated structural limits.
- Optimization formulations: Full-space formulations expose all input, network, and auxiliary variables to the global optimizer, whereas reduced-space formulations optimize only over the original decision variables.
- Optimization formulations: In reduced space, network outputs are represented as functions of inputs, and network equality constraints are hidden from the optimization algorithm.
- Limitations: Reduced-space elimination is incomplete for arrangements involving several MLPs or hybrid formulations, where equality constraints and additional variables may remain.
- ANN relaxations: The method uses convex and concave envelopes of tanh and automatically propagates McCormick relaxations through ANN equations to bound network outputs.
- ANN relaxations: For MLPs using hyperbolic tangent and identity activations, the resulting relaxations are once continuously differentiable, with Lipschitz-continuous first derivatives.
- ANN relaxations: This C1,1 smoothness permits potentially more efficient optimization algorithms than the nonsmooth methods generally required by McCormick relaxations.
- ANN relaxations: The exact tanh envelopes are tighter than McCormick relaxations of several reformulations, while F3 provides stronger reformulation relaxations than F1, F2, and F4.
- Implementation: The implementation uses MAiNGO with branch-and-bound, automatic McCormick propagation, bound tightening, local upper bounding, and LP-based node relaxations.
5 Numerical Results
The numerical studies evaluate deterministic global optimization of ANN-embedded problems across illustrative and process examples, emphasizing formulation size, relaxation choice, and solver performance. Reduced-space formulations and activation-function envelopes generally improve computational efficiency, though complexity increases with network depth and the cumene case remains difficult.
- 5.1 Illustrative Example & Scaling of the Algorithm: All reduced-space optimizations converge to the same solution, -6.563, which differs by about 0.18% from the underlying peaks function's global optimizer.The difference is within the expected accuracy of the MLP prediction.
- 5.1 Illustrative Example & Scaling of the Algorithm: Increasing network depth raises CPU time approximately exponentially, and deep networks require more optimization time than shallow networks with the same or more neurons.The envelope approach consistently outperforms reformulation F3 in the reported scaling experiments.
- 5.2 Fermentation Process: In the fermentation process, the deterministic optimum is x1 = 156.466 g/L, x2 = 3 g/L, x3 = 57.086 mg/L, y = 170.127 g/L, and ygl = 99.937.The deterministic methods converge to the same solution, unlike the reported stochastic literature methods, whose solutions vary across executions.
- 5.2 Fermentation Process: For the fermentation process, the reduced-space envelope formulation takes 0.11 seconds, about 5.4 times less CPU time than the full-space formulation.The comparison is reported for the presented solver; alternative activation-function reformulations can favor BARON.
6 Conclusion and Future Work
The proposed reduced-space method combines McCormick relaxations with ANN activation-function envelopes for deterministic global optimization. Across four examples, it reduces problem size and achieves favorable computational performance, while shallow networks remain more efficient than deep ones.
- Method: The method formulates ANN embedded optimization in reduced space, hiding network variables and equations from the optimization algorithm.Lower bounds are computed by propagating McCormick relaxations through the network equations.
- Evaluation: Four examples—one illustrative function and three engineering applications—test the proposed deterministic global optimization approach.The engineering applications include fermentation, compressor plant, and chemical process optimization in the paper context.
- Results: Reduced-space formulations reduce the number of optimization variables and equality constraints, particularly for ANNs with many neurons.The reduction results from excluding internal ANN variables and network-equation constraints from the optimization problem.
- Results: The reduced-space formulation accelerates optimization by factors of up to four hundred thousand compared with the full-space formulation using the same solver.The paper also reports favorable performance relative to BARON, although direct comparison is complicated by BARON’s lack of hyperbolic-tangent activation support.
- Results: Single shallow ANNs with up to 700 neurons were optimized in under 10 seconds, whereas deep networks required more CPU time than shallow networks.The conclusion identifies shallow ANNs as currently more suitable for efficient optimization than deep ANNs.
- Limitations: The complex cumene process case study converged slowly, likely because relaxations propagated through many ANNs and equations.The engineering examples embedded up to 14 ANNs, and the considered problem sizes exceeded earlier deterministic ANN embedded optimization examples.
A.1 Convex and Concave Envelopes of the Hyperbolic Tangent Activation Function
The section constructs convex and concave envelopes for the hyperbolic tangent activation over bounded intervals, including intervals crossing zero. It establishes their smoothness, monotonicity, and derivative regularity.
- The envelopes are constructed on compact intervals D = [xL, xU], with separate forms depending on the interval's position relative to zero.For intervals crossing zero, breakpoint values are obtained by solving the stated tangency conditions numerically.
- For xL < 0 < xU, the hyperbolic tangent is nonconvex and nonconcave, motivating distinct convex and concave envelope constructions.
- When the interval lies entirely on one side of zero, one envelope coincides with tanh while the other is represented by a secant-based relaxation.
- The first derivatives of both envelopes are Lipschitz continuous because their second derivatives are bounded.The section states this regularity for both the convex and concave relaxations.
- The convex and concave envelopes are strictly monotonically increasing and once continuously differentiable (C1), but generally not C2.
A.2 Convex and Concave Envelopes of the Sigmoid Activation Function
This section derives convex and concave envelopes for the sigmoid activation by reformulating it in terms of the hyperbolic tangent function. Similar regularity results can therefore be derived for sigmoid envelopes.
- The sigmoid activation is reformulated as sig(x) = 1/2(1 + tanh(x/2)) to obtain its convex and concave envelopes.
- The sigmoid envelopes are derived using the reformulation together with the convex and concave envelopes of the hyperbolic tangent.
- The manuscript does not provide proofs for the smoothness and monotonicity of the sigmoid envelopes.
- Similar results to the hyperbolic tangent case can be derived for the sigmoid activation, including envelope monotonicity.
A.3 McCormick Relaxations of Reformulations of the Hyperbolic Tangent Activation Function
This section considers reformulations of tanh for solvers where the hyperbolic tangent is unavailable. It compares their McCormick relaxations and identifies cases where reformulations weaken relaxation quality or smoothness.
- Four reformulations F1, F2, F3, and F4 express the hyperbolic tangent using exponential functions.
- McCormick convex and concave relaxations can be computed for the reformulated functions using MC++.
- On specific intervals such as D = [-1, 1], relaxations of F1, F2, and F4 are weaker than those of F3.
- The relaxations of F1, F2, and F4 are not differentiable, and reformulation-based relaxations are considerably weaker than direct hyperbolic-tangent envelopes.