×

Inexact Hessian-vector products in reduced-space differential-equation constrained optimization. (English) Zbl 1364.49037

Summary: Reduced-space inexact-Newton-Krylov (RSNK) algorithms provide a modular and scalable framework for solving differential-equation-constrained optimization problems; thus, this class of algorithms provides an attractive compromise between poorly scaling “black-box” methods and more intrusive, full-space optimization algorithms. One of the challenges of implementing RSNK methods is the efficient solution of the linear subproblems, which involve the reduced Hessian. This paper explores inexact Hessian-vector products to improve the efficiency of these subproblems. The reduced-Hessian-vector products, which are required by the Krylov solver in RSNK, can be determined by solving two second-order adjoint equations. To reduce computational cost, we consider the approximate (i.e. inexact) solution of the second-order adjoints. We present bounds for the second-order adjoint tolerances that ensure the Hessian-vector product remains sufficiently accurate for inexact-Krylov methods. The bounds involve the 2-norm of the state and first-order adjoint sensitivities, and we provide an inexpensive Lanczos algorithm to estimate these matrix norms. Using numerical experiments, we investigate the proposed RSNK algorithm and compare it to other optimization algorithms.

MSC:

49M25 Discrete approximations in optimal control
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
90C06 Large-scale problems in mathematical programming

Software:

L-BFGS; KNITRO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akçelik V, Biros G, Ghattas O (2002) Parallel multiscale Gauss-Newton-Krylov methods for inverse wave propagation. SC Conference, p. 41 doi:10.1109/SC.2002.10002
[2] Akçelik V, Biros G, Ghattas O, Hill J, Keyes D, van Bloemen Waanders B (2006) Parallel algorithms for PDE-constrained optimization. In: Heroux MA, Raghavan P, Simon HD (eds) Parallel processing for scientific computing, chap. 16. Society for Industrial and Applied Mathematics, pp 291-322. doi:10.1137/1.9780898718133.ch16 · Zbl 1085.76050
[3] Anderson JD (1991) Fundamentals of aerodynamics, 2nd edn. McGraw-Hill Inc., New York
[4] Arnold DN, Brezzi F, Cockburn B, Marini LD (2002) Unified analysis of discontinuous Galerkin methods for elliptic problems. SIAM J Numer Anal 39(5):1749-1779. doi:10.1137/s0036142901384162 · Zbl 1008.65080 · doi:10.1137/s0036142901384162
[5] Biros G, Ghattas O (2005) Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver. SIAM J Sci Comput 27:687-713 · Zbl 1091.65061 · doi:10.1137/S106482750241565X
[6] Biros G, Ghattas O (2005) Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part II: The Lagrange-Newton solver and its application to optimal control of steady viscous flows. SIAM J Sci Comput 27:714-739 · Zbl 1091.65062 · doi:10.1137/S1064827502415661
[7] Borzì A, Schulz V (2011) Computational optimization of systems governed by partial differential equations. Society for Industrial and Applied Mathematics, pp. 47-48 doi:10.1137/1.9781611972054 · Zbl 1186.35134
[8] Borzì A, Schulz V (2011) Computational optimization of systems governed by partial differential equations. Society for Industrial and Applied Mathematics, pp 62-66. doi:10.1137/1.9781611972054
[9] Bouras A, Frayssé V (2005) Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy. SIAM J Matrix Anal Appl 26(3):660-678. doi:10.1137/s0895479801384743 · Zbl 1075.65041 · doi:10.1137/s0895479801384743
[10] Braack M (2009) Optimal control in fluid mechanics by finite elements with symmetric stabilization. SIAM J Control Optim 48(2):672-687. doi:10.1137/060653494 · Zbl 1186.35134 · doi:10.1137/060653494
[11] Byrd RH, Curtis FE, Nocedal J (2008) An inexact SQP method for equality constrained optimization. SIAM J Optim 19(1):351-369. doi:10.1137/060674004 · Zbl 1158.49035 · doi:10.1137/060674004
[12] Byrd RH, Curtis FE, Nocedal J (2010) An inexact Newton method for nonconvex equality constrained optimization. Math Program 122(2):273-299. doi:10.1007/s10107-008-0248-3 · Zbl 1184.90127 · doi:10.1007/s10107-008-0248-3
[13] Carpenter MH, Gottlieb D, Abarbanel S (1994) Time-stable boundary conditions for finite-difference schemes solving hyperbolic systems: methodology and application to high-order compact schemes. J Comput Phys 111(2):220-236. doi:10.1006/jcph.1994.1057 · Zbl 0832.65098 · doi:10.1006/jcph.1994.1057
[14] Conn AR, Gould NIM, Toint PL (2000) Trust region methods. Society for Industrial and Applied Mathematics doi:10.1137/1.9780898719857 · Zbl 0958.65071
[15] Dembo RS, Eisenstat SC, Steihaug T (1982) Inexact Newton methods. SIAM J Numer Anal 19(2):400-408. doi:10.1137/0719025 · Zbl 0478.65030 · doi:10.1137/0719025
[16] Du X, Sarkis M, Schaerer CE, Szyld DB (2013) Inexact and truncated parareal-in-time Krylov subspace methods for parabolic optimal control problems. Electron Trans Numer Anal 40:36-57 · Zbl 1288.65093
[17] Farin GE (1997) Curves and surfaces for computed aided geometric design: a practical guide, 4th edn. Academic Press, Inc, London
[18] Feng D, Pulliam TH (1995) An all-at-once reduced hessian SQP scheme for aerodynamic design optimization. Tech. Rep. RIACS-TR-95.19, NASA Ames Research Center, Moffett Field, California · Zbl 1227.65102
[19] Fletcher R (2000) Practical methods of optimization, 2nd edn. A Wiley-Interscience Publication, Wiley, New York · Zbl 0905.65002 · doi:10.1002/9781118723203
[20] Frank PD, Shubin GR (1992) A comparison of optimization-based approaches for a model computational aerodynamics design problem. J Comput Phys 98(1):74-89 · Zbl 0741.76067 · doi:10.1016/0021-9991(92)90174-W
[21] Funaro D, Gottlieb D (1988) A new method of imposing boundary conditions in pseudospectral approximations of hyperbolic equations. Math Comput 51(184):599-613 · Zbl 0699.65079 · doi:10.1090/S0025-5718-1988-0958637-X
[22] Gatsis J, Zingg DW (2003) A fully-coupled Newton-Krylov algorithm for aerodynamic optimization. In: 16th AIAA Computational Fluid Dynamics Conference, AIAA-2003-3956. Orlando. · Zbl 0599.65018
[23] Ghate D, Giles M (2007) Efficient Hessian calculation using automatic differentiation. In: 25th AIAA Applied Aerodynamics Conference, AIAA-2007-4059. Miami. doi:10.2514/6.2007-4059
[24] Golub GH, Ye Q (1999) Inexact preconditioned conjugate gradient method with inner-outer iteration. SIAM J Sci Comput 21(4):1305-1320. doi:10.1137/s1064827597323415 · Zbl 0955.65022 · doi:10.1137/s1064827597323415
[25] Griewank A, Walther A (2008) Evaluating derivatives: principles and techniques of algorithmic differentiation. Society for Industrial and Applied Mathematics http://www.worldcat.org/isbn/9780898716597 · Zbl 1159.65026
[26] Griewank A, Walther A (2008) Evaluating derivatives: principles and techniques of algorithmic differentiation, chap. 5. Society for Industrial and Applied Mathematics, pp. 91-105. http://www.worldcat.org/isbn/9780898716597 · Zbl 1159.65026
[27] Gunzburger MD (2003) Perspectives in flow control and optimization. Society for Industrial and Applied Mathematics http://www.worldcat.org/isbn/9780898715279 · Zbl 1088.93001
[28] Haber E, Ascher UM (2001) Preconditioned all-at-once methods for large, sparse parameter estimation problems. Inverse Probl 17(6):1847-1864. doi:10.1088/0266-5611/17/6/319 · Zbl 0995.65110 · doi:10.1088/0266-5611/17/6/319
[29] Hartmann R (2007) Adjoint consistency analysis of discontinuous Galerkin discretizations. SIAM J Numer Anal 45(6):2671-2696. doi:10.1137/060665117 · Zbl 1189.76341 · doi:10.1137/060665117
[30] Heinkenschloss M, Vicente LN (1999) An interface optimization and application for the numerical solution of optimal control problems. ACM Trans Math Softw 25(2):157-190. doi:10.1145/317275.317278 · Zbl 0961.65061 · doi:10.1145/317275.317278
[31] Hicken JE, Alonso JJ (2013) Comparison of reduced- and full-space algorithms for PDE-constrained optimization. In: 51st AIAA aerospace sciences meeting, AIAA-2013-1043. Grapevine. doi:10.2514/6.2013-1043
[32] Hicken JE, Zingg DW (2011) Superconvergent functional estimates from summation-by-parts finite-difference discretizations. SIAM J Sci Comput 33(2):893-922. doi:10.1137/100790987 · Zbl 1227.65102 · doi:10.1137/100790987
[33] Hicken JE, Zingg DW (2011) The role of dual consistency in functional accuracy: error estimation and superconvergence. In: 20th AIAA computational fluid dynamics conference, AIAA-2011-3855. Honolulu. · Zbl 1048.65032
[34] Hicken JE, Zingg DW (2012) Dual consistency and functional accuracy: a finite-difference perspective. J Comput Phys 256:161-182 · Zbl 1349.65559 · doi:10.1016/j.jcp.2013.08.014
[35] Hinze M, Pinnau R, Ulbrich M, Ulbrich S (2009) Optimization with PDE constraints. Springer, New York, pp 64-65. http://www.worldcat.org/isbn/9781402088384 · Zbl 1167.49001
[36] Iollo A, Salas MD, Ta’asan S (1993) Shape optimization governed by the Euler equations using an adjoint method. Tech. Rep. ICASE 93-78, NASA Langley Research Center, Hampton. · Zbl 0856.76067
[37] Keyes DE (1995) Aerodynamic applications of Newton-Krylov-Schwarz solvers. In: Proceedings of the 14th international conference on numerical methods in fluid dynamics. Springer, New York, pp 1-20 · Zbl 0854.76073
[38] Knoll DA, Keyes DE (2004) Jacobian-free Newton-Krylov methods: a survey of approaches and applications. J Comput Phys 193(2):357-397. doi:10.1016/j.jcp.2003.08.010 · Zbl 1036.65045 · doi:10.1016/j.jcp.2003.08.010
[39] Kreiss HO, Scherer G (1974) Finite element and finite difference methods for hyperbolic partial differential equations. In: de Boor C (ed) Mathematical aspects of finite elements in partial differential equations. Mathematics Research Center, the University of Wisconsin Academic Press, Madison · Zbl 0355.65085
[40] Lanczos C (1950) An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J Res Natl Bur Stand 45(4):255-282 · doi:10.6028/jres.045.026
[41] Liu DC, Nocedal J (1989) On the limited memory BFGS method for large scale optimization. Math Program 45:503-528. doi:10.1007/BF01589116 · Zbl 0696.90048 · doi:10.1007/BF01589116
[42] Lu JC (2005) An a posteriori error control framework for adaptive precision optimization using discontinuous Galerkin finite element method. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge
[43] Martins JRRA, Sturdza P, Alonso JJ (2003) The complex-step derivative approximation. ACM Trans Math Softw 29(3):245-262. doi:10.1145/838250.838251 · Zbl 1072.65027 · doi:10.1145/838250.838251
[44] Mattsson K, Svärd M, Nordström J (2004) Stable and accurate artificial dissipation. J Sci Comput 21(1):57-79 · Zbl 1085.76050 · doi:10.1023/B:JOMP.0000027955.75872.3f
[45] Melvin RG, Huffman WP, Young DP, Johnson FT, Hilmes CL (1999) Recent progress in aerodynamic design optimization. Int J Numer Methods Fluids 30(2):205-206. doi:10.1002/(sici)1097-0363(19990530)30:2 · Zbl 0923.76234
[46] Morales JL, Nocedal J (2000) Automatic preconditioning by limited memory quasi-Newton updating. SIAM J Optim 10(4):1079-1096. doi:10.1137/S1052623497327854 · Zbl 1020.65019 · doi:10.1137/S1052623497327854
[47] Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn. Springer, Berlin · Zbl 1104.65059
[48] Nocedal J, Wright SJ (2006) Numerical optimization, chap. 6, 2nd edn. Springer, Berlin · Zbl 1104.65059
[49] Nocedal J, Wright SJ (2006) Numerical optimization, chap. 7, 2nd edn. Springer, Berlin · Zbl 1104.65059
[50] Nocedal J, Wright SJ (2006) Numerical optimization, chap. 12, 2nd edn. Springer, Berlin · Zbl 1104.65059
[51] Rumpfkeil MP, Mavriplis DJ (2010) Efficient Hessian calculations using automatic differentiation and the adjoint method with applications. AIAA J 48(10):2406-2417. doi:10.2514/1.j050451 · doi:10.2514/1.j050451
[52] Saad Y (1993) A flexible inner-outer preconditioned GMRES algorithm. SIAM J Sci Stat Comput 14(2):461-469 · Zbl 0780.65022 · doi:10.1137/0914028
[53] Saad Y (2003) Iterative methods for sparse linear systems, chap. 6, 2nd edn. SIAM, Philadelphia · Zbl 1002.65042 · doi:10.1137/1.9780898718003
[54] Saad Y (2011) Numerical methods for Large eigenvalue problems. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611970739 · Zbl 1242.65068
[55] Saad Y, Schultz MH (1986) GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J Sci Stat Comput 7(3):856-869 · Zbl 0599.65018 · doi:10.1137/0907058
[56] Simoncini V, Szyld DB (2003) Theory of inexact Krylov subspace methods and applications to scientific computing. SIAM J Sci Comput 25(2):454-477. doi:10.1137/s1064827502406415 · Zbl 1048.65032 · doi:10.1137/s1064827502406415
[57] Squire W, Trapp G (1998) Using complex variables to estimate derivatives of real functions. SIAM Rev 40(1):110-112 · Zbl 0913.65014 · doi:10.1137/S003614459631241X
[58] Strand B (1994) Summation by parts for finite difference approximations for d/dx. J Comput Phys 110(1):47-67. doi:10.1006/jcph.1994.1005 · Zbl 0792.65011 · doi:10.1006/jcph.1994.1005
[59] Ta’asan S, Kuruvila G, Salas MD (1992) Aerodynamic design and optimization in one shot. In: The 30th AIAA aerospace sciences meeting and exhibit, AIAA-1992-25
[60] Waltz RA, Nocedal J (2003), KNITRO user’s manual. Northwestern University, Evanston, Technical, Report OTC-2003/5 · Zbl 0995.65110
[61] Wang Z, Navon IM, Dimet FX, Zou X (1992) The second order adjoint analysis: theory and applications. Meteorol Atmos Phys 50:3-20. doi:10.1007/BF01025501 · doi:10.1007/BF01025501
[62] van den Eshof J, Sleijpen GLG (2004) Inexact Krylov subspace methods for linear systems. SIAM J Matrix Anal Appl 26(1):125-153. doi:10.1137/s0895479802403459 · Zbl 1079.65036 · doi:10.1137/s0895479802403459
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.