×

On regularization and active-set methods with complexity for constrained optimization. (English) Zbl 1390.90512

Summary: The main objective of this research is to introduce a practical method for smooth bound-constrained optimization that possesses worst-case evaluation complexity \(O(\varepsilon^{-3/2})\) for finding an \(\varepsilon\)-approximate first-order stationary point when the Hessian of the objective function is Lipschitz continuous. As other well-established algorithms for optimization with box constraints, the algorithm proceeds visiting the different faces of the domain aiming to reduce the norm of an internal projected gradient and abandoning active constraints when no additional progress is expected in the current face. The introduced method emerges as a particular case of a method for minimization with linear constraints. Moreover, the linearly constrained minimization algorithm is an instance of a minimization algorithm with general constraints whose implementation may be unaffordable when the constraints are complicated. As a procedure for leaving faces, a different method is employed that may be regarded as an independent device for constrained optimization. Such an independent algorithm may be employed to solve linearly constrained optimization problems on its own, without relying on the active-set strategy. A careful implementation and numerical experiments show that the algorithm that combines active sets with leaving-face iterations is more effective than the independent algorithm on which leaving-face iterations are based, although both exhibit similar complexities \(O(\varepsilon^{-3/2})\).

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity

Software:

ALGENCAN; SPG; CUTEst
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Andreani, E. G. Birgin, J. M. Martínez, and J. Y. Yuan, {\it Spectral projected gradient and variable metric methods for optimization with linear inequalities}, IMA J. Numer. Anal., 25 (2005), pp. 221-252, . · Zbl 1072.90051
[2] R. Andreani, G. Haeser, and J. M. Martínez, {\it On sequential optimality conditions for smooth constrained optimization}, Optimization, 60 (2011), pp. 627-641, . · Zbl 1225.90123
[3] M. Andretta, E. G. Birgin, and J. M. Martínez, {\it Practical active-set euclidian trust-region method with spectral projected gradients for bound-constrained minimization}, Optimization, 54 (2005), pp. 305-325, . · Zbl 1079.65070
[4] M. Andretta, E. G. Birgin, and J. M. Martínez, {\it Partial spectral projected gradient method with active-set strategy for linearly constrained optimization}, Numer. Algorithms, 53 (2010), pp. 23-52, . · Zbl 1185.65096
[5] D. P. Bertsekas, {\it Nonlinear Programming}, 2nd ed., Athena Scientific, Belmont, MA, 1999. · Zbl 1015.90077
[6] T. Bianconcini, G. Liuzzi, B. Morini, and M. Sciandrone, {\it On the use of iterative methods in cubic regularization for unconstrained optimization}, Comput. Optim. Appl., 60 (2015), pp. 35-57, . · Zbl 1308.90166
[7] T. Bianconcini and M. Sciandrone, {\it A cubic regularization algorithm for unconstrained optimization using line search and nonmonotone techniques}, Optim. Methods Softw., 31 (2016), pp. 1008-1035, . · Zbl 1351.49040
[8] E. G. Birgin, J. L. Gardenghi, J. M. Martínez, and S. A. Santos, {\it Is it Worth Using Third-Order Models with Fourth-Order Regularization for Unconstrained Optimization?}, Technical report MCDO131017, Institute of Mathematics, Statistics, and Scientific Computing, University of Campinas, Brazil, 2017.
[9] E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and P. L. Toint, {\it Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models}, SIAM J. Optim., 26 (2016), pp. 951-967, . · Zbl 1335.90094
[10] E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and P. L. Toint, {\it Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models}, Math. Program., 163 (2017), pp. 359-368, . · Zbl 1365.90236
[11] E. G. Birgin and J. M. Gentil, {\it Evaluating bound-constrained minimization software}, Comput. Optim. Appl., 53 (2012), pp. 347-373, . · Zbl 1258.90067
[12] E. G. Birgin and J. M. Martínez, {\it A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients}, in Topics in Numerical Analysis, Computing Suppl. 15, G. Alefeld and X. Chen, eds., Springer, Vienna, 2001, pp. 49-60, . · Zbl 1002.65067
[13] E. G. Birgin and J. M. Martínez, {\it Large-scale active-set box-constrained optimization method with spectral projected gradients}, Comput. Optim. Appl., 23 (2002), pp. 101-125, . · Zbl 1031.90012
[14] E. G. Birgin and J. M. Martínez, {\it Practical Augmented Lagrangian Methods for Constrained Optimization}, Fundam. Algorithms 10, SIAM, Philadelphia, PA, 2014, . · Zbl 1339.90312
[15] E. G. Birgin and J. M. Martínez, {\it The use of quadratic regularization with a cubic descent condition for unconstrained optimization}, SIAM J. Optim., 27 (2017), pp. 1049-1074, . · Zbl 1370.90260
[16] E. G. Birgin, J. M. Martínez, and M. Raydan, {\it Nonmonotone spectral projected gradient methods on convex sets}, SIAM J. Optim., 10 (2000), pp. 1196-1211, . · Zbl 1047.90077
[17] E. G. Birgin, J. M. Martínez, and M. Raydan, {\it Algorithm 813: SPG – software for convex-constrained optimization}, ACM Trans. Math. Software, 27 (2001), pp. 340-349, . · Zbl 1070.65547
[18] E. G. Birgin, J. M. Martínez, and M. Raydan, {\it Inexact spectral projected gradient methods on convex sets}, IMA J. Numer. Anal., 23 (2003), pp. 539-559, . · Zbl 1047.65042
[19] E. G. Birgin, J. M. Martínez, and M. Raydan, {\it Spectral projected gradient methods: Review and perspectives}, J. Stat. Softw., 60 (2014), .
[20] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization}, SIAM J. Optim., 20 (2010), pp. 2833-2852, . · Zbl 1211.90225
[21] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it Adaptive cubic regularization methods for unconstrained optimization. Part I: Motivation, convergence and numerical results}, Math. Program., 127 (2011), pp. 245-295, . · Zbl 1229.90192
[22] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it Adaptive cubic regularization methods for unconstrained optimization. Part II: Worst-case function and derivative complexity}, Math. Program., 130 (2011), pp. 295-319, . · Zbl 1229.90193
[23] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity}, IMA J. Numer. Anal., 32 (2012), pp. 1662-1695, . · Zbl 1267.65061
[24] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it Complexity bounds for second-order optimality in unconstrained optimization}, J. Complexity, 28 (2012), pp. 93-108, . · Zbl 1245.65063
[25] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it Optimal Newton-Type Methods for Nonconvex Optimization}, Technical report naXys-17-2011, Namur Center for Complex Systems (naXys), University of Namur, Belgium, 2012. · Zbl 1267.65061
[26] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it Evaluation Complexity Bounds for Smooth Constrained Nonlinear Optimization using Scaled KKT Conditions and High-Order Models}, Technical report naXys-11-2015(R1), Namur Center for Complex Systems (naXys), University of Namur, Belgium, 2015. · Zbl 1425.90113
[27] C. Cartis, N. I. M. Gould, and P. L. Toint, {\it Universal regularization methods – varying the power, the smoothness and the accuracy}, Optim. Methods Softw., to appear. · Zbl 1211.90225
[28] A. R. Conn, N. I. M. Gould, and P. L. Toint, {\it Global convergence of a class of trust region algorithms for optimization with simple bounds}, SIAM J. Numer. Anal., 25 (1988), pp. 433-460, . · Zbl 0643.65031
[29] A. R. Conn, N. I. M. Gould, and P. L. Toint, {\it Trust Region Methods}, Society for Industral and Applied Mathematics, Philadelphia, PA, 2000, .
[30] F. E. Curtis, D. P. Robinson, and M. Samadi, {\it An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of \(o(ϵ^{-3/2})\) for Nonconvex Optimization}, preprint, arXiv:1708.00475, 2017.
[31] F. E. Curtis, D. P. Robinson, and M. Samadi, {\it A trust-region algorithm with a worst-case iteration complexity of \(O(ε^{-3/2})\)}, Math. Program., 162 (2017), pp. 1-32, . · Zbl 1360.49020
[32] M. Domorádová and Z. Dostál, {\it Projector preconditioning for partially bound-constrained quadratic optimization}, Numer. Linear Algebra Appl., 14 (2007), pp. 791-806, . · Zbl 1199.65196
[33] Z. Dostál, {\it Directions of Large Decrease and Quadratic Programming}, Technical report, Department of Applied Mathematics, Technical University of Ostrava, Czech Republic, 1994.
[34] Z. Dostál, {\it Box constrained quadratic programming with proportioning and projections}, SIAM J. Optim., 7 (1997), pp. 871-887, doi:10.1137/S1052623494266250. · Zbl 0912.65052
[35] Z. Dostál, {\it Optimal Quadratic Programming Algorithms}, Springer Optim. Appl. 23, Springer, Heidelberg, Berlin, New York, 2009, .
[36] J. C. Dunn, {\it Newton’s method and the Goldstein step-length rule for constrained minimization problems}, SIAM J. Control Optim., 18 (1980), pp. 659-674, . · Zbl 0445.90098
[37] J. C. Dunn, {\it Global and asymptotic convergence rate estimates for a class of projected gradient processes}, SIAM J. Control Optim., 19 (1981), pp. 368-400, . · Zbl 0488.49015
[38] J. C. Dunn, {\it On the convergence of projected gradient processes to singular critical points}, J. Optim. Theory Appl., 55 (1987), pp. 203-216, . · Zbl 0616.90060
[39] J. P. Dussault, {\it \(Arc_q\): A new adaptive regularization by cubics}, Optim. Methods Softw., 33 (2017), pp. 322-335, . · Zbl 1397.90356
[40] R. Fletcher, {\it Practical Methods of Optimization}, 2nd ed., John Wiley and Sons, London, 1987, . · Zbl 0905.65002
[41] A. Friedlander and J. M. Martínez, {\it On the numerical solution of bound constrained optimization problems}, RAIRO Oper. Res., 23 (1989), pp. 319-341. · Zbl 0683.90073
[42] N. I. M. Gould, D. Orban, and P. L. Toint, {\it CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization}, Comput. Optim. Appl., 60 (2014), pp. 545-557, . · Zbl 1325.90004
[43] G. N. Grapiglia and Y. Nesterov, {\it Regularized Newton methods for minimizing functions with Hölder continuous hessians}, SIAM J. Optim., 27 (2017), pp. 478-506, . · Zbl 1406.49029
[44] G. N. Grapiglia, J.-Y. Yuan, and Y.-X. Yuan, {\it On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization}, Math. Program., 152 (2015), pp. 491-520, . · Zbl 1319.90065
[45] A. Griewank, {\it The Modification of Newton’s Method for Unconstrained Optimization by Bounding Cubic Terms}, Technical report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 1981.
[46] J. M. Martínez, {\it On high-order model regularization for constrained optimization}, SIAM J. Optim., 27 (2017), pp. 2447–2458, . · Zbl 1387.90200
[47] J. M. Martínez and M. Raydan, {\it Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization}, J. Global Optim., 68 (2017), pp. 367-385, . · Zbl 1379.90029
[48] J. M. Martínez and B. F. Svaiter, {\it A practical optimality condition without constraint qualifications for nonlinear programming}, J. Optim. Theory Appl., 118 (2003), pp. 117-133, . · Zbl 1033.90090
[49] J. L. Morales and J. Nocedal, {\it Remark on Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization}, ACM Trans. Math. Software, 38 (2011), article 7, . · Zbl 1365.65164
[50] B. A. Murtagh and M. A. Saunders, {\it Large-scale linearly constrained optimization}, Math. Program., 14 (1978), pp. 41-72, . · Zbl 0383.90074
[51] Y. Nesterov and B. T. Polyak, {\it Cubic regularization of Newton’s method and its global performance}, Math. Program., 108 (2006), pp. 177-205, . · Zbl 1142.90500
[52] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006, . · Zbl 1104.65059
[53] M. Weiser, P. Deuflhard, and B. Erdmann, {\it Affine conjugate adaptive Newton methods for nonlinear elastomechanics}, Optim. Methods Softw., 22 (2007), pp. 413-431, . · Zbl 1128.74007
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.