{"entities":{"Q1974569":{"pageid":1985311,"ns":120,"title":"Item:Q1974569","lastrevid":46919553,"modified":"2025-12-25T20:47:51Z","type":"item","id":"Q1974569","labels":{"en":{"language":"en","value":"Complexity analysis for certain convex programming problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1439897"}},"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":"Q1974569$736B106F-3DBF-4EF6-89DA-A37CA53852AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f966c467407d8dfe0422a7925081255a8aed8eb9","datavalue":{"value":{"text":"Complexity analysis for certain convex programming problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1974569$3FAEC108-2C7D-48B3-B3F5-CD0A0AE69F7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5709ae3d29dc0c1a230dbf3c4032fd4e2d7a1e07","datavalue":{"value":"0952.90033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974569$1B63BC75-E43E-48A5-9126-109C2DB9501D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"393fe4a0b9caa50a0811825df29506b1ec1f39cc","datavalue":{"value":{"entity-type":"item","numeric-id":1974568,"id":"Q1974568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$030ABE56-66C9-497C-B16E-A4DB13F318FA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$BB33FF1D-E786-4B53-A017-DEC34B5BBDBE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cc17136081e6b5d5fc40d3affb0beecbc4f23a8c","datavalue":{"value":{"time":"+2000-05-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1974569$1812FC12-7810-462A-B38D-6B7D0FB763E8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a95db6086d786bfc513a6f470f9cddfc888c02d","datavalue":{"value":"For the convex linear-constrained optimization problem  \\[ f(x)\\to \\min,\\quad\\text{s.t. }\\langle x,b_i\\rangle\\geq \\beta_i\\quad (i= 1,\\dots, p) \\]  in finite-dimensional spaces, the author provides a barrier method using the auxiliary function  \\[ f_t(x):= f(x)- t \\sum^p_{i=1} \\ln(\\langle x,b_i\\rangle- \\beta_i),\\quad t>0. \\]  In the theoretical part it is pointed out that (under weak assumptions) this function admits for any \\(t>0\\) an unique minimum point \\(\\xi_t\\) which varies smoothly with \\(t\\to 0\\) to the minimum point \\(\\xi_0\\) of the original problem. Obviously, these minimum points \\(\\xi_t\\) are zeros of \\(\\nabla f_t\\), i.e. they are solutions of the nonlinear equations \\(\\nabla f_t(x)= 0\\).   The presented algorithm bases on the classical Newton method. The author describes a suitable subdivision \\(1= t_0> t_1>\\cdots> t_M> 0\\) of the interval \\([0,1]\\) such that -- starting with a suitable point \\(x_0\\) (near to the zero \\(\\xi_{t_0}\\)) and a small positive number \\(\\varepsilon\\) -- one gets after \\(M\\) Newton steps according to  \\[ x_{i+ 1}:= x_i- [\\nabla^2 f_{t_{i+ 1}}(x_i)]^{- 1}\\nabla f_{t_{i+ 1}}(x_i) \\]  an approximative zero \\(x_M\\) of \\(\\nabla f_{t_M}\\) with associated exact zero \\(\\xi_{t_M}\\) which is an \\(\\varepsilon\\)-minimizer of the original problem.   The integer \\(M\\)-proportional to the quantity \\(\\sqrt p(1+\\delta)(|\\ln \\varepsilon|+ \\ln p)\\) (here \\(\\delta\\) is a generalized norm of the functions \\(f_t\\), \\(t\\in [0,1]\\), calculated by different derivatives) -- provides a measure for the complexity of the algorithm. Obviously this quantity is simpler using linear or quadratic objective functions since in this case it is \\(\\delta= 0\\).   The approach of the paper bases heavily on Smale's alpha-theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974569$85EEBE7D-E1CC-4E1C-8D9B-66BFEFECA3C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974569$B0CF4CB6-AE0E-4F59-AF99-3C65B12FA672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974569$1E7ED6BD-2237-44CE-8524-E7086E230C2C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e27e2eba18cedcbb06afcd90febc1120b26205b","datavalue":{"value":"1439897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974569$827DBA19-56CD-4C95-A9E2-2FF7DCF22ED7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6967e67113aaa139c1c0b5c2a96849f0ad345afa","datavalue":{"value":"convex programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974569$6CFE2E21-D5A3-459D-96BE-8AB7B5365ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a7094b8834573514a742d46216098470ab4ec8f","datavalue":{"value":"Smale's alpha-theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974569$D645E887-6765-4A41-8101-CF88710E9489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974569$10627529-641A-4B63-86E8-AFFF0C3F7065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5caa88ee6a3b6e0ac0e7de963e2cf78e4a0cb8c","datavalue":{"value":"barrier method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1974569$A0340479-2B2F-4171-90D8-771B9B9266C7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"78ddd6a633d7bfe7c43e876562487d2e1bd7ac9a","datavalue":{"value":{"entity-type":"item","numeric-id":588441,"id":"Q588441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$0A24820D-DBD7-4C50-9CBB-E3608B26F624","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":"Q1974569$C321990E-5BD6-4215-A31C-F758B10A164D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"94d69e84ef5b2ab08e2ba9ae76af348c40256dfb","datavalue":{"value":"https://doi.org/10.1006/jcom.1999.0500","type":"string"},"datatype":"url"},"type":"statement","id":"Q1974569$18A2941E-D085-48B1-8200-A62DCF811EA0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0adc963acddea8907d8b942f084521c6a8a0633","datavalue":{"value":"W2009774833","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974569$6C259D7A-E9AB-4FB2-A0AF-DEA63393809A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d9ab5a36f6d303eb24379924044933d0fea059c","datavalue":{"value":{"entity-type":"item","numeric-id":2277366,"id":"Q2277366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$40AD2C9F-A043-4602-A362-78FF31582CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48c0342476626a2966d5839a3d4733ee0bcf738c","datavalue":{"value":{"entity-type":"item","numeric-id":4324980,"id":"Q4324980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$7415A084-53D0-4C6D-BB67-776EA1F40769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf5b1ce2523e0781462d139382818414af743628","datavalue":{"value":{"entity-type":"item","numeric-id":687091,"id":"Q687091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$BE1CF123-2491-41BA-BFC1-F5CD44DA07CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"798382b76672e163594b36ebfa44f34ae7364b36","datavalue":{"value":{"entity-type":"item","numeric-id":1184332,"id":"Q1184332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$0F3AA66A-2666-4150-8245-164E9526F3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef8f0a43a581ac4fbdd4a0d5ff2ca8e4c0dbe2ae","datavalue":{"value":{"entity-type":"item","numeric-id":4039362,"id":"Q4039362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$0363A63B-DDE0-4499-871F-E31600C97C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2573df983d7b2d8847c9ef52ff2238b8e8f98c1f","datavalue":{"value":{"entity-type":"item","numeric-id":4720691,"id":"Q4720691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1974569$1B2B6ADD-E4C9-483C-ADF8-55CDAAA54E3A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"03c6c53766410d039231ecfbdc5d573c9a20cd07","datavalue":{"value":"10.1006/JCOM.1999.0500","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1974569$9A8C5690-7C0B-4568-B5EC-86264CBCB30D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cdf19decb92b31406f8982846b73af2513a5cc9","datavalue":{"value":{"entity-type":"item","numeric-id":4697086,"id":"Q4697086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2577a8f7b4612598590fc46bdb2c28119d08e27e","datavalue":{"value":{"amount":"+0.8105291128158569","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":"Q1974569$AF384D52-D33A-4A21-89C0-A240B8529150","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0e93128785a593716501e0eb0bb75f13550628f","datavalue":{"value":{"entity-type":"item","numeric-id":1321158,"id":"Q1321158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de6d54ec8ba21f927d4b0233a14e822d0450aca3","datavalue":{"value":{"amount":"+0.8025829195976257","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":"Q1974569$9741C469-54BC-400B-99EA-44EC49B3A713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ea5ebbf9d30f8b6848c668873343df1709d9d01","datavalue":{"value":{"entity-type":"item","numeric-id":687091,"id":"Q687091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5341dff90e74c3d65151267aeae750af474d743e","datavalue":{"value":{"amount":"+0.7974027991294861","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":"Q1974569$8D80175C-A00C-4DE3-BC65-14EBC6110B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"618144b13c8483197df0089e816a540a353c5b04","datavalue":{"value":{"entity-type":"item","numeric-id":583119,"id":"Q583119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3ae7d5b4c3b37ee5d956e159b613fa9652b5463","datavalue":{"value":{"amount":"+0.7967661619186401","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":"Q1974569$1E014EA9-5DE7-4913-A3E6-C768180B6D3D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1974569","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1974569"}}}}}