On the Curse of Dimensionality in the Ritz Method

详细信息    查看全文

• 作者：Giorgio Gnecco
• 关键词：Ritz method ; Curse of dimensionality ; Infinite ; dimensional optimization ; Approximation schemes ; Extended Ritz method ; 90C06 ; 90C26 ; 90C48
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：168
• 期：2
• 页码：488-509
• 全文大小：557 KB
• 参考文献：1.Ritz, W.: Über eine neue Methode zur Lösung gewisser Variationsprobleme der mathematischen Physik. Journal für die Reine und Angewandte Mathematik 135, 1–61 (1909)MathSciNet
  2.Gelfand, I.M., Fomin, S.V.: Calculus of Variations. Prentice Hall, Englewood Cliffs, NJ (1963)
  3.Kůrková, V., Sanguineti, M.: Error estimates for approximate optimization by the extended Ritz method. SIAM J. Optim. 15, 461–487 (2005)CrossRef MATH
  4.Zoppoli, R., Sanguineti, M., Parisini, T.: Approximating networks and extended Ritz method for the solution of functional optimization problems. J. Optim. Theory Appl. 112, 403–440 (2002)CrossRef MathSciNet MATH
  5.Gnecco, G.: A comparison between fixed-basis and variable-basis schemes for function approximation and functional optimization. J. Appl. Math. 2012 (2012). Article ID, 806945
  6.Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)MATH
  7.Bosarge Jr, W.E., Johnson, O.G., McKnight, R.S., Timlake, W.P.: The Ritz-Galerkin procedure for nonlinear control problems. SIAM J. Numer. Anal. 10, 94–111 (1973)
  8.Daniel, J.W.: The Ritz-Galerkin method for abstract optimal control problems. SIAM J. Control 11, 53–63 (1973)CrossRef MathSciNet MATH
  9.Felgenhauer, U.: On Ritz type discretizations for optimal control problems. In: Proceedings of the 18th IFIP-ICZ Conference, pp. 91–99. Chapman-Hall (1999)
  10.Hager, W.W.: The Ritz-Trefftz method for state and control constrained optimal control problems. SIAM J. Numer. Anal. 12, 854–867 (1975)CrossRef MathSciNet MATH
  11.Sirisena, H.R., Chou, F.S.: Convergence of the control parameterization Ritz method for nonlinear optimal control problems. J. Optim. Theory Appl. 29, 369–382 (1979)CrossRef MathSciNet MATH
  12.Alt, W.: On the approximation of infinite optimization problems with an application to optimal control problems. Appl. Math. Optim. 12, 15–27 (1984)CrossRef MathSciNet MATH
  13.Tjuhtin, V.B.: An error estimate for approximate solutions in one-sided variational problems. Vestnik Leningr. Univ. Math. 14, 247–254 (1982)
  14.Zoppoli, R., Parisini, T.: Learning techniques and neural networks for the solution of N-stage nonlinear nonquadratic optimal control problems. In: Isidori, A., Tarn, T.J. (eds.) Systems, Models and Feedback: Theory and Applications, pp. 193–210. Birkhäuser, Boston (1992)CrossRef
  15.Kainen, P., Kůrková, V., Sanguineti, M.: Minimization of error functionals over variable-basis functions. SIAM J. Optim. 14, 732–742 (2003)CrossRef MathSciNet MATH
  16.Giulini, S., Sanguineti, M.: Approximation schemes for functional optimization problems. J. Optim. Theory Appl. 140, 33–54 (2009)CrossRef MathSciNet MATH
  17.Gnecco, G., Sanguineti, M.: Estimates of variation with respect to a set and applications to optimization problems. J. Optim. Theory Appl. 145, 53–75 (2010)CrossRef MathSciNet MATH
  18.Zolezzi, T.: Condition numbers and Ritz type methods in unconstrained optimization. Control Cybern. 36, 811–822 (2007)MathSciNet MATH
  19.Alessandri, A., Cervellera, C., Sanguineti, M.: Functional optimal estimation problems and their solution by nonlinear approximation schemes. J. Optim. Theory Appl. 134, 445–466 (2007)CrossRef MathSciNet MATH
  20.Gnecco, G., Sanguineti, M.: Suboptimal solutions to dynamic optimization problems via approximations of the policy functions. J. Optim. Theory Appl. 146, 764–794 (2010)CrossRef MathSciNet MATH
  21.Gnecco, G., Sanguineti, M., Gaggero, M.: Suboptimal solutions to team optimization problems with stochastic information structure. SIAM J. Optim. 22, 212–243 (2012)CrossRef MathSciNet MATH
  22.Kainen, P., Kůrková, V., Sanguineti, M.: Dependence of computational models on input dimension: tractability of approximation and optimization tasks. IEEE Trans. Inf. Theory 58, 1203–1214 (2012)CrossRef
  23.Apostol, T.M.: Calculus, vol. 2. Wiley, Hoboken (1968)
  24.Parlett, B.N.: The Symmetric Eigenvalue Problem. SIAM, Philadelphia (1998)CrossRef MATH
  25.Luenberger, D.: Optimization by Vector Space Methods. Wiley, Hoboken (1969)MATH
  26.Birman, M.S., Solomjak, M.Z.: Spectral Theory of Self-Adjoint Operators in Hilbert Space. D. Reidel Publishing Company, Dordrecht (1987)MATH
  27.Rudin, W.: Real and Complex Analysis. McGraw-Hill, Singapore (1987)MATH
  28.Knuth, D.E.: Big omicron and big omega and big theta. SIGACT News 8, 18–24 (1976)CrossRef
  29.Chatelin, F.: Spectral Approximation of Linear Operators. Classics in Applied Mathematics. SIAM, Philadelphia (2011)CrossRef
  30.Stein, E.M., Weiss, G.: Introduction to Fourier Analysis on Euclidean Spaces. Princeton University Press, Princeton (1971)MATH
  31.Pinkus, A.: \(n\) -Widths in Approximation Theory. Springer, Berlin (1985)
  32.DeVore, R.A., Sharpley, R.C., Riemenschneider, S.D.: \(n\) spaces. Anniversary Volume on Approximation Theory and Functional Analysis. ISNM 65: International Series of Numerical Mathematics, vol. 65, pp. 213–222. Springer, Basel (1984)
  33.Barron, A.R.: Universal approximation bounds for superpositions of a sigmoidal function. IEEE Trans. Inf. Theory 39, 930–945 (1993)CrossRef MathSciNet MATH
  34.Naylor, A.W., Sell, G.R.: Linear Operator Theory in Engineering and Science. Springer, New York (2000)MATH
  
• 作者单位：Giorgio Gnecco (1)
  
  1. IMT Institute for Advanced Studies, Piazza S. Francesco 19, 55100, Lucca, Italy
  
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878

文摘

It is shown that the classical Ritz method of the calculus of variations suffers from the “curse of dimensionality,” i.e., an exponential growth, as a function of the number of variables, of the dimension a linear subspace needs in order to achieve a desired relative improvement in the accuracy of approximation of the optimal solution value. The proof is constructive and is obtained by exhibiting a family of infinite-dimensional optimization problems for which this happens, namely those with quadratic functional and spherical constraint. The results provide a theoretical motivation for the search of alternative solution methods, such as the so-called “extended Ritz method,” to deal with the curse of dimensionality. Keywords Ritz method Curse of dimensionality Infinite-dimensional optimization Approximation schemes Extended Ritz method