Numerical Results

Published:

In this blog post, I will present numerical results obtained solving problems from the CUTEst collection [1] using the algorithms implemented during my GSoC project.

Let us consider two solvers:

  1. A Sequential Quadratic Programming (SQP) solver for equality-constrained problems, of the type: \begin{eqnarray} \min_x && f(x), \\
    \text{subject to } && c(x) = 0. \\
    \end{eqnarray} A detailed description of this method can be found here.
  2. An interior point solver capable of solving general nonlinear programing problems of the type: \begin{eqnarray} \min_x && f(x), \\
    \text{subject to } && c_E(x) = 0,\\
    && c_I(x) \le 0, \end{eqnarray} This solver uses the SQP solver as a substep and is described here.

The table bellow describes the performance of the SQP solver on large-scale equality constrained problems.

namenmnnznitersf evalsCG iterstimeoptc viol
HAGER2100015000150007764.961.6947e-081.8914e-12
HAGER3100015000150007764.986.2766e-081.8369e-12
ORTHREGA205310247168731131789.51.5134e-082.0262e-15
ORTHREGC100550035004267810.758.8626e-088.1001e-16
ORTHREGD*1000350002500016161651.06.5561e-087.1054e-13
DTOC1ND*29981996139721717281.257.4098e-082.2138e-13
DTOC229981996798412122211.263.8127e-086.5081e-12
DTOC3149999998349931010826.151.8746e-083.5527e-15
DTOC41499999983499377618.52.8176e-086.5436e-12
DTOC599994999149979987.972.9281e-082.0709e-12
DTOC62001100030001919380.52.8538e-088.0491e-16
EIGENA2255012751250005540.392.8422e-140.0000e+00
EIGENC2462231926129362950.437.0736e-084.4869e-16
ARTIF100210003000111100.160.0000e+004.9495e-10
BRATU3D49133375236256606.320.0000e+001.7761e-10

* Solver is working with non-default initial trust-radius/penalty.

The interior point method was also tested on a set of large-scale problems and the results are displayed on the table bellow:

namenmnnznitersf evalsCG iterstimeoptc viol
CORKSCRW456350105061531770.621.1608e-082.3709e-10
COSHFUN*612011839371824081.692.5143e-082.8721e-08
DIXCHLNV10050255034252490.322.2829e-085.5511e-16
HAGER420011000300040311941.326.7230e-081.9438e-12
HIMMELBK2414336931001000.325.5796e-081.2075e-08
NGONE**10012734996100119533409121.278.2771e-074.0800e-10
OPTCNTRL3220706455710.337.0090e-087.8022e-08
OPTMASS1210100532161522691452.34.6736e-131.8061e-11
ORTHREGF120540032003730451.33.0486e-085.7454e-14
SVANBERG5005004500393122112.262.5408e-083.0900e-08
READING12021004004056320.32.6524e-081.1029e-10

* Solver is working with non-default initial trust-radius/penalty/barrier parameter.

** Fails to convege

For each problem the above tables provides the number of variable n, the number of constraints m, the number of nonzero jacobian elements nnz, the number of iterations niters, the number of function evaluations f evals, the number of CG iteractions CG iters, the total running time time, the optimality of the solution opt (gradient of the lagrangian norm) and the constraint violation c_viol (norm of the constraints).

The solver fails to converge with the desired optimality in the problem NGONE and gets interrupted for reaching 1000 iteration. Nevertheless it does get very close to a solution.

I have also tested both solvers on many nonlinear small problems to test their robustness. The results are displayed on the table bellow. For problems with no inequalities constraints the equality_constrained_sqp method is used, otherwise the interior point method tr_interior_point is used. This choice is motivated by the fact that the interior point solver does not offers any advantages in relation to equality_constrained_sqp when no inequality constraints are present and, on the other hand, the SQP solver cannot deals with inequality constraints.

namenmnitersf evalsCG iterstimeoptc violmethod
HS7219980.021.7663e-152.6645e-14equality_constrained_sqp
HS10211914200.061.6462e-081.6433e-08tr_interior_point
HS1121128110.043.5341e-082.6238e-09tr_interior_point
HS13212718220.114.1431e-084.4427e-08tr_interior_point
HS142214980.051.1981e-081.3775e-09tr_interior_point
HS16222115190.095.9156e-123.1605e-14tr_interior_point
HS17223628420.144.1628e-082.1239e-10tr_interior_point
HS19225143450.211.7639e-121.0397e-14tr_interior_point
HS20231511130.061.0765e-107.6798e-13tr_interior_point
HS22221511120.054.4231e-082.3549e-09tr_interior_point
HS24232113120.083.1179e-081.2526e-16tr_interior_point
HS26312222410.061.2174e-104.9481e-08equality_constrained_sqp
HS28313330.019.8334e-164.4409e-16equality_constrained_sqp
HS3131128180.056.8221e-085.1291e-10tr_interior_point
HS32322617230.121.7249e-087.9836e-13tr_interior_point
HS33323024250.115.4584e-088.4626e-14tr_interior_point
HS39421616180.041.3941e-113.9848e-12equality_constrained_sqp
HS46522949700.089.4806e-083.3307e-16equality_constrained_sqp
HS5153101090.039.6031e-084.4409e-16equality_constrained_sqp
HS52532220.013.5527e-151.1102e-16equality_constrained_sqp
HS535316880.063.5548e-081.7764e-15tr_interior_point
HS633213870.051.2935e-091.6548e-08tr_interior_point
HS64313430530.151.2576e-086.8588e-11tr_interior_point
HS65312217320.11.1647e-081.3055e-08tr_interior_point
HS70414650870.213.6633e-085.4290e-14tr_interior_point
HS71422015260.091.9529e-112.6958e-10tr_interior_point
HS72422621410.111.5971e-112.9104e-11tr_interior_point
HS73431814230.086.6664e-088.6237e-08tr_interior_point
HS74451812110.085.9286e-122.2775e-09tr_interior_point
HS75451041011000.532.4438e-088.2036e-10tr_interior_point
HS77521820340.056.3707e-083.7303e-14equality_constrained_sqp
HS78535540.017.5462e-116.1410e-11equality_constrained_sqp
HS795377120.021.7792e-111.2566e-11equality_constrained_sqp
HS8053171080.065.5398e-127.7953e-10tr_interior_point
HS8153171080.065.5400e-127.7953e-10tr_interior_point
HS83535647840.268.5807e-081.4211e-14tr_interior_point
HS84533021390.137.9979e-082.3283e-10tr_interior_point
HS85*5211422571420.755.1953e-087.0781e-08tr_interior_point
HS865102115380.094.0448e-086.5503e-15tr_interior_point
HS93622619670.128.1024e-101.0978e-12tr_interior_point
HS95641811761760.554.9185e-081.8147e-11tr_interior_point
HS96642262272300.73.7408e-087.4934e-11tr_interior_point
HS97*645956016301.872.7109e-081.8602e-09tr_interior_point
HS98*644124135921.344.1266e-082.3293e-09tr_interior_point
HS99**72861421580.172.6963e-042.9104e-11tr_interior_point
HS100742922920.115.4858e-083.9712e-14tr_interior_point
HS104*8547391510.225.2744e-081.5324e-10tr_interior_point
HS1058146421490.273.0374e-084.9440e-17tr_interior_point
HS106862563463330.945.9059e-086.8528e-09tr_interior_point
HS107961713260.076.4559e-102.6756e-13tr_interior_point
HS1089131121591790.419.9895e-081.3809e-10tr_interior_point
HS109**9101001100111574.39.9912e-024.4244e+04tr_interior_point
HS1111032720470.113.4073e-088.4907e-12tr_interior_point
HS112*1033831740.171.1989e-089.7145e-17tr_interior_point
HS11310839311150.154.7649e-081.6342e-13tr_interior_point
HS114*101186882710.445.3934e-082.1956e-12tr_interior_point
HS11613141451574650.624.3199e-081.3091e-12tr_interior_point
HS11715538291170.184.8370e-084.0625e-13tr_interior_point
HS11815175849890.297.7744e-081.4211e-14tr_interior_point
HS11916838291120.195.3776e-088.8818e-16tr_interior_point

* Solver is working with non-default initial trust-radius/penalty/barrier parameter.

** Fails to convege

The algorithm fails on HS99 and on HS109. In the first it fails but it does terminate very close to an solution. And in the problem HS109, it fails because the Jacobian matrix becomes singular.

References

[1]    Gould, Nicholas IM, Dominique Orban, and Philippe L. Toint. “CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization.” Computational Optimization and Applications 60.3 (2015): 545-557.