{"entities":{"Q1121792":{"pageid":1132541,"ns":120,"title":"Item:Q1121792","lastrevid":66466683,"modified":"2026-04-12T10:16:11Z","type":"item","id":"Q1121792","labels":{"en":{"language":"en","value":"An extension of Karmarkar's projective algorithm for convex quadratic programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4104725"}},"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":"Q1121792$831DC1AF-BCFC-475B-AE9D-32FB00089009","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34336bb74461ced03a40e55138968f5b947bacf6","datavalue":{"value":{"text":"An extension of Karmarkar's projective algorithm for convex quadratic programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121792$A6B4483E-B9B5-4C8D-9C25-529C21C227A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24d7f8f2cc2e6870134b244bda441dad7ceb4688","datavalue":{"value":"0674.90077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$F9F2DA2A-A416-4972-B66A-E0ECE21B5D1D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e467db1b36ad0c2744202fb3f15bcd756e235a30","datavalue":{"value":"10.1007/BF01587086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$0E80B3DB-CB2C-4F6D-BBDD-B6A0D8E0D1C3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"593457efc25a34c12f5e86daf2bf47f778699a57","datavalue":{"value":{"entity-type":"item","numeric-id":1115330,"id":"Q1115330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$172161D5-04FB-47E2-A380-2636ECA831F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f722a9d373eb3dc93c3a37caf61c6de6dd0a5d2b","datavalue":{"value":{"entity-type":"item","numeric-id":173845,"id":"Q173845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$FF87CD78-4419-4340-9892-3DAC709B4E53","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":"Q1121792$8B5BDDAA-4AD4-4366-B63D-F4E360A5F11A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1121792$DA91FF59-6A21-4308-AE01-432180730DB2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d7653389c13c102da9f828e840b55b3dfd433763","datavalue":{"value":"The paper uses Karmarkar's polynomial-time LP algorithm as a base on which to develop a polynomial-time algorithm for convex quadratic programs. Using the interior ellipsoid method, the following sub- optimization problem is solved:  \\[  \\min f(\\hat x)=\\hat x[n]^ T\\hat Q\\hat x[n]/2\\hat x_{n+1}-\\hat c\\hat x[n]  \\]  subject to: \\(\\hat A\\hat x=\\hat b\\), \\(\\| \\hat x-e\\| \\leq \\beta <1\\), where  \\[  \\hat Q=DQD\\quad (D=diag(x^ k)),\\quad \\hat c=cD,\\quad \\hat A=\\left( \\begin{matrix} AD-b\\\\ e^ T\\end{matrix} \\right),\\quad \\hat b=\\left( \\begin{matrix} 0\\\\ n+1\\end{matrix} \\right),\\quad and  \\]  \\^x[n] is the vector of the first n components of \\(\\hat x\\in R^{n+1}\\). The authors show that this problem can be solved in \\(O(Ln^ 3)\\) operations and that \\(O(Ln)\\) iterates are required. While no computational results are presented, the authors claim an efficient implementation is possible and cite a Ph.D. thesis as a source of some such testing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121792$DF4525DF-2764-49C1-A06C-F7F00AF8AC7D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3d464cc60311db927c1c313615c1099a2ab56816","datavalue":{"value":{"entity-type":"item","numeric-id":920830,"id":"Q920830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$AD5AAD07-0F84-4B7E-ABF7-E99E4082D217","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccd1dd4cefa81e8158b9f080486a4eaed61a9ee8","datavalue":{"value":"90C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$161C5ABC-0EDF-4ED7-B6CD-8333FE8441A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$E2F367FB-14EA-4BF1-9067-DE243D76DB3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$CECF63FE-43A5-4781-B0E2-72AA34AC25CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$ECE26FB7-D2F0-46AA-ABF7-D6BC9E79617D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$B45FAF89-543E-4AD5-A244-C61F9F18BDE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2fc48f2418a4f8e7a5212b23797a7919b876b73d","datavalue":{"value":"4104725","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$AC298FB1-860B-4745-9D92-ADC49F48D8E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e278b85c59e660479eed42d6109ee9924df896e","datavalue":{"value":"Karmarkar's projective algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121792$E918E998-CA65-4307-ACB3-34154F2F4689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121792$5A7F98D4-3698-41DA-88CB-B59DCC6D9A0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4ec5ff4571e8b22ab1091c14aa27886ed1eb96","datavalue":{"value":"convex quadratic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121792$592C4906-9540-4EF3-826D-F6E435DA62CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ee052ddc181a78c276108b97553ee0f5c108092","datavalue":{"value":"interior ellipsoid method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121792$AE608BD4-472A-4D92-90B4-EABA4D9D8D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69830fdecbaeca8617feebfd37921bd9e15af48c","datavalue":{"value":"sub-optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121792$8555F722-42CF-4876-883E-D0AA0EF6E2F6","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":"Q1121792$7924C7C5-29E7-4EA5-844E-4FF966112B8F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2aa250e3b281d881c1358be098bb79318ac3c5","datavalue":{"value":{"entity-type":"item","numeric-id":580191,"id":"Q580191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$B2A284FE-4B7D-4C01-84AC-99EC1E98E79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c633d9447e5d986230e2957316f8249514ca99d","datavalue":{"value":{"entity-type":"item","numeric-id":3030578,"id":"Q3030578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$A5FF0B63-BDB3-4537-A426-33CB6EB53529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9556b07decab54f0004fc47b4383cad55a1de3f","datavalue":{"value":{"entity-type":"item","numeric-id":2527120,"id":"Q2527120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$3DE08FFF-108A-4365-8805-ED4676D8A55B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6d1ec9843c65861c97c28bde17d5f7b4cd3ee00","datavalue":{"value":{"entity-type":"item","numeric-id":5583564,"id":"Q5583564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$9C6029E3-B227-44E2-9918-62CDC0267DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40259340826a891f102b9fb80ebcbc925180375b","datavalue":{"value":{"entity-type":"item","numeric-id":5635265,"id":"Q5635265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$3B4910D8-D631-4A73-A241-A361C93DF2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50f843ce5d8877454cd958856159d2c008712885","datavalue":{"value":{"entity-type":"item","numeric-id":4051917,"id":"Q4051917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$7BD40DE9-0F4B-4543-921F-D2C990F5BE53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$9B8C17CE-3A0F-49D4-83D8-A7B753C8E599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$2E5A8195-EC52-4863-A5D1-4E08B9ED6381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$346DA614-B59B-4795-BA19-8964872CC660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b290b3db3f847e0f1cb275f225ebdd148d96e5a1","datavalue":{"value":{"entity-type":"item","numeric-id":3873927,"id":"Q3873927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$F5F8CF81-61B6-473F-A111-A846D4D7A5B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"538de0152ebdec9732d0f9cf12c3446215cdfe4a","datavalue":{"value":{"entity-type":"item","numeric-id":5514161,"id":"Q5514161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$0E0C7C89-FCC9-4C8D-8C6E-258BDCC6AF52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97732b64fbc7a85d84ecc89bd22454f57b398880","datavalue":{"value":{"entity-type":"item","numeric-id":3688092,"id":"Q3688092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$36752DD8-4D83-4780-A6D2-01E34307C3E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$F35EC4CE-DA4C-4F5E-9F5E-D255EF089835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39c5f3c959a924b42f2f4b78299d6fadbe3c1ef","datavalue":{"value":{"entity-type":"item","numeric-id":5535888,"id":"Q5535888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$8C928581-B5F8-4FE8-BA24-4FB588B54B79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e059544c8c0698cff660c84df5dcef31f590703a","datavalue":{"value":{"entity-type":"item","numeric-id":3688117,"id":"Q3688117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$F77A67D6-4815-4E97-A50F-5F2FB26DA50D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b365497a35d2bc4f523f5dc7d8ba065391e6222","datavalue":{"value":{"entity-type":"item","numeric-id":1090601,"id":"Q1090601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$7156BE83-6E1F-445E-B2BB-17F3DA2C7FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a975d39735d0d10d92ac745a75752a43e0af022","datavalue":{"value":{"entity-type":"item","numeric-id":581231,"id":"Q581231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$713FA6FE-D150-433B-B7D2-D30785F415C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3223323d1c6215bfb2ca00fac2471a05c75ea3b1","datavalue":{"value":{"entity-type":"item","numeric-id":3287702,"id":"Q3287702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$255349D9-8A2F-41F2-9B3A-8F87674C87D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31c1a5fe61529ded0932202d29677b531990fe53","datavalue":{"value":{"entity-type":"item","numeric-id":3780756,"id":"Q3780756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121792$0D13A0B0-CB41-45DD-AC68-19713A06D624","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0ecaebc7558527fb3ab3e69e43a5deb4ae8fe833","datavalue":{"value":"https://doi.org/10.1007/bf01587086","type":"string"},"datatype":"url"},"type":"statement","id":"Q1121792$4ED2CD60-09F7-4046-AEDF-4DA085EBD1D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"31da5e7257b974053ff3b6acbc55d1fa1c637352","datavalue":{"value":"W1982929029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121792$665CA540-C10E-4782-99C9-DE34728F7800","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f821d581bbb16020c376e08e3529b90ebeedcb10","datavalue":{"value":{"entity-type":"item","numeric-id":3200887,"id":"Q3200887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd11472420f97d6e4979a15836beab7252e88a8d","datavalue":{"value":{"amount":"+0.8717883229255676","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":"Q1121792$67E2EC97-7310-4036-9318-1B562A26EE95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0de3a4183f148817e8439c226e0bddc8071e6fdd","datavalue":{"value":{"entity-type":"item","numeric-id":1919097,"id":"Q1919097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f14fa78b044178e88bbbcc2d44c7e43c5261672","datavalue":{"value":{"amount":"+0.8632178902626038","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":"Q1121792$6434ED9E-ABB0-4CCF-97B4-C6120C07181B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba8ce205977cc5bad062ebfaeeaa819a26c01f93","datavalue":{"value":{"entity-type":"item","numeric-id":5202848,"id":"Q5202848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdb19caa81b1c61c724f9d7aaf46f29b6a0297b9","datavalue":{"value":{"amount":"+0.8458085656166077","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":"Q1121792$857E4C1D-90CC-406E-BAF2-2BBE898645E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"115d89b341340137f5c668bc0d6478684f8a24c5","datavalue":{"value":{"entity-type":"item","numeric-id":3320129,"id":"Q3320129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c41e4bd21296f92ed477175604a7ce2b8bf0189","datavalue":{"value":{"amount":"+0.84498131275177","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":"Q1121792$CF725FDD-ADC6-47DD-9799-7FB47335110D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfa8a160b07ecd7cbdc917cf6d83ed590f6782d6","datavalue":{"value":{"entity-type":"item","numeric-id":3316970,"id":"Q3316970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29667da837d0de9a4ea7a060533df01a664d93be","datavalue":{"value":{"amount":"+0.8427078723907471","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":"Q1121792$51C6564D-B075-482C-9052-48F568926B25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extension of Karmarkar's projective algorithm for convex quadratic programming","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_extension_of_Karmarkar%27s_projective_algorithm_for_convex_quadratic_programming"}}}}}