×

Null space gradient flows for constrained optimization with applications to shape optimization. (English) Zbl 1464.65064

Summary: 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 H. Yamashita [Math. Program. 18, 155–168 (1980; Zbl 0436.90094)] 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.

MSC:

65K10 Numerical optimization and variational techniques
49Q10 Optimization of shapes other than minimal surfaces
65L05 Numerical methods for initial value problems involving ordinary differential equations

Citations:

Zbl 0436.90094

Software:

Ipopt; CVXOPT; PLCP; SQPlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.-A. Absil and J. Malick, Projection-like retractions on matrix manifolds. SIAM J. Optim. 22 (2012) 135-158. · Zbl 1248.49055
[2] P.-A. Absil, R. Mahony and R. Sepulchre, Optimization algorithms on matrix manifolds. Princeton University Press, Princeton (2009). · Zbl 1147.65043
[3] G. Allaire, Conception optimale de structures, Vol. 58 of Mathématiques & Applications. Springer-Verlag, Berlin (2007). · Zbl 1132.49033
[4] G. Allaire and F. Jouve, Minimum stress optimal design with the level set method. Eng. Anal. Bound. Elements 32 (2008) 909-918. · Zbl 1244.74104 · doi:10.1016/j.enganabound.2007.05.007
[5] G. Allaire and O. Pantz, Structural optimization with freefem++. Struct. Multidiscipl. Optim. 32 (2006) 173-181. · Zbl 1245.74049
[6] G. Allaire, F. Jouve and A.-M. Toader, Structural optimization using sensitivity analysis and a level-set method. J. Comput. Phys. 194 (2004) 363-393. · Zbl 1136.74368
[7] G. Allaire, C. Dapogny and P. Frey, Shape optimization with a level set based mesh evolution method. Comput. Methods Appl. Mech. Eng. 282 (2014) 22-53. · Zbl 1423.74739
[8] G. Allaire, F. Jouve and G. Michailidis, Casting constraints in structural optimization via a level-set method, in 10th world Congress on Structural and Multidisciplinary Optimization (2013).
[9] G. Allaire, F. Jouve and G. Michailidis, Thickness control in structural optimization via a level set method. Struct. Multidiscipl. Optim. 53 (2016) 1349-1382.
[10] G. Allaire, C. Dapogny, R. Estevez, A. Faure and G. Michailidis, Structural optimization under overhang constraints imposed by additive manufacturing technologies. J. Comput. Phys. 351 (2017) 295-328. · Zbl 1375.74076
[11] L. Ambrosio, M. Colombo and A. Figalli, Existence and uniqueness of maximal regular flows for non-smooth vector fields. Arch. Ration. Mech. Anal. 218 (2015) 1043-1081. · Zbl 1348.34039
[12] M. Andersen, J. Dahl and L. Vandenberghe, CVXOPT: A Python package for convex optimization Available at (2012).
[13] S. Arguillère, E. Trélat, A. Trouvé and L. Younes, Shape deformation analysis from the optimal control viewpoint. J. Math. Pures Appl. 104 (2015) 139-178. · Zbl 1319.49064
[14] H. Azegami and Z.C. Wu, Domain optimization analysis in linear elastic problems: approach using traction method. JSME Int. J. Ser. A, Mech. Mater. Eng. 39 (1996) 272-278.
[15] C. Barbarosie and S. Lopes, A gradient-type algorithm for optimization with constraints, submitted for publication, see also Pre-PrintCMAF Pre-2011-001 at (2011).
[16] C. Barbarosie, A.-M. Toader and S. Lopes, A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discr. Cont. Dyn. Syst. B 22 (2020) 1729-1755. · Zbl 07195103
[17] J.-F. Bonnans, J.C. Gilbert, C. Lemaréchal and C.A. Sagastizábal, Numerical optimization: theoretical and practical aspects. Springer Science & Business Media, Berlin (2006). · Zbl 1108.65060
[18] H. Brezis, Functional analysis, Sobolev spaces and partial differential equations. Springer Science & Business Media, Berlin (2010). · Zbl 1220.46002 · doi:10.1007/978-0-387-70914-7
[19] R. Bro and S. De Jong A fast non-negativity-constrained least squares algorithm. J. Chemometr. 11 (1997) 393-401. · doi:10.1002/(SICI)1099-128X(199709/10)11:5<393::AID-CEM483>3.0.CO;2-L
[20] C. Bui, C. Dapogny and P. Frey, An accurate anisotropic adaptation method for solving the level set advection equation. Int. J. Num. Methods Fluids 70 (2012) 899-922. · Zbl 1412.65133 · doi:10.1002/fld.2730
[21] M. Burger, A framework for the construction of level set methods for shape optimization and reconstruction. Interfaces Free Bound. 5 (2003) 301-329. · Zbl 1081.35134 · doi:10.4171/IFB/81
[22] C. Dapogny, C. Dobrzynski and P. Frey, Three-dimensional adaptive domain remeshing, implicit domain meshing, and applications to free and moving boundary problems. J. Comput. Phys. 262 (2014) 358-378. · Zbl 1349.76598
[23] C. Dapogny, P. Frey, F. Omnès and Y. Privat, Geometrical shape optimization in fluid mechanics using FreeFem++, in Structural and Multidisciplinary Optimization. Springer, Germany (2017) 1-28.
[24] F. De Gournay Velocity extension for the level-set method and multiple eigenvalues in shape optimization. SIAM J. Control Optim. 45 (2006) 343-367. · Zbl 1108.74046
[25] L. Dieci and L. Lopez, A survey of numerical methods for ivps of odes with discontinuous right-hand side. J. Comput. Appl. Math. 236 (2012) 3967-3991. · Zbl 1246.65111
[26] J. Dieudonné, Foundations of modern analysis. Academic press, New York (1960). · Zbl 0100.04201
[27] P.D. Dunning and H.A. Kim, Introducing the sequential linear programming level-set method for topology optimization. Struct. Multidiscipl. Optim. 51 (2015) 631-643.
[28] P. Duysinx and M.P. Bendsøe, Topology optimization of continuum structures with local stress constraints. Int. J. Numer. Methods Eng. 43 (1998) 1453-1478. · Zbl 0924.73158
[29] A. Edelman, T.A. Arias and S.T. Smith, The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20 (1998) 303-353. · Zbl 0928.65050
[30] A. Faure, 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] F. Feppon, 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] F. Feppon, G. Allaire, F. Bordeu, J. Cortial and C. Dapogny, Shape optimization of a coupled thermal fluid-structure problem in a level set mesh evolution framework. SerMA J. 76 (2019) 413-458. · Zbl 1422.49038
[33] A.F. Filippov, Differential equations with discontinuous righthand sides: control systems. Vol. 18. Springer Science & Business Media, Berlin (2013).
[34] R. Fletcher, Practical methods of optimization. John Wiley & Sons, New Jersey (2013). · Zbl 0905.65002
[35] A. Henrot and M. Pierre, 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).
[36] M. Hintermüller, K. Ito and K. Kunisch, The primal-dual active set strategy as a semismooth newton method. SIAM J. Optim. 13 (2002) 865-888. · Zbl 1080.90074
[37] H.T. Jongen and O. Stein, On the complexity of equalizing inequalities. J. Global Optim. 27 (2003) 367-374. · Zbl 1061.90118 · doi:10.1023/A:1026051901133
[38] H.T. Jongen and O. Stein, 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. · Zbl 1176.90571 · doi:10.1007/978-1-4613-0251-3_12
[39] J. Jost, Chapter 7 Morse Theory and Floer Homology. Springer Berlin Heidelberg (2011) 327-417.
[40] C. Le, J. Norato, T. Bruns, C. Ha and D. Tortorelli, Stress-based topology optimization for continua. Struct. Multidiscipl. Optim. 41 (2010) 605-620.
[41] J.D. Lee, M. Simchowitz, M.I. Jordan and B. Recht, Gradient descent only converges to minimizers, in 29th Annual Conference on Learning Theory. Edited by V. Feldman, A. Rakhlin and O. Shamir. Vol. 49 of Proceedings of Machine Learning Research Columbia University, New York, USA (2016) 1246-1257.
[42] J. Liu and Y. Ma, A survey of manufacturing oriented topology optimization methods. Adv. Eng. Softw. 100 (2016) 161-175.
[43] L. Ljung, Analysis of recursive stochastic algorithms. IEEE Trans. Autom. Control 22 (1977) 551-575. · Zbl 0362.93031 · doi:10.1109/TAC.1977.1101561
[44] D.G. Luenberger, The gradient projection method along geodesics. Manag. Sci. 18 (1972) 620-631. · Zbl 0253.90050 · doi:10.1287/mnsc.18.11.620
[45] B. Mohammadi and O. Pironneau, Applied shape optimization for fluids. Oxford University Press, Oxford (2010). · Zbl 0970.76003
[46] P. Morin, R. Nochetto, M. Pauletti and M. Verani, Adaptive sqp method for shape optimization, in Numerical Mathematics and Advanced Applications 2009. Springer, Berlin (2010) 663-673. · Zbl 1216.65077 · doi:10.1007/978-3-642-11795-4_71
[47] F. Murat and J. Simon, Sur le contrôle par un domaine géométrique, publications du Laboratoire d’Analyse Numérique, Université Pierre et Marie Curie (1976).
[48] J. Nocedal and S.J. Wright, Numerical optimization. Springer Science, Berlin (1999) 35. · Zbl 0930.65067
[49] S. Osher and J.A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on hamilton-jacobi formulations. J. Comput. Phys. 79 (1988) 12-49. · Zbl 0659.65132
[50] I. Panageas and G. Piliouras, Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. Preprint (2016). · Zbl 1402.90210
[51] J. Schropp and I. Singer, A dynamical systems approach to constrained minimization. Numer. Funct. Anal. Optim. 21 (2000) 537-551. · Zbl 1017.90106
[52] V.H. Schulz, A Riemannian view on shape optimization. Found. Comput. Math. 14 (2014) 483-501. · Zbl 1296.49037 · doi:10.1007/s10208-014-9200-5
[53] V.H. Schulz, M. Siebenborn and K. Welker, Efficient pde constrained shape optimization based on steklov-poincaré-type metrics. SIAM J. Optim. 26 (2016) 2800-2819. · Zbl 1354.49095
[54] V. Shikhman and O. Stein, Constrained optimization: projected gradient flows. J. Optim. Theory Appl. 140 (2009) 117-130. · Zbl 1226.90107
[55] O. Sigmund, Manufacturing tolerant topology optimization. Acta Mech. Sinica 25 (2009) 227-239. · Zbl 1270.74165 · doi:10.1007/s10409-009-0240-z
[56] J. Sokolowski and J.-P. Zolesio, Introduction to shape optimization, in Introduction to Shape Optimization. Springer, Berlin (1992) 5-12. · Zbl 0761.73003 · doi:10.1007/978-3-642-58106-9_1
[57] J. Sokolowski and J.-P. Zolésio, Introduction to shape optimization. Vol. 16 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin (1992). · Zbl 0761.73003 · doi:10.1007/978-3-642-58106-9
[58] K. Svanberg, The method of moving asymptotes—a new method for structural optimization. Int. J. Numer. Methods Eng. 24 (1987) 359-373. · Zbl 0602.73091
[59] K. Tanabe, A geometric method in nonlinear programming. J. Optim. Theory Appl. 30 (1980) 181-210. · Zbl 0396.90078
[60] G.N. Vanderplaats and F. Moses, Structural optimization by methods of feasible directions. Comput. Struct. 3 (1973) 739-755.
[61] A. Wächter and L.T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106 (2006) 25-57. · Zbl 1134.90542
[62] M.Y. Wang, X. Wang and D. Guo, A level set method for structural topology optimization. Comput. Methods Appl. Mech. Eng. 192 (2003) 227-246. · Zbl 1083.74573
[63] Q. Xia and M.Y. Wang, Topology optimization of thermoelastic structures using level set method. Comput. Mech. 42 (2008) 837-857. · Zbl 1163.74540
[64] Q. Xia, T. Shi, M. Y. Wang and S. Liu, A level set based method for the optimization of cast part. Struct. Multidiscipl. Optim. 41 (2010) 735-747.
[65] H. Yamashita, A differential equation approach to nonlinear programming. Math. Program. 18 (1980) 155-168. · Zbl 0436.90094
[66] Y.-X. Yuan, A review of trust region algorithms for optimization. ICIAM 99 (2000) 271-282. · Zbl 0992.65061
[67] M. Yulin and W. Xiaoming, A level set method for structural topology optimization with multi-constraints and multi-materials. Acta Mech. Sin. 20 (2004) 507-518.
[68] G. Zoutendijk, Methods of feasible directions: A study in linear and non-linear programming. Elsevier Publishing Co., Amsterdam (1960). · Zbl 0097.35408
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.