# Optimisation globale à complexité réduite: Application à divers problèmes industriels

Benjamin Ivorra, Damien Isèle, Bijan Mohammadi

► To cite this version:

Benjamin Ivorra, Damien Isèle, Bijan Mohammadi. Optimisation globale à complexité réduite: Application à divers problèmes industriels. 7e colloque national en calcul des structures, CSMA, May 2005, Giens, France. http://hal-01812962

HAL Id: hal-01812962

https://hal.science/hal-01812962

Submitted on 12 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Optimisation globale à complexité réduite

## Application à divers problèmes industriels

Benjamin Ivorra, Damien Isèbe & Bijan Mohammadi

Laboratoire I3M
Bâtiment 9 - Université Montpellier 2
Place Eugène Bataillon
34095 Montpellier Cedex
mohamadi@math.univ-montp2.fr

**ABSTRACT.** In this paper we introduce two main ideas :

We reformulate global optimization problems in term of boundary value problem (BVP). This allow us to introduce new optimization algorithms using what is known to solve BVPs. Indeed, current optimization methods, including non-deterministic ones, are based on discretization of initial value problems for differential equations.

On the other hand, we introduce low complexity sensitivity evaluation techniques using incom- plete sensitivity concept, reduced complexity models and multi-level discretizations. Sensitivity knowledge permits to distinguish between points of a Pareto front in multi-criteria optimization problems characterizing these points from a robustness point of view.

**RÉSUMÉ.** Dans cette présentation nous présentons deux idées :

Reformuler les problèmes d'optimisation globale en terme de problème à valeurs aux limites. Ceci permet de présenter les problèmes d'optimisation globale sous un nouvel angle et de dé- couvrir de nouveaux algorithmes en utilisant ce que l'on connaît sur la résolution des problèmes à valeurs aux limites. En effet, toutes les méthodes d'optimisation actuelles, y compris les non- déterministes, sont basées sur la résolution de problèmes à valeurs initiales pour des équations différentielles.

Nous introduirons aussi les techniques de calcul de sensitivités à faible complexité telles que les gradients incomplets, les modèles à complexité réduite et les discrétisations à niveaux multiples. Ceci est intéressant en optimisation sous contrainte, même lors de l'utilisation des techniques sans gradient. En effet, cette information supplémentaire permet de discriminer entre les points d'un front de Pareto en optimisation multi-critère, en mettant en évidence le caractère plus ou moins robuste d'un point du front.

**KEYWORDS:** Shape optimization; Global optimization; Microfluidic mixers

**MOTS-CLÉS :** Optimisation de forme ; Optimisation globale ; Mélangeur Microfluidique
# 1. Introduction

A fundamental remark on classical gradient based minimization algorithms, having a continuous representation as a cauchy problem for a first order dynamic system [MOH 02, ATT 96], is that they can find the global minimum if the initial condition belongs to the attraction basin of the infimum and that otherwise the minimizing sequence they build is in principle captured by a local minimum. In that sense, the problem of global minimization with a gradient based algorithm becomes the prescription of an initial condition for the mentioned Cauchy problem in the suitable attraction basin. On the other hand, one notice that minimization algorithms, including non-deterministic ones such as genetic algorithms, are discrete forms of first or second order ODE (or system of ODEs) [IVO 05a]. This paper presents a formulation of global minimization problems in term of over-determined boundary value problems (BVP) and show how to solve these using methods for the solution BVPs.

Another important issue in minimization is sensitivity evaluation. Gradients are useful in constrained optimization even if a gradient free approach is used. Indeed, the knowledge of sensitivity permits to qualify various points of a Pareto front from the point of view of robustness. However, sensitivity evaluation for large dimension minimization problems is not an easy task. The most efficient approach is to use an adjoint variable with the difficulty that it requires the development of specific software [CéA 71, MOH 02]. We show how to reduce the effort in sensitivity evaluation introducing the concept of incomplete sensitivity.

These ingredients are illustrated on various configurations of industrial optimizations.

# 2. Low-complexity Global optimization method

Most deterministic minimization algorithms can be seen as discretizations of the following dynamical system [MOH 01, MOH 02]:

$$M(t)\dot{x}(t) = -d(x(t)), x(t = 0) = x_0 \quad [1]$$

where $d$ is the descent direction and $M$ a matrix.

For example when $d = \nabla J$ and $M = Id$ (resp. $M = \nabla^2 J$), we recover the classical steepest descent (resp. Newton method).

In addition, we make the following assumptions [IVO 06]: $J \in C^1(\Omega_{ad}, \mathbb{R})$ and coercive. The infimum $J_m$ exist and is known. The problem is admissible: $\exists x_m \in \Omega_{ad}$ such that $J(x_m) = J_m$.

We consider that system [1] has a solution if for a given $x_0 \in \Omega_{ad}$, we can find a finite $T_{x_0}$ such that $J(x(T_{x_0})) = J_m$:

$$M(t)\dot{x}(t) = -d(x(t)), x(0) = x_0, J(x(T_{x_0})) = J_m \quad [2]$$
This is an over-determined boundary value problem which can be solved using classical techniques for BVPs (e.g. shooting, finite differences,...). Because we are interested by constrained global optimization we prefer to express the condition at $T_{x_0}$ on the functional instead of its gradient. Indeed, in our context first order optimality condition is usually not satisfied at infimum.

This over-determination is an explanation of why we should not solve global optimization problems with methods which are particular discretizations of first order differential systems. We could use variants of classical methods after adding second order derivatives [ATT 96]:

$$ \eta\ddot{x}(t) + M(t)\dot{x}(t) = -d(x(t)), x(0) = x_0, \quad \dot{x}(0) = \dot{x}_0, J(x(T_{x_0})) = J_m \quad [3] $$

with $\eta \in \mathbb{R}$. In practice, we consider $|\eta| << 1$ in order not to introduce too much perturbation in the method.

The over determination can be removed, for instance, by considering $x_0 = v$ for [1] (resp. $\dot{x}(0) = v$ for [3]) as a new variable to be found by the minimization of:

$$ h(v) = J(x_v(T_v)) - J_m \quad [4] $$

where $x_v(T_v)$ is the solution of [1] (resp. [3]) found at $t = T_v$ starting from $v$.

To perform the minimization of [4], we then consider the following algorithm $A_1(v_1, v_2)$, with $(v_1, v_2) \in \Omega^2$:

- $(v_1, v_2)$ given,

- Find $v \in \argmin_{w \in \mathcal{O}(v_2)} h(w)$ where $h(w) = J(x_w(T_w)) - J_m$, with $x_w(T_w)$ solution of system [1] found at $t = Z_w$ starting from $w$, and $\mathcal{O}(v_2) = \{tv_1v_2, t \in \mathbb{R}\} \cap \Omega_{ad}$.

- return $v$

The line search minimization might fail. For instance, a secant method degenerates on plateau and critical points. In that case, we add an external level to the algorithm $A_1$, keeping $v_1$ unchanged, and looking for $v_2$ by minimizing a new functional $\tilde{h}$ defined by:

$$ \tilde{h}(w) = h(A_1(v_1, w)) \quad [5] $$

To perform the minimization of [5], we then consider the following two-level algorithm $A_2(v_1, \tilde{v}_2)$, with $(v_1, \tilde{v}_2) \in \Omega^2$:

- $(v_1, \tilde{v}_2)$ given,

- Find $\tilde{v} \in \argmin_{w \in \mathcal{O}(\tilde{v}_2)} \tilde{h}(w)$ where $\tilde{h}(w) = h(A_1(v_1, w))$ and $\mathcal{O}(\tilde{v}_2) = \{\underset{\rightarrow}{tv_1\tilde{v}_2}, t \in \mathbb{R}\} \cap \Omega_{ad}$.

- return $\tilde{v}$
The choice of initial conditions in this algorithm contains the non-deterministic feature of the algorithm. The construction can be pursued building recursively $h^i(v^i) = \min_{v^i} h^{i-1}(v^i)$ using $A_{i-1}(v_1, v^i)$, with $h^1(v) = h(v)$, $h^2(v) = \tilde{h}(v)$ where $i$ denotes the external level. Mathematical background for this algorithm and validation on academic test cases and solution of nonlinear PDEs as well as geometrical interpretations of the different functionals ($J, h, h^2, h^3, ...$) are available in [MOH 02, IVO 05a].

In practice, the algorithm gives satisfaction if the trajectory passes close enough to the infimum (i.e. in $B_{\epsilon}(x_m)$ where $\epsilon$ defines the accuracy in the capture of the infimum). This means that we should consider for $h$ a functional of the form $h(v) = \int_{T_1}^{T} (J(x_v(\tau)) - J_m)^2 d\tau$, for $0 < T_1 < \tau < T$ where $x_v(\tau)$ is the trajectory generated by [1] and $T_1 = T/2$ for instance. Also, in the algorithm above $x_w(T_w)$ is replaced by the best solution found over $[0, T_w]$.

In cases $J_m$ is unknown, we set $J_m = -\infty$ and look for the best solution for a given complexity and computational effort.

### 3. Low-complexity sensitivity

Consider a general simulation loop, leading from shape parametrization $x$ to the cost functional $J$:

$$J(x) : x \to q(x) \to U(q(x)) \to J(x, q(x), U(q(x))) \quad [6]$$

where $q$ is the shape geometry, $U$ is the state equation solution.

The Jacobian of $J$ is given by:

$$\frac{dJ}{dx} = \frac{\partial J}{\partial x} + \frac{\partial J}{\partial q} \frac{\partial q}{\partial x} + \frac{\partial J}{\partial U} \frac{\partial U}{\partial q} \frac{\partial q}{\partial x} \quad [7]$$

An incomplete definition of the sensitivity [MOH00] can be used, neglecting state variations, if the cost function is, or can be reformulated, to have the following characteristics: The cost function $J$ and the parameterization $x$ are defined on the shape (or a same part of it). $J$ is of the form: $J(x) = \int_{\Gamma} f(x, q)g(u)d\gamma$ where $\Gamma$ = shape or part of the shape, which means that it involves a product of geometrical and state based functions. The shape curvature is not too high (this has to be quantified). This leads to neglecting the last term in [7].

We can illustrate this idea on the following simple example. Consider as cost function $J(a) = a^n u_x(a)$ and as state equation the following diffusion equation: $-u_{xx} = 1$, on $]\epsilon, 1[$, $u(\epsilon) = 0$, $u(1) = 0$, which has as solution $u(x) = -x^2/2 + ((\epsilon - 1)x)/2 - (\epsilon x)/2n$. We are in the domain of application of the incomplete sensitivities: The cost function is product of state and geometrical quantities (larger is $n$, better is the approximation). It is defined at the boundary. The curvature of the boundary is small (here no curvature at all). The gradient of $J$ with respect to $\epsilon$ is given by: $J_{\epsilon}(\epsilon) = \epsilon^{n-1}(nu_x(\epsilon) + \epsilon u_{x\epsilon}(\epsilon)) = \frac{\epsilon^{n-1}}{2}(-n(\epsilon + 1) - \epsilon)$. The second
term between parenthesis is the state linearization contribution which is neglected in incomplete sensitivities. We can see that the sign of the gradient is always correct and the approximation is better for large $n$.

One way to improve incomplete evaluation of sensitivities is to use reduced complexity models which provide an inexpensive approximation of the missing term in [7] (i.e. the last term). For instance, consider the following reduced model for the definition of $\tilde{U}(x) \sim U(q(x))$. Suppose $\tilde{U}$ is a wall function to be used instead of the full flow equation on the wall and giving wall values knowing local internal flow description. The incomplete gradient of $J$ with respect to $x$ can be improved evaluating the former term in [7] linearizing the simple model. Note that $\tilde{U}$ is never used in the definition of the state $U$, but only in an approximation of $\partial\tilde{U}/\partial x$. It is also important to notice that the reduced model needs to be valid only over the support of the control parameters. More precisely, we linearize the following approximate simulation loop

$$x \to q(x) \to \tilde{U}(x)\left(\frac{U(q(x))}{\tilde{U}(x)}\right) \quad [8]$$

freezing $U(q(x))/\tilde{U}(x)$ which gives $\frac{dJ}{dx} \approx \frac{\partial J(U)}{\partial x} + \frac{\partial J(U)}{\partial q} \frac{\partial q}{\partial x} + \frac{\partial J(U)}{\partial U} \frac{\partial \tilde{U}}{\partial x} \frac{U(q(x))}{\tilde{U}(x)}$.

A simple example shows the importance of the scaling introduced in [8]. Consider $U(x) = \log(1+x)$ scalar for simplicity and $J(x) = U^2(x)$ with $dJ(x)/dx = 2U(x)U'(x) = 2\log(1+x)(1+x) \sim 2\log(1+x)(1-x+x^2)$ and consider $\tilde{U}(x) = x$ as the reduced complexity model, valid around $x=0$. To see the impact of the scaling factor we compare $J'(x) \sim 2U(x)\tilde{U}'(x) = 2\log(1+x)$ with $J'(x) \sim 2U(x)\tilde{U}'(x)(U(x)/\tilde{U}(x)) = 2\log(1+x)(\log(1+x)/x) \sim 2\log(1+x)(1-x/2+x^2/3...)$.

Another way to define low-complexity models is to use a different level of discretization for $U$ with the same state equation. We can look for state sensitivity on coarse meshes while the state is evaluated on much finer discretizations:

$$\frac{dJ}{dx} = \frac{\partial J}{\partial x}(U_f, q_f) + \frac{\partial J}{\partial q}(U_f, q_f) + \frac{\partial J}{\partial U}(U_f, q_f) \frac{\partial q}{\partial x}(I_f^c U_f, q_c) \text{ where } I_f^c \text{ is an interpolation operator between the fine and coarse meshes, } f \text{ and } c \text{ subscripts denote fine and coarse meshes with typically 4 times more mesh nodes in the fine mesh. By fine mesh we mean a mesh enough fine for the solution to become independent from the mesh. This means that the linearization is performed on a coarse mesh, however around an accurate state variable computed on a fine mesh. In that case, obviously if the coarse mesh tends to the fine one, the approximate gradient tends to the gradient on the fine mesh.}$$

## 4. Applications

We illustrate the previous ingredients through the following optimization problems: temperature and pollution control in a bunsen flame [DEB 04], shape optimization of coastal structures [ISE 05], shape optimization of fast-microfluidic-mixer devices [IVO 05b], optical multiplexer fibers design [IVO 04], shape optimization of
under aerodynamic and acoustic constraints for internal and external flows [MOH 01, MOH 04b, MOH 04a].

## 5. Conclusion

A global optimization algorithm based on the solution of boundary value has been presented. To keep the computational complexity low and make optimization problems easy to solve with industrial softwares approximate gradient evaluation has been introduced.

## 6. References

[ATT 96] ATTOUCH H., COMINETTI R., "A dynamical approach to convex minimization coupling approximation with the steepest descent method.", *J. Differential Equations*, vol. 128, num. 2, 1996, p. 519-540.

[CéA 71] CÉA J., *Optimisation théorie et algorithmes*, 1971.

[DEB 04] DEBIANE L., IVORRA B., MOHAMMADI B., NICOUD F., ERN A., POINSOT T., PITSCH H., "Temperature and pollution control in flames", *Proceeding of the Summer Program*, Center for Turbulence Research, NASA/Stanford Univ., 2004, p. 367-375.

[ISE 05] ISEBE D., MOHAMMADI B., AZERAD P., IVORRA B., BOUCHETTE F., "Optimal Shape Design of Coastal Structures", *Proceeding of Siam on Mathematical & Computational Issues in the Geosciences*, 2005.

[IVO 04] IVORRA B., MOHAMMADI B., DUMAS L., MOREAU Y., PILLE G., DURAND O., "Apodisation de fibres à réseaux de Bragg pour la synthèse de codes CDMA spectral", *IEEE Lasers and Electro-Optics Society French Chapter*, vol. Conference COSTO04, 2004.

[IVO 05a] IVORRA B., MOHAMMADI B., REDONT P., "Low-Complexity Global Optimization by Solution of BVP", *Optimal Control and Applied Mathematics*, vol. submitted, 2005.

[IVO 05b] IVORRA B., MOHAMMADI B., SANTIAGO J.G. AND HERTZOG D., "Design of Fast Microfluidic Protein Folding Devices by a Semi-Deterministic Global Optimization Algorithm", *Proceeding of Congrès Français de Mécanique 05*, 2005.

[IVO 06] IVORRA B., "Semi-Deterministic Global Optimization", PhD. University of Montpellier 2, 2006.

[MOH 01] MOHAMMADI B., PIRONNEAU O., *Applied Shape Optimization for Fluids*, Oxford University Press, 2001.

[MOH 02] MOHAMMADI B., SAIAC J.-H., "Pratique de la simulation numérique", Dunod, 2002.

[MOH 04a] MOHAMMADI B., "Optimization of aerodynamic and acoustic performances of supersonic civil transports", *International J. Numerical Methods for Heat & Fluid Flow*, vol. 14, num. 7, 2004.

[MOH 04b] MOHAMMADI B., PIRONNEAU O., "Shape Optimization in Fluid Mechanics", *Annual Review of Fluid Mechanics*, vol. 36, 2004, p. 255-279.