Home 21090308 › Forums › Numerical Method › Optimization › SQP – “cannot perform quadratic programming”
 This topic is empty.

AuthorPosts

October 21, 2014 at 5:57 am #2907RyuMember
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.October 21, 2014 at 5:58 am #2908haksunliKeymasterThank 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 trialanderror 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.
October 21, 2014 at 5:58 am #2909RyuMemberThanks 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 (http://www.numericalmethod.com/javadoc/suanshu/com/numericalmethod/suanshu/optimization/multivariate/constrained/general/sqp/activeset/SQPActiveSetMinimizer.htmlOctober 21, 2014 at 5:58 am #2910haksunliKeymasterThere are two epsilons.
epsilon1 determines two things:
1. whether a constraint is active in a QP subproblem (numerically determining zeros)
2. whether a new solution in the next iteration changes much; if not the algorithm stopsepsilon2 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.
October 21, 2014 at 5:58 am #2911RyuMemberDoes 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?October 21, 2014 at 5:59 am #2912haksunliKeymasterMy email is consistent with the javadoc description.
epsilon1 is for the whole SQP solver
The way to determine a stop on the algorithm is:
123<code> if (d.norm() < epsilon1) {break;}</code>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, WuSheng 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 greaterthanorequalto 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 (n1) entries consist of a feasible initial point.
* The last entry is the single point perturbation.123<code> if (x.get(x.size()) > epsilon) {throw new QPInfeasible();}</code>So, the last entry needs to be bigger than epsilon2.

AuthorPosts
 You must be logged in to reply to this topic.