×

Constructing a subgradient from directional derivatives for functions of two variables. (English) Zbl 07875621

Summary: For any scalar-valued bivariate function that is locally Lipschitz continuous and directionally differentiable, it is shown that a subgradient may always be constructed from the function’s directional derivatives in the four compass directions, arranged in a so-called “compass difference”. When the original function is nonconvex, the obtained subgradient is an element of Clarke’s generalized gradient, but the result appears to be novel even for convex functions. The function is not required to be represented in any particular form, and no further assumptions are required, though the result is strengthened when the function is additionally L-smooth in the sense of Nesterov. For certain optimal-value functions and certain parametric solutions of differential equation systems, these new results appear to provide the only known way to compute a subgradient. These results also imply that centered finite differences will converge to a subgradient for bivariate nonsmooth functions. As a dual result, we find that any compact convex set in two dimensions contains the midpoint of its interval hull. Examples are included for illustration, and it is demonstrated that these results do not extend directly to functions of more than two variables or sets in higher dimensions.

MSC:

49J52 Nonsmooth analysis
26B05 Continuity and differentiation questions

Software:

PNEW

References:

[1] A. Griewank, Automatic directional di erentiation of nonsmooth composite functions, in Recent Developments in Optimization, French-German Conference on Optimization, Springer, Dijon, .
[2] A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Di erentiation, Other Titles in Applied Mathematics, SIAM, Philadelphia, PA, nd edition, .
[3] P. Hartman, Ordinary Di erential Equations ( nd ed.), Classics in Applied Mathematics, SIAM, .
[4] J. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I: Funda-mentals, A Series of Comprehensive Studies in Mathematics, Springer-Verlag, Berlin, .
[5] J. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms II: Ad-vanced Theory and Bundle Methods, A Series of Comprehensive Studies in Mathematics, Springer-Verlag, Berlin, .
[6] W. Hogan, Directional derivatives for extremal-value functions with applications to the completely convex case, Oper. Res. ( ), -. · Zbl 0278.90062
[7] C. Imbert, Support functions of the Clarke generalized Jacobian and of its plenary hull, Nonlinear Anal.-Theor. ( ), -. · Zbl 1009.49017
[8] K. A. Khan, Sensitivity analysis for nonsmooth dynamic systems, PhD thesis, Massachusetts Insti-tute of Technology, .
[9] K. A. Khan, Relating lexicographic smoothness and directed subdi erentiability, Set-Valued Var. Anal. ( ), -.
[10] K. A. Khan, Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit funcitons, Optim. Method Softw. ( ), -.
[11] K. A. Khan, Subtangent-based approaches for dynamic set propagation, in IEEE Conference on Decision and Control, IEEE, Miami Beach, .
[12] K. A. Khan and P. I. Barton, Generalized derivatives for solutions of parametric ordinary dif-ferential equations with non-di erentiable right-hand sides, J. Optimiz. Theory App. ( ), -.
[13] K. A. Khan and P. I. Barton, A vector forward mode of automatic di erentiation for generalized derivative evaluation, Optim. Method Softw. ( ), -.
[14] K. A. Khan and P. I. Barton, Generalized derivatives for hybrid systems, IEEE T. Automat. Contr. ( ), -. · Zbl 1370.93097
[15] K. C. Kiwiel, Methods of Descent for Nondi erentiable Optimization, Lecture Notes in Mathematics, Springer-Verlag, Berlin, .
[16] A. Y. Kruger, On Fréchet subdi erentials, J. Math. Sci. ( ), -.
[17] C. Lemaréchal, J. J. Strodiot, and A. Bihain, On a bundle algorithm for nonsmooth optimization, in Nonlinear Programming , O. L. Mangasarian, R. R. Meyer, and S. M. Robinson (eds.), Academic Press, New York, NY, . · Zbl 0533.49023
[18] L. Lukšan and J. Vlček, A bundle-Newton method for nonsmooth unconstrained minimization, Math. Program. ( ), -. · Zbl 0920.90132
[19] A. Khan and Y. Yuan Constructing a subgradient from directional derivatives
[20] M. M. Mäkelä, Survey of bundle methods for nonsmooth optimization, Optim. Method. Softw. ( ), -. · Zbl 1050.90027
[21] B. S. Mordukhovich, Variational analysis and generalized di erentiation I: Basic theory, Springer, Berlin, .
[22] Y. Nesterov, Lexicographic di erentiation of nonsmooth functions, Math. Program. B ( ), -.
[23] A. Neumaier, Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, . · Zbl 1152.65054
[24] J. S. Pang and D. E. Stewart, Solution dependence on initial conditions in di erential variational inequalities, Math. Program. B ( ), -.
[25] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res. ( ), -. · Zbl 0776.65037
[26] L. Qi and J. Sun, A nonsmooth version of Newton’s method, Math. Program. ( ), -. · Zbl 0780.90090
[27] R. T. Rockafellar and R. J. B. Wets, Variational Analysis, A Series of Comprehensive Studies in Mathematics, Springer, Berlin, .
[28] G. Rote, The convergence rate of the sandwich algorithm for approximating convex functions, Computing ( ), -.
[29] S. Scholtes, Introduction to Piecewise Di erentiable Equations, SpringerBriefs in Optimization, Springer, New York, NY, .
[30] N. Z. Shor, Minimization Methods for Non-Di erentiable Functions, Springer Series in Computa-tional Mathematics, Springer-Verlag, Berlin, .
[31] S. S. Skiena, Problems in geometric probing, Algorithmica ( ), -.
[32] P. G. Stechlinski and P. I. Barton, Generalized derivatives of di erential-algebraic equations, J. Optim. Theory App. ( ), -.
[33] P. G. Stechlinski, K. A. Khan, and P. I. Barton, Generalized sensitivity analysis of nonlinear pro-grams, SIAM J. Optim. ( ), -. · Zbl 1383.49024
[34] A. Tsoukalas and A. Mitsos, Multivariate McCormick relaxations, J. Glob. Optim. ( ), -. · Zbl 1312.90068
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.