Add feasibility checks to optimizers/converters

[adekusar-drl]

What is the expected enhancement?

Please add that an optimization algorithm should check whether a solution is feasible and change the status to INFEASIBLE if not. This should also be part of the interpret of the equality to penalty converter.
This would likely require to add a is_feasible(x) method to QuadraticProgram, but given the evaluate(x) we already have that should be straight-forward.

[KahanMajmudar]

Hello, I am new to Qiskit contributions and would like to contribute, Is this a good issue which I can work on?

[t-imamichi]

OptimizationResult already has the status. You can check it by OptimizationResult.status == OptimizationResult.Status.INFEASIBLE.
https://github.com/Qiskit/qiskit-aqua/blob/854bd820b43a0c3f981fae588d1a0323a6e3486d/qiskit/optimization/algorithms/optimization_algorithm.py#L92
LinearEqualityToPenalty checks the feasibility to set the status when interpreting the result.
https://github.com/Qiskit/qiskit-aqua/blob/854bd820b43a0c3f981fae588d1a0323a6e3486d/qiskit/optimization/converters/linear_equality_to_penalty.py#L201
What do you think still missing?

[KahanMajmudar]

I think nothing's missing, I am trying to find issues which I can work on and saw this as an open one but it already has a solution. Thank you for pointing it out

[t-imamichi]

I got the point now. It would be convenient if QuadraticProgram can check the feasibility of OptimizationResult.x and point out violated constraints.
E.g.,

>>> problem = QuadraticProgram()
>>> ...
>>> result = OptimizationAlgorithm.solve(problem)
>>> print(result.status)
OptimizationResultStatus.INFEASIBLE
>>> print(problem.is_feasible(result.x))
false
>>> problem.violated_linear_constraints(result.x)
[0, 3]
>>> problem.violated_quadratic_constraints(result.x)
[0]

[adekusar-drl]

@t-imamichi is right in general, but the idea is to explicitly check feasibility in optimizers/converters and change the status accordingly:

# somewhere in the solve method of the optimizer
status = SUCCESS if qp.is_feasible(x) else INFEASIBLE
return (x, fval, results, status)

Now we may get a result with the SUCCESS status that is infeasible.

@KahanMajmudar this is not a tough issue but may require quite a lot of changes in many files.

[t-imamichi]

Yes, it does so already. The following line applies QP.subsitute_variables(OptimizationRestuls.x)https://github.com/Qiskit/qiskit-aqua/blob/854bd820b43a0c3f981fae588d1a0323a6e3486d/qiskit/optimization/converters/linear_equality_to_penalty.py#L192
and checks substituted_qp.status is VALID or not. VALID corresponds to feasible.
https://github.com/Qiskit/qiskit-aqua/blob/854bd820b43a0c3f981fae588d1a0323a6e3486d/qiskit/optimization/converters/linear_equality_to_penalty.py#L201
https://github.com/Qiskit/qiskit-aqua/blob/854bd820b43a0c3f981fae588d1a0323a6e3486d/qiskit/optimization/problems/quadratic_program.py#L888

Given values of variables, QP.substitute_variables can check the entire problem is feasible or not, but it cannot report whether each constraint is feasible or not currently.
I understand that this idiom is not intuitive, so I agree to add QP.is_feasible. It will be more efficient to use LinearExpression.evaluate() and QuadraticExpression.evaluate() than QP.substitute_variables.

[KahanMajmudar]

@t-imamichi @adekusar-drl If the issue is solvable, can I help with it? Even if it requires changes in many files, I would like to help and with the help and guidelines of others, the feature might be added

[adekusar-drl]

@KahanMajmudar I don't know to what extent you are familiar with Aqua and the optimization stack in particular, so I'll try to summarize what should be done here. Anyway, this writing is nice to have to be sure that everybody is on the same page.

1. Add a method is_feasible(x) to QuadraticProgram. This is pretty straight-forward, the method should verify that all constraints in the QP instance are satisfied and either return True or False. Perhaps, it is good to know which constraints are violated but this does not coincide with the potential signature of the method as it should return just a boolean value. So here we may think of the signature of this method. A probable signature may look like:

def is_feasible(x:Union[List[float], np.ndarray], detailed=False) -> Union[bool, Tuple[bool, List[Constraint]]]:

where detailed=False means return just a boolean, otherwise return a boolean and a list of violated constraints. Looks complicated but this the first thing that came up to my mind.

2. Once the latter is done then the code of all optimizers should be augmented to include feasibility check in the end. So, once a solution is obtained it should be verified as I wrote above:

# somewhere in the solve method of the optimizer
status = SUCCESS if qp.is_feasible(x) else INFEASIBLE
return (x, fval, results, status)

Right now it's easy to spot that optimizers (may be not all of them though) just return OptimizationResult with the found solution without checking the status. And by default the status is set toSUCCESS.
We also have two wrappers of SciPy: CobylaOptimizer and SlsqpOptimizer, so these are different, you may analyze what is returned by the underlying code and provide even more insights(well, don't know how, anyway).

3. Maybe a similar logic should be also added to converters. But it depends on their implementations and should be reviewed on a one by one case.

In overall I'm not insisting that this is the only one and exhaustive way to cope with the issue.
@t-imamichi Imamichi-san, please correct me if I wrong or if I missed something.

[t-imamichi]

@adekusar-drl Thank you for summarizing the details.

1. Parameter name detailed -> violated_constraints or report_violated_constraints might be clear. I agree on the functionality. It might be useful to return the indices of violated linear and quadratic constraints. But, I'm fine with the list of all violated constraints.
2. As for converters, I think LinearEqualityToPenalty is the only converter to take care of the feasibility. The others do not change constraints, so we don't need to compute the feasibility again, but also copy the status. Anyway, we have to check them one by one.

[adekusar-drl]

1. It is open for discussion, either constraints or indices, both are fine with me. Agree that report_violated_constraints is better, but very long :)
   @KahanMajmudar so, what do you think?

[KahanMajmudar]

@adekusar-drl , you are correct, I don't have much familiarity when it comes to aqua and optimization stack but I am ready to put the effort of going through the docs and reading the necessary code and I think I would catch up as it moves along :) .

As for the summary, I think it would be great to work in chunks, like completing the 1st and moving along, so that we can track the problem as we move along, but it's just a suggestion

For the parameter name, I think return_violations could work as well, but it can be figured out as this moves along if it's not an issue.

[adekusar-drl]

Fine! Welcome aboard!

[KahanMajmudar]

Thank you so much, excited to work on this. So should I start with documentations(would be great if I knew what to pay attention to) or do you have something which needs more attention first?