{"entities":{"Q2492698":{"pageid":2503441,"ns":120,"title":"Item:Q2492698","lastrevid":78763487,"modified":"2026-05-06T12:23:02Z","type":"item","id":"Q2492698","labels":{"en":{"language":"en","value":"An optimal adaptive algorithm for the approximation of concave functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5032442"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$2D7D8D60-BBB6-4629-8D46-9BE2BFF4EC21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca31a78491667a0f7af7b01a9a77a6d5a5b9467f","datavalue":{"value":{"text":"An optimal adaptive algorithm for the approximation of concave functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2492698$25F443DB-71D6-4BF3-B6C3-5870FADCBF15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"23b4c0aa7daccf7094961879ca8621197ac27815","datavalue":{"value":"1132.90018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$2AE7CA02-CC59-4885-8F3B-C1131221146A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$B88D139E-5D44-43C7-8031-9CE2AEAD4758","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$039CA5DE-EDC4-4500-ABA3-9D005EC4C603","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f91943cbc48cbb876e3cad2360ffd8493e93ef75","datavalue":{"value":{"time":"+2006-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2492698$3213E2E0-A4AE-4FB4-A0A6-6B9ACE391969","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2cb839c9046f80cc93226db431d8efc3d2668f80","datavalue":{"value":"Consider a proper concave function \\(f:[ 0,1] \\to\\mathbb R\\), normalized so that \\(f( 0) =0\\) and \\(f( 1) =1.\\) \\ Denote by \\(f^{\\prime }( \\overline{x}) \\) an arbitrary supergradient \\(\\xi \\) of \\(f\\) at \\(\\overline{x},\\) i.e., a supergradient \\(\\xi \\) satisfying:   \\[  f( x) \\leq f( \\overline{x}) +\\xi ( x-\\overline{x} ) \\text{ for all }x\\in [ 0,1]  \\]   Let \\(x_{1},\\dots .,x_{n}\\) denote a finite sequence of \\(n\\) distinct points of evaluation, called knots, in \\(( 0,1) \\) and \\(\\sigma \\) a permutation that reorders the knots and the two endpoints from left to right, i.e.,  \\[  0=x_{\\sigma ( 0) }<x_{\\sigma ( 1) }<\\dots <x_{\\sigma ( n) }<x_{\\sigma ( n+1) }=1  \\]  Denote the under and over approximations of \\(f\\) over the interval \\(( 0,1) ,\\) respectively, by   \\[ \\begin{aligned} L( t) &=\\min_{i=1,\\dots, n+1}\\left\\{ f( x_{\\sigma ( i-1) }) \\frac{( t-x_{\\sigma ( i) }) }{ x_{\\sigma ( i-1) }-x_{\\sigma ( i) }}+f( x_{\\sigma ( i) }) \\frac{( t-x_{\\sigma ( i-1) }) }{x_{\\sigma ( i) }-x_{\\sigma ( i-1) }}\\right\\}, \\\\ U( t) &=\\min_{i=0,\\dots, n+1}\\{ f( x_{i}) +f^{\\prime }( x_{i}) ( t-x_{i}) \\}. \\end{aligned} \\]   This yields the approximation error term \\(\\int_{0}^{1}( U( t) -L( t) ) \\,dt.\\) Using dynamic programming, the paper derives a procedure for minimizing the error term through a sequential procedure of knot selection which is proved to be optimal in the sense that it minimizes the error term in the worst case. The procedure is a deterministic adaptive algorithm in the sense that the selection of the current knot is dependent on the locations of the previous knots, i.e., the choice of \\(x_{i}\\) may depend upon the previous information \\(x_{1},f( x_{1}) ,f^{\\prime }( x_{1}) ,\\dots ,x_{i-1},f( x_{i-1}) ,f^{\\prime }( x_{i-1}) .\\)   The analysis seeks to improve upon previous works by \\(( 1) \\) obtaining both the optimal convergence rate and optimal selection rules for each \\(n\\) and \\(( 2) \\) getting parameter free results, i.e., no a priori information about the function to be approximated is required.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492698$75745D37-975D-4446-91F6-A9E364EEFD56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$873BDA55-7EE0-4CF8-98B7-5EA28EA0BB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"adff925b384f770cc2b5b9332648f5ec07fcc1fa","datavalue":{"value":"41A29","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$114266D6-F586-4191-A305-141889C9DEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2afc8b14470e661c10725547661d94fa1583b792","datavalue":{"value":"65D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$4CFE4976-8824-4A6E-BFB6-E1B6B9734206","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28600235523b82beae247cdab33f31a1386fe0af","datavalue":{"value":"5032442","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$F9A0B765-631B-4EDB-99A5-A1743339D3E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc5f023690b50b23665cef84fb881f798fc4c448","datavalue":{"value":"concave functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492698$C445468A-B2C3-4612-8988-5841427D8D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0dfeaa15526caecb2a6845352ecfc54328a30cd","datavalue":{"value":"piecewise linear","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492698$FBF10F9F-E0B5-4210-BA31-24342BC6C052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6cc263effb66630f07afdafe72334605befee28","datavalue":{"value":"adaptive algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492698$8DF5D867-CF38-4F13-9404-D8BE7A770975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492698$351DA96D-47B1-4640-9C12-C530658EE71B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$34B1D549-22E7-4AEA-B1ED-7A1194F63FA0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d96b294a1dfe6d3944e60f9452b4ff4dc9d9241f","datavalue":{"value":"https://doi.org/10.1007/s10107-003-0502-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q2492698$608A9BF6-77F8-43E6-8AC6-0AFFBA43FECC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4b4ed08397b33c39c02a5c6225a278990f985294","datavalue":{"value":"W2051890519","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$51956892-D680-4AC2-91AD-716EC4946F1C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a308e30505dd380998190c7f81f45679fe7a55a5","datavalue":{"value":{"entity-type":"item","numeric-id":3292915,"id":"Q3292915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$7B1C8897-FBB2-4AF5-904D-5BABFE982F27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5570a2e324328cbc82c26584eab9190f01025c45","datavalue":{"value":{"entity-type":"item","numeric-id":3987782,"id":"Q3987782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$AEA37372-5B1E-4882-BF63-D588122E5863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da354e0015d3d9a0c0db52d6be037bcd8df5f7e0","datavalue":{"value":{"entity-type":"item","numeric-id":1825606,"id":"Q1825606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$8A66816F-3BDA-420E-8721-A62EDFABB34E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e9d49de8efb6cbc44cf9b5e5cb8aac5e796bc61","datavalue":{"value":{"entity-type":"item","numeric-id":4353544,"id":"Q4353544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$99F911BB-EAEB-4C47-A184-EAAB33BFCC82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de2910677d1d9f82ffd0e8e579264f350a9f00d4","datavalue":{"value":{"entity-type":"item","numeric-id":4284671,"id":"Q4284671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$19F437CD-4218-4F54-8CAB-56DEDEE24BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"908bdd72007ca5bf0d089601baaa34270de9eed6","datavalue":{"value":{"entity-type":"item","numeric-id":1195962,"id":"Q1195962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$9431E60B-FE7C-45A7-B2E5-353D3FBABAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81b427356501f3d8cab66a8d838e32d77b8eefc5","datavalue":{"value":{"entity-type":"item","numeric-id":3345662,"id":"Q3345662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$795DD7E1-C928-42E9-86EC-F4E65EEDBBDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6624ad2a16c42deba1a0f49c54ead1a87d265ce5","datavalue":{"value":{"entity-type":"item","numeric-id":1305176,"id":"Q1305176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$34F76BEC-2EFD-4E1F-90FF-E098F4995179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9223dcd2c25d9d4465c5e2c79882867fe1d64856","datavalue":{"value":{"entity-type":"item","numeric-id":1278603,"id":"Q1278603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492698$18293A75-DC53-4773-AA0C-A78EBBD32766","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65f38086114104308e5e330c2a00596091939fa3","datavalue":{"value":"10.1007/S10107-003-0502-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492698$05E9D14D-FA2B-416D-AA1C-ADD45CA10F5F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7a5280ea7a269911ed850be9b41a9da75e866a8","datavalue":{"value":{"entity-type":"item","numeric-id":2247899,"id":"Q2247899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dae159323d7e1c9b1c3e1f81df68b1a886f9693","datavalue":{"value":{"amount":"+0.8363379836082458","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2492698$95D6E425-D251-4F6E-8846-812B3584AF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"691465f0ea4910f8531629958ad2d2c8c2f94669","datavalue":{"value":{"entity-type":"item","numeric-id":1870009,"id":"Q1870009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da753c057bfc64176fef7236e3834de92720ccb3","datavalue":{"value":{"amount":"+0.7675585746765137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2492698$CD55B6FB-B66F-4FE0-B032-C8A65BD4CB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73cd176499fdf56d7be05c44a1862f160147afd5","datavalue":{"value":{"entity-type":"item","numeric-id":3345662,"id":"Q3345662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c18e2027d1be9aba3266e6eb43c06c16918eaa42","datavalue":{"value":{"amount":"+0.7548186182975769","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2492698$51F28C16-074F-4C5D-A16B-E47DC7659C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51510b71fe43d890f53fce1e127187de8ffbc245","datavalue":{"value":{"entity-type":"item","numeric-id":3987782,"id":"Q3987782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dfcc8f3ebeab9e0f60e674776deb5c8ba95c325","datavalue":{"value":{"amount":"+0.7492837905883789","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2492698$BBF5332E-625E-4B02-99E8-325F8EA4779B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd6816a6c35a53c5290d5c3157cb95b9464b1086","datavalue":{"value":{"entity-type":"item","numeric-id":3032094,"id":"Q3032094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72517437b2c66372e0e9cc38dab6dbcb051601d9","datavalue":{"value":{"amount":"+0.7469361424446106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2492698$AF383888-206E-40CA-8389-952676337FA3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal adaptive algorithm for the approximation of concave functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_adaptive_algorithm_for_the_approximation_of_concave_functions"}}}}}