Browse

A note on the strong polynomiality of convex quadratic programming

DC Field Value Language
dc.contributor.authorHong, Sung-Pil-
dc.contributor.authorVerma, Sushil-
dc.date.accessioned2009-07-07T22:54:03Z-
dc.date.available2009-07-07T22:54:03Z-
dc.date.issued1995-
dc.identifier.citationMathematical Programming 68 (1995) 131-139en
dc.identifier.issn0025-5610 (print)-
dc.identifier.issn1436-4646 (online)-
dc.identifier.urihttp://hdl.handle.net/10371/5315-
dc.description.abstractWe prove that a general convex quadratic program (QP) can be reduced to the problem of finding the nearest point on a simplicial cone inO(n 3 +n logL) steps, wheren andL are, respectively, the dimension and the encoding length of QP. The proof is quite simple and uses duality and repeated perturbation. The implication, however, is nontrivial since the problem of finding the nearest point on a simplicial cone has been considered a simpler problem to solve in the practical sense due to its special structure. Also we show that, theoretically, this reduction implies that (i) if an algorithm solves QP in a polynomial number of elementary arithmetic operations that is independent of the encoding length of data in the objective function then it can be used to solve QP in strongly polynomial time, and (ii) ifL is bounded by a first order exponential function of n then (i) can be stated even in stronger terms: to solve QP in strongly polynomial time, it suffices to find an algorithm running in polynomial time that is independent of the encoding length of the quadratic term matrix or constraint matrix. Finally, based on these results, we propose a conjecture.en
dc.description.sponsorshipThe research was partially supported by ONR grant N00014-91-j-1241.en
dc.language.isoen-
dc.publisherSpringer Verlagen
dc.subjectConvex quadratic programmingen
dc.subjectStrong polynomialityen
dc.subjectNearest point problem on simplicial coneen
dc.titleA note on the strong polynomiality of convex quadratic programmingen
dc.typeArticleen
dc.contributor.AlternativeAuthor홍성필-
dc.identifier.doi10.1007/BF01585760-
dc.identifier.doi10.1007/BF01585760-
dc.citation.journaltitleMathematical Programming-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
Files in This Item:
There are no files associated with this item.
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse