Second order semi-smooth Proximal Newton methods in Hilbert spaces
Tóm tắt
We develop a globalized Proximal Newton method for composite and possibly non-convex minimization problems in Hilbert spaces. Additionally, we impose less restrictive assumptions on the composite objective functional considering differentiability and convexity than in existing theory. As far as differentiability of the smooth part of the objective function is concerned, we introduce the notion of second order semi-smoothness and discuss why it constitutes an adequate framework for our Proximal Newton method. However, both global convergence as well as local acceleration still pertain to hold in our scenario. Eventually, the convergence properties of our algorithm are displayed by solving a toy model problem in function space.
Tài liệu tham khảo
Argyriou, A., Micchelli, C.A., Pontil, M., Shen, L., Xu, Y.: Efficient first order methods for linear composite regularizers. Preprint (2011)
Beck, A.: First-order methods in optimization. Soc. Indus. Appl. Math. (2017). https://doi.org/10.1137/1.9781611974997
Byrd, R.H., Nocedal, J., Oztoprak, F.: An inexact successive quadratic approximation method for l-1 regularized optimization. Math. Program. 157(2), 375–396 (2015). https://doi.org/10.1007/s10107-015-0941-y
Chen, D.Q., Zhou, Y., Song, L.J.: Fixed point algorithm based on adapted metric method for convex minimization problem with application to image deblurring. Adv. Comput. Math. 42(6), 1287–1310 (2016). https://doi.org/10.1007/s10444-016-9462-3
Chen, P., Huang, J., Zhang, X.: A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions. Fixed Point Theory Appl. 2016(1) (2016). https://doi.org/10.1186/s13663-016-0543-2
Dinh, Q.T., Kyrillidis, A., Cevher, V.: A proximal newton framework for composite minimization: Graph learning without cholesky decompositions and matrix inversions. Presented at the (2013)
Fountoulakis, K., Tappenden, R.: A flexible coordinate descent method. Comput. Optim. Appl. 70(2), 351–394 (2018). https://doi.org/10.1007/s10589-018-9984-3
Fukushima, M., Mine, H.: A generalized proximal point algorithm for certain non-convex minimization problems. Int. J. Syst. Sci. 12(8), 989–1000 (1981). https://doi.org/10.1080/00207728108963798
Ghanbari, H., Scheinberg, K.: Proximal quasi-newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates. Comput. Optim. Appl. 69(3), 597–627 (2017). https://doi.org/10.1007/s10589-017-9964-z
Gräser, C., Sander, O.: Truncated nonsmooth newton multigrid methods for block-separable minimization problems. IMA J. Numer. Anal. 39(1), 454–481 (2018). https://doi.org/10.1093/imanum/dry073
Hintermüller, M., Ulbrich, M.: A mesh-independence result for semismooth Newton methods. Math. Program. 101(1, Ser. B), 151–184 (2004). https://doi.org/10.1007/s10107-004-0540-9
Hintermüller, M., Ito, K., Kunisch, K.: The primal-dual active set strategy as a semismooth newton method. SIAM J. Optim. 13(3), 865–888 (2002). https://doi.org/10.1137/s1052623401383558
Kanzow, C., Lechner, T.: Globalized inexact proximal newton-type methods for nonconvex composite functions. Comput. Optim. Appl. (2020). https://doi.org/10.1007/s10589-020-00243-6
Kruger, A.Y.: On fréchet subdifferentials. J. Math. Sci. 116(3), 3325–3358 (2003). https://doi.org/10.1023/a:1023673105317
Lee, C.-P., Wright, S.J.: Inexact successive quadratic approximation for regularized optimization. Comput. Optim. Appl. 72(3), 641–674 (2019). https://doi.org/10.1007/s10589-019-00059-z
Lee, J.D., Sun, Y., Saunders, M.A.: Proximal newton-type methods for minimizing composite functions. SIAM J. Optim. 24(3), 1420–1443 (2014). https://doi.org/10.1137/130921428
Li, J., Andersen, M.S., Vandenberghe, L.: Inexact proximal newton methods for self-concordant functions. Math. Methods Oper. Res. 85(1), 19–41 (2016). https://doi.org/10.1007/s00186-016-0566-9
Li, Q., Shen, L., Xu, Y., Zhang, N.: Multi-step fixed-point proximity algorithms for solving a class of optimization problems arising from image processing. Adv. Comput. Math. 41(2), 387–422 (2014). https://doi.org/10.1007/s10444-014-9363-2
Milzarek, A.: Numerical methods and second order theory for nonsmooth problems. Ph.D. thesis, TU München (2016)
Milzarek, A., Ulbrich, M.: A semismooth newton method with multidimensional filter globalization for \(l_1\)-optimization. SIAM J. Optim. 24(1), 298–333 (2014). https://doi.org/10.1137/120892167
Scheinberg, K., Goldfarb, D., Bai, X.: Fast first-order methods for composite convex optimization with backtracking. Found. Comput. Math. 14(3), 389–417 (2014). https://doi.org/10.1007/s10208-014-9189-9
Scheinberg, K., Tang, X.: Practical inexact proximal quasi-newton method with global complexity analysis. Math. Program. 160(1–2), 495–529 (2016). https://doi.org/10.1007/s10107-016-0997-3
Schiela, A.: A simplified approach to semismooth Newton methods in function space. SIAM J. Optim. 19(3), 1417–1432 (2008). https://doi.org/10.1137/060674375
Stella, L., Themelis, A., Patrinos, P.: Forward–backward quasi-newton methods for nonsmooth optimization problems. Comput. Optim. Appl. 67(3), 443–487 (2017). https://doi.org/10.1007/s10589-017-9912-y
Tran-Dinh, Q., Li, Y.H., Cevher, V.: Composite convex minimization involving self-concordant-like cost functions. In: Advances in Intelligent Systems and Computing, pp. 155–168. Springer International Publishing (2015). https://doi.org/10.1007/978-3-319-18161-5_14
Tröltzsch, F.: In: Optimal Control of Partial Differential Equations. In: Graduate Studies in Mathematics, vol. 112. Theory, Methods and Applications, Translated from the 2005 German original by Jügen Sprek. American Mathematical Society, Providence, RI (2010). https://doi.org/10.1090/gsm/112
Tseng, P., Yun, S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117(1–2), 387–423 (2007). https://doi.org/10.1007/s10107-007-0170-0
Ulbrich, M.: Nonsmooth newton-like methods for variational inequalities and constrained optimization problems in function spaces. Habilitation thesis (2002)
Ulbrich, M.: Semismooth Newton methods for variational inequalities and constrained optimization problems in function spaces. Soc. Indus. Appl. Math. (2011). https://doi.org/10.1137/1.9781611970692
Walther, A., Griewank, A.: Getting started with ADOL-c. In: Combinatorial Scientific Computing, pp. 181–202. Chapman and Hall/CRC (2012). https://doi.org/10.1201/b11644-8
Weiser, M., Deuflhard, P., Erdmann, B.: Affine conjugate adaptive newton methods for nonlinear elastomechanics. Optim. Methods Softw. 22(3), 413–431 (2007). https://doi.org/10.1080/10556780600605129