New package: NewtonCQK.jl

Specific Domains Optimization (Mathematical)
1

Hi,

I would like to announce a new Julia package named NewtonCQK.jl. It implements a semismooth Newton method to solve the Continuous Quadratick Knapsack problem

\min_x \frac{1}{2}x^tDx - a^tx \quad \text{s.t.} \quad b^tx = r, \ l \leq x \leq u,

where D is a positve diagonal, a, b, l, u are vectors and r is a scalar. You can think of it as “projecting onto the intersection of a box and a hyperplane”.

The implementation has many features:

  • It has specialized code for projecting onto a Simplex and onto a \ell_1 ball.
  • It is fast. Faster than Condat implementation for the Simplex and \ell_1 ball and almost as fast as the original C code for the general case.
  • It allows to return the solution as a sparse vector (nonzero coordinate indexes and values) or as a full vector.
  • It can use multiple threads (thanks to OhMyThread.jl) in a multicore setting. It scales very well for large problems (up to consuming all memory bandwidth).
  • It can run on NVidia GPUs (it should be trivial to make it run on AMD GPUs too, but I don’t have one to test). For the general case the GPU implementation is up to 185 faster than the serial code for very large problems (10^8 variables).
  • It allows for hotstart: it can use the last point in an iterative procedure (where it is called at each iteration) that has potential for further speed up.

The implementation is described in a technical report that is submitted for publication.

At this moment it is only available directly from Github, but I plan to add the package to the registry soon. It still needs better documentation and tests.

Fun fact: what is faster for n=10^9, call zero(n) or project a random n-dimensional vector onto the unit Simplex? If you accept the solution as a sparse vector, the projection is faster.

Have fun!

3 Likes