Login
Login

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

    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| (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.

    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.

    #2911
    Ryu
    Member

    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?

    #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.

    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.

    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.