×

zbMATH — the first resource for mathematics

A derivative-free \(\mathcal{V} \mathcal{U}\)-algorithm for convex finite-max problems. (English) Zbl 1443.90331
This paper presents a complete and fully-functional derivative-free optimization (DFO )\(\mathcal{V}\mathcal{U}\)-algorithm for minimizing nonsmooth convex finite-max objective functions on \(R^n\) under reasonable assumptions. This algorithm is the derivative-free setting, where exact function values are available but approximations of subgradients are sufficient for convergence. Global convergence is proved. Numerical results show that, at the expence of increased CPU time and number of function calls, the DFO \(\mathcal{V}\mathcal{U}\)-algorithm gives an improvement on final function value accuracy when compared to other inexact methods, and even compared to the ExBun method that uses exact first-order information.

MSC:
90C56 Derivative-free methods and methods using generalized derivatives
65K10 Numerical optimization and variational techniques
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramson, M.; Audet, C.; Dennis Jr., J.; Le Digabel, S., OrthoMADS: A deterministic MADS instance with orthogonal directions, SIAM J. Optim., 20, 2, 948-966 (2009) · Zbl 1189.90202
[2] Ackooij, W. V.; Oliveira, W. D., Level bundle methods for constrained convex optimization with various oracles, Comput. Optim. Appl., 57, 3, 555-597 (2014) · Zbl 1329.90109
[3] Apkarian, P.; Noll, D.; Ravanbod, L., Nonsmooth bundle trust-region algorithm with applications to robust stability, Set-Valued Var. Anal., 24, 1, 115-148 (2016) · Zbl 1334.49092
[4] Asplund, E.; Rockafellar, R., Gradients of convex functions, Trans. Amer. Math. Soc., 139, 443-467 (1969) · Zbl 0181.41901
[5] Audet, C., A Survey on Direct Search Methods for Blackbox Optimization and Their Applications, 31-56 (2014), Springer: Springer, New York · Zbl 1321.90125
[6] Audet, C.; Béchard, V.; Le Digabel, S., Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, J. Global Optim., 41, 2, 299-318 (2008) · Zbl 1157.90535
[7] Audet, C.; Dennis Jr., J., Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 1, 188-217 (2006) · Zbl 1112.90078
[8] Audet, C.; Hare, W., Derivative-free and Blackbox Optimization (2017), Springer International AG: Springer International AG, Switzerland · Zbl 1391.90001
[9] Bagirov, A.; Karasözen, B.; Sezer, M., Discrete gradient method: Derivative-free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 2, 317-334 (2008) · Zbl 1165.90021
[10] Bigdeli, K.; Hare, W.; Nutini, J.; Tesfamariam, S., Optimizing damper connectors for adjacent buildings, Optim. Eng., 17, 1, 47-75 (2016) · Zbl 1364.90361
[11] Bonnans, J.; Gilbert, J.; Lemaréchal, C.; Sagastizábal, C., Numerical Optimization. Theoretical and Practical Aspects, xiv+490 (2006), Universitext. Springer-Verlag: Universitext. Springer-Verlag, Berlin · Zbl 1108.65060
[12] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1058.90049
[13] Combettes, P. and Pesquet, J., Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer Optim. Appl., vol. 49, Springer, New York, 2011, pp. 185-212. doi:10.1007/978-1-4419-9569-8_10. · Zbl 1242.90160
[14] Conn, A., Scheinberg, K., and Toint, P., On the convergence of derivative-free methods for unconstrained optimization, in Approximation Theory and Optimization (Cambridge, 1996), Cambridge Univ. Press, Cambridge, 1997, pp. 83-108. · Zbl 1042.90617
[15] Conn, A., Scheinberg, K., and Vicente, L., Introduction to derivative-free optimization, MPS/SIAM Series on Optimization Vol. 8, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2009. doi:10.1137/1.9780898718768. · Zbl 1163.49001
[16] Correa, R.; Lemaréchal, C., Convergence of some algorithms for convex minimization, Math. Program, 62, 2, 261-275 (1993) · Zbl 0805.90083
[17] Custódio, A.; Vicente, L., Using sampling and simplex derivatives in pattern search methods, SIAM J. Optim., 18, 2, 537-555 (2007) · Zbl 1144.65039
[18] Frangioni, A.; Gorgone, E., Bundle methods for sum-functions with ‘easy’ components: Applications to multicommodity network design, Math. Program, 145, 1-2, 133-161 (2014) · Zbl 1300.90027
[19] Fuduli, A.; Gaudioso, M.; Giallombardo, G., A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optim. Methods Softw., 19, 1, 89-102 (2004) · Zbl 1211.90182
[20] Hare, W., Numerical analysis of V U-decomposition, U-gradient, and U-hessian approximations, SIAM J. Optim., 24, 4, 1890-1913 (2014) · Zbl 1318.49053
[21] Hare, W.; Lucet, Y., Derivative-free optimization via proximal point methods, J. Optim. Theory Appl., 160, 1, 204-220 (2014) · Zbl 1291.90317
[22] Hare, W.; Macklem, M., Derivative-free optimization methods for finite minimax problems, Optim. Methods Softw., 28, 2, 300-312 (2013) · Zbl 1270.90099
[23] 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
[24] Hare, W.; Nutini, J.; Tesfamariam, S., A survey of non-gradient optimization methods in structural engineering, Adv. Eng. Soft., 59, 19-28 (2013)
[25] Hare, W. and Planiden, C., Computing proximal points of convex functions with inexact subgradients, preprint (2018). to appear in Set-Valued Var. Anal. pp. 469-492. · Zbl 1401.49039
[26] Hare, W.; Sagastizábal, C.; Solodov, M., A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim. Appl., 63, 1, 1-28 (2016) · Zbl 1343.90069
[27] Helmberg, C.; Overton, M.; Rendl, F., The spectral bundle method with second-order information, Optim. Methods Softw., 29, 4, 855-876 (2014) · Zbl 1306.90118
[28] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM J. Optim., 10, 3, 673-696 (2000) · Zbl 0960.65074
[29] Hiriart-Urruty, J.B. and Lemaréchal, C., Convex analysis and minimization algorithms. II, Grundlehren der Mathematischen Wissenschaften [Fundamental principles of mathematical sciences] Vol. 306. Springer-Verlag, Berlin, 1993. Advanced theory and bundle methods. · Zbl 0795.49001
[30] Joki, K.; Bagirov, A.; Karmitsa, N.; Mäkelä, M., A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes, J. Global Optim., 68, 3, 501-535 (2017) · Zbl 1369.90137
[31] Karmitsa, N., Test problems for large-scale nonsmooth minimization, Rep. Depart. Math. Inf. Technol. Ser. B, Sci. Comp., 4, 1-12 (2007)
[32] Karmitsa, N.; Bagirov, A.; Taheri, S., New diagonal bundle method for clustering problems in large data sets, Eur. J. Oper. Res., 263, 2, 367-379 (2017) · Zbl 1380.90226
[33] Kelley, C., Iterative methods for optimization, Frontiers in Applied Mathematics Vol. 18, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. doi:10.1137/1.9781611970920. · Zbl 0934.90082
[34] Kelley, C., Implicit filtering, Software, Environments, and Tools Vol. 23, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. doi:10.1137/1.9781611971903.
[35] Kiwiel, K., Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program, 46, 1, 105-122 (1990) · Zbl 0697.90060
[36] Kiwiel, K., A proximal bundle method with approximate subgradient linearizations, SIAM J. Optim., 16, 4, 1007-1023 (2006) · Zbl 1104.65055
[37] Kiwiel, K., A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim., 20, 4, 1983-1994 (2010) · Zbl 1205.90230
[38] Larson, J.; Menickelly, M.; Wild, S., Manifold sampling for \(####\) nonconvex optimization, SIAM J. Optim., 26, 4, 2540-2563 (2016) · Zbl 1351.90167
[39] Le Digabel, S., Nomad: Nonlinear optimization with the mads algorithm. Rapport technique G-2009-39, Les cahiers du GERAD (2009). · Zbl 1365.65172
[40] Lemaréchal, C.; Oustry, F.; Sagastizábal, C., The U-Lagrangian of a convex function, Trans. Amer. Math. Soc., 352, 2, 711-729 (2000) · Zbl 0939.49014
[41] Lewis, A.; Wright, S., A proximal method for composite minimization, Math. Program, 158, 1-2, 501-546 (2016) · Zbl 1345.49041
[42] Mifflin, R. and Sagastizábal, C., V U-decomposition derivatives for convex max-functions, in Ill-posed Variational Problems and Regularization Techniques (Trier, 1998), Lecture Notes in Econom. and Math. Systems, Vol. 477, Springer, Berlin, 1999, pp. 167-186. doi:10.1007/978-3-642-45780-7_11. · Zbl 0944.65069
[43] Mifflin, R. and Sagastizábal, C., Functions with primal-dual gradient structure and U-Hessians, in Nonlinear Optimization and Related Topics (Erice, 1998), Appl. Optim., Vol. 36. Kluwer Acad. Publ., Dordrecht, 2000, pp. 219-233. doi:10.1007/978-1-4757-3226-9_12. · Zbl 1138.90482
[44] Mifflin, R.; Sagastizábal, C., On V U-theory for functions with primal-dual gradient structure, SIAM J. Optim., 11, 2, 547-571 (2000) · Zbl 1015.90084
[45] Mifflin, R.; Sagastizábal, C., Proximal points are on the fast track, J. Convex Anal., 9, 2, 563-579 (2002) · Zbl 1037.49031
[46] Mifflin, R.; Sagastizábal, C., Primal-dual gradient structured functions: Second-order results; links to epi-derivatives and partly smooth functions, SIAM J. Optim., 13, 4, 1174-1194 (2003) · Zbl 1036.90067
[47] Mifflin, R.; Sagastizábal, C., V U-smoothness and proximal point results for some nonconvex functions, Optim. Methods Softw., 19, 5, 463-478 (2004) · Zbl 1097.90059
[48] Mifflin, R.; Sagastizábal, C., A V U-algorithm for convex minimization, Math. Program, 104, 2-3, 583-608 (2005) · Zbl 1085.65051
[49] Moré, J. J.; Wild, S. M., Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 1, 172-191 (2009) · Zbl 1187.90319
[50] Nel, L., Continuity Theory (2016), Springer: Springer, Basel · Zbl 1350.54001
[51] Noll, D.; Prot, O.; Rondepierre, A., A proximity control algorithm to minimize nonsmooth and nonconvex functions, Pac. J. Optim., 4, 3, 571-604 (2008) · Zbl 1162.49020
[52] Oliveira, W.D., Proximal bundle methods for nonsmooth DC programming, preprint (2017). Available at http://www.oliveira.mat.br/publications. · Zbl 1428.90130
[53] Oliveira, W. D.; Sagastizábal, C.; Lemaréchal, C., Convex proximal bundle methods in depth: A unified analysis for inexact oracles, Math. Program, 148, 1-2, 241-277 (2014) · Zbl 1327.90321
[54] Oliveira, W. D.; Solodov, M., A doubly stabilized bundle method for nonsmooth convex optimization, Math. Program, 156, 1-2, 125-159 (2016) · Zbl 1346.90675
[55] Powell, M., Developments of NEWUOA for minimization without derivatives, IMA J. Numer. Anal., 28, 4, 649-664 (2008) · Zbl 1154.65049
[56] Press, W.; Teukolsky, S.; Vetterling, W.; Flannery, B., Numerical Recipes: The Art of Scientific Computing (2007), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1132.65001
[57] Rockafellar, R. and Wets, J.B., Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental principles of mathematical sciences]. Springer-Verlag, Berlin, 1998. doi:10.1007/978-3-642-02431-3.
[58] Sagastizábal, C., Composite proximal bundle method, Math. Program, 140, 1, 189-233 (2013) · Zbl 1273.90163
[59] Salomão, E.; Santos, S.; Simões, L., On the differentiability check in gradient sampling methods, Optim. Methods Softw., 31, 5, 983-1007 (2016) · Zbl 1354.65122
[60] Salomão, E., Santos, S., and Simões, L., On the local convergence analysis of the gradient sampling method, preprint (2016). to appear in Optimization. Available at www.optimization-online.org/DB_HTML/2016/10/5683.html. · Zbl 1386.90148
[61] Salomão, E., Santos, S., and Simões, L., A second-order information-based gradient and function sampling method for nonconvex nonsmooth optimization. preprint (2017), to appear in Optimization. Available at www.optimization-online.org/DB_HTML/2016/06/5513.html.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.