Linear, quadratic, and bilinear programming approaches to the linear complementarity problem (Q1068731): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 23:54, 30 January 2024

scientific article
Language Label Description Also known as
English
Linear, quadratic, and bilinear programming approaches to the linear complementarity problem
scientific article

    Statements

    Linear, quadratic, and bilinear programming approaches to the linear complementarity problem (English)
    0 references
    0 references
    1986
    0 references
    Traditional pivoting procedures for solving the linear complementarity problem can only guarantee convergence for problems having well defined structures. Recently, optimization procedures based on linear, quadratic, and bilinear programming have been developed to extend the class of problems that can be solved efficiently. These latter approaches are the focus of this paper. The strengths and weaknesses of each of the approaches are discussed. The linear programming approach, advanced by Mangasarian, is the most efficient once an appropriate objective function is found. This requires the solution of a system of linear and bilinear equations that is easily solvable only in some cases. Extensions to this approach, due to Shiau, show some promise but are still limited to special cases of the general problem. The quadratic programming approaches discussed here are restricted to specialized procedures for the complementarity problem. One, proposed by Cheng, is based on the Levitin-Poljak gradient projection method, and the other, due to Cirina, is based on Karush-Kuhn- Tucker theory. Both are only successful on some problems. The two bilinear programming algorithms discussed are the most general. For any problem, they are guaranteed to find at least one solution or conclude that none exist. One is a specialization of the recent biconvex programming algorithm of the author and \textit{J. E. Falk} [Math. Oper. Res. 8, 273-286 (1983; Zbl 0521.90087)] and the other is an entirely new implicit enumeration procedure.
    0 references
    nonconvex programming
    0 references
    global optimization
    0 references
    branch and bound
    0 references
    linear complementarity
    0 references
    bilinear programming
    0 references
    biconvex programming
    0 references
    implicit enumeration
    0 references

    Identifiers