A decomposition method for large-scale box constrained optimization. (English) Zbl 1410.90207
Summary: A decomposition method for solving large-scale box constrained optimization is proposed. The algorithm is motivated by the successful use of the decomposition method presented by Joachims for training support vector machines. In particular, a new technique, based on the new definition “KKT-violating index”, is introduced for working set identification. Finally, the numerical experiments and implementation details show that this method is practical for large-scale problems.
Keywords:
box constrained optimization; decomposition method; working set identification; large-scale; KKT-violating indexSoftware:
SVMlightReferences:
| [1] | Glowinski, R., Numerical methods for nonlinear variational problems, (1984), Springer-Verlag Berlin, New York · Zbl 0575.65123 |
| [2] | Ciarlet, P. G., The finite element method for elliptic problems, (1978), NorthCHolland Amsterdam · Zbl 0383.65058 |
| [3] | Glunt, W.; Hayden, T. L.; Raydan, M., Molecular conformations from distance matrices, J. Comput. Chem., 14, 114-120, (1993) |
| [4] | Moré, J. J.; Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM J. Optim., 1, 93-113, (1991) · Zbl 0752.90053 |
| [5] | Birgin, E. G.; Chambouleyron, I.; Martínez, J. M., Estimation of the optical constants and the thickness of thin films using unconstrained optimization, J. Comput. Phys., 151, 862-880, (1999) · Zbl 1017.74501 |
| [6] | Birgin, E. G.; Biloti, R.; Tygel, M.; Santos, L. T., Restricted optimization: a clue to a fast and accurate implementation of the common reflection surface stack method, J. Appl. Geophys., 42, 143-155, (1999) |
| [7] | Birgin, E. G.; Martínez, J. M., A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients, (Topics in Numerical Analysis, Computational Supplements, vol. 15, (2001), Springer Vienna), 49-60 · Zbl 1002.65067 |
| [8] | Facchinei, F.; Lucidi, S.; Palagi, L., A truncated Newton algorithm for large scale box constrained optimization, SIAM J. Optim., 12, 1100-1125, (2002) · Zbl 1035.90103 |
| [9] | Ni, Q.; Yuan, Y. X., A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput., 66, 1509-1520, (1997) · Zbl 0886.65065 |
| [10] | Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 149-154, (1964) · Zbl 0132.11701 |
| [11] | Dostál, Z., Box constrained quadratic programming with proportioning and projections, SIAM J. Optim., 7, 871-887, (1997) · Zbl 0912.65052 |
| [12] | Conn, A. R.; Gould, N. I.M.; Toint, Ph. L., Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM J. Numer. Anal., 25, 433-460, (1988) · Zbl 0643.65031 |
| [13] | Friedlander, A.; Martínez, J. M.; Santos, S. A., A new trust region algorithm for bound constrained minimization, Appl. Math. Optim., 30, 235-266, (1994) · Zbl 0821.90101 |
| [14] | Lescrenier, M., Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold, SIAM J. Numer. Anal., 28, 476-495, (1991) · Zbl 0726.65068 |
| [15] | Heinkenschloss, M.; Ulbrich, M.; Ulbrich, S., 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, (1999) · Zbl 0945.49023 |
| [16] | Kanzow, C.; Klug, A., On affine-scaling interior-point Newton methods for nonlinear minimization with bound constraints, Comput. Optim. Appl., 35, 177-197, (2006) · Zbl 1151.90552 |
| [17] | Polyak, B. T., The conjugate gradient method in extremal problems, USSR Comput. Math. Math. Phys., 9, 94-112, (1969) · Zbl 0229.49023 |
| [18] | R.S. Dembo, U. Tulowitzki, On the minimization of quadratic functions subject to box constraints, Tech. report, School of organization and management, Yale University New Haven, CT, 1983. |
| [19] | Hager, W. W.; Zhang, H., A new active set algorithm for box constrained optimization, SIAM J. Optim., 17, 526-557, (2006) · Zbl 1165.90570 |
| [20] | Facchinei, F.; Judice, J.; Soares, J., An active set Newton algorithm for large-scale nonlinear programs with box constraints, SIAM J. Optim., 8, 158-186, (1998) · Zbl 0911.90301 |
| [21] | Lin, C. J., On the convergence of the decomposition method for support vector machines, IEEE Trans. Neural Networks, 12, 6, 1288-1298, (2001) · Zbl 1012.94501 |
| [22] | Lucidi, S.; Palagi, L.; Risi, A.; Sciandrone, M., A convergent decomposition algorithm for support vector machines, Comput. Optim. Appl., 38, 217-234, (2007) · Zbl 1172.90443 |
| [23] | C.J. Lin, Linear convergence of a decomposition method for support vector machines, Technical Report, Department of Computer Science and Information Engineering, Taiwan University, Taipei, Taiwan, 2001. |
| [24] | Joachims, T., Making large-scale SVM learning practical, (Schölkopf, B.; Burges, C. J.C.; Smola, A. J., Advances in Kernel Methods - Support Vector Learning, (1998), MIT Press Cambridge), 169-184 · Zbl 0935.68084 |
| [25] | Platt, J., Sequential minimal optimization: A fast algorithm for training support vector machines, (Schölkopf, B.; Burges, C. J.C.; Smola, A. J., Advances in Kernel Methods - Support Vector Learning, (1998), MIT Press Cambridge), 185-208 |
| [26] | Chen, P. H.; Fan, R. E.; Lin, C. J., A study on SMO-type decomposition methods for support vector machines, IEEE Trans. Neural Networks, 17, 893-908, (2006) |
| [27] | Zoutendijk, G., Methods of feasible directions, (1960), Elsevier Amsterdam, Holland · Zbl 0097.35408 |
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.
