×

On the paper “Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem”. (English) Zbl 07865034

Summary: In the paper E. M. R. Torrealba et al. [ibid. 299, No. 1, 46–59 (2022; Zbl 1495.65084)] an augmented Lagrangian algorithm was proposed for resource allocation problems with the intriguing characteristic that instead of solving the box-constrained augmented Lagrangian subproblem, they propose projecting the solution of the unconstrained subproblem onto such box. A global convergence result for the quadratic case was provided, however, this is somewhat counterintuitive, as in usual augmented Lagrangian theory, this strategy can fail in solving the augmented Lagrangian subproblems. In this note we investigate further this algorithm and we show that the proposed method may indeed fail when the Hessian of the quadratic is not a multiple of the identity. In the paper, it is not clear enough that two different projections are being used: one for obtaining their convergence results and other in their implementation. However, despite the lack of theoretical convergence, their strategy works remarkably well in some classes of problems; thus, we propose a hybrid method which uses their idea as a starting point heuristics, switching to a standard augmented Lagrangian method under certain conditions. Our contribution consists in presenting an efficient way of determining when the heuristics is failing to improve the KKT residual of the problem, suggesting that the heuristic procedure should be abandoned. Numerical results are provided showing that this strategy is successful in accelerating the standard method.

MSC:

90Bxx Operations research and management science

Citations:

Zbl 1495.65084

Software:

ALGENCAN
Full Text: DOI

References:

[1] Andreani, R.; Haeser, G.; Martínez, J. M., On sequential optimality conditions for smooth constrained optimization. Optimization, 627-641 (2011) · Zbl 1225.90123
[2] Birgin, E. G.; Floudas, C. A.; Martínez, J. M., Global minimization using an Augmented Lagrangian method with variable lower-level constraints. Mathematical Programming, 139-162 (2010) · Zbl 1198.90322
[3] Birgin, E. G.; Martínez, J. M., Practical augmented lagrangian methods for constrained optimization (2014), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1339.90312
[4] Bretthauer, K. M.; Shetty, B., The nonlinear knapsack problem-algorithms and applications. European Journal of Operational Research, 3, 459-472 (2002) · Zbl 1003.90036
[5] Cominetti, R.; Mascarenhas, W. F.; Silva, P. J.S., A Newton’s method for the continuous quadratic knapsack problem. Mathematical Programming Computation, 151-169 (2014) · Zbl 1328.65135
[6] Frangioni, A.; Gorgone, E., A library for continuous convex separable quadratic knapsack problems. European Journal of Operational Research, 37-40 (2013) · Zbl 1317.90255
[7] Hochbaum, D. S., A nonlinear knapsack problem. Operations Research Letters, 103-110 (1995) · Zbl 0838.90092
[8] Li, D.; Sun, X., Nonlinear Integer Programming (2006), Springer · Zbl 1140.90042
[9] Lotito, P. A., Issues in the implementation of the DSD algorithm for the traffic assignment problem. European Journal of Operational Research, 1577-1587 (2006) · Zbl 1142.90355
[10] Patriksson, M., A survey on the continuous nonlinear resource allocation problem. European Journal of Operational Research, 1, 1-46 (2008) · Zbl 1146.90493
[11] Patriksson, M.; Strömberg, C., Algorithms for the continuous nonlinear resource allocation problem: New implementations and numerical studies. European Journal of Operational Research, 3, 703-722 (2015) · Zbl 1346.90672
[12] Torrealba, E. M.R.; J. G., Silva.; L. C., Matioli.; Kolossoski, O.; Santos, P. J.S., Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem. European Journal of Operational Research, 1, 46-59 (2021) · Zbl 1495.65084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.