Indicator function in the OSQP algorithm

[IssamChekakta]

Hi everyone,

Currently, I'm working with OSQP solver and I'm trying to understand the math behind it. I know it uses ADMM with augmented Lagrange multiplier. I just want to understand the following steps in the algorithm from the OSQP paper. From the indicator functions introduction to ADMM iterations. What's the point of using the indicator functions here if they're not going to be used in the iteration, except for the projection onto a set in z. Thanks

[imciner2]

The indicator functions are a mathematical tool in this case to help with writing out the splitting step of the ADMM method that OSQP uses, since it will lead to an equivalent optimization problem (they act as extremal barrier terms for the constraint sets). By introducing an indicator function for both constraints, all the terms are moved into the cost function, removing any coupling in the constraints. Then we can perform the splitting into the two terms of the cost to form the subproblems.

After that, it just so happens that the Ax=z indicator function is an equality constraint, and so we can just put it back as a constraint for the first subproblem to form the equality-constrained QP, and then the second problem becomes the Eucliedean projection when we specialize it to the QP constraints initially discussed.

[IssamChekakta]

Thanks @imciner2 for your very informative comment. So, when we have only inequality constraints, we will end up with QP problem that has a projection onto a set to satisfy those constraints. And the augmented lagrangian will be constructed as usual!

[imciner2]

Yes, in this case the second problem with the inequality constraints will be a proximal operator with a 0-infinity indicator function in it in this formulation, but more generally it may be a more generic optimization problem. You can see the more general ADMM formulation in Section 3 of https://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf.