×

A nonsmooth trust-region method for locally Lipschitz functions with application to optimization problems constrained by variational inequalities. (English) Zbl 1446.49006

Summary: We propose a general trust-region method for the minimization of nonsmooth and nonconvex, locally Lipschitz continuous functions that can be applied, e.g., to optimization problems constrained by elliptic variational inequalities. The convergence of the considered algorithm to C-stationary points is verified in an abstract setting and under suitable assumptions on the involved model functions. For a special instance of a variational inequality constrained problem, we are able to properly characterize the Bouligand subdifferential of the reduced cost function, and, based on this characterization result, we construct a computable trust-region model which satisfies all hypotheses of our general convergence analysis. The article concludes with numerical experiments that illustrate the main properties of the proposed algorithm.

MSC:

49J40 Variational inequalities
49J52 Nonsmooth analysis
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives

Software:

GRANSO; GradSamp; DGM; PNEW
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Z. Akbari, R. Yousefpour, and M. Reza Peyghami, A new nonsmooth trust region algorithm for locally Lipschitz unconstrained optimization problems, J. Optim. Theory Appl., 164 (2015), pp. 733-754. · Zbl 1318.49054
[2] P. Apkarian, D. Noll, and L. Ravanbod, Nonsmooth bundle trust-region algorithm with applications to robust stability, Set-Valued Var. Anal., 24 (2016), pp. 115-148. · Zbl 1334.49092
[3] A. Bagirov, N. Karmitsa, and M. M. Mäkelä, Introduction to Nonsmooth Optimization, Springer, New York, 2014. · Zbl 1312.90053
[4] A. M. Bagirov, L. Jin, N. Karmitsa, A. Al Nuaimat, and N. Sultanova, Subgradient method for nonconvex nonsmooth optimization, J. Optim. Theory Appl., 157 (2013), pp. 416-435. · Zbl 1282.90133
[5] A. M. Bagirov, B. Karasözen, and M. Sezer, Discrete gradient method: Derivative-free method for nonsmooth optimization, J. Optim. Theory Appl., 137 (2008), pp. 317-334. · Zbl 1165.90021
[6] V. Barbu, Necessary conditions for distributed control problems governed by parabolic variational inequalities, SIAM J. Control Optim., 19 (1981), pp. 64-86, https://doi.org/10.1137/0319006. · Zbl 0474.49024
[7] V. Barbu, Optimal Control of Variational Inequalities, Res. Notes Math. 100, Pitman, Boston, MA, 1984. · Zbl 0574.49005
[8] A. Bihain, Optimization of upper semidifferentiable functions, J. Optim. Theory Appl., 44 (1984), pp. 545-568. · Zbl 0534.90069
[9] S. C. Brenner and L. R. Scott, The Mathematical Theory of Finite Element Methods, 3rd ed., Springer, New York, 2008. · Zbl 1135.65042
[10] J. V. Burke, A. Lewis, and M. L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15 (2005), pp. 751-779, https://doi.org/10.1137/030601296. · Zbl 1078.65048
[11] J. V. Burke, A. S. Lewis, and M. L. Overton, A nonsmooth, nonconvex optimization approach to robust stabilization by static output feedback and low-order controllers, IFAC Proc. Vol., 36 (2003), pp. 175-181.
[12] L. Calatroni, C. Chung, J. C. De los Reyes, C.-B. Schönlieb, and T. Valkonen, Bilevel approaches for learning of variational imaging models, in Variational Methods, Radon Ser. Comput. Appl. Math. 18, De Gruyter, Berlin, 2017, pp. 252-290. · Zbl 1468.94014
[13] C. Carstensen, B. D. Reddy, and M. Schedensack, A natural nonconforming FEM for the Bingham flow problem is quasi-optimal, Numer. Math., 133 (2016), pp. 37-66. · Zbl 1457.65186
[14] Y. J. Chen, T. Pock, and H. Bischof, Learning \(l_1\)-based analysis and synthesis sparsity priors using bi-level optimization, in Workshop on Analysis Operator Learning vs. Dictionary Learning, NIPS2012, 2012.
[15] C. Christof, Sensitivity Analysis of Elliptic Variational Inequalities of the First and the Second Kind, Ph.D. thesis, Technische Universität Dortmund, Dortmund, Germany, 2018.
[16] C. Christof, Gradient-based solution algorithms for a class of bilevel optimization and optimal control problems with a nonsmooth lower level, SIAM J. Optim., 30 (2020), pp. 290-318, https://doi.org/10.1137/18M1225707. · Zbl 1432.49007
[17] C. Christof, C. Clason, C. Meyer, and S. Walther, Optimal control of a non-smooth semilinear elliptic equation, Math. Control Relat. Fields, 8 (2018), pp. 247-276. · Zbl 1407.49026
[18] C. Christof, J. C. De los Reyes, and C. Meyer, A Non-Smooth Trust-Region Method for B-Differentiable Functions with Application to Optimization Problems Constrained by Variational Inequalities, preprint, https://arxiv.org/abs/1711.03208v1, 2017.
[19] F. H. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, 1990, https://doi.org/10.1137/1.9781611971309. · Zbl 0696.49002
[20] B. Colson, P. Marcotte, and G. Savard, A trust-region method for nonlinear bilevel programming: Algorithm and computational experience, Comput. Optim. Appl., 30 (2005), pp. 211-227. · Zbl 1078.90041
[21] F. E. Curtis, T. Mitchell, and M. Overton, A BFGS-SQP method for nonsmooth, nonconvex, constrained optimization and its evaluation using relative minimization profiles, Optim. Methods Softw., 32 (2017), pp. 148-181. · Zbl 1364.90359
[22] F. E. Curtis and X. Que, An adaptive gradient sampling algorithm for non-smooth optimization, Optim. Methods Softw., 28 (2013), pp. 1302-1324. · Zbl 1284.49036
[23] A. Daniilidis and P. Georgiev, Approximate convexity and submonotonicity, J. Math. Anal. Appl., 291 (2004), pp. 292-301. · Zbl 1048.49008
[24] J. C. De los Reyes, Optimal control of a class of variational inequalities of the second kind, SIAM J. Control Optim., 49 (2011), pp. 1629-1658, https://doi.org/10.1137/090764438. · Zbl 1226.49008
[25] J. C. De los Reyes, Optimization of mixed variational inequalities arising in flow of viscoplastic materials, Comput. Optim. Appl., 52 (2012), pp. 757-784. · Zbl 1258.49010
[26] J. C. De los Reyes and C. Meyer, Strong stationarity conditions for a class of optimization problems governed by variational inequalities of the second kind, J. Optim. Theory Appl., 168 (2016), pp. 375-409. · Zbl 1337.49040
[27] E. J. Dean, R. Glowinski, and G. Guidoboni, On the numerical simulation of Bingham visco-plastic flow: Old and new results, J. Non-Newton. Fluid Mech., 142 (2007), pp. 36-62. · Zbl 1107.76061
[28] J. E. Dennis, S.-B. B. Li, and R. A. Tapia, A unified approach to global convergence of trust region methods for nonsmooth optimization, Math. Program., 68 (1995), pp. 319-346. · Zbl 0835.90086
[29] G. Emiel and C. Sagastizábal, Incremental-like bundle methods with application to energy planning, Comput. Optim. Appl., 46 (2010), pp. 305-332. · Zbl 1220.90120
[30] M. Fuchs and G. Seregin, Variational Methods for Problems from Plasticity Theory and for Generalized Newtonian Fluids, Springer, Berlin, 2000. · Zbl 0964.76003
[31] A. Fuduli, M. Gaudioso, and G. Giallombardo, A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optim. Methods Softw., 19 (2004), pp. 89-102. · Zbl 1211.90182
[32] G. Giallombardo and D. Ralph, Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs, Math. Program., 112 (2008), pp. 335-369. · Zbl 1145.90073
[33] A. A. Goldstein, Optimization of Lipschitz continuous functions, Math. Program., 13 (1977), pp. 14-22. · Zbl 0394.90088
[34] W. Hare and C. Sagastizábal, A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20 (2010), pp. 2442-2473, https://doi.org/10.1137/090754595. · Zbl 1211.90183
[35] L. Hertlein and M. Ulbrich, An inexact bundle algorithm for nonconvex nonsmooth minimization in Hilbert space, SIAM J. Control Optim., 57 (2019), pp. 3137-3165, https://doi.org/10.1137/18M1221849. · Zbl 1461.49041
[36] M. Hintermüller, A proximal bundle method based on approximate subgradients, Comput. Optim. Appl., 20 (2001), pp. 245-266. · Zbl 1054.90053
[37] M. Hintermüller and T. M. Surowiec, A bundle-free implicit programming approach for a class of elliptic MPECs in function space, Math. Program., 160 (2016), pp. 271-305. · Zbl 1355.49025
[38] R. R. Huilgol and Z. You, Application of the augmented Lagrangian method to steady pipe flows of Bingham, Casson and Herschel-Bulkley fluids, J. Non-Newton. Fluid Mech., 128 (2005), pp. 126-143. · Zbl 1195.76024
[39] K. Ito and K. Kunisch, Optimal control of parabolic variational inequalities, J. Math. Pures Appl., 93 (2010), pp. 329-360. · Zbl 1247.35062
[40] N. Karmitsa, A. Bagirov, and M. M. Mäkelä, Comparing different nonsmooth minimization methods and software, Optim. Methods Softw., 27 (2012), pp. 131-153. · Zbl 1242.90233
[41] N. Karmitsa and M. M. Mäkelä, Limited memory bundle method for large bound constrained nonsmooth optimization: Convergence analysis, Optim. Methods Softw., 25 (2010), pp. 895-916. · Zbl 1198.90359
[42] A. M. Khludnev and J. Sokołowski, Modelling and Control in Solid Mechanics, Birkhäuser Boston, Boston, 1991. · Zbl 0865.73003
[43] N. Kikuchi and J. T. Oden, Contact Problems in Elasticity, Stud. Appl. Math. 8, SIAM, Philadelphia, 1988, https://doi.org/10.1137/1.9781611970845. · Zbl 0685.73002
[44] K. C. Kiwiel, Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim., 18 (2007), pp. 379-388, https://doi.org/10.1137/050639673. · Zbl 1149.65043
[45] K. C. Kiwiel, Improved convergence result for the discrete gradient and secant methods for nonsmooth optimization, J. Optim. Theory Appl., 144 (2009), pp. 69-75. · Zbl 1183.90389
[46] K. Kunisch and T. Pock, A bilevel optimization approach for parameter learning in variational models, SIAM J. Imaging Sci., 6 (2013), pp. 938-983, https://doi.org/10.1137/120882706. · Zbl 1280.49053
[47] C. Lemaréchal, A view of line-searches, in Optimization and Optimal Control, A. Auslender, W. Oettli, and J. Stoer, eds., Springer, Berlin, 1981, pp. 59-78.
[48] C. Lemaréchal, J. J. Strodiot, and A. Bihain, On a bundle algorithm for nonsmooth optimization, in Nonlinear Programming 4, O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds., Academic Press, New York, 1981, pp. 245-282. · Zbl 0533.49023
[49] A. S. Lewis, Active sets, nonsmoothness, and sensitivity, SIAM J. Optim., 13 (2002), pp. 702-725, https://doi.org/10.1137/S1052623401387623. · Zbl 1055.90072
[50] A. S. Lewis and M. L. Overton, Nonsmooth optimization via quasi-Newton methods, Math. Program., 141 (2013), pp. 135-163. · Zbl 1280.90118
[51] A. S. Lewis and S. J. Wright, A proximal method for composite minimization, Math. Program., 158 (2016), pp. 501-546. · Zbl 1345.49041
[52] L. Lukšan and J. Vlček, A bundle-Newton method for nonsmooth unconstrained minimization, Math. Program., 83 (1998), pp. 373-391. · Zbl 0920.90132
[53] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, UK, 1996.
[54] N. Mahdavi-Amiri and R. Yousefpour, An effective nonsmooth optimization algorithm for locally Lipschitz functions, J. Optim. Theory Appl., 155 (2012), pp. 180-195. · Zbl 1255.90113
[55] M. M. Mäkelä, N. Karmitsa, and A. Bagirov, Subgradient and bundle methods for nonsmooth optimization, in Numerical Methods for Differential Equations, Optimization, and Technological Problems, Springer, Dordrecht, The Netherlands, 2013, pp. 275-304. · Zbl 1267.65066
[56] P. Marcotte, G. Savard, and D. L. Zhu, A trust region algorithm for nonlinear bilevel programming, Oper. Res. Lett., 29 (2001), pp. 171-179. · Zbl 0993.90071
[57] R. Mifflin, An algorithm for constrained optimization with semismooth functions, Math. Oper. Res., 2 (1977), pp. 191-207. · Zbl 0395.90069
[58] P. P. Mosolov and V. P. Miasnikov, Variational methods in the theory of the fluidity of a viscous-plastic medium, J. Appl. Math. Mech., 29 (1965), pp. 545-577. · Zbl 0168.45505
[59] P. P. Mosolov and V. P. Miasnikov, On stagnant flow regions of a viscous-plastic medium in pipes, PMM, 30 (1966), pp. 705-717.
[60] P. P. Mosolov and V. P. Miasnikov, On qualitative singularities of the flow of a viscoplastic medium in pipes, J. Appl. Math. Mech., 31 (1967), pp. 609-613. · Zbl 0236.76006
[61] H. V. Ngai, D. T. Luc, and M. Thera, Approximate convex functions, J. Nonlinear Convex Anal., 1 (2011), pp. 155-176. · Zbl 1033.49029
[62] D. Noll, Cutting plane oracles to minimize non-smooth non-convex functions, Set-Valued Var. Anal., 18 (2010), pp. 531-568. · Zbl 1219.49013
[63] D. Noll, Bundle method for non-convex minimization with inexact subgradients and function values, in Computational and Analytical Mathematics, D. H. Bailey, H. H. Bauschke, P. Borwein, F. Garvan, M. Théra, J. D. Vanderwerff, and H. Wolkowicz, eds., Springer, New York, 2013, pp. 555-592. · Zbl 1282.90241
[64] D. Noll, Convergence of non-smooth descent methods using the Kurdyka-Lojasiewicz inequality, J. Optim. Theory Appl., 160 (2014), pp. 553-572. · Zbl 1298.90079
[65] D. Noll, Cutting plane oracles for non-smooth trust-regions, Pure Appl. Funct. Anal., Special Issue Dedicated to the Memory of Jon Borwein, to appear. · Zbl 1219.49013
[66] J. Outrata, M. Kocvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results, Springer, Dordrecht, The Netherlands, 1998. · Zbl 0947.90093
[67] J. Outrata and J. Zowe, A numerical approach to optimization problems with variational inequality constraints, Math. Program., 68 (1995), pp. 105-130. · Zbl 0835.90093
[68] M. J. D. Powell, A hybrid method for nonlinear equations, in Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, ed., Gordon and Breach, London, 1970. · Zbl 0277.65028
[69] L. Qi and J. Sun, A trust region algorithm for minimization of locally Lipschitzian functions, Math. Program., 66 (1994), pp. 25-43. · Zbl 0821.90108
[70] A.-T. Rauls and S. Ulbrich, Computation of a Bouligand generalized derivative for the solution operator of the obstacle problem, SIAM J. Control Optim., 57 (2019), pp. 3223-3248, https://doi.org/10.1137/18M1187283. · Zbl 1425.49004
[71] A.-T. Rauls and G. Wachsmuth, Generalized derivatives for the solution operator of the obstacle problem, Set-Valued Var. Anal., 28 (2020), pp. 259-285. · Zbl 1442.49030
[72] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren Math. Wiss. 317, Springer, Berlin, 1998.
[73] C. Sagastizábal, Composite proximal bundle method, Math. Program., 140 (2013), pp. 189-233. · Zbl 1273.90163
[74] W. Schirotzek, Nonsmooth Analysis, Springer, Berlin, 2007. · Zbl 1120.49001
[75] S. Scholtes, Introduction to Piecewise Differentiable Equations, Springer, New York, 2012. · Zbl 1453.49002
[76] S. Scholtes and M. Stöhr, Exact penalization of mathematical programs with equilibrium constraints, SIAM J. Control Optim., 37 (1999), pp. 617-652, https://doi.org/10.1137/S0363012996306121. · Zbl 0922.90128
[77] H. Schramm, Eine Kombination von Bundle- und Trust-Region-Verfahren zur Lösung nichtdifferenzierbarer Optimierungsprobleme, Ph.D. thesis, Universität Bayreuth, Bayreuth, Germany, 1989. · Zbl 0683.90069
[78] H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2 (1992), pp. 121-152, https://doi.org/10.1137/0802008. · Zbl 0761.90090
[79] N. Z. Shor, Minimization Methods for Non-Differentiable Functions, Springer Ser. Comput. Math. 3, Springer, New York, 1985. · Zbl 0561.90058
[80] T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20 (1983), pp. 626-637, https://doi.org/10.1137/0720042. · Zbl 0518.65042
[81] T. M. Surowiec, Numerical Optimization Methods for the Optimal Control of Elliptic Variational Inequalities, Springer, New York, 2018, pp. 123-170. · Zbl 1416.49034
[82] G. Wachsmuth, Towards M-stationarity for optimal control of the obstacle problem with control constraints, SIAM J. Control Optim., 54 (2016), pp. 964-986, https://doi.org/10.1137/140980582. · Zbl 1337.49042
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.