×

Algorithmic construction of the subdifferential from directional derivatives. (English) Zbl 1403.52009

Let \(f: \mathbb{R}^n\to\mathbb{R}\) be a nonsmooth function with regular subdifferential \[ \partial f(x^0)= \{v\in\mathbb{R}^n: f(x)\geq f(x^0)+ v^T(x- x^0)+ o\| x-x^0\|\}. \] If \(f\) is convex then this subdifferential is equivalent to the classical subdifferential. If \(f\) is the maximum of a finite number of smooth functions then this subdifferential is a polyhedral set. The last case is the focus of the paper. Based on the relation \[ \partial f(x^0)= \{v\in\mathbb{R}^n: v^T d\leq df(x^0; d)\,\forall d\in\mathbb{R}^n\} \] the authors provide an algorithm to reconstruct such polyhedral subdifferentials by the computation of suitable values of the associated directional derivative \(df(x^0;d)\). In any step, a new direction is created to enlarge a polyhedral inner approximation (by adding further vertices) and to decrease an outer polyhedral approximation (by intersection with the associated half space). It is shown that the algorithm terminates after a finite number of steps.
In case of \(\mathbb{R}^2\) the algorithm needs about \(3n_v\) directional derivative evaluations (where \(n\) is the number of vertices of the subdifferential). In case of \(\mathbb{R}^n\) (with \(n_v\leq 3)\), the call of directional derivatives is smaller than \(5n\).

MSC:

52B12 Special polytopes (linear programming, centrally symmetric, etc.)
65K15 Numerical methods for variational inequalities and related problems
49M37 Numerical methods based on nonlinear programming
49J53 Set-valued and variational analysis
90C30 Nonlinear programming

Software:

DGM
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Audet, C; Dennis, JEJr, Analysis of generalized pattern searches, SIAM J. Optim., 13, 889-903, (2003) · Zbl 1053.90118 · doi:10.1137/S1052623400378742
[2] Audet, C; Dennis, JEJr, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2006) · Zbl 1112.90078 · doi:10.1137/040603371
[3] Bagirov, A.M.: Continuous subdifferential approximations and their applications, vol. 115. Optimization and related topics, 2 (2003) · Zbl 0664.52002
[4] Bagirov, AM; Karasözen, B; Sezer, M, Discrete gradient method: derivative-free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 317-334, (2008) · Zbl 1165.90021 · doi:10.1007/s10957-007-9335-5
[5] Bernstein, HJ, Determining the shape of a convex n-sided polygon by using 2n + k tactile probes, Inf. Process. Lett., 22, 255-260, (1986) · Zbl 0592.68085 · doi:10.1016/0020-0190(86)90103-1
[6] Cole, R; Yap, CK, Shape from probing, Journal of Algorithms, 8, 19-38, (1987) · Zbl 0643.68180 · doi:10.1016/0196-6774(87)90025-3
[7] Demyanov, V.F., Rubinov, A.M.: Constructive Nonsmooth Analysis, vol. 7. Verlag Peter Lang, Frankfurt (1995) · Zbl 0887.49014
[8] Dobkin, D., Edelsbrunner, H., Yap, C.K.: Probing convex polytopes. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, pp. 424-432. ACM, New York (1986)
[9] Finkel, D.E., Kelley, C.T.: Convergence analysis of the DIRECT algorithm. Technical Report. CRSC-TR04-28 Center for Research in Scientific Computation (2004)
[10] Finkel, DE; Kelley, CT, Convergence analysis of sampling methods for perturbed Lipschitz functions, Pacific Journal of Optimization, 5, 339-350, (2009) · Zbl 1181.65084
[11] Hare, W; Nutini, J, A derivative-free approximate gradient sampling algorithm for finite minimax problems, Comput. Optim. Appl., 56, 1-38, (2013) · Zbl 1300.90064 · doi:10.1007/s10589-013-9547-6
[12] Hare, W., Macklem, M.: Derivative-free optimization methods for finite minimax problems. Optimization Methods and Software, iFirst, 1-13 (2011) · Zbl 1270.90099
[13] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993). Advanced theory and bundle methods · Zbl 0795.49001
[14] Imiya, A; Sato, K; Brimkov, EV (ed.); Barneva, PR (ed.), Shape from silhouettes in discrete space, 323-358, (2012), Netherlands, Dordrecht · Zbl 1251.68300 · doi:10.1007/978-94-007-4174-4_11
[15] Kiwiel, KC, A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim., 20, 1983-1994, (2010) · Zbl 1205.90230 · doi:10.1137/090748408
[16] Lindenbaum, M; Bruckstein, A, Parallel strategies for geometric probing, Journal of Algorithms, 13, 320-349, (1992) · Zbl 0744.52002 · doi:10.1016/0196-6774(92)90022-5
[17] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, volume 317 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Berlin (1998) · Zbl 0888.49001
[18] Romanik, K.: Geometric probing and testing - a survey. Technical Report 95-42, DIMACS Technical Report (1995) · Zbl 1165.90021
[19] Shuo-Yen, RL, Reconstruction of polygons from projections, Inf. Process. Lett., 28, 235-240, (1988) · Zbl 0664.52002 · doi:10.1016/0020-0190(88)90196-2
[20] Skiena, SS, Problems in geometric probing, Algorithmica, 4, 599-605, (1989) · doi:10.1007/BF01553911
[21] Tiwary, H.R.: Complexity of Some Polyhedral Enumeration Problems. PhD Thesis. Universität des Saarlandes, Germany (2008)
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.