# SQP – “cannot perform quadratic programming”

Home 21090308 Forums Numerical Method Optimization SQP – “cannot perform quadratic programming”

• This topic is empty.
Viewing 6 posts - 1 through 6 (of 6 total)
• Author
Posts
• #2907
Ryu
Member

Hi NM team,

We did some test against the SQP method,
But the performance is not that well compared with SQP in R.
We got the some exceptions like “cannot perform quadratic programming” from SQP of NumericalMethod.
Do you have any documents about how to eliminate those exceptions?
Also, the definition of tolerance of SQP is vague. (http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/multivariate/constrained/general/sqp/activeset/SQPActiveSetMinimizer.html)
Do you have mathematical document describing definition of tolerance.

#2908
haksunli
Keymaster

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.

#2909
Ryu
Member

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| (http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/multivariate/constrained/general/sqp/activeset/SQPActiveSetMinimizer.html

#2910
haksunli
Keymaster

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.

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

#2911
Ryu
Member

Does your definition of epsilon 1 and 2 are different from the following definition?
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?
And how do you define “solution is feasible” or not by using your epsilon 2?

#2912
haksunli
Keymaster

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:

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.

* “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.

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

Viewing 6 posts - 1 through 6 (of 6 total)
• You must be logged in to reply to this topic.