Quadratic Program

Introduction

A quadratic program is an optimization problem with a quadratic objective and affine equality and inequality constraints. A common standard form is the following:

$$\begin{array}{ll}\text{minimize}& (1/2)x^{T}Px+q^{T}x\\ \text{subject to}& Gx\le h\\ & Ax=b.\end{array}$$

Here $P\in {\mathcal{S}}_{+}^n$, $q\in {\mathcal{R}}^n$, $G\in {\mathcal{R}}^{m\times n}$, $h\in {\mathcal{R}}^m$, $A\in {\mathcal{R}}^{p\times n}$, and $b\in {\mathcal{R}}^p$ are problem data and $x\in {\mathcal{R}}^n$ is the optimization variable. The inequality constraint $Gx\le h$ is elementwise.

A simple example of a quadratic program arises in finance. Suppose we have $n$ different stocks, an estimate $r\in {\mathcal{R}}^n$ of the expected return on each stock, and an estimate $\mathrm{\Sigma }\in {\mathcal{S}}_{+}^n$ of the covariance of the returns. Then we solve the optimization problem

$$\begin{array}{ll}\text{minimize}& (1/2)x^T\mathrm{\Sigma }x-r^{T}x\\ \text{subject to}& x\ge 0\\ & {\mathbf{1}}^{T}x=1,\end{array}$$

to find a portfolio allocation $x\in {\mathcal{R}}_{+}^n$ that optimally balances expected return and variance of return.

When we solve a quadratic program, in addition to a solution $x^{\star }$, we obtain a dual solution ${\lambda }^{\star }$ corresponding to the inequality constraints. A positive entry ${\lambda }_i^{\star }$ indicates that the constraint $g_i^{T}x\le h_i$ holds with equality for $x^{\star }$ and suggests that changing $h_i$ would change the optimal value.

Example

In the following code, we solve a quadratic program with CVXR.

## Generate a random non-trivial quadratic program.
## Construct h and b from a known feasible point x0
## to guarantee joint feasibility of the constraints.
set.seed(1)
m <- 15
n <- 10
p <- 5
P <- matrix(rnorm(n * n), nrow = n, ncol = n)
P <- t(P) %*% P
q <- rnorm(n)
G <- matrix(rnorm(m * n), nrow = m, ncol = n)
A <- matrix(rnorm(p * n), nrow = p, ncol = n)
x0 <- rnorm(n)
h <- G %*% x0 + abs(rnorm(m))
b <- A %*% x0

## Define and solve the CVXR problem
x <- Variable(n)
ineq_con <- G %*% x <= h
eq_con <- A %*% x == b
prob <- Problem(Minimize(0.5 * quad_form(x, P) + t(q) %*% x),
                constraints = list(ineq_con, eq_con))
result <- psolve(prob)
check_solver_status(prob)

## Print result
cat(sprintf("The optimal value is %f\n", result))
cat("A solution x is\n")
print(value(x))
cat("A dual solution corresponding to the inequality constraints is\n")
print(dual_value(ineq_con))

The optimal value is 10.511135
A solution x is
             [,1]
 [1,]  1.02038881
 [2,]  0.65071749
 [3,] -0.21167231
 [4,] -0.54479000
 [5,]  0.00227552
 [6,]  1.03862768
 [7,] -0.20833046
 [8,]  0.44450188
 [9,] -1.15910026
[10,]  0.27972523
A dual solution corresponding to the inequality constraints is
 [1] 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.303641 2.879660
 [9] 0.000000 0.000000 2.467416 0.000000 0.000000 0.000000 8.135815

Session Info

R version 4.5.2 (2025-10-31)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices datasets  utils     methods   base     

other attached packages:
[1] CVXR_1.8.0.9213

loaded via a namespace (and not attached):
 [1] slam_0.1-55       cli_3.6.5         knitr_1.51        ECOSolveR_0.6.1  
 [5] rlang_1.1.7       xfun_0.56         clarabel_0.11.2   gurobi_13.0-1    
 [9] otel_0.2.0        Rglpk_0.6-5.1     highs_1.12.0-3    cccp_0.3-3       
[13] scs_3.2.7         S7_0.2.1          jsonlite_2.0.0    Rcplex_0.3-8     
[17] backports_1.5.0   Rmosek_11.1.1     rprojroot_2.1.1   htmltools_0.5.9  
[21] gmp_0.7-5.1       piqp_0.6.2        rmarkdown_2.30    grid_4.5.2       
[25] evaluate_1.0.5    fastmap_1.2.0     yaml_2.3.12       compiler_4.5.2   
[29] codetools_0.2-20  htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2       
[33] osqp_1.0.0        lattice_0.22-9    digest_0.6.39     checkmate_2.3.4  
[37] Matrix_1.7-4      tools_4.5.2      

References