A derivative-free approximate gradient sampling algorithm for finite minimax problems. (English) Zbl 1300.90064
Summary: In this paper we present a derivative-free optimization algorithm for finite minimax problems. The algorithm calculates an approximate gradient for each of the active functions of the finite max function and uses these to generate an approximate subdifferential. The negative projection of 0 onto this set is used as a descent direction in an Armijo-like line search. We also present a robust version of the algorithm, which uses the ‘almost active’ functions of the finite max function in the calculation of the approximate subdifferential. Convergence results are presented for both algorithms, showing that either \(f(x^{k})\rightarrow - \infty \) or every cluster point is a Clarke stationary point. Theoretical and numerical results are presented for three specific approximate gradients: the simplex gradient, the centered simplex gradient and the Gupal estimate of the gradient of the Steklov averaged function. A performance comparison is made between the regular and robust algorithms, the three approximate gradients, and a regular and robust stopping condition.
MSC:
| 90C47 | Minimax problems in mathematical programming |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Keywords:
derivative-free optimization; minimax problems; generalized gradient; subgradient approximationReferences:
| [1] | Abramson, A.M., Audet, C., Couture, G., Dennis, J.E. Jr., Le Digabel, S., Tribes, C.: The NOMAD project. Software available at http://www.gerad.ca/nomad · Zbl 1065.15029 |
| [2] | Bagirov, A.M., 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 · doi:10.1007/s10957-007-9335-5 |
| [3] | Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Springer, New York (2011) · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7 |
| [4] | Booker, A. J.; Dennis, J. E.; Frank, P. D.; Serafini, D. B.; Torczon, V., Optimization using surrogate objectives on a helicopter test example, Arlington, VA, 1997, Boston · Zbl 0937.76067 · doi:10.1007/978-1-4612-1780-0_3 |
| [5] | Bortz, D. M.; Kelley, C. T., The simplex gradient and noisy optimization problems, No. 24, 77-90 (1998), Boston · Zbl 0927.65077 · doi:10.1007/978-1-4612-1780-0_5 |
| [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] | Cai, X., Teo, K., Yang, X., Zhou, X.: Portfolio optimization under a minimax rule. Manag. Sci. 46(7), 957-972 (2000) · Zbl 1231.91149 · doi:10.1287/mnsc.46.7.957.12039 |
| [9] | Clarke, F.H.: Optimization and Nonsmooth Analysis, 2nd edn. Classics Appl. Math., vol. 5. SIAM, Philadelphia (1990) · Zbl 0696.49002 · doi:10.1137/1.9781611971309 |
| [10] | Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS/SIAM Series on Optimization, vol. 8. SIAM, Philadelphia (2009) · Zbl 1163.49001 · doi:10.1137/1.9780898718768 |
| [11] | Custódio, A.L., Dennis, J.E. Jr., Vicente, L.N.: Using simplex gradients of nonsmooth functions in direct search methods. IMA J. Numer. Anal. 28(4), 770-784 (2008) · Zbl 1156.65059 · doi:10.1093/imanum/drn045 |
| [12] | Custódio, A.L., Vicente, L.N.: Using sampling and simplex derivatives in pattern search methods. SIAM J. Optim. 18(2), 537-555 (2007) · Zbl 1144.65039 · doi:10.1137/050646706 |
| [13] | Dennis, J.E. Jr., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Classics in Applied Mathematics. SIAM, Philadelphia (1996) · Zbl 0847.65038 · doi:10.1137/1.9781611971200 |
| [14] | Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2, Ser. A), 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [15] | Duvigneau, R., Visonneau, M.: Hydrodynamic design using a derivative-free method. Struct. Multidiscip. Optim. 28, 195-205 (2004) · Zbl 1067.76589 · doi:10.1007/s00158-004-0414-z |
| [16] | Ermoliev, Y.M., Norkin, V.I., Wets, R.J.-B.: The minimization of semicontinuous functions: mollifier subgradients. SIAM J. Control Optim. 33, 149-167 (1995) · Zbl 0822.49016 · doi:10.1137/S0363012992238369 |
| [17] | Goldstein, A.A.: Optimization of Lipschitz continuous functions. Math. Program. 13(1), 14-22 (1977) · Zbl 0394.90088 · doi:10.1007/BF01584320 |
| [18] | Gupal, A.M.: A method for the minimization of almost differentiable functions. Kibernetika 1, 114-116 (1977) (in Russian); English translation in: Cybernetics, 13(2), 220-222 (1977) |
| [19] | 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 |
| [20] | Hare, W. L., Using derivative free optimization for constrained parameter selection in a home and community care forecasting model, 61-73 (2010) |
| [21] | Imae, J., Ohtsuki, N., Kikuchi, Y., Kobayashi, T.: A minimax control design for nonlinear systems based on genetic programming: Jung’s collective unconscious approach. Int. J. Syst. Sci. 35, 775-785 (2004) · Zbl 1081.93008 · doi:10.1080/00207720412331303705 |
| [22] | Kelley, C.T.: Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition. SIAM J. Optim. 10(1), 43-55 (1999) · Zbl 0962.65048 · doi:10.1137/S1052623497315203 |
| [23] | Kelley, C.T.: Iterative Methods for Optimization. Frontiers in Applied Mathematics, vol. 18. SIAM, Philadelphia (1999) · Zbl 0934.90082 · doi:10.1137/1.9781611970920 |
| [24] | 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 |
| [25] | Le Digabel, S.: Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37(4), 1-15 (2011) · Zbl 1365.65172 · doi:10.1145/1916461.1916468 |
| [26] | Liuzzi, G., Lucidi, S., Sciandrone, M.: A derivative-free algorithm for linearly constrained finite minimax problems. SIAM J. Optim. 16(4), 1054-1075 (2006) · Zbl 1131.90074 · doi:10.1137/040615821 |
| [27] | Lukšan, L., Vlček, J.: Test Problems for Nonsmooth Unconstrained and Linearly Constrained Optimization. Technical report (February 2000) |
| [28] | Madsen, K.: Minimax solution of non-linear equations without calculating derivatives. Math. Program. Stud. 3, 110-126 (1975) · Zbl 0364.90085 · doi:10.1007/BFb0120701 |
| [29] | Marsden, A.L., Feinstein, J.A., Taylor, C.A.: A computational framework for derivative-free optimization of cardiovascular geometries. Comput. Methods Appl. Mech. Eng. 197(21-24), 1890-1905 (2008) · Zbl 1194.76296 · doi:10.1016/j.cma.2007.12.009 |
| [30] | Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, New York (1999) · Zbl 0930.65067 · doi:10.1007/b98874 |
| [31] | Di Pillo, G., Grippo, L., Lucidi, S.: A smooth method for the finite minimax problem. Math. Program., Ser. A 60(2), 187-214 (1993) · Zbl 0799.90106 · doi:10.1007/BF01580609 |
| [32] | Polak, E.: On the mathematical foundations of nondifferentiable optimization in engineering design. SIAM Rev. 29(1), 21-89 (1987) · doi:10.1137/1029002 |
| [33] | Polak, E., Royset, J.O., Womersley, R.S.: Algorithms with adaptive smoothing for finite minimax problems. J. Optim. Theory Appl. 119(3), 459-484 (2003) · Zbl 1061.90117 · doi:10.1023/B:JOTA.0000006685.60019.3e |
| [34] | Polyak, R.A.: Smooth optimization methods for minimax problems. SIAM J. Control Optim. 26(6), 1274-1286 (1988) · Zbl 0657.90075 · doi:10.1137/0326071 |
| [35] | Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317. Springer, Berlin (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3 |
| [36] | Stafford, R.: Random Points in an n-Dimensional Hypersphere. MATLAB File Exchange (2005). http://www.mathworks.com/matlabcentral/fileexchange/9443-random-points-in-an-n-dimensional-hypersphere · Zbl 1165.90021 |
| [37] | 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 |
| [38] | Wschebor, M.: Smoothed analysis of κ(A). J. Complex. 20(1), 97-107 (2004) · Zbl 1065.15029 · doi:10.1016/j.jco.2003.09.003 |
| [39] | Xu, S.: Smoothing method for minimax problems. Comput. Optim. Appl. 20(3), 267-279 (2001) · Zbl 1054.90087 · doi:10.1023/A:1011211101714 |
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.
