Problem with linprob exit criteria?

I am gettting the following exit status using the "lsqlin" algorithm when solving a quadratic objective function and linear constraints:

"Optimization stopped because the relative changes in all elements of x are

less than options.StepTolerance = 1.000000e-10, but the relative maximum constraint

violation, 2.401393e-10, exceeds options.ConstraintTolerance = 1.000000e-06."

To me this does not make sense because 2.401393e-10 is less than options.ConstraintTolerance = 1.000000e-06. Is the magintude of the constraint function (in this case 2.401393e-10) supposed to be greater than the options.ConstraintTolerance? From my understanding/research of the options.ConstraintTolerance and other succesful solutions this does not seem to be the case.

Other details on the problem: The problem setup is very similar to another. It is intended to be the symmetric condition to another. The only differerence is a single constraint is inverted (accross the symmetric axis of the system). The other condition solved without issue. I have run similar problems without any issue in the past.

Ultimately my question boils down to: Is this a problem with the exit criteria or my understanding of the solver?

[Matt J]

It does sound strange. Do you have an example that reproduces it?

[John]

I don't have an example that I can publically share that reproduces it. I can provide some of the iteration results (see below). The left and right plots represent the same case but they have a single constraint that is different (the symmetric one discussed above). There seems to be some strange behavior once it gets near/at the solution for the LHS. Its almost like it gets to the solution, however the exit criteria fails to break from the algorithm and as a result some weirdness takes place blasting it away from the solution. The objective is quadratic and the constraints are linear so I should not expect this behavior.

When I only show up to iter 14 (the iter the RHS case found a solution) we see similar behavior in everything except the Dual Infeas (see below).

One thing I can add as well is that I just tried increasing the options.ConstraintTolerance from 1.000000e-06 to 1.0 and it returned the expected solution (such a tolerance is not a problem for the accuracy I am looking for) but also tripled the time to find a solution for some reason. I don't see this as a long term solution. I have lots of cases I need to run and need to rely on the stability of the solver. Which, in my opinion, should be nearly garunteed considering I am using very simple objectives and constraints (albeit a lot of them).

[Torsten]

Ok, but you will understand that it's impossible for us to help if we cannot reproduce the contradictory message from the solver.

[John]

I understand, it's frustrating from my end but I don't get to decide what I am allowed to share. I agree it is not possible to provide troubleshooting support without source data, and I am not necessarily looking for that. I was mostly looking for conceptual guidance or information about known bugs with the solver (and to be clear I am assuming there are no issues with the solver until explicitly told so by staff).

If you have any conceptual guidance (even something as simple as your assumptions about how options.ConstraintTolerance are not wrong) that would be helpful and appreciated. Just trying to reduce the number of things I need to investigate on my end.

Answer 1

[Steve Grikschat]

Hi John,

It's hard for me to be sure without reproduction steps, but I think this is a bug with the exit criteria and reporting.

If you can, please send reproduction steps here or via a tech-support request so that we can properly diagnose and fix this.

Assumptions:

1. You are running lsqlin's default algorithm ('interior-point')
2. You are running the "dense" version of said algorithm: either the C matrix is full or you're setting the LinearSolver specifically (see below)
3. Your release is past R2017a

The dense version of interior-point runs a few post processing steps after the main algorithm terminates. A primal feasibility check is performed where ConstraintTolerance is used as an absolute tolerance.

However, as stated in the message, a check using ConstraintTolerance as a relative tolerance is used to stop the iterations and it's those values reported in the message. Judging from the plots, the initial primal feasibility is quite large, which leads me to believe that the relative feasibility used internally may be skewed to look artificially small by the scale.

I don't think you can access the final parameters to verify that it is indeed infeasible in the absolute sense. Instead, you could try to work around the bug using the "sparse" method. It will change the path to a solution, but it should be stable and does not feature this post-processing step.

Set the LinearSolver option to 'sparse':

% Default options - Algorithm is 'interior-point'
options = optimoptions('lsqlin');
% Set to "sparse" version
options.LinearSolver = 'sparse';

[John]

Ok, I'll work on getting a support request put in.

Thanks