12
$\begingroup$

I have an NLP that I am hoping to solve with Knitro and I am aware of a multitude of different settings that you can "tune" in order to improve solution performance. I am not familiar with optimization solvers and the various settings, and so what I am trying to determine is exactly how much of a difference tuning the settings can make in solving problems. Does tuning the solver have the potential to drastically improve the solving times, and if so, could you provide a small conceptual example that illustrates how different solver settings might be able to improve the computational efficiency of a problem?

I am trying to determine if investing time into learning the fundamentals of the solver (and thus the tuning specs) is really worth my time as a student if my problem is very difficult to solve.

$\endgroup$
  • $\begingroup$ This is not about Knitro, but this gurobi troubleshooting and performance tuning pdf has some nice explanations and use cases and can be a starting point $\endgroup$ – EhsanK Nov 28 '19 at 16:02
  • $\begingroup$ I will have to check it out. Even though it's not Knitro specific i'm sure it could be helpful. $\endgroup$ – GrayLiterature Nov 28 '19 at 16:03
  • $\begingroup$ Read artelys.com/docs/knitro/2_userGuide/tuner.html#sec-tuner about the "KNITRO Tuner" if you haven't already. The most important "option" though is often the starting (initial) value for the optimization (a.k.a. decision) variables - model or domain-specific knowledge may help you in that regard. If you give some info about the model type (objective, constraints, availability of first or 2nd derivatives, etc.), more useful guidance may be possible on option choices. $\endgroup$ – Mark L. Stone Nov 28 '19 at 16:17
  • $\begingroup$ I don't think you should invest too much time in it. Basically the solvers are now making it possible for the user to give little to no extra settings (other than the objective function, constraints, etc). So, this 'tuning', to the best of my knowledge, something more related to Knitro (I used it, I don't think it saves the world at the end of the day). Still, Knitro is a very powerful solver, so if you think you will use it a lot, you should learn it! Sorry for the paradox.. $\endgroup$ – independentvariable Nov 30 '19 at 1:23
  • $\begingroup$ I suppose your model is not convex? $\endgroup$ – ErlingMOSEK Dec 3 '19 at 12:20
12
+100
$\begingroup$

(Disclaimer: I am a developer of Knitro)

When developing a NLP solver, we set the default values for the different options so as to minimize the resolution time in average for different class of problems (CUTer, QPLIB, Mittelmann instances, etc.). When working on a specific problem, it often pays to find appropriate parameters to improve the resolution time. In Knitro, the most impactful parameters are usually:

  • algorithm: Knitro comes with 4 different algorithms to solve NLP problems.
    • algorithm=1 uses the classical interior point algorithm, and Knitro computes at each iteration a line-search step using direct linear algebra (you could specify the line-search procedure with linesearch). If the line-search fails to improve the merit function used inside Knitro, the algorithm falls back to a trust-region step (the CG step appearing in the log of Knitro).
    • algorithm=2 uses a trust-region algorithm, using a quadratic approximation of the non-linear function internally. This algorithm could be powerful if you have callbacks available to compute the Hessian vector product $\nabla^2f(x^k) v$, as you won't need to compute the whole Hessian in this case.
    • algorithm=3 uses an active-set algorithm (more precisely, a sequential linear-quadratic programming algorithm).
    • algorithm=4 uses a classical SQP algorithm, which could be powerful if evaluating the oracle for the function, the gradient and the Hessian is costly. Indeed, the SQP algorithm usually performs a smaller number of iterations than the other algorithms.
  • linsolver: determine which linear solvers to use when solving the Newton step at each iteration. On large-scale problems, setting an appropriate linear solver could improve a lot the performance. MA27 and MA57 give good performance overall, and MA86/MA97 target more specific architecture. You may also want to use Intel PARDISO here.
  • hessopt: specify which algorithm to use internally. If you provide the Hessian, hessopt=1 performs the classical Newton algorithm. If you have only gradients available, I recommend using hessopt=2 (BFGS) if the problem is medium-sized, and hessopt=6 (L-BFGS) if the problem has more than 10,000 variables or constraints. When using L-BFGS, you can play with the parameter lm_size to determine how many coefficients to use in the limited memory approximation of the Hessian.
  • presolve: determine the level of the presolve. Basically, the presolve removes redundancies in the linear constraints (fixed variables, linearly dependant rows, etc). You can specify the level of the presolve with presolve_level.
  • Concerning the specific parameters for the barrier used inside the interior point algorithm, they are often more difficult to tune. I recommend setting bar_conic_enable=1 if you are using the conic API of Knitro. bar_murule allows to change the update rule of the penalty parameter \mu, bar_penaltycons is useful if your problem has difficult or degenerate constraints, bar_watchdog enables a watchdog procedure in the line-search, and bar_penaltyrule allows more control to define the merit function uses internally in Knitro.

In any case, before tuning the performance of the solver, I recommend to spend some time on formulating the NLP problem properly, e.g.:

  • Choosing an appropriate scaling (the closer the objective and the range of the constraint to 1.0, the better) ;
  • Avoiding redundant and linearly dependent constraints ;
  • Specifying most of the constraints by using the linear and quadratic API of Knitro (by doing so, we let Knitro computes automatically the Jacobian and the Hessian, and that could lead to much better performance).

In any case, I recommend having a look at:

and we would be happy to help you more specifically if you choose to contact the support team on support-knitro [AT] artelys.com!

I am trying to determine if investing time into learning the fundamentals of the solver (and thus the tuning specs) is really worth my time as a student if my problem is very difficult to solve.

If you are interested by the theory lying behind the optimization solver Knitro, I advise usually to have a look at this article: http://users.iems.northwestern.edu/~nocedal/PDFfiles/integrated.pdf

Furthermore, Numerical Optimization by Nocedal and Wright is a must read.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice answer. But by failing to mention it, you "dissed" SR1, hessopt=3, which I have found useful if the solution path encounters significant non-convexities, which SR1 seems better able to handle than BFGS due to not enforcing positive definiteness of the Hessian approximation. $\endgroup$ – Mark L. Stone Dec 2 '19 at 12:57
  • $\begingroup$ Completely agree with this answer. Even if average performance is good, there is always potential to improve on specific problems. I like to manually tune parameters based on my knowledge of the underlying methods, and I can vouch for Nocedal and Wright as a good reference. On the other hand: if performance is 'sufficient', it may not be worth the investment to manually tune parameters. Some solvers (CPLEX and Gurobi, for example) provide automatic parameter tuning tools. Automatic parameter tuning is also being studied in the machine learning community, and may be more common in the future. $\endgroup$ – Kevin Dalmeijer Dec 2 '19 at 14:02
4
$\begingroup$

Tuning a solver can make a big difference when it comes to IP/MIP problems. For continuous problems, it's unlikely to see a significant difference in performance.

If the solver enters branch and bound and/or has to use MIP heuristics to find primal solutions/feasible points, then there's no reason that the default settings would work better than something different.

That being said, it's rare to find a better configuration than what a solver's developers suggest.

In general, we tune our solvers over large diverse sets of difficult problems (our own set is 3,000+) and pick combinations of features that (i) work best on average, and (ii) are well balanced, i.e., don't give an amazing performance for some problems but horrendous in others.

We even have hard coded overrides to prevent users from using combinations of options that are known to perform badly for certain types of problems.

There's usually 1% of cases not covered by the defaults, which is the only reason we make algorithmic options available to our users.

If one finds themselves in that 1% of cases, I would suggest experimenting with one option at a time, and to pick the important ones first, e.g. branching rules, type/frequency of heuristics, etc. I strongly advise against tweaking numbers/parameters, maybe with the exception of feasibility tolerances.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It seems that you work on these types of solvers, so I think this is probably going to be the best response. I think that for my purposes then that the default settings are probably going to be the best bet. My problem is a continuous NLP, so I think I fall in the 99% as opposed to the 1%. $\endgroup$ – GrayLiterature Dec 1 '19 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.