Minor iterations

Solving the QP subproblem is itself an iterative procedure, with the minor iterations of an SQP method being the iterations of the QP method.  At each minor iteration, the constraints Ax - s = b are (conceptually) partitioned into the form

Bx_B + Sx_s +  Nx_N  = b,

where the basis matrix B is square and nonsingular.  The elements of x_B, x_s and x_N are called the basic, superbasic and nonbasic variables respectively; they are a permutation of the elements of x and s.  At a QP solution, the basic and superbasic variables will lie somewhere between their bounds, while the nonbasic variables will be equal to one of their upper or lower bounds.  At each iteration, x_s is regarded as a set of independent variables that are free to move in any desired direction, namely one that will improve the value of the QP objective (or the sum of infeasibilities). The basic variables are then adjusted in order to ensure that (x, s) continues to satisfy Ax - s = b.  The number of superbasic variables (n_s say) therefore indicates the number of degrees of freedom remaining after the constraints have been satisfied. In broad terms, n_s is a measure of how nonlinear the problem is. In particular, n_s will always be zero for LP problems.
 
If it appears that no improvement can be made with the current definition of B, S and N, a nonbasic variable is selected to be added to S, and the process is repeated with the value of n_s increased by one. At all stages, if a basic or superbasic variable encounters one of its bounds, the variables is made nonbasic and the value of n_s is decreased by one.

Associated with each of the m equality constraints Ax - s = b are the dual variables p.  Similarly, each variable in (x, s)  has an associated reduced gradient d_j .  The reduced gradients for the variables x are the quantities g - ATp, where g is the gradient of the QP objective, and the reduced gradients for the slacks are the dual variables p.  The QP subproblem is optimal if d_j0 for all nonbasic variables at their lower bounds, d_j0 for all nonbasic variables at their upper bounds, and d_j = 0 for other variables, including superbasics.  In practice, an approximate QP solution is found by relaxing these conditions on d_j (see the Minor optimality tolerance described in Section Description of the optional parameters).