A projected–gradient interior–point algorithm for complementarity problems

A projected–gradient interior–point algorithm for complementarity problems

0.00 Avg rating0 Votes
Article ID: iaor20116957
Volume: 57
Issue: 4
Start Page Number: 457
End Page Number: 485
Publication Date: Aug 2011
Journal: Numerical Algorithms
Authors: , , ,
Keywords: programming: convex
Abstract:

Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.

Reviews

Required fields are marked *. Your email address will not be published.