Theoretical Research And Algorithm Design On Global Solutions For Several Kinds Of Quadratically Constrained Quadratic Optimization Problems

The quadratically constrained quadratic optimization problem plays an important role in optimization theory.This problem is generally NP-hard and often has multiple extreme points,so it is difficult to find its global optimal solution using traditional optimization methods such as the steepest descent method,Newton’s method,and penalty function method.At the same time,The quadratically constrained quadratic optimization problem is widely used in important fields such as enterprise production management,communications engineering,financial engineering,and speech recognition.Therefore,it is of great significance to study the quadratically constrained quadratic optimization problem.The research results and innovations of this paper mainly include the following four aspects.We give a necessary and sufficient condition that the semidefinite relaxation is tight relaxation for the homogeneous quadratic optimization problem with three homogeneous quadratic constraints in the real number field and the homogeneous quadratic optimization problem with four homogeneous quadratic constraints in the complex number field for the first time.When the positive semidefinite relaxation is a tight relaxation,we further provide two polynomial time algorithms to solve the global optimal solutions of the two types of original problems respectively.Numerical experiments also show the effectiveness of the algorithms.In addition,we extend the key theorems required to prove this necessary and sufficient condition to the quaternion set,which provides some theoretical support for the future research on the quadratically constrained quadratic optimization problem of the quaternion set.Using the above necessary and sufficient condition,we generalize the classic S-lemma and Yuan’s lemma to three real quadratic forms or four complex quadratic forms,and give the necessary and sufficient conditions for the establishment of the S-lemma in these two situations for the first time,which generalizes the classic conclusions of existing literature and also provides more theoretical basis for the application of S-lemma in the field of cybernetics.In addition,these conditions can also be used to prove that the quadratic optimization problem with two general quadratic constraints on the real number field has implicit convexity in a specific case.For the extended trust region subproblem with multiple linear inequality constraints on the real number field,a geometric property between the feasible region of this problem and the feasible region of the semidefinite relaxation problem after second-order cone reshaping is proposed,which generalizes the classic conclusions of existing literature.In particular,applying this geometric property,a class of extended trust region subproblems with multiple special quadratic constraints can be split into some semidefinite programming problems for solving.In addition,when any two of the linear constraints do not intersect in the trust region,a polynomial time algorithm for quickly recovering the optimal solution of the original problem from the optimal solution of the semidefinite relaxation problem is given in this paper.Finally,we study the extended trust region subproblem with multiple quadratic constraints on the real number field.When any two quadratic constraints do not intersect in the trust region,we prove that at most two quadratic constraints can be retained without changing the optimal value of the problem.Therefore,the difficulty of solving this problem is equivalent to solving the extended trust region subproblem with two quadratic constraints.Correspondingly,we give a polynomial time algorithm to solve the global optimal solution of this type of problem.In addition,for the generalized CDT problem,we give a new sufficient condition to completely eliminate the dual gap of the problem by adding a linear constraint,which broadens the known situations where the dual gap can be completely eliminated.