Quadratic Programming Example Using CVXPY

Quadratic Programming Example Using CVXPY

$Quadratic Programming (QP)$ is an optimization problem where the objective function is quadratic, and the constraints are linear.

A typical $QP$ problem can be written as:

$$
\text{Minimize } \frac{1}{2} x^T Q x + c^T x
$$
subject to:
$$
Ax \leq b \quad \text{and} \quad Ex = d
$$

Where:

  • $( Q )$ is a positive semi-definite matrix (for convexity),
  • $( c )$ is a vector of linear coefficients,
  • $( A )$, $( b )$, $( E )$, and $( d )$ represent the inequality and equality constraints, respectively.

Example: Portfolio Optimization

We will solve a portfolio optimization problem using $QP$.

The goal is to minimize the risk (variance) of a portfolio, subject to achieving a certain return and satisfying investment constraints.

Problem Formulation:

  • Objective: Minimize the portfolio’s risk, measured as the variance of returns.
  • Constraints:
    • The total weight of assets must sum to $1$ (fully invested).
    • Each weight must be non-negative (no short selling).
    • The portfolio’s expected return must be at least a target return.

Data Setup:

  • The problem has 3 assets with the following parameters:
    • Expected returns: $([0.1, 0.2, 0.15])$
    • Covariance matrix (risk):
      $$
      \begin{pmatrix}
      0.005 & -0.010 & 0.004 \
      -0.010 & 0.040 & -0.002 \
      0.004 & -0.002 & 0.023 \
      \end{pmatrix}
      $$
    • Target return: $(0.16)$

Step-by-Step Solution:

  1. Define the Variables and Problem:
    Let $( x = \begin{bmatrix} x_1 \ x_2 \ x_3 \end{bmatrix} )$ represent the weights of the three assets in the portfolio.

  2. Objective:
    The objective is to minimize the variance (quadratic term):
    $$
    \frac{1}{2} x^T Q x
    $$
    where $( Q )$ is the covariance matrix of the asset returns.

  3. Constraints:

    • The sum of portfolio weights must be 1: $( x_1 + x_2 + x_3 = 1 )$
    • The expected return of the portfolio must be at least $(0.16)$:

    $$
    0.1x_1 + 0.2x_2 + 0.15x_3 \geq 0.16
    $$

    • No short selling: $( x_1, x_2, x_3 \geq 0 )$

Python Implementation:

We will use the $cvxpy$ library to solve this $QP$ problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import cvxpy as cp
import numpy as np

# Step 1: Define the problem data
Q = np.array([[0.005, -0.010, 0.004],
              [-0.010, 0.040, -0.002],
              [0.004, -0.002, 0.023]])  # Covariance matrix

expected_returns = np.array([0.1, 0.2, 0.15])  # Expected returns for the assets
target_return = 0.16  # Target portfolio return

# Step 2: Define the decision variable (portfolio weights)
x = cp.Variable(3)

# Step 3: Define the objective function (minimize variance)
objective = cp.Minimize((1/2) * cp.quad_form(x, Q))

# Step 4: Define the constraints
constraints = [
    cp.sum(x) == 1,  # Fully invested (weights sum to 1)
    expected_returns @ x >= target_return,  # Target return constraint
    x >= 0  # No short selling constraint
]

# Step 5: Formulate the problem
problem = cp.Problem(objective, constraints)

# Step 6: Solve the problem
problem.solve()

# Step 7: Output results
print("Status:", problem.status)
print("Optimal portfolio allocation:", x.value)
print("Minimum risk (variance):", problem.value)

Detailed Explanation:

  1. Covariance Matrix ( Q ):
    This matrix represents the risk (variance and covariance) associated with the assets in the portfolio.
    The term cp.quad_form(x, Q) calculates the quadratic form $( x^T Q x )$, representing the portfolio variance.

  2. Objective Function:
    The objective is to minimize the portfolio variance.
    In cvxpy, we use the cp.Minimize() function, where the quadratic form represents the risk.

  3. Constraints:

    • Fully Invested: cp.sum(x) == 1 ensures that the portfolio is fully invested (the weights sum to 1).
    • Target Return: expected_returns @ x >= target_return ensures that the portfolio’s expected return is at least $0.16$.
    • No Short Selling: x >= 0 ensures that no asset has a negative weight (i.e., no short selling).

  4. Solve the Problem:
    The problem.solve() function solves the $QP$ problem and finds the optimal portfolio allocation that minimizes risk while satisfying all the constraints.

Output:

1
2
3
Status: optimal
Optimal portfolio allocation: [0.26055046 0.46055046 0.27889908]
Minimum risk (variance): 0.004140183486238534

Interpretation of Results:

  • Optimal Portfolio Allocation:
    The optimal weights for the assets are approximately $26.06$% in Asset $1$, $46.06$% in Asset $2$, and $27.89$% in Asset $3$.
    These weights minimize the portfolio variance while achieving the target return.

  • Minimum Risk:
    The minimum variance (risk) is approximately $0.00414$.
    This represents the lowest possible portfolio risk that satisfies the return constraint.

Conclusion:

This example demonstrates how to solve a quadratic programming problem using Python’s $cvxpy$ library.

The problem was formulated as a portfolio optimization task, where we minimized risk subject to return and no-short-selling constraints.