QCQP

QCQP stands for Quadratically Constrained Quadratic Program, a class of optimization problems in which both the objective and the constraints are quadratic functions of the decision vector x. Formally, the problem can be written as minimize x^T P x + q^T x + r subject to x^T A_i x + b_i^T x + c_i ≤ 0 for i = 1,...,m, where P, A_i are symmetric matrices and q, b_i, r, c_i are vectors and scalars of appropriate dimensions. Equality constraints can also be incorporated by setting the right-hand side to zero.

Convexity plays a central role in QCQPs. If the objective matrix P is positive semidefinite and every constraint matrix A_i is positive semidefinite (for inequality constraints), the problem is convex and can be solved to global optimality by convex optimization techniques, such as interior-point methods or semidefinite programming (SDP) relaxations. Non-convex QCQPs, where these conditions fail, are generally hard and may be NP-hard in general.

Common solution approaches include SDP relaxations (notably Shor’s relaxation), Lagrangian dual methods, and globalOptimization techniques such as branch-and-bound. In practice, people also use problem-specific heuristics and convex-concave procedures for certain structured QCQPs.

Applications span engineering and science, including control design with quadratic costs and constraints, power systems and optimal power flow problems, signal processing, wireless communications, computer vision, and portfolio optimization. Special cases include the trust-region subproblem, where the constraint restricts the solution to a ball, and certain generalized eigenvalue problems.