Efficiency with atomic operations

[pierslawrence]

I am looking for a way to improve the efficiency of optimizing a quadratic function using atomic operations in CppAD. The basic prototypical function I have in mind is

f: R^n->R
f(x) = 1/2*x^T*A*x+b^T*x

where x is a vector of length n, A is a positive definite n x n matrix and b is a vector of length n. Normally, I have a more complicated function, but I think it will suffice for simplicity to work with f(x).

The problem I have is to solve a constrained minimization problem using Ipopt (see, for example, Nonlinear Programming Using CppAD and Ipopt: Example and Test).

Now, in that example, the objective is specified and taped, but I am wondering if/how the computations could be made more efficient by defining the objective function as an atomic operation and providing the analytic gradient/Hessian. In my more general problem, the constraint equations could be quite general, so I want to keep the regular CppAD approach to differentiating those equations for the solution of the nonlinear optimization problem.

What I have done so far is to define f(x) as an atomic operation inheriting from CppAD::atomic_base, given that the function is quadratic, the implementation of the forward mode is quite simple, the reverse mode is only slightly more difficult (it is a pity that the documentation does not include an example of reverse mode for a scalar function of many variables, I think that would be quite constructive).

My more general question: is this approach likely to actually bring a significant speedup? I tried with a simple 2x2 case, and the results were not very promising, the Hessian computation of the atomic function is actually slower than the equivalent for the taped operation (is this to be expected?).

[bradbell]

There is an option in the speed tests to compare atomic matrix multiply with just coding a matrix multiply; see
https://coin-or.github.io/CppAD/doc/speed_main.htm#Global%20Options.atomic

I think your problem is that there is an overhead to interfacing to an atomic function and it should have a significant amount of calculation to make it worth while from a speed perspective (note that atomic functions also reduce the necessary memory which for large problems is important).

Perhaps if you made matrix multiplication an atomic operation it would do what you want an have more general applications. There are some examples about this; see
https://coin-or.github.io/CppAD/doc/atomic_three_mat_mul.cpp.htm
https://coin-or.github.io/CppAD/doc/atomic_two_eigen_mat_mul.cpp.htm

More generally, it would be nice for someone to make a CppAD add on that has a nice set of atomic matrix operations (including sparse operations).

Note that I should convert the Eigen matrix multiply example to the atomic three interface, but I have not gotten around to that.

[pierslawrence]

I think that would be really great if there was a plain vanilla mat-vec multiply. I have been following my way through most of the CppAD documentation, and often find that the examples are either too simple or too complex. There needs to be something in between.

In terms of the problems I am facing: I can, of course, just code the gradient and Hessian computations on their own, I imagine that this would avoid all of the overhead surrounding the AD. However, the crux is when it comes to mixing those outputs with the constraints in the non-linear optimization. I am really not sure exactly how to go about doing this in a good way (hence the use of the atomic operation replacing the function evaluation/taping).

It would be nice to know if others have encountered a similar need, and perhaps some smart cookies have discovered a sensible way of doing this mixing?

[bradbell]

It may be that the CppADCodeGen project has what you want and even better; see
https://github.com/joaoleal/CppADCodeGen

[bradbell]

I am moving this issue to discussion #82