sqp (version 0.5)

qp_solver: Quadratic optimization solver

Description

Dense & Sparse solvers for linearly constrained quadratic optimization problems @cf. @fletcher71; @nocedal99; @powell78; @wilson63sqp.

Usage

qp_solver(
  Q,
  C_eq = NULL,
  C_ineq = NULL,
  l = NULL,
  t_eq = NULL,
  t_ineq = NULL,
  x = NULL,
  penalty = 1e+10,
  tol = 1e-07,
  max_iter = 500,
  fast = FALSE,
  all_slack = FALSE,
  debug = FALSE,
  solver = 0
)

Arguments

Q, C_eq, C_ineq

Dense or sparse numeric matrices:

Q

\(N \times N\)-matrix: Quadratic distance (loss) multiplier for the optimization problem.

C_eq

\(N_{eq} \times N\)-matrix: Equality constraint multiplier for the \(N_{eq}\) equality constraints.

C_ineq

\(N_{ineq} \times N\)-matrix: Inequality constraint multiplier for the \(N_{ineq}\) inequality constraints.

l, t_eq, t_ineq

Numeric vectors:

l

Vector of size \(N\): Linear distance (loss) multiplier for the optimization problem.

t_eq

Vector of size \(N_{eq}\): Targets for equality constraints.

t_ineq

Vector of size \(N_{ineq}\): upper bound for inequality constraints.

x

Numeric vector of size N: Initial values for optimization parameters. Slack variables are only used for constraints violated by this x, unless all_slack is TRUE.

penalty

Numeric value: Penalty multiplier for slack variables in distance function.

tol

Numeric value: Tolerance for assessing convgergence criteria & constraints.

max_iter

Integer value: Tolerance for assessing convgergence criteria & constraints.

fast

Boolean: Whether to use faster (but lower quality) solver (cf. Armadillo documentation: fast mode: disable determining solution quality via rcond, disable iterative refinement, disable equilibration.

all_slack

Boolean: Whether to use slack variables for all constraints instead of only for the ones violated by the initial values

debug

Boolean: Whether to print debugging status messages.

solver

Solver identification used for optimization in the dense matrix case. Not yet used.

Value

A named list with values

x

Final values for optimization parameters

lagrange_eq, lagrange_ineq

Lagrange multipliers for equality and inequality constraints

slack_eq_positive, slack_eq_negative

Positive and negative slack variables for equality constraints

slack_ineq

Slack variables for inequalits constraints

lagrange_slack_eq_positive, lagrange_slack_eq_negative, lagrange_slack_ineq

Lagrange multipliers for positivity of slack variables

Details

Sequential quadratic programming relies on iteratively solving linear approximations of the optimality conditions @cf. @kjeldsen00; @kuhn51sqp.

This is equivalent to minimizing a quadratic approximation of the distance function under linearised constraint functions. qp_solver can be used to solve this quadratic sub-problem. Solving a quadratic problem under linear equalits constraints is equivalent to solving a system of linear equations. The inequality constraints are handeled by an active set strategy, where the binding ones are treated as equalities, and the active set is found iteratively @cf. @fletcher71; @nocedal99; @powell78; @wilson63sqp.

References

Examples

# NOT RUN {
set.seed(1)
n <- 5

x_init <- cbind(runif(n))

w <- runif(n)

Q <- 3*diag(n) # minimize sum(3*x^2 + 3*x)
l <- cbind(rep(3,n)) # minimize sum(3*x^2 + 3*x)

C_eq <- rbind(1,w) # constraints: sum(x) == 1, sum(w*x) == 5
C_ineq <- rbind(diag(n),-diag(n)) # constraints: all(x >= -4) & all(x <= 4)

t_eq <- rbind(1,5) # constraints: sum(x) == 1, sum(w*x) == 5 
t_ineq <- cbind(rep(c(4,4),each=n)) # constraints: all(x >= -4) & all(x <= 4) 

output <- qp_solver(Q = Q,
               C_eq = C_eq,
               C_ineq = C_ineq,
               l=l,
               t_eq = t_eq,
               t_ineq = t_ineq,
               x = x_init,
               tol = 1e-15)


sum(output$x) # constraints: sum(x) == 1
sum(w*output$x) # constraints: sum(w*x) == 5

all(output$x >= -4) # constraints: all(x >= -4)
all(output$x <= 4) # constraints: all(x <= 4)

# }