Constrained optimization with ceres-solver

[Dmitriy Korchemkin]

Hi,

I have a couple of questions regarding constrained optimization with ceres-solver.


1. On the proper implementation of constrained optimization and local parameterizations
Documentation and code mention paper "Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints" by C. Kanzow et al., and provide a note that current implementation is not 100% accurate to the paper.

I would like to clarify the following:
a. Current approach used in ceres-solver is to
   * Perform line search over step size scale up to an intersection with the boundary [or 1, whichever comes first]
   * Step is scaled in tangent space and its' direction does not change

b. In the paper mentioned above:
   * It is checked if projection onto feasible subset provides a sufficient decrease by itself
   * Otherwise, line search over step size is performed, with direction given by gradient of cost function, projecting onto feasible set on each step

c. Assuming that my understanding is correct, it is impossible to make a correct implementation while keeping local parameterizations and boundaries separate (and it seems to me that current behavior of projecting initial point onto feasible subset is somewhat incorrect in case of parameter block having non-trivial local parameterization)

2. A general question about constrained optimization

For the subsets I am interested in it seems hard to provide a true "projection" routine, but relatively simple to provide "intersection with ray".
It seems to me that paper of C. Kanzow explicitly relies on optimality properties of projection onto a convex set for proving convergence.
I am interested if there are any known results about replacing "true projection" with intersection of segment between current point and point outside feasible set and feasible set boundary.

[Dmitriy Korchemkin]

> a. Current approach used in ceres-solver is to
>   * Perform line search over step size scale up to an intersection with the boundary [or 1, whichever comes first]
>   * Step is scaled in tangent space and its' direction does not change

I missed that ParameterBlock::Plus does projection onto feasible set, instead of returning false.

So, in a notation that is mix from Kanzow's article and ceres-solver docs, current implementation is doing search over alpha for optimum of

> c. Assuming that my understanding is correct, it is impossible to make a correct implementation while keeping local parameterizations and boundaries separate (and it seems to me that current behavior of projecting initial point onto feasible subset is somewhat incorrect in case of parameter block having non-trivial local parameterization)

I've meant that if boundaries and local parameterization are "separate" entities (instead of some "manifold" entity, providing projection routines as well as local parameterization), and local parameterization is non-trivial - we may get point that is not on the same manifold as starting point (in other words, a point that is not reachable by making steps with local parameterization).
For example, when optimizing over S^n, projecting point onto feasible set defined as axis-aligned bounding box might take us away from the surface of the sphere.

[Dmitriy Korchemkin]

> For example, when optimizing over S^n, projecting point onto feasible set defined as axis-aligned bounding box might take us away from the surface of the sphere.

Here is a small example of minimizing distance between vectors on sphere, demonstrating two problems:  https://gist.github.com/DmitriyKorchemkin/c506c8f5814f06d16fca49f689f285f3

a. Started from point on unit sphere in feasible region, but result is not on the unit sphere (Test #2); I assume that in that case one would expect one of four local minimas

b. Started from point on unit sphere outside feasible region, iterates are not on the unit sphere starting from iteration #0; not sure what is an expected outcome in this case; probably it is garbage-in/garbage-out situation, but if local parameterizations and boundaries were tightly coupled - current approach might produce some reasonable result even in this case.

[Sameer Agarwal]

Dmitriy,

Before I start answering your questions. Are your questions in the context of Ceres or are you asking about constrained optimization more generally?

If I understand what you are trying to do, I maybe able to answer your question better.

Sameer

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/45b8e77a-22b6-4558-be2a-00d3e7cfb3c9n%40googlegroups.com.

[Dmitriy Korchemkin]

I am actually interested in both.

From practical side of things I would benefit most from things that are more or less applicable in the paradigm of ceres-solver, even if it would require some modifications of ceres-solver itself (+ I could probably fix some known issues on my way).

From theoretical side of things - I would be thankful for insights and references on constrained non-linear least squares on manifolds with a boundary.

From practical side of things I also want to make local parameterizations and parameter block boundaries in Ceres more "compatible" with each other (it seems to me that applying constraints to parameter block with non-trivial local parameterization breaks invariant of local parameterization, when boundary conditions become utilized).

The particular problem I am solving now involves optimization over polynomials of a fixed degree,  monotonically non-decreasing on the fixed interval [this is a convex subset of polynomials of a fixed degree d, and interior is a manifold with dimension d+1], and a bunch of SE3 and R^3 parameters.

So far I've tried:

 * Sum-of-squares parameterization of polynomials (since derivative of monotonically increasing polynomial is positive, and every polynomial p positive on the interval can be rewritten in a certain way using squared polynomials), but it has some problems (zero gradients over parameters for p(x)=0, etc)

 * Optimization directly over coefficients of monotonic polynomial, rejecting steps that result into "bad" roots of derivative; this seem to have some problems near boundary, but works better (in terms of number of cases when optimization succeeds)

Playing with hyper-parameters (degree of polynomial) for this problem makes me think that I might benefit from a more suitable optimization algorithm, that would work better on the boundary.

For example, when fitting a model to synthetic data, generated with polynomial p(x) of degree d, with roots of dp/dx near the ends of interval  -  typically it helps to fit polynomial of degree d+2, discard extra coefficients, and optimize again as polynomial of degree d.

[Sameer Agarwal]

Dmitriy, this is very timely.

The way manifolds are implemented in Ceres is an artifact of history (inheriting from an earlier solver at google), and they only implement half of what is needed. A few weeks ago put together a plan to have proper manifolds in Ceres. 

Here is the plan

https://docs.google.com/document/d/1CoGMoKaRYfKNtfkHWVhGab-kDvXgtbzRPySECcsOlHM/edit?usp=sharing

This plan does not address boundaries. I am happy to have your help with it.

On Thu, Oct 21, 2021 at 11:42 AM Dmitriy Korchemkin <dmitriy.k...@gmail.com> wrote:

I am actually interested in both.

From practical side of things I would benefit most from things that are more or less applicable in the paradigm of ceres-solver, even if it would require some modifications of ceres-solver itself (+ I could probably fix some known issues on my way).

From theoretical side of things - I would be thankful for insights and references on constrained non-linear least squares on manifolds with a boundary.

I think there is not much which is particularly special to nonlinear least squares. If you are interested in general theory of optimization on manifolds, a really great reference is a new book by Nicolas Boumal 

http://sma.epfl.ch/~nboumal/book/index.html

 

From practical side of things I also want to make local parameterizations and parameter block boundaries in Ceres more "compatible" with each other (it seems to me that applying constraints to parameter block with non-trivial local parameterization breaks invariant of local parameterization, when boundary conditions become utilized).

Yes, there is a similar problem with numeric differentiation too, where if the manifold has a boundary and we are near it, then the finite differencing does not respect the boundary and can easily produce points off the manifold. It is because CostFunctions do not know about manifolds. I do not know of an easy fix here.

 

The particular problem I am solving now involves optimization over polynomials of a fixed degree,  monotonically non-decreasing on the fixed interval [this is a convex subset of polynomials of a fixed degree d, and interior is a manifold with dimension d+1], and a bunch of SE3 and R^3 parameters. 

So far I've tried:

 * Sum-of-squares parameterization of polynomials (since derivative of monotonically increasing polynomial is positive, and every polynomial p positive on the interval can be rewritten in a certain way using squared polynomials), but it has some problems (zero gradients over parameters for p(x)=0, etc)

 * Optimization directly over coefficients of monotonic polynomial, rejecting steps that result into "bad" roots of derivative; this seem to have some problems near boundary, but works better (in terms of number of cases when optimization succeeds)

Playing with hyper-parameters (degree of polynomial) for this problem makes me think that I might benefit from a more suitable optimization algorithm, that would work better on the boundary.

For example, when fitting a model to synthetic data, generated with polynomial p(x) of degree d, with roots of dp/dx near the ends of interval  -  typically it helps to fit polynomial of degree d+2, discard extra coefficients, and optimize again as polynomial of degree d.

so you are trying to construct polynomials of a particular kind by optimizing its coefficients? From your description this problem seems to have a lot of structure and may benefit from more analysis before you throw a solver at it.

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/d6760423-373a-4b5c-899f-fb81884bf460n%40googlegroups.com.