×

Visualization of the \(\varepsilon \)-subdifferential of piecewise linear-quadratic functions. (English) Zbl 1406.90092

Summary: Computing explicitly the \(\varepsilon\)-subdifferential of a proper function amounts to computing the level set of a convex function namely the conjugate minus a linear function. The resulting theoretical algorithm is applied to the the class of (convex univariate) piecewise linear-quadratic functions for which existing numerical libraries allow practical computations. We visualize the results in a primal, dual, and subdifferential views through several numerical examples. We also provide a visualization of the Brøndsted-Rockafellar theorem.

MSC:

90C25 Convex programming
90C20 Quadratic programming

Software:

PLCP; Scilab; SQPlab; CCA
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aravkin, A., Burke, J., Pillonetto, G.: Sparse/robust estimation and Kalman smoothing with nonsmooth log-concave densities: modeling, computation, and theory. J. Mach. Learn. Res. 14, 2689-2728 (2013). http://jmlr.org/papers/v14/aravkin13a.html · Zbl 1318.62237
[2] Bonnans, J., Gilbert, J.C., Lemaréchal, C., Sagastizábal, C.A.: Numerical Optimization: Theoretical and Practical Aspects. Springer, Berlin (2006) · Zbl 1108.65060
[3] Borwein, J., Lewis, A.: Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, Berlin (2010)
[4] Brøndsted, A., Rockafellar, R.T.: On the subdifferentiability of convex functions. Proc. Am. Math. Soc. 16, 605-611 (1965). http://www.jstor.org/stable/2033889 · Zbl 0141.11801
[5] Correa, R; Hantoute, A; Jourani, A, Characterizations of convex approximate subdifferential calculus in Banach spaces, Trans. Am. Math. Soc., 368, 4831-4854, (2016) · Zbl 1336.49018
[6] Correa, R; Lemaréchal, C, Convergence of some algorithms for convex minimization, Math. Program., 62, 261-275, (1993) · Zbl 0805.90083
[7] Dembo, R., Anderson, R.: An efficient linesearch for convex piecewise-linear/quadratic functions. In: Advances in numerical partial differential equations and optimization (Mérida, 1989), pp. 1-8. SIAM, Philadelphia, PA (1991) · Zbl 1186.90089
[8] Oliveira, W; Sagastizábal, C, Level bundle methods for oracles with on-demand accuracy, Optim. Methods Softw., 29, 1180-1209, (2014) · Zbl 1306.90121
[9] Oliveira, W; Solodov, M, A doubly stabilized bundle method for nonsmooth convex optimization, Math. Program., 156, 125-159, (2016) · Zbl 1346.90675
[10] Frangioni, A, Generalized bundle methods, SIAM J. Optim., 13, 117-156, (2002) · Zbl 1041.90037
[11] Gardiner, B; Jakee, K; Lucet, Y, Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions, Comput. Optim. Appl., 58, 249-272, (2014) · Zbl 1320.90059
[12] Gardiner, B; Lucet, Y, Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis, Set Valued Var. Anal., 18, 467-482, (2010) · Zbl 1205.90222
[13] Gardiner, B; Lucet, Y, Computing the conjugate of convex piecewise linear-quadratic bivariate functions, Math. Program., 139, 161-184, (2013) · Zbl 1271.90057
[14] Hare, W; Planiden, C, Thresholds of prox-boundedness of PLQ functions, J. Convex Anal., 23, 1-28, (2016) · Zbl 1347.49022
[15] Hare, W; Sagastizábal, C, A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20, 2442-2473, (2010) · Zbl 1211.90183
[16] Hiriart-Urruty, J., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, vol. 306 of Grundlehren der mathematischen Wissenschaften. Springer, New York (1993) · Zbl 0795.49002
[17] Hiriart-Urruty, J; Moussaoui, M; Seeger, A; Volle, M, Subdifferential calculus without qualification conditions, using approximate subdifferentials: A survey, Nonlinear Anal. Theory Methods Appl., 24, 1727-1754, (1995) · Zbl 0846.49004
[18] Ioffe, AD, Approximate subdifferentials and applications. I. the finite-dimensional theory, Trans. Am. Math. Soc., 281, 389-416, (1984) · Zbl 0531.49014
[19] Jakee, K.M.K.: Computational Convex Analysis Using Parametric Quadratic Programming. Master’s thesis, University of British Columbia (2013). https://circle.ubc.ca/handle/2429/45182
[20] Kiwiel, K, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program., 46, 105-122, (1990) · Zbl 0697.90060
[21] Kiwiel, K, Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities, Math. Program., 69, 89-109, (1995) · Zbl 0857.90101
[22] Lemaréchal, C; Sagastizábal, C, Variable metric bundle methods: from conceptual to implementable forms, Math. Program., 76, 393-410, (1997) · Zbl 0872.90072
[23] Lucet, Y.: Computational convex analysis library, 1996-2016. http://atoms.scilab.org/toolboxes/CCA/ · Zbl 0852.90117
[24] Lucet, Y; Bauschke, H; Trienis, M, The piecewise linear-quadratic model for computational convex analysis, Comput. Optim. Appl., 43, 95-118, (2009) · Zbl 1186.90089
[25] Rantzer, A; Johansson, M, Piecewise linear quadratic optimal control, IEEE Trans. Automat. Control, 45, 629-637, (2000) · Zbl 0969.49016
[26] Rockafellar, R.: On the Essential Boundedness of Solutions to Problems in Piecewise Linear Quadratic Optimal Control. Analyse mathematique et applications. Gauthier villars, pp. 437-443 (1988) · Zbl 0671.49018
[27] Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (2015) · Zbl 0193.18401
[28] Rockafellar, R., Wets, R.: A lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming. In: Stochastic Programming 84 Part II, pp. 63-93. Springer, Berlin (1986) · Zbl 0599.90090
[29] Rockafellar, R., Wets, R.: Variational Analysis, vol. 317. Springer, Berlin (2009) · Zbl 0888.49001
[30] Scilab:: Scilab. http://www.scilab.org/ (2015) · Zbl 1306.90121
[31] Trienis, M.: Computational Convex Analysis: From Continuous Deformation to Finite Convex Integration. Master thesis (2007) · Zbl 1205.90222
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.