Solving Bilinear Programming Problems Via Convex Relaxation

For most of quadratically constrained quadratic programming problems aiming finding minimum value, if either the objective function is nonconvex or there are constraint conditions that are not convex, they are NP-hard. Many nonpolynomial time algorithms have been proposed in dealing with this kind of problems. In this paper we concentrate on solving a special case of quadratically constrained quadratic programming problems–the bilinear programming problems.The bilinear programming(BP) is a special case of quadratically constrained quadratic programming(QCQP), which is known NP-hard. There are many applications for bilinear programming problems, including production planning, human active recognition, multi-agent planning and so on. All the situations above can be modeled as bilinear programming problems.In the recent years, little attention was paid to bilinear programming problems, in the meanwhile, large progression has been made in dealing with quadratically constrained quadratic programming, some algorithms have been proposed to solve quadratically constrained quadratic programming problems effciently. Although we can solve bilinear programming problems via the algorithms proposed for solving general quadratic programming problems, this make no use of the structure of bilinear programming problems,thus, will not have effciency.In this thesis, in dealing with this situation, we present a convex relaxation(CR)algorithm for the BP problems, which takes the structure of bilinear items into consideration. Our algorithm reformulates the BP problem into a QCQP problem by using the singular value decomposition on the matrix in the BP objective function. Adopting a convex envelop to relax the reformulation problem leads us to a QCQP convex relaxation model which has O(n) additional linear constraints. Using our convex relaxation method in a branch-and-bound algorithm, we get sequences of lower and upper bounds for the BP problem. These sequences are proven to converge to the global optimal value of the BP problem. Numerical examples show our algorithm is more effcient in dealing with high dimensional problems.The contributions of this thesis are as follows:· a relaxation model in less dimension by using SVD decomposition· a branch-and-bound algorithm· effciency of the proposed algorithm is tested...