×

zbMATH — the first resource for mathematics

Whitney differentiability of optimal-value functions for bound-constrained convex programming problems. (English) Zbl 07051556
Summary: In the spirit of the Whitney Extension Theorem, consider a function on a compact subset of Euclidean space to be ‘Whitney-differentiable’ if it is a restriction of a continuously Fréchet-differentiable function with an open domain. Whitney-differentiable functions have been shown to have useful (yet possibly nonunique) derivatives and calculus properties even on the boundaries of their domains. This article shows that optimal-value functions for bound-constrained convex programmes with Whitney-differentiable objective functions are themselves Whitney-differentiable, even when the linear-independence constraint qualification is not satisfied. This result extends classic sensitivity results for convex programmes, and generalizes recent work. As an application, sufficient conditions are presented for generating continuously differentiable convex underestimators of nonconvex functions for use in methods for deterministic global optimization in the multivariate McCormick framework. In particular, the main result is applied to generate Whitney-differentiable convex underestimators for quotients of functions with known Whitney-differentiable relaxations.
MSC:
26B05 Continuity and differentiation questions
90C31 Sensitivity, stability, parametric optimization
90C25 Convex programming
Software:
amodMC; ANTIGONE; BARON; dcc; libMC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Whitney, H., Analytic extensions of differentiable functions defined in closed sets, Trans Amer Math Soc, 36, 63-89, (1934) · JFM 60.0217.01
[2] Khan, KA; Watson, HAJ; Barton, PI., Differentiable McCormick relaxations, J Global Optim, 67, 687-729, (2017) · Zbl 1365.49027
[3] Danskin, JM., The theory of Max–Min, with applications, J SIAM Appl Math, 14, 4, 641-664, (1966) · Zbl 0144.43301
[4] Hogan, W., Directional derivatives for extremal-value functions with applications to the completely convex case, Oper Res, 21, 1, 188-209, (1973) · Zbl 0278.90062
[5] Gauvin, J.; Dubeau, F., Differential properties of the marginal function in mathematical programming, Math Program Stud, 19, 101-119, (1982) · Zbl 0502.90072
[6] Bonnans, JF; Shapiro, A., Optimization problems with perturbations: a guided tour, SIAM Rev, 40, 2, 228-264, (1998) · Zbl 0915.49021
[7] Bonnans, JF; Shapiro, A., Perturbation analysis of optimization problems, (2000), New York: Springer, New York
[8] Fiacco, AV., Introduction to sensitivity and stability analysis in nonlinear programming, (1983), New York: Academic Press, New York
[9] Bertsekas, DP., Nonlinear programming, (1999), Nashua: Athena Scientific, Nashua
[10] Rockafellar, RT., Convex analysis, (1970), Princeton: Princeton University Press, Princeton
[11] Horst, R.; Tuy, H., Global optimization: deterministic approaches, (1993), Berlin: Springer-Verlag, Berlin
[12] Tsoukalas, A.; Mitsos, A., Multivariate McCormick relaxations, J Global Optim, 59, 633-662, (2014) · Zbl 1312.90068
[13] BARON 15.9: Global optimization of mixed-integer nonlinear programs. User’s Manual; 2015. Available at
[14] Sahinidis, NV., BARON: a general purpose global optimization software package, J Global Optim, 8, 201-205, (1996) · Zbl 0856.90104
[15] Misener, R.; Floudas, CA., ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J Global Optim, 59, 503-526, (2014) · Zbl 1301.90063
[16] Stuber, MD; Scott, JK; Barton, PI., Convex and concave relaxations of implicit functions, Optim Method Softw, 30, 3, 424-460, (2015) · Zbl 1327.65114
[17] Scott, JK; Barton, PI., Improved relaxations for the parametric solutions of ODEs using differential inequalities, J Global Optim, 57, 143-176, (2013) · Zbl 1273.49034
[18] Griewank, A.; Walther, A., Evaluating derivatives: principles and techniques of algorithmic differentiation, (2008), SIAM · Zbl 1159.65026
[19] Naumann, U., The art of differentiating computer programs: An introduction to algorithmic differentiation, (2012), Philadelphia: SIAM, Philadelphia · Zbl 1275.65015
[20] Cao, Y.; Li, S.; Petzold, L., Adjoint sensitivity analysis for differential-algebraic equations: the adjoint DAE system and its numerical solution, SIAM J Sci Comput, 24, 3, 1076-1089, (2003) · Zbl 1034.65066
[21] Mitsos, A.; Chachuat, B.; Barton, PI., McCormick-based relaxations of algorithms, SIAM J Optim, 20, 573-601, (2009) · Zbl 1192.65083
[22] Adjoint mode computation of subgradients for McCormick relaxations. In: Forth S, Hovland P, Phipps E, et al., editors. Recent advances in algorithmic differentiation. Berlin: Springer-Verlag; 2012. p. 103–113
[23] Hiriart-Urruty, JB; Lemaréchal, C., Convex analysis and minimization algorithms II: advanced theory and bundle methods, (1993), Berlin: Springer-Verlag, Berlin · Zbl 0795.49002
[24] Shor, NZ., Minimization methods for non-differentiable functions, (1985), Berlin: Springer-Verlag, Berlin
[25] Bard, JF., Practical bilevel optimization, (1998), New York: Springer, New York
[26] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[27] Hiriart-Urruty, JB; Lemaréchal, C., Convex analysis and minimization algorithms I: fundamentals, (1993), Berlin: Springer-Verlag, Berlin
[28] Moore, RE., Methods and applications of interval analysis, (1979), Philadelphia: SIAM, Philadelphia
[29] Neumaier, A., Interval methods for systems of equations, (1990), Cambridge: Cambridge University Press, Cambridge · Zbl 0706.15009
[30] On a Whitney extension problem for convex functions; 2015. Preprint, Available from:
[31] Filippov, AF., Differential equations with discontinuous righthand sides, (1988), Dordrecht: Kluwer Academic Publishers, Dordrecht
[32] Tawarmalani, M.; Sahinidis, NV., Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications, (2002), Dordrecht: Springer Science+Business Media, Dordrecht · Zbl 1031.90022
[33] McCormick, GP., Computability of global solutions to factorable nonconvex programs: part I - Convex underestimating problems, Math Program, 10, 147-175, (1976) · Zbl 0349.90100
[34] Zamora, JM; Grossmann, IE., A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits, Comput Chem Eng, 22, 3, 367-384, (1998)
[35] Najman, J.; Mitsos, A., Convergence analysis of multivariate McCormick relaxations, J Global Optim, 66, 4, 597-628, (2016) · Zbl 1394.90471
[36] Bompadre, A.; Mitsos, A., Convergence rate of McCormick relaxations, J Global Optim, 52, 1-28, (2012) · Zbl 1257.90077
[37] Du, K.; Kearfott, RB., The cluster problem in multivariate global optimization, J Global Optim, 5, 253-265, (1994) · Zbl 0824.90121
[38] Wechsung, A.; Schaber, SD; Barton, PI., The cluster problem revisited, J Global Optim, 58, 429-438, (2014) · Zbl 1297.49046
[39] Adjiman, CS; Dallwig, S.; Floudas, CA, A global optimization method, αBB, for general twice-differentiable constrained NLPs – I. Theoretical advances, Computers Chem Engng, 22, 1137-1158, (1998)
[40] Bertsimas, D.; Tsitsiklis, JN., Introduction to linear optimization, (1997), Belmont, MA: Athena Scientific and Dynamic Ideas, LLC, Belmont, MA
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.