×

Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions. (English) Zbl 1320.90059

Summary: Piecewise linear-quadratic (PLQ) functions are an important class of functions in convex analysis since the result of most convex operators applied to a PLQ function is a PLQ function. We modify a recent algorithm for computing the convex (Legendre-Fenchel) conjugate of convex PLQ functions of two variables, to compute its partial conjugate i.e. the conjugate with respect to one of the variables. The structure of the original algorithm is preserved including its time complexity (linear time with some approximation and log-linear time without approximation). Applying twice the partial conjugate (and a variable switching operator) recovers the full conjugate. We present our partial conjugate algorithm, which is more flexible and simpler than the original full conjugate algorithm. We emphasize the difference with the full conjugate algorithm and illustrate results by computing partial conjugates, partial Moreau envelopes, and partial proximal averages.

MSC:

90C25 Convex programming

Software:

na24; CGAL; CCA ; Scilab; na13
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Alfeld, P.; Schumaker, L.L., Smooth macro-elements based on powell-sabin triangle splits, Adv. Comput. Math., 16, 29-46, (2002) · Zbl 0993.65124
[2] Bauschke, H.H.; Goebel, R.; Lucet, Y.; Wang, X., The proximal average: basic theory, SIAM J. Optim., 19, 768-785, (2008) · Zbl 1172.26003
[3] Bauschke, H.H.; Lucet, Y.; Trienis, M., How to transform one convex function continuously into another, SIAM Rev., 50, 115-132, (2008) · Zbl 1145.90050
[4] Bauschke, H.H.; Lucet, Y.; Wang, X., Primal-dual symmetric intrinsic methods for finding antiderivatives of cyclically monotone operators, SIAM J. Control Optim., 46, 2031-2051, (2007) · Zbl 1189.47050
[5] Bauschke, H.H.; Moffat, S.M.; Wang, X.; Bauschke, H.H. (ed.); Burachik, R.S. (ed.); Combettes, P.L. (ed.); Elser, V. (ed.); Luke, D.R. (ed.); Wolkowicz, H. (ed.), Self-dual smooth approximations of convex functions via the proximal average, No. 49, 23-32, (2011), New York · Zbl 1250.26015
[6] Bauschke, H.H.; Wang, X.; Yao, L., Autoconjugate representers for linear monotone operators, Math. Program., 123, 5-24, (2010) · Zbl 1185.47050
[7] Brenier, Y.: Un algorithme rapide pour le calcul de transformées de Legendre-Fenchel discrètes. C. R. Acad. Sci. Paris, Sér. I, Math. 308, 587-589 (1989) · Zbl 0667.65006
[8] Cao, J.; Li, X.; Wang, G.; Qin, H., Surface reconstruction using bivariate simplex splines on Delaunay configurations, Tsinghua Univ, Beijing, P.R. China, Jun. 26-28, 2009
[9] CGAL: Computational geometry algorithms library. http://www.cgal.org · Zbl 1365.68441
[10] CGLAB a Scilab toolbox for geometry based on CGAL. http://cglab.gforge.inria.fr/ · Zbl 1078.47008
[11] Consortium, S.: Scilab (1994). http://www.scilab.org · Zbl 1224.41010
[12] Corrias, L., Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equations and conservation laws, SIAM J. Numer. Anal., 33, 1534-1558, (1996) · Zbl 0856.49023
[13] Dæhlen, M.; Lyche, T., Bivariate interpolation with quadratic box splines, Math. Comput., 51, 219-230, (1988) · Zbl 0648.41003
[14] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry, 3rd edn. Algorithms and Applications. Springer, Berlin (2008) · Zbl 1140.68069
[15] Dierckx, P.; Leemput, S.; Vermeire, T., Algorithms for surface Fitting using powell-sabin splines, IMA J. Numer. Anal., 12, 271-299, (1992) · Zbl 0774.65007
[16] Gardiner, B.; Lucet, Y., Numerical computation of Fitzpatrick functions, J. Convex Anal., 16, 779-790, (2009) · Zbl 1184.65028
[17] 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
[18] Gardiner, B.; Lucet, Y.; Bauschke, H.H. (ed.); Burachik, R.S. (ed.); Combettes, P.L. (ed.); Elser, V. (ed.); Luke, D.R. (ed.); Wolkowicz, H. (ed.), Graph-matrix calculus for computational convex analysis, No. 49, 243-259, (2011), New York · Zbl 1242.90163
[19] Gardiner, B., Lucet, Y.: Computing the conjugate of convex piecewise linear-quadratic bivariate functions. Math. Program. 1-24 (2013) · Zbl 1271.90057
[20] Goebel, R.: Convexity, convergence and feedback in optimal control. PhD thesis, University of Washington, Seattle (2000) · Zbl 1116.65027
[21] Goebel, R., Self-dual smoothing of convex and saddle functions, J. Convex Anal., 15, 179-190, (2008) · Zbl 1142.26010
[22] Hare, W., A proximal average for nonconvex functions: a proximal stability perspective, SIAM J. Optim., 20, 650-666, (2009) · Zbl 1206.26019
[23] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305-306. Springer, Berlin (1993). Vol I: Fundamentals, Vol II: Advanced theory and bundle methods
[24] Johnstone, J.; Koch, V.; Lucet, Y., Convexity of the proximal average, J. Optim. Theory Appl., 148, 107-124, (2011) · Zbl 1215.26010
[25] Lai, M.-J., Schumaker, L.L.: Spline Functions on Triangulations. Encyclopedia of Mathematics and Its Applications, vol. 110. Cambridge University Press, Cambridge (2007) · Zbl 1185.41001
[26] Lucet, Y., A fast computational algorithm for the Legendre-Fenchel transform, Comput. Optim. Appl., 6, 27-57, (1996) · Zbl 0852.90117
[27] Lucet, Y.: Computational convex analysis library, 1996-2011. https://people.ok.ubc.ca/ylucet/cca.html · Zbl 0852.90117
[28] Lucet, Y., Faster than the fast Legendre transform, the linear-time Legendre transform, Numer. Algorithms, 16, 171-185, (1997) · Zbl 0909.65037
[29] Lucet, Y., Fast Moreau envelope computation I: numerical algorithms, Numer. Algorithms, 43, 235-249, (2006) · Zbl 1116.65027
[30] Lucet, Y., What shape is your conjugate? A survey of computational convex analysis and its applications, SIAM Rev., 52, 505-542, (2010) · Zbl 1197.65072
[31] Lucet, Y.; Bauschke, H.H.; Trienis, M., The piecewise linear-quadratic model for computational convex analysis, Comput. Optim. Appl., 43, 95-118, (2009) · Zbl 1186.90089
[32] Manni, C.; Sablonnière, P., Quadratic spline quasi-interpolants on powell-sabin partitions, Adv. Comput. Math., 26, 283-304, (2007) · Zbl 1116.65008
[33] Moffat, S.M.: On the kernel average of n functions. Master’s thesis, Department of Mathematics, University of British Columbia (Dec 2009) · Zbl 0856.49023
[34] Noullez, A.; Vergassola, M., A fast Legendre transform algorithm and applications to the adhesion model, J. Sci. Comput., 9, 259-281, (1994) · Zbl 0823.76058
[35] Patrinos, P., Sarimveis, H.: Convex parametric piecewise quadratic optimization: theory, algorithms and control applications. Tech. rep., National Technical University of Athens, Greece (2010) · Zbl 1202.90207
[36] Patrinos, P.; Sarimveis, H., A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings, Automatica, 46, 1405-1418, (2010) · Zbl 1202.90207
[37] Patrinos, P.; Sarimveis, H., Convex parametric piecewise quadratic optimization: theory and algorithms, Automatica, 47, 1770-1777, (2011) · Zbl 1228.90121
[38] Penot, J.-P., The relevance of convex analysis for the study of monotonicity, Nonlinear Anal., 58, 855-871, (2004) · Zbl 1078.47008
[39] Powell, M.J.D.; Sabin, M.A., Piecewise quadratic approximations on triangles, ACM Trans. Math. Softw., 3, 316-325, (1977) · Zbl 0375.41010
[40] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[41] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001
[42] Sbibih, D.; Serghini, A.; Tijini, A., Polar forms and quadratic spline quasi-interpolants on powell-sabin partitions, Appl. Numer. Math., 59, 938-958, (2009) · Zbl 1167.65005
[43] Sbibih, D.; Serghini, A.; Tijini, A., Bivariate simplex spline quasi-interpolants, Numer. Math., 3, 97-118, (2010) · Zbl 1224.41010
[44] She, Z.-S.; Aurell, E.; Frisch, U., The inviscid Burgers equation with initial data of Brownian type, Commun. Math. Phys., 148, 623-641, (1992) · Zbl 0755.60104
[45] Sorokina, T.; Zeilfelder, F., Optimal quasi-interpolation by quadratic \(C\)\^{}{1}-splines on type-2 triangulations, 423-438, (2005), Brentwood · Zbl 1074.65015
[46] Speleers, H.; Dierckx, P.; Vandewalle, S., Quasi-hierarchical powell-sabin B-splines, Comput. Aided Geom. Des., 26, 174-191, (2009) · Zbl 1205.65056
[47] Wiley, D.F.; Childs, H.R.; Hamann, B.; Joy, K.I.; Max, N.L., Best quadratic spline approximation for hierarchical visualization, Switzerland
[48] Willemans, K.; Dierckx, P., Surface Fitting using convex powell-sabin splines, J. Comput. Appl. Math., 56, 263-282, (1994) · Zbl 0827.65017
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.