{"entities":{"Q2364486":{"pageid":2375229,"ns":120,"title":"Item:Q2364486","lastrevid":52864142,"modified":"2026-01-23T16:23:24Z","type":"item","id":"Q2364486","labels":{"en":{"language":"en","value":"On the complexity of quadratic programming with two quadratic constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6751021"}},"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":"Q2364486$98A2A3FB-B385-4E20-B5FF-DB0AE59468FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60c9cffbfd6e087569e31458183fe48c47e654ac","datavalue":{"value":{"text":"On the complexity of quadratic programming with two quadratic constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2364486$077ACE4D-42F7-4B90-BA24-B7600EF988D4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c5189aa51dac61f24050e6be2237eceb774b64a","datavalue":{"value":"1396.90055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364486$5CF54E4F-43CB-47B8-A492-ECB4517E5DA0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0f6acf0ee94b09a009d612447a1d015a3dc7f35","datavalue":{"value":{"entity-type":"item","numeric-id":459000,"id":"Q459000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$32628445-EC06-4DBB-AF16-F93398BE8273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a760814dae32fb1464ea2826b04d372929806fc","datavalue":{"value":{"entity-type":"item","numeric-id":166220,"id":"Q166220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$F8C49AD0-6C85-4255-8422-3CF8B43CB584","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":"Q2364486$40275F09-0549-40F8-9176-6ECC9706ED4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"36ae9f0663dd67e81623b5f2360b90198adfccf0","datavalue":{"value":{"time":"+2017-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2364486$2B4EECF1-F1BF-4C8D-95D2-48D8AD374EEE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"df27d9873d204603e16eea3937729fccd5a83f25","datavalue":{"value":"This paper deals with problems of the form  \\[ \\begin{aligned} \\min & \\frac{1}{2}x^{T}Qx+q^{T}x \\\\ \\text{s.t.} & \\frac{1}{2}x^{T}x\\leq \\frac{1}{2} \\\\ & \\frac{1}{2}x^{T}Ax+a^{T}x\\geq u, \\end{aligned} \\tag{1} \\]  where \\(A\\) is a positive definite \\(n\\times n\\) symmetric matrix. This type of problem arises as a subproblem to be solved at each iteration of a trust-region algorithm for equality constrained nonlinear problems. It was known that some particular instances of (1) were solvable in polynomial time (e.g., in the case when \\(q=a=0\\)). The main result of the paper, Theorem 5.2, shows that, under rather mild conditions, the so-called Algorithm 1 is a polynomial time algorithm to compute an \\(\\varepsilon \\)-optimal solution for Problem (1). The preparation of the proof consists of three steps:  1. Identification of the KKT points for (1);  2. Discussion for the case where the Hessian of the Lagrangian function is singular, and for the case it is non-singular; and  3. Derivation of feasible solutions of (1) from approximate KKT points.  As the authors point out, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364486$D1708CE2-AE12-48FE-96D8-CBB3B812BD89","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364486$AFD610BA-94A3-4C93-B3DF-E6B395257CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed10a41ec587cb61dc683f25ef4b3e827c7fee2f","datavalue":{"value":"90C26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364486$98D3398A-DBB5-40C6-AEB3-3FE5EC107880","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dfbd5d4963d092cbe9df105b1c2d361b246c30f2","datavalue":{"value":"6751021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364486$53AA4E7E-4F59-4A95-A176-C9D8A642FD14","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba40dff3c0b83d47c446b87555d8cee8d52f262f","datavalue":{"value":"quadratic problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364486$C3DDEF17-D70D-4A99-AF2F-DCC909AE2642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364486$5E9EFAE5-F6AE-46AD-AF48-D3D31C5D9A39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc87ac09cd09c6ed236582156c7fc892515eeaa","datavalue":{"value":"bivariate polynomial systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364486$1E5DFDED-70F2-4F81-A7ED-3E3B3622AE74","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ec0ed7fa80ee1280a33c93bd6984aa8fe85b14a8","datavalue":{"value":{"entity-type":"item","numeric-id":591565,"id":"Q591565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$D0320E99-18E8-4767-90F4-7FE7551D6EC8","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":"Q2364486$917AF514-109B-4461-A8AC-C987CF0FAE36","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd20632da43fcb131de5fed7c7199fc3ceef5570","datavalue":{"value":"https://doi.org/10.1007/s10107-016-1073-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2364486$D2A3E0F2-4138-40B5-B316-FE7124E25213","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"affcceeaec161d9ada526e1272fc4e8b51ea6e55","datavalue":{"value":"W2525586417","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364486$070A17F1-8042-4F21-BAA9-913AF46A657B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ea4b7cc1c8cd30af41bd5890ab36368fd30c42d","datavalue":{"value":{"entity-type":"item","numeric-id":3648528,"id":"Q3648528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$DADF2E60-96F6-44DD-9F26-A36C6927D947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"470c3f6dcef44d0df95d200f18e5ce1ae4fa6f12","datavalue":{"value":{"entity-type":"item","numeric-id":1919813,"id":"Q1919813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$7D78E2A8-AEF5-462A-B89C-AFC5F43159F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d27a9848efc6bbdfefb034aad706b89b73b108fa","datavalue":{"value":{"entity-type":"item","numeric-id":2436648,"id":"Q2436648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$4D0B2D62-E0B2-4D57-82B3-AEC91BD9DEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0848048ef0791e9a8a9b881407207c0d424200c4","datavalue":{"value":{"entity-type":"item","numeric-id":3192097,"id":"Q3192097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$13D06A3F-1CA0-4EC7-8E7C-D578CC3F82EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a8b9785ff2da2aa5b5c40c80eea12c12eda6abd","datavalue":{"value":{"entity-type":"item","numeric-id":5300533,"id":"Q5300533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$3758CF19-95A8-49EB-90F0-18489B55BFDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf90a4a1561edcd86867de96cbf427be37cfb78c","datavalue":{"value":{"entity-type":"item","numeric-id":3681854,"id":"Q3681854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$AA4E6238-03A6-4BE2-95A9-E4200EE6F280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf7e5ea8b887807f5a5d06a897412368d42a81e7","datavalue":{"value":{"entity-type":"item","numeric-id":5245268,"id":"Q5245268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$89C8166B-F38B-4B18-B34D-59DEB3464672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5f156ce463438a21ba421522f2f5f7514e7bf51","datavalue":{"value":{"entity-type":"item","numeric-id":5244530,"id":"Q5244530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$E4D5D5E0-6EDB-43D4-A777-F180561523A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b1e2145132319d616eb7e6ef4d623cd6376ecd8","datavalue":{"value":{"entity-type":"item","numeric-id":2946545,"id":"Q2946545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$9FE6D847-CA0F-4C2F-90F3-94A3EB03ED26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4383ef7001bb3ea6ac756c551b5ca6ccf437da15","datavalue":{"value":{"entity-type":"item","numeric-id":2254683,"id":"Q2254683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$4AEDD568-71E9-4381-9DA2-149EC71F6055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb602d89ab66ead03d3f1fd918bb1dd7ddba1390","datavalue":{"value":{"entity-type":"item","numeric-id":1785624,"id":"Q1785624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$539AF26A-85D1-4F7B-8C6F-2C0C99E068F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02c72e10b00eeef1f80983912a07725a93d33fb4","datavalue":{"value":{"entity-type":"item","numeric-id":4852578,"id":"Q4852578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$B3E27F86-C2A7-41F3-995F-63083D912736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca81ffc0a0fc2b8dd84f7a26555d7ff6bc7fb2eb","datavalue":{"value":{"entity-type":"item","numeric-id":4838957,"id":"Q4838957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$61881392-D46A-455E-807D-E861997611C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"322a9017aa840f546f25e07f3021d250f9dba4d8","datavalue":{"value":{"entity-type":"item","numeric-id":4781203,"id":"Q4781203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$03FCE3E1-BA3F-401B-9E69-F917961B6609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e73e011868785b4423c767e09fe203869911ac9b","datavalue":{"value":{"entity-type":"item","numeric-id":3605247,"id":"Q3605247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$47A25470-F124-4ECB-80BD-8C2A4547C99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e104214af32a891dd7b7a304e04bb5b5865d95e9","datavalue":{"value":{"entity-type":"item","numeric-id":1572673,"id":"Q1572673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$F999CCF4-8904-4E3E-A90C-3CC221471E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e369ecf242e46951033b306422c79ed1061653","datavalue":{"value":{"entity-type":"item","numeric-id":1304392,"id":"Q1304392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$C103C50A-1012-42B5-81A3-D9D4FBAA4C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8d4ecf90720bf2b686de006ec46563f317e2db3","datavalue":{"value":{"entity-type":"item","numeric-id":4441956,"id":"Q4441956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364486$DA0FF505-A378-41D3-AF73-8EA5ECDAE4EE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ccf62e73cce2282f530cb4716ca1daf6405ce12d","datavalue":{"value":"10.1007/S10107-016-1073-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364486$1C06354D-6B3B-4F2F-8C92-3F9BB6548BA2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0b62b36f62e8738d62b2c64bb9eef0c96e200ae","datavalue":{"value":{"entity-type":"item","numeric-id":4441956,"id":"Q4441956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9acf5f9126f1217c1a42c2b53005126d2e0d4928","datavalue":{"value":{"amount":"+0.8442049622535706","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":"Q2364486$E87EAEE4-8989-4584-ABB1-D75398BA8720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce8a306a53ab66ee70059bbaefe639a4f02157d7","datavalue":{"value":{"entity-type":"item","numeric-id":2789609,"id":"Q2789609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f927d478c4ef80e8094dadbeaf5afe373e1f084b","datavalue":{"value":{"amount":"+0.8204164505004883","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":"Q2364486$C4B4D944-E7C0-46AA-8DC0-8FA4210C1B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f633c79990a65e9bb15645498a25662304428ca","datavalue":{"value":{"entity-type":"item","numeric-id":3200891,"id":"Q3200891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3841e7696790320c89442a1cc3b4326be2a37e3a","datavalue":{"value":{"amount":"+0.8187219500541687","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":"Q2364486$5BE0A463-05CD-4E76-AAF5-3BD46A0D4D26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cc44d875ba078b6c96389517957f5d110b05345","datavalue":{"value":{"entity-type":"item","numeric-id":4377569,"id":"Q4377569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d18718dbedf00f7e47be10c0d287341a713d1bf2","datavalue":{"value":{"amount":"+0.8072813153266907","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":"Q2364486$85473219-BD7B-4138-8D0F-8A41D2EFA4FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d8758c4df5276738d171494c2038d15bbb73c2d","datavalue":{"value":{"entity-type":"item","numeric-id":2016445,"id":"Q2016445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c29a5b9cf0146fa760d00222f8466f86d6f84c5a","datavalue":{"value":{"amount":"+0.802541971206665","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":"Q2364486$4BF078DE-4957-4950-AB22-969B50A728A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2364486","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2364486"}}}}}