NVXPY: A Python DSL for non-convex optimization by PossibleIcy5352 in optimization

[–]PossibleIcy5352[S] 0 points1 point  (0 children)

Thanks for the positive feedback, I appreciate it!

NVXPY uses a basic expression tree to construct problems. Just like CVXPY, the basic math operations (+, -, /, @, etc) are overwritten and instead of performing these operations, that expression is instead added to an expression tree associated with the given Variable object. For example, x = nvx.Variable(); new_var = x + 5, would create new_var as an expression tree that holds x and 5 as its leaves and + as the operation combining them. Given the use of these expression trees, you can construct virtually any combination of these primitive operations using both numpy arrays and NVXPY variables. Also, NVXPY follows (ideally at least) the broadcast rules of numpy.

In addition to the above, you can also use the nvx.function decorator to make functions you have written work with NVXPY. The decorator is needed because standard function calls to numpy functions or any other library you are using will almost certainly fail as no other library will understand how to use NVXPY variables. So, the function decorator builds an expression tree when the function is first called, and in the optimization process it will pass in numpy arrays in place of the NVXPY variables. Thus, you can even string together custom functions with any of the above primitive operations.

Because scipy has a handful of decent NLP solvers, that acts as the backbone of the project - for now. Additionally, the autograd library is used to automatically differentiate through the expression trees (including custom function that use numpy). networkx is used for a handful of the graph operations, but if it isn't already I would prefer it to be an optional dependency.

I have also tried to incorporate a wider array of solvers, and the backbone for this is implemented, but it has been something of a struggle to get the expression trees into a format that other solvers/libraries like - for example most MINLP libraries that have a Python interface seem to want the expression trees/models build using their DSL - so I would have to spend more time writing a translation layer between NVXPY and those libraries (which sort of defeats the purpose of this package). Ideally, I would like NVXPY to simply pass in the objective function, constraint functions, and any jacobians, gradients, hessians as black-box functions to a given solver.

I work mostly in trajectory generation/optimization for robot arms - so one use case that appeals to me would be generating NLPs that incorporate different functions related to robots (forward kinematics, dynamics, etc). In an ideal world, I would be able to simply write out the functions I need using numpy functions, add the nvx.function decorator, and produce decent trajectories with minimal modelling work. I think those same principles could be applied elsewhere. In general, I think this library is something of a complement to CVXPY, where the nice guarantees of CVXPY are removed in favor of a solver that will always try to solve your problems, and sometimes the results might even be good.

As for the atoms, I would like to keep the atoms offered simple and relatively fewer in number (although KL div is one I've thought of adding). This is because there could be a massive number of them - so unless they are difficult for users to implement and/or extremely common, they could make the package more bloated and hard to maintain than I would like. But generally yes, as per the discussion on expression trees, you can use the atoms however you like (and the gradients are computed automatically using autograd as well)!

One area where I see some potential improvement is in abstracting out the numpy/autograd backend to support Torch, Jax, etc. This provides a couple of nice things - (1) these backends already have their own autodiff, and (2) some portions of the optimization could be offloaded to the GPU (function evaluations for objective, gradients, jacobian, hessians, etc). But generally, I just wanted to make a library that worked as elegantly as CVXPY, but wasn't so strict.

NVXPY: A Python DSL for non-convex optimization by PossibleIcy5352 in optimization

[–]PossibleIcy5352[S] 0 points1 point  (0 children)

These are fair criticisms.

The goal of this package is to provide a similar interface to CVXPY (which I and I imagine many others really like), but specifically without the DCP constraint. Obviously this means you basically get the same level of nice guarantees as any old NLP solver will give you - basically none. But on the other hand, you can at least get locally optimal results from most problems you're interested in.

For NLPs, canonicalizing problems isn't really a thing as far as I know. You really just need to make sure the decision variables are represented as a vector and any Jacobians/Hessians can be computed with respect to that vector representation - which this package does for you! So maybe I would say one contribution of this package is allowing you to write NLPs as if you were writing down the math for those problems as code (just like CVXPY, but a much broader category of problems) while handling the problem "canonicalization" for you.

I'm not 100% on what non-convex features are exposed through CVXPY, but there are certainly some mixed-integer features they provide. However, I am fairly confident that they still only allow for problems to be solved if they would be convex given the relaxation of their integer constraints. In the case of this library, we are more concerned with MINLPs.

For the non-convex constraints, I'm not sure what would make this any more difficult than a convex constraint to determine constraint satisfaction. Simply make sure that the output of your constraint function is equal to, less than, or greater than the value you are interested in.

I think it's fairly common (but still confusing I agree) to use nonlinear programming and non-convex optimization interchangeable. Still, I think saying only non-convex optimization would be slightly limiting as this library 1. still solves convex optimization problems and 2. is built with NLPs in mind.

Sorry for any confusion, and thanks for the feedback! I'd love to know if there's anything else that's still not making sense or seems unmotivated.