The purpose of this article is to introduce a gradient-flow algorithm for solving equality and inequality constrained optimization problems, which is particularly suited for shape optimization applications. We rely on a variant of the Ordinary Differential Equation (ODE) approach proposed by Yamashita (Math. Program. 18 (1980) 155–168) for equality constrained problems: the search direction is a combination of a null space step and a range space step, aiming to decrease the value of the minimized objective function and the violation of the constraints, respectively. Our first contribution is to propose an extension of this ODE approach to optimization problems featuring both equality and inequality constraints. In the literature, a common practice consists in reducing inequality constraints to equality constraints by the introduction of additional slack variables. Here, we rather solve their local combinatorial character by computing the projection of the gradient of the objective function onto the cone of feasible directions. This is achieved by solving a dual quadratic programming subproblem whose size equals the number of active or violated constraints. The solution to this problem allows to identify the inequality constraints to which the optimization trajectory should remain tangent. Our second contribution is a formulation of our gradient flow in the context of – infinite-dimensional – Hilbert spaces, and of even more general optimization sets such as sets of shapes, as it occurs in shape optimization within the framework of Hadamard’s boundary variation method. The cornerstone of this formulation is the classical operation of extension and regularization of shape derivatives. The numerical efficiency and ease of implementation of our algorithm are demonstrated on realistic shape optimization problems.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/cocv/2020015
Mots-clés : Nonlinear constrained optimization, gradient flows, shape and topology optimization, null space method
@article{COCV_2020__26_1_A90_0,
author = {Feppon, F. and Allaire, G. and Dapogny, C.},
title = {Null space gradient flows for constrained optimization with applications to shape optimization},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {26},
year = {2020},
doi = {10.1051/cocv/2020015},
mrnumber = {4174416},
zbl = {1464.65064},
language = {en},
url = {http://www.numdam.org/articles/10.1051/cocv/2020015/}
}
TY - JOUR AU - Feppon, F. AU - Allaire, G. AU - Dapogny, C. TI - Null space gradient flows for constrained optimization with applications to shape optimization JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2020 VL - 26 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv/2020015/ DO - 10.1051/cocv/2020015 LA - en ID - COCV_2020__26_1_A90_0 ER -
%0 Journal Article %A Feppon, F. %A Allaire, G. %A Dapogny, C. %T Null space gradient flows for constrained optimization with applications to shape optimization %J ESAIM: Control, Optimisation and Calculus of Variations %D 2020 %V 26 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv/2020015/ %R 10.1051/cocv/2020015 %G en %F COCV_2020__26_1_A90_0
Feppon, F.; Allaire, G.; Dapogny, C. Null space gradient flows for constrained optimization with applications to shape optimization. ESAIM: Control, Optimisation and Calculus of Variations, Tome 26 (2020), article no. 90. doi : 10.1051/cocv/2020015. http://www.numdam.org/articles/10.1051/cocv/2020015/
[1] and , Projection-like retractions on matrix manifolds. SIAM J. Optim. 22 (2012) 135–158. | DOI | MR | Zbl
[2] , and , Optimization algorithms on matrix manifolds. Princeton University Press, Princeton (2009). | MR | Zbl
[3] , Conception optimale de structures, Vol. 58 of Mathématiques & Applications. Springer-Verlag, Berlin (2007). | MR | Zbl
[4] and , Minimum stress optimal design with the level set method. Eng. Anal. Bound. Elements 32 (2008) 909–918. | DOI | Zbl
[5] and , Structural optimization with freefem++. Struct. Multidiscipl. Optim. 32 (2006) 173–181. | DOI | MR | Zbl
[6] , and , Structural optimization using sensitivity analysis and a level-set method. J. Comput. Phys. 194 (2004) 363–393. | DOI | MR | Zbl
[7] , and , Shape optimization with a level set based mesh evolution method. Comput. Methods Appl. Mech. Eng. 282 (2014) 22–53. | DOI | MR | Zbl
[8] , and , Casting constraints in structural optimization via a level-set method, in 10th world Congress on Structural and Multidisciplinary Optimization (2013).
[9] , and , Thickness control in structural optimization via a level set method. Struct. Multidiscipl. Optim. 53 (2016) 1349–1382. | DOI | MR
[10] , , , and , Structural optimization under overhang constraints imposed by additive manufacturing technologies. J. Comput. Phys. 351 (2017) 295–328. | DOI | MR | Zbl
[11] , and , Existence and uniqueness of maximal regular flows for non-smooth vector fields. Arch. Ration. Mech. Anal. 218 (2015) 1043–1081. | DOI | MR | Zbl
[12] , and , CVXOPT: A Python package for convex optimization Available at http://cvxopt.org/ (2012).
[13] , , and , Shape deformation analysis from the optimal control viewpoint. J. Math. Pures Appl. 104 (2015) 139–178. | DOI | MR | Zbl
[14] and , Domain optimization analysis in linear elastic problems: approach using traction method. JSME Int. J. Ser. A, Mech. Mater. Eng. 39 (1996) 272–278.
[15] and , A gradient-type algorithm for optimization with constraints, submitted for publication, see also Pre-PrintCMAF Pre-2011-001 at http://cmaf.ptmat.fc.ul.pt/preprints.html (2011).
[16] , and , A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discr. Cont. Dyn. Syst. B 22 (2020) 1729–1755. | MR | Zbl
[17] , , and , Numerical optimization: theoretical and practical aspects. Springer Science & Business Media, Berlin (2006). | MR | Zbl
[18] , Functional analysis, Sobolev spaces and partial differential equations. Springer Science & Business Media, Berlin (2010). | MR | Zbl
[19] and A fast non-negativity-constrained least squares algorithm. J. Chemometr. 11 (1997) 393–401. | DOI
[20] , and , An accurate anisotropic adaptation method for solving the level set advection equation. Int. J. Num. Methods Fluids 70 (2012) 899–922. | DOI | MR | Zbl
[21] , A framework for the construction of level set methods for shape optimization and reconstruction. Interfaces Free Bound. 5 (2003) 301–329. | DOI | MR | Zbl
[22] , and , Three-dimensional adaptive domain remeshing, implicit domain meshing, and applications to free and moving boundary problems. J. Comput. Phys. 262 (2014) 358–378. | DOI | MR | Zbl
[23] , , and , Geometrical shape optimization in fluid mechanics using FreeFem++, in Structural and Multidisciplinary Optimization. Springer, Germany (2017) 1–28. | MR
[24] Velocity extension for the level-set method and multiple eigenvalues in shape optimization. SIAM J. Control Optim. 45 (2006) 343–367. | DOI | MR | Zbl
[25] and , A survey of numerical methods for ivps of odes with discontinuous right-hand side. J. Comput. Appl. Math. 236 (2012) 3967–3991. | DOI | MR | Zbl
[26] , Foundations of modern analysis. Academic press, New York (1960). | MR | Zbl
[27] and , Introducing the sequential linear programming level-set method for topology optimization. Struct. Multidiscipl. Optim. 51 (2015) 631–643. | DOI | MR
[28] and , Topology optimization of continuum structures with local stress constraints. Int. J. Numer. Methods Eng. 43 (1998) 1453–1478. | DOI | MR | Zbl
[29] , and , The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20 (1998) 303–353. | DOI | MR | Zbl
[30] , Optimisation de forme de matériaux et structures architecturés par la méthode des lignes de niveaux avec prise en compte des interfaces graduées. Ph.D. thesis, Grenoble Alpes (2017).
[31] , Shape and topology optimization of multiphysics systems. Ph.D. thesis, Thèse de doctorat de l’Université Paris Saclay préparée à l’Écolepolytechnique (2019).
[32] , , , and , Shape optimization of a coupled thermal fluid-structure problem in a level set mesh evolution framework. SerMA J. 76 (2019) 413–458. | MR | Zbl
[33] , Differential equations with discontinuous righthand sides: control systems. Vol. 18. Springer Science & Business Media, Berlin (2013).
[34] , Practical methods of optimization. John Wiley & Sons, New Jersey (2013). | MR | Zbl
[35] and , Shape variation and optimization, A geometrical analysis. English version of the French publication [MR2512810] with additions and updates. Vol. 28 of EMS Tracts in Mathematics, European Mathematical Society (EMS). Zürich (2018). | MR | Zbl
[36] , and , The primal-dual active set strategy as a semismooth newton method. SIAM J. Optim. 13 (2002) 865–888. | DOI | MR | Zbl
[37] and , On the complexity of equalizing inequalities. J. Global Optim. 27 (2003) 367–374. | DOI | MR | Zbl
[38] and , Constrained global optimization: adaptive gradient flows, in Frontiers in global optimization, Vol. 74 of Nonconvex Optimization and its Application. Kluwer Academic Publishing, Boston, MA (2004) 223–236. | DOI | MR | Zbl
[39] , Chapter 7 Morse Theory and Floer Homology. Springer Berlin Heidelberg (2011) 327–417.
[40] , , , and , Stress-based topology optimization for continua. Struct. Multidiscipl. Optim. 41 (2010) 605–620. | DOI
[41] , , and , Gradient descent only converges to minimizers, in 29th Annual Conference on Learning Theory. Edited by , and . Vol. 49 of Proceedings of Machine Learning Research Columbia University, New York, USA (2016) 1246–1257.
[42] and , A survey of manufacturing oriented topology optimization methods. Adv. Eng. Softw. 100 (2016) 161–175. | DOI
[43] , Analysis of recursive stochastic algorithms. IEEE Trans. Autom. Control 22 (1977) 551–575. | DOI | MR | Zbl
[44] , The gradient projection method along geodesics. Manag. Sci. 18 (1972) 620–631. | DOI | MR | Zbl
[45] and , Applied shape optimization for fluids. Oxford University Press, Oxford (2010). | MR | Zbl
[46] , , and , Adaptive sqp method for shape optimization, in Numerical Mathematics and Advanced Applications 2009. Springer, Berlin (2010) 663–673. | DOI | Zbl
[47] and , Sur le contrôle par un domaine géométrique, publications du Laboratoire d’Analyse Numérique, Université Pierre et Marie Curie (1976).
[48] and , Numerical optimization. Springer Science, Berlin (1999) 35. | MR | Zbl
[49] and , Fronts propagating with curvature-dependent speed: algorithms based on hamilton-jacobi formulations. J. Comput. Phys. 79 (1988) 12–49. | DOI | MR | Zbl
[50] and , Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. Preprint (2016). | arXiv | MR
[51] and , A dynamical systems approach to constrained minimization. Numer. Funct. Anal. Optim. 21 (2000) 537–551. | DOI | MR | Zbl
[52] , A Riemannian view on shape optimization. Found. Comput. Math. 14 (2014) 483–501. | DOI | MR | Zbl
[53] , and , Efficient pde constrained shape optimization based on steklov–poincaré-type metrics. SIAM J. Optim. 26 (2016) 2800–2819. | DOI | MR | Zbl
[54] and , Constrained optimization: projected gradient flows. J. Optim. Theory Appl. 140 (2009) 117–130. | DOI | MR | Zbl
[55] , Manufacturing tolerant topology optimization. Acta Mech. Sinica 25 (2009) 227–239. | DOI | Zbl
[56] and , Introduction to shape optimization, in Introduction to Shape Optimization. Springer, Berlin (1992) 5–12. | DOI | MR | Zbl
[57] and , Introduction to shape optimization. Vol. 16 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin (1992). | MR | Zbl
[58] , The method of moving asymptotes—a new method for structural optimization. Int. J. Numer. Methods Eng. 24 (1987) 359–373. | DOI | MR | Zbl
[59] , A geometric method in nonlinear programming. J. Optim. Theory Appl. 30 (1980) 181–210. | DOI | MR | Zbl
[60] and , Structural optimization by methods of feasible directions. Comput. Struct. 3 (1973) 739–755. | DOI
[61] and , On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106 (2006) 25–57. | DOI | MR | Zbl
[62] , and , A level set method for structural topology optimization. Comput. Methods Appl. Mech. Eng. 192 (2003) 227–246. | DOI | MR | Zbl
[63] and , Topology optimization of thermoelastic structures using level set method. Comput. Mech. 42 (2008) 837–857. | DOI | Zbl
[64] , , and , A level set based method for the optimization of cast part. Struct. Multidiscipl. Optim. 41 (2010) 735–747. | DOI
[65] , A differential equation approach to nonlinear programming. Math. Program. 18 (1980) 155–168. | DOI | MR | Zbl
[66] , A review of trust region algorithms for optimization. ICIAM 99 (2000) 271–282. | DOI | MR | Zbl
[67] and , A level set method for structural topology optimization with multi-constraints and multi-materials. Acta Mech. Sin. 20 (2004) 507–518. | DOI | MR
[68] , Methods of feasible directions: A study in linear and non-linear programming. Elsevier Publishing Co., Amsterdam (1960). | MR | Zbl
Cité par Sources :
This work was supported by the Association Nationale de la Recherche et de la Technologie (ANRT) [grant number CIFRE 2017/0024] and by the project ANR-18-CE40-0013 SHAPO financed by the French Agence Nationale de la Recherche (ANR).
F. F. is a CIFRE PhD student, funded by SAFRAN, the support of which is kindly acknowledged. G. A. is a member of the DEFI project at INRIA Saclay Ile-de-France. The work of C.D. is partially supported by the IRS-CAOS grant from Université Grenoble-Alpes.
We thank Alexis Faure for sharing his optimization experience with us.
