×

Large-scale quasi-Newton trust-region methods with low-dimensional linear equality constraints. (English) Zbl 1435.90147

Summary: We propose two limited-memory BFGS (L-BFGS) trust-region methods for large-scale optimization with linear equality constraints. The methods are intended for problems where the number of equality constraints is small. By exploiting the structure of the quasi-Newton compact representation, both proposed methods solve the trust-region subproblems nearly exactly, even for large problems. We derive theoretical global convergence results of the proposed algorithms, and compare their numerical effectiveness and performance on a variety of large-scale problems.

MSC:

90C53 Methods of quasi-Newton type
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2007) · Zbl 1058.90049
[2] Brust, J.J., Burdakov, O., Erway, J.B., Marcia, R.F., Yuan, Y.X.: Shape-changing L-SR1 trust-region methods. Technical Report 2016-2, Department of Mathematics, Wake Forest University (2016)
[3] Brust, JJ; Burdakov, OP; Erway, JB; Marcia, RF, Dense initializations for limited-memory quasi-Newton methods, Comput. Optim. Appl., 74, 121-142 (2019) · Zbl 1427.90292 · doi:10.1007/s10589-019-00112-x
[4] Brust, JJ; Erway, JB; Marcia, RF, On solving L-SR1 trust-region subproblems, Comput. Optim. Appl., 66, 245-266 (2017) · Zbl 1364.90239 · doi:10.1007/s10589-016-9868-3
[5] Burdakov, O.; Gong, L.; Yuan, YX; Zikrin, S., On efficiently combining limited memory and trust-region techniques, Math. Program. Comput., 9, 101-134 (2016) · Zbl 1368.90103 · doi:10.1007/s12532-016-0109-7
[6] Burdakov, O.; Martinez, J.; Pilotta, E., A limited-memory multipoint symmetric secant method for bound constrained optimization, Ann. Oper. Res., 117, 51-70 (2002) · Zbl 1025.90038 · doi:10.1023/A:1021561204463
[7] Burke, J.V., Wiegmann, A., Xu, L.: Limited memory BFGS updating in a trust-region framework. Technical Report, University of Washington (1996)
[8] Byrd, RH; Gilbert, JC; Nocedal, J., A trust region method based on interior point techniques for nonlinear programming, Math. Program. Ser. A, 89, 149-185 (2000) · Zbl 1033.90152 · doi:10.1007/PL00011391
[9] Byrd, RH; Hribar, M.; Nocedal, J., An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9, 877-900 (1999) · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[10] Byrd, RH; Nocedal, J.; Schnabel, RB, Representations of quasi-Newton matrices and their use in limited-memory methods, Math. Program., 63, 129-156 (1994) · Zbl 0809.90116 · doi:10.1007/BF01582063
[11] Celis, M., Dennis Jr., J., Tapia, R.: A trust region strategy for equality constrained optimization. Technical Report 84-1, Mathematical Sciences Department, Rice University (1984) · Zbl 0566.65048
[12] Coleman, T., Branch, M.A., Grace, A.: Optimization Toolbox for Use with MATLAB. MathWorks, Natick (1999)
[13] Coleman, T.; Verma, A., A preconditioned conjugate gradient approach to linear equality constrained minimization, Comput. Optim. Appl., 20, 61-72 (2001) · Zbl 0983.90073 · doi:10.1023/A:1011271406353
[14] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071 · doi:10.1137/1.9780898719857
[15] DeGuchy, O.; Erway, JB; Marcia, RF, Compact representation of the full Broyden class of quasi-Newton updates, Numer Linear Algebra Appl, 25, e2186 (2018) · Zbl 1513.65147 · doi:10.1002/nla.2186
[16] Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[17] Erway, JB; Marcia, RF, Algorithm 943: MSS: MATLAB software for L-BFGS trust-region subproblems for large-scale optimization, ACM Trans. Math. Softw., 40, 28:1-28:12 (2014) · Zbl 1371.65050 · doi:10.1145/2616588
[18] Hager, WW, Updating the inverse of a matrix, SIAM Rev., 31, 221-239 (1989) · Zbl 0671.65018 · doi:10.1137/1031049
[19] Lalee, M.; Nocedal, J.; Plantenga, T., On the implementation of an algorithm for large-scale equality constrained optimization, SIAM J. Optim., 8, 682-706 (1998) · Zbl 0913.65055 · doi:10.1137/S1052623493262993
[20] Moré, JJ; Sorensen, DC, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572 (1983) · Zbl 0551.65042 · doi:10.1137/0904038
[21] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[22] Powell, M.; Yuan, Y., A trust region algorithm for equality constrained optimization, Math. Program., 49, 189-211 (1991) · Zbl 0816.90121 · doi:10.1007/BF01588787
[23] Saunders, M.A.: PDCO: Primal-dual interior method for convex objectives (2002-2015). http://www.stanford.edu/group/SOL/software/pdco.html. Accessed 21 June 2018
[24] Steihaug, T., The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20, 626-637 (1983) · Zbl 0518.65042 · doi:10.1137/0720042
[25] Vardi, A., A trust region algorithm for equality constrained minimization: convergence properties and implementation, SIAM J. Numer. Anal., 22, 575-591 (1985) · Zbl 0581.65045 · doi:10.1137/0722035
[26] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[27] Waltz, R.; Morales, J.; Nocedal, J.; Orban, D., An interior algorithm for nonlinear optimization that combines line search and trust region steps, SIAM. J. Optim., 9, 877-900 (1999) · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[28] Yuan, Y.X.: Trust region algorithms for constrained optimization. Technical report, State Key Laboratory of Scientific and Engineering Computing, Beijing · Zbl 0711.90062
[29] Zhijiang, S.: RSQP toolbox for MATLAB (2006). https://www.mathworks.com/matlabcentral/fileexchange/13046-rsqp-toolbox-for-matlab. Accessed 21 June 2018
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.