Problem:
I want to solve a big linearly constrained nonlinear least squares problem. The number of unknowns is between millions and billions. In terms of cost functions, the Hessian would be pretty big and dense. But it's not too difficult to compute the cost function's gradients at particular points.
The linear constraint can be represented as an intersection of two linear subspaces. Let's call them A and B. Nice properties of A and B are that I'm able to efficiently perform an orthogonal projection into either of these subspaces. But they are not necessarily orthogonal to each other. So, if given a vector g I wouldn't know to how to efficiently compute an orthogonal projection of g into the intersection of A and B.
But... if I knew how to do that I could use this kind of projection on the cost function's gradient so that a gradient-based solver would never take any steps that violate the linear constraints.
Do you see a way to efficiently perform such an orthogonal projection into the intersection of A and B?
I'm also open to other suggestions of how to solve this problem in a different way. I've recently stumbled upon the "Augmented Lagrangian method" which appears to be useful. Any (other) suggestions would be welcome!
My last resort would be to use this projection trick only for one subspace and "move" the remaining linear constraints into the cost function (--> penalty method).
The solver I've been using successfully so far (for similar but unconstrained problems) is the L-BFGS.