A new algorithm for quadratic programming

DOI10.1016/S0377-2217(87)80152-2MaRDI QIDQ1097172zbMATH OpenOpenAlexFDO

Authors Tamás Terlaky

Publication date 1987

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(87)80152-2

zbMATH Keywords

criss-cross methodfeasible point active-set methodlinear equation systemspivotingsimplex method

Mathematics Subject Classification ID

Existence of solutions for minimax problems (49J35) Numerical mathematical programming methods (65K05) Quadratic programming (90C20)

Review text

We present a new finite algorithm for quadratic programming. Our algorithm is based on the solution procedures of linear programming (pivoting, Bland's rule), Hungarian methods, criss-cross method), however this method does not require the enlargement of the basis tableau as the Frank-Wolfe method does. It can be considered as a feasible point active- set method. We solve linear equation systems in order to reach an active constraint set (complementary solutions) and we solve a feasibility problem in order to check that optimality can be reached on this active set or to improve the actual solution. This algorithm is a straightforward generalization of Klafszky's and Terlaky's Hungarian method. It has nearly the same structure as Ritter's algorithm (which is based on conjugate directions), but it does not use conjugate directions.

Recommendations

• scientific article; zbMATH DE number 4037611
• scientific article; zbMATH DE number 4172744
• A quadratic programming algorithm
• An Algorithm for Convex Quadratic Programming That Requires O(n^3.5L) Arithmetic Operations
• An algorithm for solving quadratic programming problems

Cites work

• A convergent criss-cross method
• A quadratic programming algorithm
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3543799 (Why is no real title available?)
• scientific article; zbMATH DE number 3224200 (Why is no real title available?)
• On \(\ell_ p\) programming
• Some Empirical Tests of the Criss-Cross Method
• The Criss-Cross Method for Solving Linear Programming Problems
• Variants of the Hungarian method for solving linear programming problems

Cited in

(17)

• New theoretical results on recursive quadratic programming algorithms
• Pivot rules for linear programming: A survey on recent theoretical developments
• Approximation algorithms for quadratic programming
• A near-quadratic algorithm for fence design
• New variants of the criss-cross method for linearly constrained convex quadratic programming
• A new algorithm for solving the general quadratic programming problem
• A new algorithm for quadratic integer programming problems with cardinality constraint
• scientific article; zbMATH DE number 4172744 (Why is no real title available?)
• scientific article; zbMATH DE number 4204121 (Why is no real title available?)
• scientific article; zbMATH DE number 3943565 (Why is no real title available?)
• scientific article; zbMATH DE number 4037611 (Why is no real title available?)
• A quadratic programming algorithm
• scientific article; zbMATH DE number 1215253 (Why is no real title available?)
• Some generalizations of the criss-cross method for quadratic programming
• scientific article; zbMATH DE number 1117802 (Why is no real title available?)
• Quadratic programming algorithms for obstacle problems
• Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids

This page was built for publication: A new algorithm for quadratic programming

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