×

A quasi-Newton algorithm for nonconvex, nonsmooth optimization with global convergence guarantees. (English) Zbl 1333.49042

The authors propose a new algorithm for minimizing a locally Lipschitz function which is continuously differentiable in an open dense subset of a real vector space. The algorithm requires only the first derivative of the cost function to be optimized and is based on the method initiated previously by Broyden, Fletcher, Goldfarb and Shanno. The algorithm is first described, then the authors proceed to a randomized analysis of its global convergence and conclude with the implementation of the method together with numerical experiments to illustrate the matter. The algorithm is supported mainly by line search technique.

MSC:

49M15 Newton-type methods
49M05 Numerical methods based on necessary conditions
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
90C53 Methods of quasi-Newton type
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
93B40 Computational methods in systems theory (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstreicher, K.M., Lee, J.: A masked spectral bound for maximum-entropy sampling. In: MODA 7—Advances in Model-Oriented Design and Analysis, Berlin, pp. 1-10 (2004) · Zbl 0225.65073
[2] Ben-Tal, A., Nemirovski, A.: Robust optimization—methodology and applications. Math. Program. Ser. B 92(3), 453-480 (2002) · Zbl 1007.90047 · doi:10.1007/s101070100286
[3] Bertsekas, D.P.: Convex Optimization Theory. Athena Scientific, Nashua (2009) · Zbl 1242.90001
[4] Bonnans, J.F., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: Numerical Optimization: Theoretical and Practical Aspects. Springer, Berlin (2006) · Zbl 1108.65060
[5] Broyden, C.G.: The convergence of a class of double-rank minimization algorithms. J. Inst. Math. Appl. 6(1), 76-90 (1970) · Zbl 0223.65023 · doi:10.1093/imamat/6.1.76
[6] Burke, J.V., Lewis, A.S., Overton, M.L.: Approximating subdifferentials by random sampling of gradients. Math. Oper. Res. 27(3), 567-584 (2002) · Zbl 1082.49019 · doi:10.1287/moor.27.3.567.317
[7] Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15(3), 751-779 (2005) · Zbl 1078.65048 · doi:10.1137/030601296
[8] Candès, E.J., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies. IEEE Trans. Inf. Theory 52(12), 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[9] Chartrand, R.: Fast algorithms for nonconvex compressive sensing: MRI reconstruction from very few data. In: IEEE International Symposium on Biomedical Imaging (ISBI’09), pp. 262-265 (2009) · Zbl 1205.90230
[10] Chen, X.: Smoothing methods for nonsmooth, nonconvex optimization. Math. Program. Ser. B 134(1), 71-99 (2012) · Zbl 1266.90145 · doi:10.1007/s10107-012-0569-0
[11] Chen, X., Niu, L., Yuan, Y.: Optimality conditions and a smoothing trust region newton method for non-Lipschitz optimization. SIAM J. Optim. 23(3), 1528-1552 (2013) · Zbl 1291.90238 · doi:10.1137/120871390
[12] Clarke, F.H.: Optimization and nonsmooth analysis. In: Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, New York (1983) · Zbl 0582.49001
[13] Curtis, F.E., Overton, M.L.: A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization. SIAM J. Optim. 22(2), 474-500 (2012) · Zbl 1246.49031 · doi:10.1137/090780201
[14] Curtis, F.E., Que, X.: An Adaptive gradient sampling algorithm for nonsmooth optimization. Optim. Methods Softw. (2012). doi:10.1080/10556788.2012.714781 · Zbl 1284.49036
[15] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[16] Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[17] Fletcher, R.: A new approach to variable metric algorithms. Comput. J. 13(3), 317-322 (1970) · Zbl 0207.17402 · doi:10.1093/comjnl/13.3.317
[18] Goldfarb, D.: A family of variable metric updates derived by variational means. Math. Comput. 24(109), 23-26 (1970) · Zbl 0196.18002 · doi:10.1090/S0025-5718-1970-0258249-6
[19] Goldfarb, D., Iyengar, G.: Robust portfolio selection problems. Math. Oper. Res. 28(1), 1-38 (2003) · Zbl 1082.90082 · doi:10.1287/moor.28.1.1.14260
[20] Goldstein, A.A.: Optimization of Lipschitz continuous functions. Math. Program. 13(1), 14-22 (1977) · Zbl 0394.90088 · doi:10.1007/BF01584320
[21] Greif, C., Varah, J.: Minimizing the condition number for small rank modifications. SIAM J. Matrix Anal. Appl. 29(1), 82-97 (2006) · Zbl 1143.65341 · doi:10.1137/050647554
[22] Guenter, S., Sempf, M., Merkel, P., Strumberger, E., Tichmann, C.: Robust control of resistive wall modes using pseudospectra. New J. Phys. 11(053015), 1-40 (2009)
[23] Gumussoy, S., Henrion, D., Millstone, M., Overton, ML.: Multiobjective robust control with HIFOO 2.0. In: Proceedings of the IFAC Symposium on Robust Control Design, Haifa (2009) · Zbl 1082.49019
[24] Haarala, M.: Large-scale nonsmooth optimization: variable metric bundle method with limited memory. PhD thesis, University of Jyväskylä (2004) · Zbl 1068.90101
[25] Haarala, M., Miettinen, K., Mäkelä, M.M.: New limited memory bundle method for large-scale nonsmooth optimization. Optim. Methods Softw. 19(6), 673-692 (2004) · Zbl 1068.90101 · doi:10.1080/10556780410001689225
[26] Hare, W., Macklem, M.: Derivative-free optimization methods for finite minimax problems. Optim. Methods Softw. 28(2), 300-312 (2013) · Zbl 1270.90099 · doi:10.1080/10556788.2011.638923
[27] Hare, W., Nutini, J.: A derivative-free approximate gradient sampling algorithm for finite minimax problems. Comput. Optim. Appl. 56(1), 1-38 (2013) · Zbl 1300.90064 · doi:10.1007/s10589-013-9547-6
[28] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex analysis and minimization algorithms II. In: A Series of Comprehensive Studies in Mathematics. Springer, New York (1993) · Zbl 0795.49002
[29] Karmitsa, N.: Limited memory bundle method (2014). http://napsu.karmitsa.fi/lmbm/. Accessed 12 May 2014 · Zbl 1309.94033
[30] Kiwiel, K.C.: Methods of descent for nondifferentiable optimization. In: Lecture Notes in Mathematics. Springer, New York (1985) · Zbl 0561.90059
[31] Kiwiel, K.C.: A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA J. Numer. Anal. 6(2), 137-152 (1986) · Zbl 0603.65041 · doi:10.1093/imanum/6.2.137
[32] Kiwiel, K.C.: Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18(2), 379-388 (2007) · Zbl 1149.65043 · doi:10.1137/050639673
[33] Kiwiel, K.C.: A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 20(4), 1983-1994 (2010) · Zbl 1205.90230 · doi:10.1137/090748408
[34] Lemaréchal, C.: A view of line-searches. In: Optimization and Optimal Control: Proceedings of a Conference Held at Oberwolfach, March 16-22, 1980, Berlin, pp. 59-78 (1981) · Zbl 1007.90047
[35] Lewis, A.S., Overton, M.L.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141(1-2), 135-163 (2013) · Zbl 1280.90118 · doi:10.1007/s10107-012-0514-2
[36] Lukšan, L., Tůma, M., Šiška, M., Vlček, J., Ramešová, N.: UFO 2002: Interactive System for Universal Functional Optimization. Tech. Rep. 883, Institute of Computer Science, Academy of Sciences of the Czech Republic (2002) · Zbl 0394.90088
[37] Mifflin, R.: An algorithm for constrained optimization with semismooth functions. Math. Oper. Res. 2(2), 191-207 (1977) · Zbl 0395.90069 · doi:10.1287/moor.2.2.191
[38] Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35(151), 773-782 (1980) · Zbl 0464.65037 · doi:10.1090/S0025-5718-1980-0572855-7
[39] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[40] Overton, M.L.: HANSO: hybrid algorithm for non-smooth optimization (2014). http://www.cs.nyu.edu/faculty/overton/software/hanso/. Accessed 12 May 2014
[41] Rockafellar, RT; Birge, JR (ed.); Murty, KG (ed.), Nonsmooth optimization, 248-258 (1994), Ann Arbor
[42] Sanderson, C., Curtin, R.: Armadillo \[C++\]++ linear algebra library (2014). http://arma.sourceforge.net/. Accessed 12 May 2014 · Zbl 0207.17402
[43] Shanno, D.F.: Conditioning of quasi-Newton methods for function minimization. Math. Comput. 24(111), 647-656 (1970) · Zbl 0225.65073 · doi:10.1090/S0025-5718-1970-0274029-X
[44] Skajaa, A.: Limited memory BFGS for nonsmooth optimization. Master’s thesis, New York University, New York (2010)
[45] Vanbiervliet, J., Verheyden, K., Michiels, W., Vandewalle, S.: A nonsmooth optimisation approach for the stabilisation of time-delay systems. ESAIM Control Optim. Calc. Var. 14(3), 478-493 (2008) · Zbl 1146.65056 · doi:10.1051/cocv:2007060
[46] Vanbiervliet, J., Vandereycken, B., Michiels, W., Vandewalle, S., Diehl, M.: The smoothed spectral abscissa for robust stability optimization. SIAM J. Optim. 20(1), 156-171 (2009) · Zbl 1185.93110 · doi:10.1137/070704034
[47] Watson, G.A.: Data fitting problems with bounded uncertainties in the data. SIAM J. Matrix Anal. Appl. 22(4), 1274-1293 (2001) · Zbl 0983.65019 · doi:10.1137/S0895479899356596
[48] Wolfe, P.: A method of conjugate subgradients for minimizing nondifferentiable functions. Math. Program. Stud. 3, 145-173 (1975) · Zbl 0369.90093 · doi:10.1007/BFb0120703
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.