Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán Lớp lồi cho Hàm Đoạn Tuyến Tính-Bậc Hai trong Phân tích Lồi Tính Toán
Tóm tắt
Việc tính toán lớp lồi là một phép toán cơ bản trong phân tích không nhẵn, kết nối thế giới lồi với thế giới không lồi. Mặc dù có nhiều thuật toán hiệu quả để tính toán các phép biến đổi cơ bản trong phân tích lồi đã được đề xuất trong nhiều năm qua, nhưng chúng chỉ giới hạn ở các hàm lồi cho đến khi một thuật toán hiệu quả trở nên khả dụng để tính toán lớp lồi của một hàm đoạn tuyến tính-bậc hai (của một biến) một cách hiệu quả. Chúng tôi trình bày hai thuật toán như vậy, một cái dựa trên việc tính toán cực trị và đối ngẫu, dễ thực hiện nhưng có độ phức tạp thời gian bậc hai, và cái còn lại dựa trên tính toán trực tiếp, đòi hỏi nhiều công sức để thực hiện nhưng có độ phức tạp tối ưu (thời gian tuyến tính). Chúng tôi chứng minh độ phức tạp thời gian (và không gian) của chúng, và so sánh hiệu suất của chúng.
Từ khóa
#hàm lồi #phân tích không nhẵn #thuật toán lớp lồi #hàm đoạn tuyến tính-bậc hai #độ phức tạp thời gianTài liệu tham khảo
Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: basic theory. SIAM J. Optim. 19, 768–785 (2008)
Bauschke, H.H., Lucet, Y., Trienis, M.: How to transform one convex function continuously into another. SIAM Rev. 50, 115–132 (2008)
Bauschke, H.H., Wang, X.: The kernel average of two convex functions and its application to the extension and representation of monotone operators. Trans. Am. Math. Soc. 361, 5947–5965 (2009)
Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Taslakian, P.: Necklaces, convolutions, and X + Y. In: Algorithms—ESA 2006. Lecture Notes in Computer Science, vol. 4168, pp. 160–171. Springer, Berlin (2006)
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)
Corrias, L.: Fast Legendre–Fenchel transform and applications to Hamilton–Jacobi equations and conservation laws. SIAM J. Numer. Anal. 33, 1534–1558 (1996)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Algorithms and applications. In: Computational Geometry, 3rd edn. Springer, Berlin (2008)
Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATC Monographs on Theoretical Computer Science. Springer (1987)
Felzenszwalb, P.F., Huttenlocher, D.P.: Distance Transforms of Sampled Functions. Tech. Rep. TR2004-1963, Cornell Computing and Information Science (2004)
Gardiner, B., Lucet, Y.: Graph-Matrix Calculus for Computational Convex Analysis. Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer Verlag series Optimization and Its Application (2010, in press)
Hare, W.: A proximal average for nonconvex functions: a proximal stability perspective. SIAM J. Optim. 20, 650–666 (2009)
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex analysis and minimization algorithms. In: Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vols. 305–306. Springer, Berlin (1993); Vol I: Fundamentals. Vol II: Advanced Theory and Bundle Methods
Hiriart-Urruty, J.-B., Lucet, Y.: Parametric computation of the Legendre–Fenchel conjugate. J. Convex Anal. 14, 657–666 (2007)
Koch, V., Johnstone, J., Lucet, Y.: Convexity of the proximal average. J. Optim. Theory Appl. (2010, in press)
Lachand-Robert, T., Oudet, É.: Minimizing within convex bodies using a convex hull method. SIAM J. Optim. 16, 368–379 (2005, electronic)
Laraki, R., Lasserre, J.B.: Computing uniform convex approximations for convex envelopes and convex hulls. J. Convex Anal. 15, 635–654 (2008)
Lucet, Y.: A fast computational algorithm for the Legendre–Fenchel transform. Comput. Optim. Appl. 6, 27–57 (1996)
Lucet, Y.: Faster than the fast Legendre transform. The linear-time Legendre transform. Numer. Algorithms 16, 171–185 (1997)
Lucet, Y.: A linear Euclidean distance transform algorithm based on the linear-time Legendre transform. In: Proceedings of the Second Canadian Conference on Computer and Robot Vision (CRV 2005), pp. 262–267, Victoria BC. IEEE Computer Society Press (2005)
Lucet, Y.: Fast Moreau envelope computation I: numerical algorithms. Numer. Algorithms 43, 235–249 (2006)
Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM J. Optim. 20, 216–250 (2009)
Lucet, Y., Bauschke, H.H., Trienis, M.: The piecewise linear-quadratic model for computational convex analysis. Comput. Optim. Appl. 43, 95–118 (2009)
Moreau, J.-J.: Proximité et dualité dans un espace Hilbertien. Bull. Soc. Math. Fr. 93, 273–299 (1965)
Noullez, A., Vergassola, M.: A fast Legendre transform algorithm and applications to the adhesion model. J. Sci. Comput. 9, 259–281 (1994)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
She, Z.-S., Aurell, E., Frisch, U.: The inviscid Burgers equation with initial data of Brownian type. Commun. Math. Phys. 148, 623–641 (1992)
Trienis, M.: Computational Convex Analysis: From Continuous Deformation to Finite Convex Integration. Master’s Thesis, University of British Columbia (2007)