For all of the success applying GPUs to optimization problems in ML, why don't any of the common optimization packages seem to support GPU acceleration?
Ceres can use GPUs for some solver bits too, I believe.
Google for linear programming gpu acceleration to see for yourself
The second approach is model-specific, and gives you nice speedups (make your model N times faster, and you will converge N times faster), but is often not particularly well-suited for accelerators (which includes GPUs) due to the latency of moving data back and forth, but again with model-specific tuning you can maybe make it work. Most of the time SIMD on CPU is best here for most traditional problems.
The first approach, which already pretty much requires the second so that the model and the optimization can run on the same computing unit, well it isn't particularly great since you're doing computations that are suboptimal and/or redundant to begin with. Any speedup isn't obvious, depends on the optimization algorithm and the convergence characteristics of your problem. Also as you follow along some paths in parallel, you'll eventually need to sync up, and since they have divergent control flow, this means you're not able to make the most of the computing resources which will be stalling quite often. Often, with enough tuning for your particular problem and method, you can make it work.
So why don't generic libraries do it on GPU? Because unless you tune everything for your particular problem, it's just not going to perform as well as on CPU.
More generally, there's a question of where the algorithms themselves benefit from GPUs or parallelism in general. For large scale nonlinear, continuous optimization problems using second-order, Newton like methods, the big costs are in the function evaluations, their derivatives, and the linear system preconditioners/solves. Generally speaking, how the function evaluations and derivatives are computed are on the user. For the preconditioning/linear system solves, there's value in parallelism. However, here, the GPUs have traditionally lagged. Basically, we need a factorization, be it sparse or dense, and it's only been recently where good library support has been extended for GPUs. For the longest time, the entire matrix factorization needed to fit onto the GPU and many of these matrices were large. That said, for optimizers that accept a user-defined preconditioner, the use of GPUs is already possible.