A polynomial algorithm for convex quadratic optimization subject to linear inequalities

DOI10.1016/J.DAM.2019.12.001MaRDI QIDQ2297665zbMATHOpenAlexWikidataFDO

Authors Sergei Chubanov

Publication date 20 February 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.12.001

zbMATH Keywords

linear programmingconvex optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A class of infeasible interior point algorithms for convex quadratic programming
• scientific article; zbMATH DE number 3847228
• scientific article; zbMATH DE number 3850827
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• scientific article; zbMATH DE number 4193461

Cites work

• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• A new polynomial-time algorithm for linear programming
• A polynomial projection algorithm for linear feasibility problems
• An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
• On the non-polynomiality of the relaxation method for systems of linear inequalities
• Proximity Maps for Convex Sets
• Solving conic systems via projection and rescaling
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

Cited in

(11)

• A note on the strong polynomiality of convex quadratic programming
• A new approximation hierarchy for polynomial conic optimization
• scientific article; zbMATH DE number 4141790 (Why is no real title available?)
• A convex optimization model for finding non-negative polynomials
• A polynomial-time algorithm for affine variational inequalities
• A quasi-linear algorithm for calculating the infimal convolution of convex quadratic functions
• Method of alternating contractions and its applications to some convex optimization problems
• A class of polynomial variable metric algorithms for linear optimization
• A generalized simplex method for integer problems given by verification oracles
• Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

This page was built for publication: A polynomial algorithm for convex quadratic optimization subject to linear inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297665)