A matrix-free trust-region Newton algorithm for convex-constrained optimization. (English) Zbl 1489.90136
Summary: We describe a matrix-free trust-region algorithm for solving convex-constrained optimization problems that uses the spectral projected gradient method to compute trial steps. To project onto the intersection of the feasible set and the trust region, we reformulate and solve the dual projection problem as a one-dimensional root finding problem. We demonstrate our algorithm’s performance on various problems from data science and PDE-constrained optimization. Our algorithm shows superior performance when compared with five existing trust-region and spectral projected gradient methods, and has the added benefit that it is simple to implement.
Keywords:
nonconvex optimization; convex constraints; trust regions; spectral projected gradient; large-scale optimization; Newton’s methodReferences:
| [1] | Andretta, M.; Birgin, EG; Martínez, JM, Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization, Optimization, 54, 3, 305-325 (2005) · Zbl 1079.65070 · doi:10.1080/02331930500100270 |
| [2] | Antil, H.; Kouri, DP; Lacasse, MD; Ridzal, D., Frontiers in PDE-constrained optimization (2018), Cham: Springer, Cham · Zbl 1402.49004 · doi:10.1007/978-1-4939-8636-1 |
| [3] | Baker, CG; Heroux, MA, Tpetra, and the use of generic programming in scientific computing, Sci. Program., 20, 2, 115-128 (2012) |
| [4] | Bendsoe, MP; Sigmund, O., Topology optimization: theory, methods, and applications (2013), Cham: Springer, Cham · Zbl 1059.74001 |
| [5] | Birgin, EG; Martínez, JM; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Opt., 10, 4, 1196-1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963 |
| [6] | Birgin, EG; Martínez, JM; Raydan, M., Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23, 4, 539-559 (2003) · Zbl 1047.65042 · doi:10.1093/imanum/23.4.539 |
| [7] | Birgin, EG; Martínez, JM; Raydan, M., Spectral projected gradient methods: review and perspectives, J. Stat. Softw, 60, 3, 1-21 (2014) · doi:10.18637/jss.v060.i03 |
| [8] | Bochev, P.; Edwards, HC; Kirby, RC; Peterson, K.; Ridzal, D., Solving PDEs with intrepid, Sci. Program., 20, 2, 151-180 (2012) |
| [9] | Borrvall, T.; Petersson, J., Topology optimization of fluids in stokes flow, Int. J. Numer. Methods Fluids, 41, 1, 77-107 (2003) · Zbl 1025.76007 · doi:10.1002/fld.426 |
| [10] | Brent, R.P.: Algorithms for minimization without derivatives. Courier Corporation (2013) · Zbl 1009.90133 |
| [11] | Burke, JV; Moré, JJ; Toraldo, G., Convergence properties of trust region methods for linear and convex constraints, Math. Program., 47, 1-3, 305-336 (1990) · Zbl 0711.90060 · doi:10.1007/BF01580867 |
| [12] | Chang, CC; Lin, CJ, LIBSVM: a library for support vector machines, ACM Trans. Intell. Syst. Technol., 2, 3, 1-27 (2011) · doi:10.1145/1961189.1961199 |
| [13] | Conn, AR; Gould, NIM; Sartenaer, A.; Toint, PL, Global convergence of a class of trust region algorithms for optimization using inexact projections on convex constraints, SIAM J. Opt., 3, 1, 164-221 (1993) · Zbl 0806.90111 · doi:10.1137/0803009 |
| [14] | Conn, AR; Gould, NIM; Sartenaer, A.; Toint, PL, Convergence properties of minimization algorithms for convex constraints using a structured trust region, SIAM J. Opt., 6, 4, 1059-1086 (1996) · Zbl 0868.90106 · doi:10.1137/S1052623492236481 |
| [15] | Conn, AR; Gould, NIM; Toint, PL, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal., 28, 2, 545-572 (1991) · Zbl 0724.65067 · doi:10.1137/0728030 |
| [16] | Dai, YH; Fletcher, R., New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Math. Program., 106, 3, 403-421 (2006) · Zbl 1134.90030 · doi:10.1007/s10107-005-0595-2 |
| [17] | Deng, Y.; Liu, Z.; Wu, J.; Wu, Y., Topology optimization of steady Navier-Stokes flow with body force, Comput. Methods Appl. Mech. Eng., 255, 306-321 (2013) · Zbl 1297.76048 · doi:10.1016/j.cma.2012.11.015 |
| [18] | Dua, D., Graff, C.: UCI machine learning repository (2017). http://archive.ics.uci.edu/ml |
| [19] | Hartung, J., An extension of Sion’s minimax theorem with an application to a method for constrained games, Pacific J. Math., 103, 2, 401-408 (1982) · Zbl 0534.49009 · doi:10.2140/pjm.1982.103.401 |
| [20] | Heinkenschloss, M.: Numerical solution of implicitly constrained optimization problems. Rice University, Tech. rep. (2008) |
| [21] | Kouri, D.P., von Winckel, G., Ridzal, D.: ROL: Rapid Optimization Library. https://trilinos.org/packages/rol (2017) |
| [22] | Lazarov, BS; Sigmund, O., Filters in topology optimization based on Helmholtz-type differential equations, Int. J. Numer. Methods Eng., 86, 6, 765-781 (2011) · Zbl 1235.74258 · doi:10.1002/nme.3072 |
| [23] | Lin, CJ; Moré, JJ, Newton’s method for large bound-constrained optimization problems, SIAM J. Opt., 9, 4, 1100-1127 (1999) · Zbl 0957.65064 · doi:10.1137/S1052623498345075 |
| [24] | Maciel, MC; Mendonça, MG; Verdiell, AB, Monotone and nonmonotone trust-region-based algorithms for large scale unconstrained optimization problems, Comput. Opt. Appl., 54, 1, 27-43 (2013) · Zbl 1267.90142 · doi:10.1007/s10589-012-9477-8 |
| [25] | Meyer, M., Vlachos, P.: StatLib—datasets archive. http://lib.stat.cmu.edu/datasets/. Accessed: 2021-05-10 |
| [26] | Pace, RK; Barry, R., Sparse spatial autoregressions, Stat. Probab. Lett., 33, 3, 291-297 (1997) · Zbl 0901.62112 · doi:10.1016/S0167-7152(96)00140-X |
| [27] | Sala, M., Stanley, K., Heroux, M.: Amesos: A set of general interfaces to sparse direct solver libraries. In: Proceedings of PARA’06 Conference, Umea, Sweden (2006) |
| [28] | Schenk, O.; Gärtner, K., Solving unsymmetric sparse systems of linear equations with PARDISO, Future Gener. Comput. Syst., 20, 3, 475-487 (2004) · doi:10.1016/j.future.2003.07.011 |
| [29] | Schmidt, M., Berg, E., Friedlander, M., Murphy, K.: Optimizing costly functions with simple constraints: A limited-memory projected quasi-Newton algorithm. In: D. van Dyk, M. Welling (eds.) Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 5, pp. 456-463. PMLR, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA (2009) |
| [30] | Toint, PL, Global convergence of a clas of trust-region methods for nonconvex minimization in Hilbert space, IMA J. Numer. Anal., 8, 2, 231-252 (1988) · Zbl 0698.65043 · doi:10.1093/imanum/8.2.231 |
| [31] | Tröltzsch, F.: Optimal control of partial differential equations: theory, methods, and applications. Graduate studies in mathematics. American Mathematical Society (2010) · Zbl 1195.49001 |
| [32] | Vapnik, VN, The nature of statistical learning theory (2013), New York: Springer, New York · Zbl 0833.62008 |
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.
