×

An affine-scaling interior-point CBB method for box-constrained optimization. (English) Zbl 1168.90007

An affine-scaling interior-point algorithm for box-constrained nonlinear optimization problems is developed. The k-th direction in the algorithm is a quasi-Newton direction for the first order optimality (KKT) conditions for the problem, where in regard to large systems as they occur, for example, in the context of image reconstruction for positron emission tomography (PET), the current Hessian of the objective function is replaced by a suitable multiple of the unit matrix. The respective factor for the unit matrix is computed by a cyclic modification of a rule which is used in the Barzilai-Borwein (BB) quasi-Newton method. In order to relate to further original features of BB type methods which typically do not reduce the value of the cost function in a monotonic way, the method is connected with a nonmonotone line search procedure. The authors prove global convergence of the method as well as local r-linear convergence to a local minimizer which is nondegenerate and satisfies the second order sufficiency optimality conditions. Numerical experiments demonstrate that the speed of convergence of the method is relatively independent of the conditioning of the problem. They moreover indicate that the new method is more efficient than the earlier developed conjugate gradient based active set algorithm ASA if a not too small error tolerance is chosen, but that it is inferior to the latter algorithm if many iterations are needed and the error tolerance is tiny respectively.

MSC:

90C06 Large-scale problems in mathematical programming
90C26 Nonconvex programming, global optimization
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akaike H. (1959). On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Stat. Math. Tokyo 11: 1–17 · Zbl 0100.14002 · doi:10.1007/BF01831719
[2] Barzilai J. and Borwein J.M. (1988). Two point step size gradient methods. IMA J. Numer. Anal. 8: 141–148 · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[3] Birgin E.G., Biloti R., Tygel M. and Santos L.T. (1999). Restricted optimization: a clue to a fast and accurate implementation of the common reflection surface stack method. J. Appl. Geophys. 42: 143–155 · doi:10.1016/S0926-9851(99)00035-X
[4] Birgin E.G., Chambouleyron I. and Martínez J.M. (1999). Estimation of the optical constants and the thickness of thin films using unconstrained optimization. J. Comput. Phys. 151: 862–880 · Zbl 1017.74501 · doi:10.1006/jcph.1999.6224
[5] Birgin E.G., Martínez J.M. and Raydan M. (2000). Nonmonotone spectral projected gradient methods for convex sets. SIAM J. Optim. 10: 1196–1211 · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[6] Chang, J.-H., Anderson, J.M.M., Mair, B.A.: An accelerated penalized maximum likelihood algorithm for positron emission tomography. IEEE Trans. Nucl. Sci. 54(5): 1648–1659
[7] Chang J.-H., Anderson J.M.M. and Votaw J.R. (2004). Regularized image reconstruction algorithms for positron emission tomography. IEEE Trans. Med. Imag. 23: 1165–1195 · doi:10.1109/TMI.2004.831224
[8] Coleman T.F. and Li Y. (1994). On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds. Math. Prog. 67: 189–224 · Zbl 0842.90106 · doi:10.1007/BF01582221
[9] Coleman T.F. and Li Y. (1996). An interior trust region approach for nonlinear minimization subject to bounds. SIAM J. Optim. 6: 418–445 · Zbl 0855.65063 · doi:10.1137/0806023
[10] Coleman T.F. and Li Y. (2000). A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints. Math. Program. 88: 1–31 · Zbl 0966.65052 · doi:10.1007/PL00011369
[11] Dai Y.H. (2003). Alternate stepsize gradient method. Optimization 52: 395–415 · Zbl 1056.65055 · doi:10.1080/02331930310001611547
[12] Dai Y.H. and Fletcher R. (2005). Projected Barzilai–Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100: 21–47 · Zbl 1068.65073 · doi:10.1007/s00211-004-0569-y
[13] Dai Y.H., Hager W.W., Schittkowski K. and Zhang H. (2006). The cyclic Barzilai–Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26: 604–627 · Zbl 1147.65315 · doi:10.1093/imanum/drl006
[14] Dai Y.H. and Zhang H. (2001). An adaptive two-point stepsize gradient algorithm. Numer. Algorithms 27: 377–385 · Zbl 0992.65063 · doi:10.1023/A:1013844413130
[15] Dikin I.I. (1967). Iterative solution of problems of linear and quadratic programming. Sov. Math. Dokl. 8: 674–675 · Zbl 0189.19504
[16] Dostál Z. (1997). Box constrained quadratic programming with proportioning and projections. SIAM J. Optim. 7: 871–887 · Zbl 0912.65052 · doi:10.1137/S1052623494266250
[17] Fletcher, R.: On the Barzilai–Borwein method. Technical Report, Department of Mathematics, University of Dundee, Dundee (2001) · Zbl 1118.90318
[18] Friedlander A., Martínez J.M., Molina B. and Raydan M. (1999). Gradient method with retards and generalizations. SIAM J. Numer. Anal. 36: 275–289 · Zbl 0940.65032 · doi:10.1137/S003614299427315X
[19] Glunt W., Hayden T.L. and Raydan M. (1993). Molecular conformations from distance matrices. J. Comput. Chem. 14: 114–120 · doi:10.1002/jcc.540140115
[20] Hager W.W. and Zhang H. (2006). A new active set algorithm for box constrained optimization. SIAM J. Optim. 17: 526–557 · Zbl 1165.90570 · doi:10.1137/050635225
[21] Heinkenschloss M., Ulbrich M. and Ulbrich S. (1999). Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption. Math. Program. 86: 615–635 · Zbl 0945.49023 · doi:10.1007/s101070050107
[22] Johnson C.A., Seidel J. and Sofer A. (2000). Interior-point methodology for 3-D PET reconstruction. IEEE Trans. Med. Imag. 19: 271–285 · doi:10.1109/42.848179
[23] Kanzow C. and Klug A. (2006). On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints. Comput. Optim. Appl. 35: 177–197 · Zbl 1151.90552 · doi:10.1007/s10589-006-6514-5
[24] Kaufman L. (1987). Implementing and accelerating the EM algorithm for positron emission tomography. IEEE Trans. Med. Imag. 6: 37–51 · doi:10.1109/TMI.1987.4307796
[25] Kaufman L. (1993). Maximum likelihood, least squares and penalized least squares for PET. IEEE Trans. Med. Imag. 12: 200–214 · doi:10.1109/42.232249
[26] Raydan M. (1997). The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7: 26–33 · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[27] Zhang H. and Hager W.W. (2004). A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14: 1043–1056 · Zbl 1073.90024 · doi:10.1137/S1052623403428208
[28] Zhang H. and Hager W.W. (2005). PACBB: a projected adaptive cyclic Barzilai–Borwein method for box constrained optimization. In: Hager, W.W., Huang, S.-J., Pardalos, P.M. and Prokopyev, O.A. (eds) Multiscale Optimization Methods and Applications, pp 387–392. Springer, New York · Zbl 1100.90050
[29] Zhang, Y.: Interior-point gradient methods with diagonal-scalings for simple-bound constrained optimization. Technical Report, TR04-06, Department of Computational and Applied Mathematics. Rice University, Houston (2004)
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.