The dual QP solver of Goldfarb and Idnani

Directly to the input form - predefined cases

Directly to the input form - user defined testcase

• The method of Goldfarb and Idnani solves strictly convex quadratic optimization problems of the form
  f(x) = 1/2 x^TGx -g₀^Tx = min_x ,
  subject to the constraints
  H^Tx+h₀ = 0,
  C^Tx + c₀ >= 0 .
  
• The matrix G of dimension n is assumed as symmetric and positive definite. This is checked first using its Cholesky decomposition. The matrix H (with dimension n × p) must have rank p. If these conditions are not met, the code terminates unsuccessfully. The column number of C and hence the number of inequality constraints is m. Of course p or m can be zero.
• The necessary and sufficient optimality conditions for the solution are
  
  • Gx-g₀ - H μ - C λ = 0 ,
    
  • h(x) = H^Tx+h₀ = 0 ,
    
  • g(x) = C^Tx + c₀ >= 0 ,
    
  • min{ λ , C^Tx + c₀ } = 0
    the ''min'' to be understood componentwise.
• μ and λ are the so called Lagrange multipliers. The fourth condition means that one of the multipliers λ_i and its corresponding constraint g_i(x) can never simultaneously be strictly larger than zero, or in other terms, that at most multipliers corresponding to ''active'' constraints (those which are at their lower bound) can play a role in the optimality test and that the λ_i can never be negative.
• The method first solves the purely equality constrained problem. This could be done in different ways, we use here the general scheme of the method, beginning with the unconstrained minimizer G^-1g₀ and subsequently satisfying one equality constraint after the other by adding it to the ''active set''. These equality constraints never leave the active set. Together with the current x one also has the currrent multipliers for the subproblem.
• Next the problem is solved on subsets J of the set {1,...,m}. Beginning with the empty set for J one adds one violated inequality constraint to the active set and tries to solve the so obtained new equality constrained problem. This results in a correction direction for x as well as for the current multipliers. In the simplest case the added inequality becomes satisfied first following this path and the new subproblem is solved. This is a ''full step'' in this code. If x is now feasible for all constraints, the solution process is complete.
• It may occur that along this mentioned linear path one (or more) of the currently strictly positive multipliers λ_i, i in J becomes zero: the movement stops there and the corresponding constraints are removed from the active set, a new path direction is obtained (with the aim to satisfy the selected inequality constraint being unchanged). This can occur several times. These steps are named ''partial steps'' here. Their number is necessarily finite and since a constraint, once satisfied, never can become violated later, the method is finite.
• The objective function increases here (weakly) monotonically and the infeasibility decreases, whereas the dual variables μ and λ always satisfy their constraints: this gives the method its characterization as a dual solver.

To the input form - predefined cases

To the input form - user defined testcase