A computational analysis of LCP methods for bilinear and concave quadratic programming

• Type: Article in International Scientific Journal
• Date: 1991

Authors

J. Júdice (Author) Other; Ana Maria Faustino (Author) FEUP

Journal

Title: Computers and Operations Research

No. 18

Pages: 645-654

ISSN: 0305-0548

Publisher: Elsevier

Scientific classification

FOS: Engineering and technology > Other engineering and technologies

Other information

Resumo (PT): It is discussed the use of a Sequential LCP (SLCP) algorithm for finding a global minimum of a Bilinear Programming problem (BLP) or a Concave Quadratic Program (CQP). The algorithm consists of solving a sequence of Linear Complementarity Problems (LCP). A Branch-and-Bound method is also considered in this study. This algorithm is based on the reformulation of a BLP into a LCP with a linear function to minimize. Computational experience with small and medium scale BLPs and CQPs indicates that the SLCP algorithm is quite efficient to find a global minimum (or at least a solution that is quite near the optimum), but it is in general unable to establish that such a solution has been found. An algorithm to f~nd a lower-bound for the BLP can overcome this drawback in some cases. Furthermore the SLCP algorithm is shown to be robust and compares favorably with the Branch-and-Bound method and another alternative technique.

Abstract (EN): It is discussed the use of a Sequential LCP (SLCP) algorithm for finding a global minimum of a Bilinear Programming problem (BLP) or a Concave Quadratic Program (CQP). The algorithm consists of solving a sequence of Linear Complementarity Problems (LCP). A Branch-and-Bound method is also considered in this study. This algorithm is based on the reformulation of a BLP into a LCP with a linear function to minimize. Computational experience with small and medium scale BLPs and CQPs indicates that the SLCP algorithm is quite efficient to find a global minimum (or at least a solution that is quite near the optimum), but it is in general unable to establish that such a solution has been found. An algorithm to f~nd a lower-bound for the BLP can overcome this drawback in some cases. Furthermore the SLCP algorithm is shown to be robust and compares favorably with the Branch-and-Bound method and another alternative technique.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 10