Accession Number : AD0737649

Title :   Bilinear Programming: Part I. Algorithm for Solving Bilinear Programs.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Konno,Hiroshi

Report Date : AUG 1971

Pagination or Media Count : 97

Abstract : 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 = e, x > or = 0 Fy < or = f, y > 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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, ALGORITHMS), LINEAR PROGRAMMING, QUADRATIC PROGRAMMING, INEQUALITIES, CONVEX SETS, SIMPLEX METHOD, GAME THEORY, THEOREMS, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE