Bilinear Programming: Part I. Algorithm for Solving Bilinear Programs

摘要

The paper deals with an algorithm for determining a global optimum of a structured non-concave quadratic programming problem called the bilinear programming problem (BLP): maximize c supt x + d supt y + x supt Cy subject to Ex or = 0 Fy or = 0 This algorithm is an elaboration of the cutting plane algorithm proposed by K. Ritter. It is established that the authors algorithm generates and epsilon-optimal solution (with respect to the objective functional value) in finitely many steps for any given epsilon > 0 provided the constraint set is non-empty and compact. It must be noted that the BLP algorithm exclusively uses the simplex algorithm and that no elaborate subproblem needs be solved. (Author)