Exact Semidefinite Formulations And Branch And Bound Algorithms For QMICQP Problems

Quadratic Matrix Inequality(QMI)can be used to describe the stability of control systems,but QMI constrained optimization problems are generally non-convex,and even QMI feasibility problems are generally NP-hard.In recent years,the problem of QMI constrained optimization has attracted more and more attention.This paper mainly studies the exact semi-definite form of Quadratic Programming Problem Constrained by Quadratic Matrix Inequality(QMICQP),and the branch-and-bound algorithm of Bilinear Matrix Inequality Feasibility Problem(BFP).The research contents of this paper mainly have two aspects:Firstly,we consider the extension of Farkas lemma on closed convex cones in Matrix space.On this basis,we study the exact semidefinite form of QMICQP problem.Firstly,the semidefinite programming relaxation form of QMICQP problem is considered,and the duality of the relaxation problem(hereinafter called relaxation duality problem)is given.Then,we consider the special diagonal QMICQP problem,and utilize the feasibility system by using the constraints of its relaxation dual problem.On this basis,we analyze the conditions under which the optimal solution of the relaxation problem of semidefinite programming is the optimal solution of the original problem.Finally,We use the above conclusion to extend the diagonal QMICQP problem.Secondly,we design a branch and bound algorithm for solving BFP problem.Based on the existing branch-and-bound algorithm framework,we propose a new branching rules,and improve a termination criterion according to the form of solving problem,then,we present a new branch-and-bound algorithm to solve the BFP problem.The influence of different lower bound problems and branching rules on the algorithm is analyzed by numerical experiments with MATLAB programming.The preliminary numerical results show that for different branching rules and lower bound problems,the branch-and-bound algorithm is more efficient after adjusting the termination criteria.In addition,a penalty method for solving the second order BFP problem is presented.The paper is organized as follows: The first chapter of this paper briefly introduces the background and development status of matrix inequality problem.The second chapter mainly introduces the Farkas lemma in vector space and its extension form,and gives the Farkas lemma on the closed convex cone in matrix space by using the concept of "asymptotically solvable".The third chapter introduces the exact semidefinite relaxation theory of QMICQP problem.In The fourth chapter,based on the existing branching and bound methods,a new branching rule and termination criterion are proposed,a new branching and bound method for solving BFP problem is designed,and the numerical experimental results are given.Last part is the summary and prospect of the thesis.