Documentation Center

  • Trials
  • Product Updates

Quadratic Programming Algorithms

Quadratic Programming Definition



interior-point-convex quadprog Algorithm

The interior-point-convex algorithm performs the following steps:

  1. Presolve/Postsolve

  2. Generate Initial Point

  3. Predictor-Corrector

  4. Multiple Corrections

  5. Total Relative Error


The algorithm begins by attempting to simplify the problem by removing redundancies and simplifying constraints. In particular, the presolve portion performs the following tasks, among others:

  • Check if any variables have equal upper and lower bounds. If so, check for feasibility, then fix and remove the variables.

  • Check if any linear inequality constraints involve just one variable. If so, check for feasibility, and change the linear constraint to a bound.

  • Check if any linear equality constraints involve just one variable. If so, check for feasibility, then fix and remove the variable.


  • Check if the bounds and linear constraints are consistent.


In the presolve step the algorithm might detect an infeasible or unbounded problem. If so, the algorithm halts and issues an appropriate exit message.

If the algorithm does not detect an infeasible or unbounded problem in the presolve step, it continues with the other steps. At the end, it reconstructs the original problem, undoing any presolve transformations. This final step is the postsolve step.

For details, see Gould and Toint [63].

Generate Initial Point

The initial point x0 for the algorithm is:







  • is the extended linear inequality matrix that includes bounds written as linear inequalities. is the corresponding linear inequality vector, including bounds.


  • z is the vector of Lagrange multipliers corresponding to s.



Definitions for the predictor step:

  • rd, the dual residual:

  • req, the primal equality constraint residual:


  • rsz, the complementarity residual:

    rsz = Sz.


  • rc, the average complementarity:




sizi = σrc.


For details, see Mehrotra [47].

Multiple Corrections


Total Relative Error



The notation and means the linear inequality coefficients, augmented with terms to represent bounds. The notation similarly represents Lagrange multipliers for the linear inequality constraints, including bound constraints. This was called z in Predictor-Corrector, and was called y.

The merit function φ is

quadprog iterative display includes a column showing the merit function under the heading Total relative error.

trust-region-reflective quadprog Algorithm









Such algorithms provide an accurate solution to Equation 6-78. However, they require time proportional to several factorizations of H. Therefore, for large-scale problems a different approach is needed. Several approximation and heuristic strategies, based on Equation 6-78, have been proposed in the literature ([42] and [50]). The approximation approach followed in Optimization Toolbox solvers is to restrict the trust-region subproblem to a two-dimensional subspace S ([39] and [42]). Once the subspace S has been computed, the work to solve Equation 6-78 is trivial even if full eigenvalue/eigenvector information is needed (since in the subspace, the problem is only two-dimensional). The dominant work has now shifted to the determination of the subspace.



or a direction of negative curvature,




  1. Formulate the two-dimensional trust-region subproblem.

  2. Solve Equation 6-78 to determine the trial step s.


  4. Adjust Δ.




Preconditioned Conjugate Gradient Method



Linear Equality Constraints


The general linear equality constrained minimization problem can be written






Box Constraints

The box constrained problem is of the form



The scaled modified Newton step arises from examining the Kuhn-Tucker necessary conditions for Equation 6-83,








The nonlinear system Equation 6-84 is not differentiable everywhere. Nondifferentiability occurs when vi = 0. You can avoid such points by maintaining strict feasibility, i.e., restricting l < x < u.

The scaled modified Newton step sk for the nonlinear system of equations given by Equation 6-84 is defined as the solution to the linear system


at the kth iteration, where






active-set quadprog Algorithm

Recall the problem quadprog addresses:


such that A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u. m is the total number of linear constraints, the sum of number of rows of A and of Aeq.

The medium-scale quadprog algorithm is an active-set strategy (also known as a projection method) similar to that of Gill et al., described in [18] and [17]. It has been modified for both Linear Programming (LP) and Quadratic Programming (QP) problems.


Active Set Iterations

In this method an active set matrix, Sk, is maintained that is an estimate of the active constraints (i.e., those that are on the constraint boundaries) at the solution point. Specifically, the active set Sk consists of the rows of Aeq, and a subset of the rows of A. Sk is updated at each iteration k, and is used to form a basis for a search direction dk. Equality constraints always remain in the active set Sk. The search direction dk is calculated and minimizes the objective function while remaining on active constraint boundaries. The feasible subspace for dk is formed from a basis Zk whose columns are orthogonal to the estimate of the active set Sk (i.e., SkZk = 0). Thus a search direction, which is formed from a linear summation of any combination of the columns of Zk, is guaranteed to remain on the boundaries of the active constraints.




Once Zk is found, a search direction dk is sought that minimizes the objective function at dk, where dk is in the null space of the active constraints. That is, dk is a linear combination of the columns of Zk: dk = Zkp for some vector p.

Then if you view the quadratic objective function as a function of p, by substituting for dk, the result is


Differentiating this with respect to p yields




The next step is


At each iteration, because of the quadratic nature of the objective function, there are only two choices of step length α. A step of unity along dk is the exact step to the minimum of the function restricted to the null space of Sk. If such a step can be taken, without violation of the constraints, then this is the solution to QP (Equation 6-88). Otherwise, the step along dk to the nearest constraint is less than unity and a new constraint is included in the active set at the next iteration. The distance to the constraint boundaries in any direction dk is given by


which is defined for constraints not in the active set, and where the direction dk is towards the constraint boundary, i.e., .



If all elements of λk are positive, xk is the optimal solution of QP (Equation 6-88). However, if any component of λk is negative, and the component does not correspond to an equality constraint, then the corresponding element is deleted from the active set and a new iterate is sought.


The algorithm requires a feasible point to start. If the initial point is not feasible, then you can find a feasible point by solving the linear programming problem


The notation Ai indicates the ith row of the matrix A. You can find a feasible point (if one exists) to Equation 6-96 by setting x to a value that satisfies the equality constraints. You can determine this value by solving an under- or overdetermined set of linear equations formed from the set of equality constraints. If there is a solution to this problem, the slack variable γ is set to the maximum inequality constraint at this point.

You can modify the preceding QP algorithm for LP problems by setting the search direction d to the steepest descent direction at each iteration, where gk is the gradient of the objective function (equal to the coefficients of the linear objective function):


If a feasible point is found using the preceding LP method, the main QP phase is entered. The search direction dk is initialized with a search direction d1 found from solving the set of linear equations



Was this topic helpful?