alphaville / optimization-engine

Nonconvex embedded optimization: code generation for fast real-time optimization + ROS support
https://alphaville.github.io/optimization-engine/
Other
509 stars 53 forks source link

Infinite loop after evaluation of points out of the constraint set #346

Closed fedemagnani closed 5 months ago

fedemagnani commented 7 months ago

Describe the bug

I've encountered an issue with the optimizer where it enters an infinite loop when the starting point is close to the minimum. This seems to occur because the optimizer tries to evaluate points outside of the defined domain (in this case, defined by the constraint set Rectangle). Here is the objective function with its gradient

$$ f(x) = \sqrt{x_0} + (x_1 - 1)^2 $$

$$ \nabla f(\mathbf{x}) = \left[\frac{1}{2\sqrt{x_0}}, 2(x_1 - 1)\right] $$

In the example, it is immediate to see that the minimum is attained at point (0, 1). However, even starting from a very close point to the minimum, like (0.1, 1.1), the optimizer will try to evaluate the function using points not feasible points ending up with looping through NaN points

fn minimize() {
    let f = |x: &[f64], y: &mut f64| -> Result<(), SolverError> {
        println!("{:?}", x);
        *y = x[0].sqrt() + (x[1] - 1.0).powi(2);
        Ok(())
    };
    let df = |x: &[f64], grad: &mut [f64]| -> Result<(), SolverError> {
        grad[0] = 0.5 / (x[0].sqrt());
        grad[1] = 2.0 * (x[1] - 1.0);
        Ok(())
    };
    let lb = vec![0.0, -f64::INFINITY];
    let ub = vec![f64::INFINITY, f64::INFINITY];
    let constraints = constraints::Rectangle::new(Some(&lb), Some(&ub));
    let problem = Problem::new(&constraints, df, f);
    let mut cache = PANOCCache::new(2, 1e-8, 15);
    let optimizer = PANOCOptimizer::new(problem, &mut cache);
    let mut optimizer = optimizer.with_max_iter(100 as usize);
    let mut x = vec![0.1, 1.1];
    let status = optimizer.solve(&mut x);
    println!("{:?}", status);
    println!("{:?}", x);
}

To Reproduce

Setting vec![0.1, 1.1], the optimizer does not converge ending up with NaN attempts after using points not belonging to the maximal domain of the function (here represented as the constraint set Rectangle). This is the sequence of attempts

[0.1, 1.1]
[0.0, 1.0102296023757276]
[0.10000010000000001, 1.1000011]
[0.0, 1.0102296023757276]
[0.0, 1.0010463351220287]
[0.0, 1.0102296023757276]
[-8.20406374170855e-5, 1.000101677010577]
[NaN, 1.0000104000354424]
[-8.20406374170855e-5, 1.000101677010577]
[NaN, NaN]
[NaN, NaN]
[NaN, NaN]
[NaN, NaN]
[NaN, NaN]
[NaN, NaN]
[NaN, NaN]
...
[NaN, NaN]

Expected behavior

The optimizer should converge to the global minimum (0, 1). In particular, I was expecting the optimizer to evaluate only feasible points

System information:

:warning: Please, provide the following information:

alphaville commented 5 months ago

This is an interesting example. The issue is that the cost function, $f$, does not satisfy the requirements that OpEn expects - namely, $f$ should be a continuously differentiable function with Lipschitz gradient. As discussed in this paper, Algorithm 2, Step 5, a point $u^{\nu+1}$ is determined at which we then compute the gradient. In your example this point can be in $(-\infty, 0]$ where the gradient is not defined.