Exactness Conditions of SDP Relaxations for Generalized Extended Trust Region Subproblems

While quadratically constrained quadratic programming (QCQP) formulation capturesnonlinearity of the real world in its simple form, it still remains as a great challenge tothe optimization community due to its nonconvexity. We investigate in this projectgeneralized extended trust region subproblem (GETRS), an important subclass of QCQP.GETRS involves a nonconvex quadratic objective function, a nonconvex quadraticconstraint and a set of linear constraints, and includes generalized trust regionsubproblem (GTRS) and extended trust region subproblem (ETRS) as its special cases.Our goal is to advance the state-of-the-art of GETRS, including GTRS and ETRS, inboth theoretical and methodological aspects.It is always interesting to derive the exactness conditions under which a convexrelaxation delivers an optimal solution of the primal problem. The exactness conditionsof the semi-definite programming (SDP) relaxation of the GETRS still remain open dueto i) the quadratic forms of the GETRS may not be simultaneously diagonalizable, and ii)the feasible region of the GETRS is no longer compact and the optimal solution may beunattainable in some cases. In this research, we will reformulate the SDP relaxation as asecond-order-cone-programming (SOCP) relaxation using the canonical form developedin the PI's previous work. We will proceed to derive sufficient conditions to ensure anexact solution from the SOCP relaxation. Under such exactness conditions, weinvestigate further the attainableness under different assumptions.When expressing GTRS in its epigraph form, if we are able to identify the convex hull ofthe epigraph, we can find the exact solution. In this research, we will derive the convexhull of the intersection of a second order cone (SOC) and a quadratic under weakerconditions than the ones in the literature, which facilitates an identification of theconvex hull of the intersection of two quadratic forms. We expect our technique to beused to derive SOCP reformulation for the GTRS under some easy-to-verify conditions.Practical implementations demand fast speed algorithms for solving the GTRS. As theGTRS has a non-compact feasible region and the objective value of GTRS is not alwaysfinite, no linear-time algorithm is available in the literature. Our preliminary researchshows that, under some regular condition, we can restrict the feasible region to acompact neighborhood of an optimal solution within which the optimal value remainsinvariant (and finite). This finding will enable us to derive a linear-time algorithm forthe GTRS under some mild conditions.