QCQP quadratically constrained quadratic program
A quadratically constrained quadratic program (QCQP) is an optimization problem that involves optimizing a quadratic objective function subject to quadratic constraints. It is a generalization of the quadratic programming problem where the constraints are linear.
The general form of a QCQP can be expressed as follows:
Minimize: f(x) = (1/2) * x^T * Q0 * x + c0^T * x
Subject to: (1/2) * x^T * Qi * x + ci^T * x + di <= 0, for i = 1, 2, ..., m Ai * x = bi, for i = 1, 2, ..., p xi in R^n, for i = 1, 2, ..., n
where:
- x is the vector of optimization variables of dimension n,
- f(x) is the objective function to be minimized,
- Q0 is an n x n symmetric positive semi-definite matrix,
- c0 is a vector of coefficients of dimension n,
- Qi are n x n symmetric matrices,
- ci are vectors of coefficients of dimension n,
- di are scalar coefficients,
- Ai are constraint matrices of dimension p x n,
- bi are vectors of constraint values of dimension p,
- m is the number of quadratic constraints, and
- p is the number of linear equality constraints.
The objective function f(x) is a quadratic form that represents the cost or objective to be minimized. The matrix Q0 determines the quadratic terms, while the vector c0 represents the linear terms.
The constraints in a QCQP are quadratic inequalities and/or linear equalities. The quadratic inequalities are expressed as (1/2) * x^T * Qi * x + ci^T * x + di <= 0, where Qi is a symmetric matrix, ci is a vector of coefficients, and di is a scalar constant. These inequalities define regions in the solution space that the optimization variables must satisfy.
The linear equalities are expressed as Ai * x = bi, where Ai is a constraint matrix and bi is a vector of constraint values. These equations impose linear constraints on the optimization variables.
Solving a QCQP involves finding the values of the optimization variables x that minimize the objective function f(x) while satisfying the quadratic inequalities and linear equalities. The solution can be obtained using various optimization algorithms, such as interior-point methods or active set methods.
QCQPs find applications in various fields, including engineering, economics, finance, and operations research. They can model and solve a wide range of problems, such as portfolio optimization, optimal control, optimal resource allocation, and quadratic assignment problems.