NASOQ algorithm
Algorithm overview
NASOQ focuses on the solution of convex quadratic programming problems to find the linearly constrained minimizers of quadratic energies. In full generality our problem then is \begin{align} \label{eq:qp} \min_x \quad \frac{1}{2} x^THx + q^Tx \quad \text{s.t.} \quad Ax=b, \quad C x\leq d \end{align} where the unknown minimizer x \in \mathbb{R}^n is constrained by linear equality constraints A x=b and inequality constraints Cx\leq d. Note that in many cases, we may have only inequality or equality constraints. However, in the following, without loss of generality, we consider the full mixed case. Here the symmetric matrix H is, either by construction or standard user regularization, a positivedefinite matrix, thus the QP is strictly convex.
NASOQ is an activeset QP solver based on GoldfarbIdnani (GI) [Goldfarb and Idnani, 1983] strategy. Activeset methods start with a feasible solution and keep a running set of proposed active inequality constraints \mathcal{W} to reach the optimal solution while maintaining feasibility conditions. Activeset methods are then either primalfeasible, preserving the primalfeasibility condition or else are dualfeasible, preserving the nonnegativity condition. GI is a dualfeasible activeset approach, and so enables direct and inexpensive initialization.
NASOQ begins by initializing an empty activeset proposal, \mathcal{W} = \emptyset with zero dual variables, z_0 = 0. The resulting initial KKT system to solve is then the indefinite linear system,
Then, each successive iteration of NASOQ improves the last iterate's solution by updating the activeset proposal \mathcal{W} and so the corresponding activeset constraint matrix C_{\mathcal{W}} and the righthand side constraint vector c_{w}. The NASOQ algorithm updates the active set by only adding one or removing one constraint in each successive iteration. Here w is the activated constraint. The next descent direction for the QP is then determined by solving the updated KKT system,
The dual and primal variables of the next iteration are then updated by finding step lengths along the computed descent directions, i.e., \Delta x, \Delta y, \Delta z. The step lengths ensure that the activated constraint becomes primalfeasible and all dual variables remain dualfeasible. Thus, in each iteration, both the dual and primal variables corresponding to the constraints in the active set are both nonnegative and primalfeasible.
Variants
NASOQ has two variants: NASOQFixed and NASOQTuned, and each of these two variants individually offers a different balance in the tradeoff between efficiency and accuracy for largerscale problems. A key feature of NASOQ is that in our construction of the linear system solver, i.e., LBL and the row modification, i.e., SoMoD we expose three parameters with direct and intuitive interpretations that enable us to balance efficiency against accuracy for different applications and problem scales. These three parameters are:

max_iter: the maximum number of refinement iterations for incrementally improving the solution of a KKT system after the solve phase;

stop_tol: the threshold defining the upper bound for the residual accuracy of the KKT system during the refinement phase;

diag_perturb: value added to zeroentry diagonals of the KKT matrix to stabilize LBL and row modification in SoMod.
NASOQFixed works well across the board without changing a default setting. To use NASOQFixed, you can set nasoq>variant = Fixed
. NASOQFixed settings are slightly different from the settings in the siggraph2020 paper. The max_iter
parameter in the new settings is decremented by one so it runs faster.
NASOQTuned uses a range of reasonable settings for these three parameters known as a priori, to perform a rapid sweep for improved accuracy. The setting for activating NASOQTuned is:
nasoq>variant = Tuned
(This mode has not been included in the API yet).
Termination criteria
The termination criteria in NASOQ are four conditions that are listed below:

Primalfeasibility: \Big( (Axb)^T, (\max(\textbf{0},Cxd))^T \Big)^T \ < \epsilon_f

Stationarity: Hx + q + A^{T}y + C^{T}z\ < \epsilon_s

Complementarity: z \odot (Cxd)\ < \epsilon_c, Here \odot is the Hadamard (elementwise) product.

Nonnegativity:\min(\textbf{0},z)\ < \epsilon_n
We design NASOQ and analyze QP methods on their ability to drive all four of these measures (\inftynorm) below a common, maximum error threshold accuracy: \epsilon \geq \max(\epsilon_f,\epsilon_s,\epsilon_c,\epsilon_n).
While necessary accuracies for each of the four measures certainly change per application, a desirable goal for a generalpurpose QP algorithm is to solve every reasonable problem to any requested accuracy.
Here we design for generalpurpose QP problems and so do not predict a priori what measures are most important. Thus we evaluate fitness by asking each solve to drive all measures below \epsilon. To set the accuracy threshold in NASOQ, you may use the following:
nasoq>eps_abs = 1e3;
Settings
The three different parameters, max_iter, stop_tol, diag_perturb that exist in NASOQ, often show a significant effect on the performance and accuracy of the solver. Also, requesting a more accurate solution, i.e., lower termination criteria or eps_abs
often leads to much more number of iterations and thus slower convergence time.
NASOQ has some predefined variants, i.e., fixed and tuned. NASOQTuned is designed conservatively for the lowest failure rate. NASOQFixed often provides a reasonable balance between balance and failurerate. However, a customized setting can lead to better performance if the requirements of the application are known.
Here we provide a few suggestions based on our experience with working with different real applications:
Setting Property  NASOQ Variant  max_iter  stop_tol  diag_perturb  eps_abs  Example Applications 

Low accuracy and fast  PREDET  0  1e15  1e9  1e3  Geometry processing, Model reconstruction 
accurate enough  PREDET  1  1e15  1e9  1e6  Contact simulations, Control 
The PREDET
variant of NASOQ is a variant that takes the input settings determined by the user. If you are not sure, you may start with the fixed variant of NASOQ.
You can also set the maximum number of NASOQ solver iterations by setting max_iter_nas
. After NASOQ's iterations reach this number, it terminates and returns the last solution.
Return value
NASOQ solver return value has four states:
0:Infeasible
the problem is unbounded.
1:Optimal
When primalfeasibility, stationary, and nonnegativity are satisfied.
2:Inaccurate
only primalfeasibility is satisfied.
3:NotConverged
None of the termination criteria are satisfied.