cobyqa.minimize() not working when most solutions are Nonlinear-equality unfeasible and unfeasibility cannot be quantified about cobyqa HOT 4 CLOSED

Hi @ragonneau, thank you for your fast and detailed answer, you solved all the doubts I had and some additional I did not know I had.

Did you hack the source code of COBYQA? The info "cobyqa terminated: ExitStatus.RADIUS_SUCCESS" should be private and not displayed to the user. I want to confirm that this is not a bug of COBYQA. The variable RADIUS_SUCCESS is internal, and it is not because its value is returned that the optimization procedure necessarily terminated successfully. If you look at the structure returned by minimize, it contains a field success whose value is False.

Yes sorry, I added a print statement on termination, its not a bug.

The bound constraints will always be satisfied, and your general constraint is 0 or 1. Therefore, the constraint violation can be either 0 or 1 but not anything else. Hence, any value in would work for feasibility_tol. The default value being np.sqrt(np.finfo(float).eps), you could leave it as is.

Ok, thanks!

Your problem is a very difficult problem due to two things: one of your constraints is unquantifiable, and your objective function is undefined outside some region. Is it possible to define even when the constraints are not satisfied?

It is possible, but evauating a solution takes 8h of GPU computation, and feasibility checks take less than a second, hence we would rather not evaluate unfeasible solutions. I spoke to the engineer and we will be able to change the constraint to quantifiable, so that should make it much easier to solve. Thanks for the warning.

The bound constraints are assumed to be unrelaxable, and for this reason, COBYQA modifies your initial guess because some properties must be verified by the initial trust region. I tried to run the code below.

Ok! That seems to be working, thanks!

Your problem does not have any theoretical solution. We expect a solver to give an objective function value arbitrarily close to zero. In this sense, COBYQA "converged" numerically.

Understood, we are not looking for the global optimum anyway, just a good enough solution.

The constraint violation is not zero, because the point returned is slightly outside the bound constraints.
Understood.

It takes some time to obtain this result, and this is expected. What is the dimension of your actual problem? COBYQA is designed to solve derivative-free optimization problems of reasonable size (at most a few hundred).

We are still working on the problem, but it will be less than a hundred for sure.

If your bound constraints are unrelaxable, you can try to reduce the value of options["radius_init"]. Let me know if this is the case I can provide more support on this.

Thanks for the tip!

Again, thanks for the detailed answer, you really helped me :) I will close the issue.

from cobyqa.

Hi @EtorArza,

Great to hear. If you use COBYQA in the future to solve your actual problem, I would be glad to have some feedback 😃

Cheers,
Tom.

from cobyqa.

Hi @EtorArza,

First, thanks for using COBYQA; your application sounds very interesting! I have several questions/comments; I list them below.

1. Did you hack the source code of COBYQA? The info "cobyqa terminated: ExitStatus.RADIUS_SUCCESS" should be private and not displayed to the user. I want to confirm that this is not a bug of COBYQA. The variable RADIUS_SUCCESS is internal, and it is not because its value is returned that the optimization procedure necessarily terminated successfully. If you look at the structure returned by minimize, it contains a field success whose value is False.
2. The bound constraints will always be satisfied, and your general constraint is 0 or 1. Therefore, the constraint violation can be either 0 or 1 but not anything else. Hence, any value in $[0, 1)$ would work for feasibility_tol. The default value being np.sqrt(np.finfo(float).eps), you could leave it as is.
3. Your problem is a very difficult problem due to two things: one of your constraints is unquantifiable, and your objective function is undefined outside some region. Is it possible to define $f$ even when the constraints are not satisfied?
4. The bound constraints are assumed to be unrelaxable, and for this reason, COBYQA modifies your initial guess because some properties must be verified by the initial trust region. I tried to run the code below.

import numpy as np
import numpy.typing
import os
from cobyqa import minimize
from scipy.optimize import LinearConstraint, NonlinearConstraint


def f(x: numpy.typing.ArrayLike):
    # If solution not feasible, return np.nan
    if not np.all(constraint_check(x)):
        return np.nan
    return np.linalg.norm(x)


def constraint_check(x: numpy.typing.ArrayLike):
    if x[0] > x[1] > x[2] > x[3] > x[4]:
        return 1.0
    return 0.0


def random_feasible_sol(dim, ):
    feasible = False
    seed = 2
    rs = np.random.RandomState(seed)
    while not feasible:
        x0 = rs.random(dim)
        feasible = constraint_check(x0)
    return x0


problem_dim = 50
x0 = random_feasible_sol(problem_dim) # get a random feasible solution to initialize the algorithm.
# bounds = Bounds([0.0 for _ in range(problem_dim)], [1.0 for _ in range(problem_dim)])
constraints = [
    LinearConstraint(np.eye(problem_dim), np.zeros(problem_dim), np.ones(problem_dim)),
    NonlinearConstraint(lambda x: [constraint_check(x)], 1.0, 1.0),
]

options = {
    "disp": True,
}

minimize(f, x0, constraints=constraints, options=options)

This is mathematically equivalent, but since bounds are supplied as linear constraints, COBYQA may visit points outside of the bounds. It gives the result below on my computer.

The lower bound for the trust-region radius has been reached.
Number of function evaluations: 3077.
Number of iterations: 1655.
Least value of f: 0.0006808081667906753.
Maximum constraint violation: 2.0122649008455027e-23.
Corresponding point: [ 3.543e-04  3.156e-04 ...  5.080e-05  1.661e-04].

Several things to note about this result:

1. Your problem does not have any theoretical solution. We expect a solver to give an objective function value arbitrarily close to zero. In this sense, COBYQA "converged" numerically.
2. The constraint violation is not zero, because the point returned is slightly outside the bound constraints.
3. It takes some time to obtain this result, and this is expected. What is the dimension of your actual problem? COBYQA is designed to solve derivative-free optimization problems of reasonable size (at most a few hundred).

If your bound constraints are unrelaxable, you can try to reduce the value of options["radius_init"]. Let me know if this is the case I can provide more support on this.

Cheers,
Tom.

from cobyqa.

Thanks Tom, I will let you know if I have feedback :)

from cobyqa.