With respect to the complexity of the task to find a solution to nonlinear
optimization problem min_{u} c(u) subject to d(u) = 0,
two things are important: the number of iterations until convergence and the
cost per iteration. Applying a Sequential Quadratic Programming approach
to this problem is equivalent to solving the system F(u, μ) :=
(∇_{u} c(u) + \mu^{T} ∇_{u} d(u), d(u))
= 0 of nonlinear equations with a Newton-type method.

The cost per Newton iteration for the lifted problem G(u, μ, s) = 0 is higher than for the original system F(u, μ) = 0. However, the typical cubic runtime dependence on the number of variables to solve a system of linear equations can be reduced drastically by a variety of different approaches that exploit the specific structure in the function G(u, s), such as by using directional derivatives, parallelizable condensing, structure-exploiting (iterative) linear algebra, or a relaxation of the matching constraints in a dual nonsmooth Newton setting.

The lifting approach has a variety of direct advantages, such as the
possibilities for parallelization of function and derivative evaluation,
initialization also of lifted variables s_{0}, e.g., in parameter
estimation or tracking problems, and the avoidance of singularities of
function evaluation for bad choices of u_{0}.

But it is not clear how to choose s_{i} in an optimal way. Therefore,
there is the open question whether it is possible to come up with a systematic
approach to decide how many and which s_{i} should be used to minimize
the (average) number of iterations.