Constrained least squares optimization using barrier functions

[Cenek]

Hi,
I'd like to use ceres to implement constrained least squares optimization using inverse and 
logaritmic barrier functions.

 For the time being, I'm adding 1-D residual blocks for every barrier function.

 However, I'm not getting expected results, as the optimum found by ceres does not lie in the feasible set most of the time, i.e., the barrier gets broken through. Is constrained optimization using barrier functions something that is at least conceptually possible with ceres and my 
code is buggy/needs parameter tuning, or am I using a tool that does not fit the task and I should not hope to get anything reasonable from the ceres/barrier function combination?

Thank you for your reply

Cenek

[Sameer Agarwal]

Cenek,
Do you have bounds constraints or something more general?

what is the algebraic form of your barrier functions?

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/6bd9509b-66e1-4339-8ec7-45800ce195f5%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Cenek]

Dear Sameer, thank you for your quick reply. I'm trying to optimize on the cone of positive semi-definite matrices A>=0, for which I'm using -log(det(A)) or 1/det(A) barriers. I have small, max 4x4 matrices. However, my initial solution lies quite near the boundary, which I think might be quite a problem.

Dne středa, 9. dubna 2014 16:10:10 UTC+2 Sameer Agarwal napsal(a):

[Sameer Agarwal]

Cenek,

If you are using a barrier function you are going to need an objective function of the form

f(x) - log(det(A))

This cannot be modeled using a least squares objective.

If you just add -log(det(A)) as  residual, what you are actually solving for is

f(x) + 1/2 log^2(det A)

A cheap trick you can use is to have a scalar residual function which always return, but false if your determinant is negative.. this will restrict ceres step to inside the positive definite cone. I am not sure of the solution quality though.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/7c5f90f6-14ac-46f9-baaf-518501982fcd%40googlegroups.com.

[Cenek]

Dear Sameer,

  suppose I'd use the inverse barrier:

f(x) + 1/det(A)

This would translate in ceres to

f(x) + 1/2 (1/det^2(A))

which is still a barrier function. Does this mean that barriers (of some sorts) are conceptually possible to implement with ceres?

A cheap trick you can use is to have a scalar residual function which always return, but false if your determinant is negative.. this will restrict ceres step to inside the positive definite cone. I am not sure of the solution quality though.

I'm not quite sure how ceres manipulates the CostFunction.operator(). If I do 'if(det(A)<0) return false;' in the operator() method, how does this affect the automatic differentiation framework? Am I not restricting det'(A) to be nonnegative as well?

 

Thanks

 Cenek

[Sameer Agarwal]

On Wed, Apr 9, 2014 at 8:49 AM, Cenek <cenek...@gmail.com> wrote:

Dear Sameer,

  suppose I'd use the inverse barrier:

f(x) + 1/det(A)

This would translate in ceres to

f(x) + 1/2 (1/det^2(A))

which is still a barrier function. Does this mean that barriers (of some sorts) are conceptually possible to implement with ceres?

The inverse barrier does not prevent jumps across the zero. The trust region algorithm could easily step across it, and it won't see the infinity at zero. And yes ceres as of not only supports nonlinear least squares objectives.

 

A cheap trick you can use is to have a scalar residual function which always return, but false if your determinant is negative.. this will restrict ceres step to inside the positive definite cone. I am not sure of the solution quality though.

I'm not quite sure how ceres manipulates the CostFunction.operator(). If I do 'if(det(A)<0) return false;' in the operator() method, how does this affect the automatic differentiation framework? Am I not restricting det'(A) to be nonnegative as well?

You don't have to use autodiff here. You can just define an analytic CostFunction.  It will work fine. Every now and then I use this to enforce positive depth in a bundle adjustment problem :).

what do you mean det'(A) ? det is a scalar.

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/54e079db-e28e-4e65-95ee-4d4b618e75b3%40googlegroups.com.