Quadratic Programming (QP)

When the objective function is quadratic but constraints are linear, the optimization problem is said to be a quadratic programming (QP) problem. The general form of a QP problem is given as follows:

where $c \in \R^d$, $A \in \R^{m \times d}$, $b \in \R^m$, and $Q \in \R^{d \times d}$ is a positive definite square matrix.

Here, the set $\mathcal{F} = \{ x \in \R^d \ \text{s.t} \ Ax \leq b \}$ is known as the feasible set because it maps the region that satisfies all the constraints. Like LP, the feasible set is a convex polyhedron because it is the intersection of a finite number of half-spaces and hyperplanes.

Example

Consider the portfolio optimization problem where the task is to find the best allocation of assets—such as stocks, bonds, or cash—that maximizes the expected return and minimizes the risk of a portfolio. Let’s say we have the following three types of assets to choose from:

• Stocks that give an expected return of $15\%$ but have a higher risk component (or variance) of $20$

• Bonds that give an expected return of $7\%$ and have a medium risk component (or variance) of $10$

• Cash that gives an expected return of $2\%$ and has low risk component (or variance) of $5$

Considering that we want to assign $x_1, x_2, x_3$ as the fractions of the portfolio to stocks, bonds, and cash, respectively, the asset weights should sum to one. At the same time, we would like to generate a collective return of at least $10\%$ on the whole portfolio. The constraints can be written as follows:

With these constraints, we need to find the asset allocation that yields the minimum risk $R(x)$. The risk is proportional to the variance of the portfolio return, which will be a quadratic function of the asset weights.

Note: $x_1 + x_2 + x_3 \leq 1$ ...