×

zbMATH — the first resource for mathematics

A partial first-order affine-scaling method. (English) Zbl 1461.65153
Summary: We present a partial first-order affine-scaling method for solving smooth optimization with linear inequality constraints. At each iteration, the algorithm considers a subset of the constraints to reduce the complexity. We prove the global convergence of the algorithm for general smooth objective functions, and show it converges at sublinear rate when the objective function is quadratic. Numerical experiments indicate that our algorithm is efficient.
MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C51 Interior-point methods
PDF BibTeX Cite
Full Text: DOI
References:
[1] Adler, I.; Resende, G. C.; Veiga, G.; etal., An implementation of karmarkar’s algorithm for linear programming, Math. Programming, 44, 297-335, (1989) · Zbl 0682.90061
[2] Barnes, E. R., A variation on karmarkar’s algorithm for solving linear programming problems, Math. Programming, 36, 174-182, (1986) · Zbl 0626.90052
[3] Bellavia, S.; Macconi, M.; Morini, B., An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44, 257-280, (2003) · Zbl 1018.65067
[4] Bonnans, J. F.; Pola, C., A trust region interior point algorithm for linearly constrained optimization, SIAM J. Optimiz., 7, 717-731, (1997) · Zbl 0899.90146
[5] Byrd, R. H.; Gilbert, J. C. N. J., A trust region method based on interior point techniques for nonlinear programming, Math. Programming, 89, 149-185, (2000) · Zbl 1033.90152
[6] Byrd, R. H.; Hribar, M. E.; Nocedal, J., An interior point algorithm for large-scale nonlinear programming, SIAM J. Optimiz., 9, 877-900, (1999) · Zbl 0957.65057
[7] Coleman, T. F.; Li, Y., A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints, Math. Programming, 88, 1-31, (2000) · Zbl 0966.65052
[8] Dantzig, G. B.; Ye, Y., A build-up interior-point method for linear programming: Affine scaling form. Tech. Rep., (1991)
[9] Dikin, I. I., No article title, Iterative solution of problems of linear and quadratic programming., 8, 747-748, (1967)
[10] Gonzaga, C. C., Carlos, L. A.: A primal affine-scaling algorithm for constrained convex programs. Report ES-238/90, COPPE-Federal University of Rio de Janeiro, 1990. Revised in September, 2002
[11] Hoffman, A. J., On approximate solutions of systems of linear inequalities, J. Research National Bureau Standards, 49, 263-265, (2015)
[12] Garbow, J. J. B. S.; Hillstrom, K. E., Algorithm 566: Fortran subroutines for testing unconstrained optimization software [c5], [e4], ACM Trans. Math. Software, 7, 136-140, (1981)
[13] Mangasarian, O. L., A simple characterization of solution sets of convex programs, Operations Research Letters, 7, 21-26, (1988) · Zbl 0653.90055
[14] Monma, C. L.; Morton, A. J., Computational experience with a dual affine variant of karmarkar’s method for linear programming, Operations Research Letters, 6, 261-267, (1987) · Zbl 0627.90065
[15] Monteiro, R. D. C.; Wang, Y., Trust region affine scaling algorithms for linearly constrained convex and concave programs, Math. Programming, 80, 283-313, (1998) · Zbl 0901.90166
[16] Tits, A.; Absil, P. A.; Woessner, W. P., Constraint reduction for linear programs with many inequality constraints, SIAM J. Optimiz., 17, 119-146, (2006) · Zbl 1112.90049
[17] Tseng, P., Partial affine-scaling for linearly constrained minimization, Math. Operations Research, 20, 678-694, (1995) · Zbl 0845.90110
[18] Tseng, P.; Bomze, I. M.; Schachinger, W., A first-order interior-point method for linearly constrained smooth optimization, Math. Programming, 127, 399-424, (2011) · Zbl 1216.49028
[19] Vanderbei, R. J.; Meketon, M. S.; Freedman, B. A., A modification of karmarkar’s linear programming algorithm, Algorithmica, 1, 395-407, (1986) · Zbl 0626.90056
[20] Waltz, R. A.; Morales, J. L.; Nocedal, J.; etal., An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math. Programming, 107, 391-408, (2006) · Zbl 1134.90053
[21] Wang, X.; Yuan, Y. X., A trust region method based on a new affine scaling technique for simple bounded optimization, Optimization Methods & Software, 28, 1-18, (2013) · Zbl 1307.90174
[22] Winternitz, L. M. B.: Primal-dual interior-point algorithms for linear programs with many inequality constraints. Dissertations & Theses-Gradworks, University of Maryland, College Park, Md., 2010
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.