Sign in Subscribe

QP (quadratic programming)

Last updated on 

Quadratic programming (QP) is a mathematical optimization problem that seeks to minimize or maximize a quadratic objective function subject to linear equality and inequality constraints. It is a special case of mathematical programming where the objective function and constraints are quadratic in nature.

The general form of a quadratic programming problem can be defined as follows:

Minimize (or maximize) f(x) = (1/2) * x^T * P * x + q^T * x + r

subject to: A * x <= b C * x = d

where:

  • x is the vector of decision variables (the values to be determined)
  • P is an n x n symmetric positive semi-definite matrix (the Hessian matrix)
  • q is an n-dimensional vector
  • r is a scalar constant
  • A is an m x n matrix representing the inequality constraints
  • b is an m-dimensional vector representing the upper bounds of the inequality constraints
  • C is a p x n matrix representing the equality constraints
  • d is a p-dimensional vector representing the right-hand side of the equality constraints

The objective function f(x) is quadratic, consisting of three parts:

  1. Quadratic term: (1/2) * x^T * P * x, where P is a symmetric positive semi-definite matrix. This term captures the quadratic relationship between the decision variables.
  2. Linear term: q^T * x, where q is a vector. This term captures the linear relationship between the decision variables.
  3. Constant term: r. This term represents any constant offset in the objective function.

The constraints in a QP problem can be classified into two types:

  1. Linear inequality constraints: A * x <= b. These constraints define upper bounds on the decision variables and restrict them to lie within certain ranges.
  2. Linear equality constraints: C * x = d. These constraints impose specific relationships between the decision variables and require them to satisfy certain equalities.

The goal of solving a QP problem is to find the optimal values of the decision variables, denoted by x*, that minimize or maximize the objective function while satisfying the given constraints. The solution to the QP problem is often referred to as the optimal solution.

There are various algorithms and solvers available to solve QP problems, such as interior-point methods, active-set methods, and quadratic programming libraries in optimization software packages. These methods employ different techniques to efficiently handle the quadratic objective function and linear constraints and find the optimal solution to the QP problem.

Quadratic programming has numerous applications in various fields, including finance, engineering, economics, and operations research. It is used to solve optimization problems involving quadratic costs or objectives and linear constraints, making it a versatile tool for modeling and solving real-world problems.