SQP – “cannot perform quadratic programming”

Thank you for the feedback. Could you give us more information for investigation? When you say R outperforms SuanShu, could you send us the code so that we can do the comparison on our side? I think the speed depends a lot on the parameters you choose.

The epsilons control when the algorithm or the iterations end. One controls the precision of the embedded QP solver; the other controls the overall SQP solver. They are user specific precision parameters. There is no “mathematical” way to optimally choose them. A lot depends on trial-and-error in practice.

If you send us the code, we can see why it throws an exception. I suspect that it has to do with the epsilons you choose.

Thanks for quick replying. About the performance, it is measured by failure rate, not speed. That is the reason why I asked what could cause SQP in SuanShu throws exception “cannot perform quadratic programing.” And I was wondering that What is “Definition of the tolerance”, RSS (residual sum of squares), relative RSS, mean of RRS or anything else, not how to tune it. It would be great if there is a mathematical definition of what is |x|<epsilon in (http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/multivariate/constrained/general/sqp/activeset/SQPActiveSetMinimizer.html

There are two epsilons.

epsilon1 determines two things: 1. whether a constraint is active in a QP sub-problem (numerically determining zeros) 2. whether a new solution in the next iteration changes much; if not the algorithm stops

epsilon2 is the epsilon in QPPrimalActiveSetMinimizer, which determines 1. whether a constraint is active (numerically determining zeros) 2. more importantly, it checks whether an automated computed initial solution is feasible. If this initial solution computed by SuanShu is not feasible, it will declare the problem infeasible.

I suspect that the last point makes your problem fails. Does increasing epsilon2 help your performance?

Again, if you send us your sample code (that compiles), we are happy to look into it.

Does your definition of epsilon 1 and 2 are different from the following definition? http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/multivariate/constrained/general/sqp/activeset/SQPActiveSetMinimizer.html It seems to be switched. Anyway, I will use your definition here.

I guess my original question are How do you define “new solution in the next iteration changes much ” or not by using your epsilon 1? Using RSS or relative RSS or something else? And how do you define “solution is feasible” or not by using your epsilon 2?

My email is consistent with the javadoc description.

epsilon1 is for the whole SQP solver

The way to determine a stop on the algorithm is:

                if (d.norm() < epsilon1) {
                    break;
                }

d is the difference between the new and old solutions.

epsilon2 is for the QP solver, QPPrimalActiveSetMinimizer.

The algorithms to find a feasible solution can be found here LinearGreaterThanConstraints.getFeasibleInitialPoint.

Here is the Javadoc:

* “Jorge Nocedal, Stephen Wright, “p. 473,” Numerical Optimization.” * “Andreas Antoniou, Wu-Sheng Lu, “Eq 11.25, Quadratic and Convex Programming,” Practical * Optimization: Algorithms and Engineering Applications.” * http://www.mathworks.com/help/toolbox/optim/ug/brnox7l.html (initialization)

* Given a collection of linear greater-than-or-equal-to constraints as well as a collection of * equality constraints, * find a feasible initial point that satisfy the constraints. * This implementation solves eq. 11.25 in the reference. * The first (n-1) entries consist of a feasible initial point. * The last entry is the single point perturbation.

            if (x.get(x.size()) > epsilon) {
                throw new QPInfeasible();
            }

So, the last entry needs to be bigger than epsilon2.