A derivative-free method for structured optimization problems. (English) Zbl 1466.90051

Cristofari, Andrea; Rinaldi, Francesco

SIAM J. Optim. 31, No. 2, 1079-1107 (2021).

Summary: Structured optimization problems are ubiquitous in fields like data science and engineering. The goal in structured optimization is using a prescribed set of points, called atoms, to build up a solution that minimizes or maximizes a given function. In the present paper, we want to minimize a black-box function over the convex hull of a given set of atoms, a problem that can be used to model a number of real-world applications. We focus on problems whose solutions are sparse, i.e., solutions that can be obtained as a proper convex combination of just a few atoms in the set, and propose a suitable derivative-free inner approximation approach that nicely exploits the structure of the given problem. This enables us to properly handle the dimensionality issues usually connected with derivative-free algorithms, thus getting a method that scales well in terms of both the dimension of the problem and the number of atoms. We analyze global convergence to stationary points. Moreover, we show that, under suitable assumptions, the proposed algorithm identifies a specific subset of atoms with zero weight in the final solution after finitely many iterations. Finally, we report numerical results showing the effectiveness of the proposed method.

MSC:

90C06	Large-scale problems in mathematical programming
90C30	Nonlinear programming
90C56	Derivative-free methods and methods using generalized derivatives

Keywords:

derivative-free optimization; decomposition methods; large-scale optimization

Software:

LINCOA; LCOBYQA; CUTEst; SDPEN; DFBOX_IMPR; CIFAR; PSwarm; SDBOX; LIBLINEAR; KELLEY; NEWUOA

References:

[1]	N. Andrei, An unconstrained optimization test functions collection, Adv. Model. Optim., 10 (2008), pp. 147-161. · Zbl 1161.90486
[2]	C. Audet, S. L. Digabel, C. Tribes, and V. R. Montplaisir, The NOMAD Project, https://www.gerad.ca/nomad.
[3]	C. Audet and W. Hare, Derivative-Free and Blackbox Optimization, Springer, New York, 2017. · Zbl 1391.90001
[4]	C. Audet, S. Le Digabel, and C. Tribes, NOMAD User Guide, Tech. Report G-2009-37, Les cahiers du GERAD, 2009, https://www.gerad.ca/nomad/Downloads/user_guide.pdf.
[5]	D. Avis, D. Bremner, and R. Seidel, How good are convex hull algorithms?, Comput. Geom., 7 (1997), pp. 265-301. · Zbl 0877.68119
[6]	F. Bach, R. Jenatton, J. Mairal, G. Obozinski, et al., Convex optimization with sparsity-inducing norms, Optim. Mach. Learn., 5 (2011), pp. 19-53. · Zbl 06064248
[7]	D. P. Bertsekas, Convex Optimization Algorithms, Athena Scientific, Belmont, MA, 2015. · Zbl 1347.90001
[8]	W. Brendel, J. Rauber, and M. Bethge, Decision-based adversarial attacks: Reliable attacks against black-box machine learning models, in Proceedings of the International Conference on Learning Representations, 2018.
[9]	C. Carathéodory, Über den variabilitätsbereich der koeffizienten von potenzreihen, die gegebene werte nicht annehmen, Math. Ann., 64 (1907), pp. 95-115. · JFM 38.0448.01
[10]	N. Carlini and D. Wagner, Towards evaluating the robustness of neural networks, in Proceedings of the IEEE Symposium on Security and Privacy, IEEE, 2017, pp. 39-57.
[11]	V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, The convex geometry of linear inverse problems, Found. Comput. Math., 12 (2012), pp. 805-849. · Zbl 1280.52008
[12]	J. Chen, D. Zhou, J. Yi, and Q. Gu, A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks, arXiv:1811.10828, 2018.
[13]	P.-Y. Chen, H. Zhang, Y. Sharma, J. Yi, and C.-J. Hsieh, ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models, in Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017, pp. 15-26.
[14]	A. R. Conn, K. Scheinberg, and L. N. Vicente, Geometry of interpolation sets in derivative free optimization, Math. Program., 111 (2008), pp. 141-172. · Zbl 1163.90022
[15]	A. R. Conn, K. Scheinberg, and L. N. Vicente, Geometry of sample sets in derivative-free optimization: Polynomial regression and underdetermined interpolation, IMA J. Numer. Anal., 28 (2008), pp. 721-748. · Zbl 1157.65034
[16]	A. R. Conn, K. Scheinberg, and L. N. Vicente, Introduction to Derivative-Free Optimization, MOS-SIAM Ser. Optim. 8, SIAM, Philadelphia, 2009. · Zbl 1163.49001
[17]	A. Cristofari, An almost cyclic 2-coordinate descent method for singly linearly constrained problems, Comput. Optim. Appl., 73 (2019), pp. 411-452. · Zbl 1414.90226
[18]	A. L. Custódio and L. N. Vicente, Using sampling and simplex derivatives in pattern search methods, SIAM J. Optim., 18 (2007), pp. 537-555. · Zbl 1144.65039
[19]	Y. Diouane, S. Gratton, and L. N. Vicente, Globally convergent evolution strategies for constrained optimization, Comput. Optim. Appl., 62 (2015), pp. 323-346. · Zbl 1326.90079
[20]	R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin, LIBLINEAR: A library for large linear classification, J. Mach. Learn. Res., 9 (2008), pp. 1871-1874. · Zbl 1225.68175
[21]	Z. Fan, H. Jeong, Y. Sun, and M. P. Friedlander, Atomic decomposition via polar alignment: The geometry of structured optimization, Found. Trends Optim., 3 (2020), pp. 280-366.
[22]	I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, Generative adversarial nets, in Advances in Neural Information Processing Systems, 2014, pp. 2672-2680.
[23]	N. I. Gould, D. Orban, and P. L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60 (2015), pp. 545-557. · Zbl 1325.90004
[24]	S. Gratton, C. W. Royer, L. N. Vicente, and Z. Zhang, Direct search based on probabilistic feasible descent for bound and linearly constrained problems, Comput. Optim. Appl., 72 (2019), pp. 525-559. · Zbl 1420.90083
[25]	E. A. Gumma, M. Hashim, and M. M. Ali, A derivative-free algorithm for linearly constrained optimization problems, Comput. Optim. Appl., 57 (2014), pp. 599-621. · Zbl 1304.90193
[26]	D. W. Hearn, S. Lawphongpanich, and J. A. Ventura, Restricted simplicial decomposition: Computation and extensions, in Computation Mathematical Programming, Springer, New York, 1987, pp. 99-118. · Zbl 0636.90027
[27]	A. Ilyas, L. Engstrom, A. Athalye, and J. Lin, Black-box adversarial attacks with limited queries and information, in Proceedings of the International Conference on Machine Learning, 2018, pp. 2137-2146.
[28]	L. P. Kaelbling, M. L. Littman, and A. W. Moore, Reinforcement learning: A survey, J. Artificial Intelligence Res., 4 (1996), pp. 237-285.
[29]	C. T. Kelley, Iterative Methods for Optimization, Frontiers in Appl. Math. 18, SIAM, Philadelphia, 1999. · Zbl 0934.90082
[30]	T. G. Kolda, R. M. Lewis, and V. Torczon, Optimization by direct search: New perspectives on some classical and modern methods, SIAM Rev., 45 (2003), pp. 385-482. · Zbl 1059.90146
[31]	T. G. Kolda, R. M. Lewis, and V. Torczon, Stationarity results for generating set search for linearly constrained optimization, SIAM J. Optim., 17 (2007), pp. 943-968. · Zbl 1126.90076
[32]	A. Krizhevsky and G. Hinton, Learning Multiple Layers of Features from Tiny Images, Technical report, 2009.
[33]	J. Larson, M. Menickelly, and S. M. Wild, Derivative-free optimization methods, Acta Numer., 28 (2019), pp. 287-404. · Zbl 1461.65169
[34]	R. M. Lewis and V. Torczon, Pattern search methods for linearly constrained minimization, SIAM J. Optim., 10 (2000), pp. 917-941. · Zbl 1031.90048
[35]	R. M. Lewis and V. Torczon, Active set identification for linearly constrained minimization without explicit derivatives, SIAM J. Optim., 20 (2010), pp. 1378-1405. · Zbl 1198.90398
[36]	G. Liuzzi, S. Lucidi, and M. Sciandrone, Sequential penalty derivative-free methods for nonlinear constrained optimization, SIAM J. Optim., 20 (2010), pp. 2614-2635. · Zbl 1223.65045
[37]	S. Lucidi and M. Sciandrone, A derivative-free algorithm for bound constrained optimization, Comput. Optim. Appl., 21 (2002), pp. 119-142. · Zbl 0988.90033
[38]	S. Lucidi and M. Sciandrone, On the global convergence of derivative-free methods for unconstrained optimization, SIAM J. Optim., 13 (2002), pp. 97-116. · Zbl 1027.90112
[39]	S. Lucidi, M. Sciandrone, and P. Tseng, Objective-derivative-free methods for constrained optimization, Math. Program., 92 (2002), pp. 37-59. · Zbl 1024.90062
[40]	J. J. Moré and S. M. Wild, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20 (2009), pp. 172-191. · Zbl 1187.90319
[41]	A. Y. Ng and M. Jordan, PEGASUS: A policy search method for large MDPs and POMDPs, in Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, 2000, pp. 406-415.
[42]	M. Patriksson, Nonlinear Programming and Variational Inequality Problems: A Unified Approach, Appl. Optim. 23, Springer, New York, 2013. · Zbl 0913.65058
[43]	M. J. Powell, LINCOA, https://en.wikipedia.org/wiki/LINCOA.
[44]	M. J. Powell, The NEWUOA software for unconstrained optimization without derivatives, in Large-Scale Nonlinear Optimization, Springer, New York, 2006, pp. 255-297. · Zbl 1108.90005
[45]	M. J. Powell, Developments of NEWUOA for minimization without derivatives, IMA J. Numer. Anal., 28 (2008), pp. 649-664. · Zbl 1154.65049
[46]	M. J. Powell, On fast trust region methods for quadratic models with linear constraints, Math. Program. Comput., 7 (2015), pp. 237-267. · Zbl 1325.65084
[47]	A. I. F. Vaz and L. N. Vicente, A particle swarm pattern search method for bound constrained global optimization, J. Global Optim., 39 (2007), pp. 197-219. · Zbl 1180.90252
[48]	A. I. F. Vaz and L. N. Vicente, PSwarm: A hybrid solver for linearly constrained global derivative-free optimization, Optim. Methods Softw., 24 (2009), pp. 669-685. · Zbl 1177.90327
[49]	E. H. Zarantonello, Projections on convex sets in Hilbert space and spectral theory, in Contributions to Nonlinear Functional Analysis, Elsevier, Amsterdam, 1971, pp. 237-424. · Zbl 0281.47043