Error Bound property in mathematical programming
https://doi.org/10.29235/1561-2430-2019-55-3-309-318
Abstract
This article is devoted to the Error Bound property (also named R-regularity) in mathematical programming problems. This property plays an important role in analyzing the convergence of numerical optimization algorithms, a topic covered by multiple publications, and at the same time it is a relatively generic constraint qualification that guarantees the satisfaction of the necessary Kuhn – Tucker optimality conditions in mathematical programming problems. In the article, new sufficient conditions for the error bound property are described, and it’s also shown that several known necessary conditions are insufficient. The sufficient conditions obtained can be used to prove the regularity of a large class of sets including sets that cannot be proven regular by other known constraints.
About the Authors
D. E. Berezhnov
Belarusian State University of Informatics and Radioelectronics
Belarus
Belarus
Daniil E. Berezhnov – Assistant of the Department of Informatics
6, P. Brovka Str., 220013, Minsk, Republic of Belarus
L. I. Minchenko
Belarusian State University of Informatics and Radioelectronics
Belarus
Belarus
Leonid I. Minchenko – Dr. Sc. (Physics and Mathematics), Professor, Professor of the Department of Informatics
6, P. Brovka Str., 220013, Minsk, Republic of Belarus
References
1. Hoffman A. J. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 1952, vol. 49, no. 4, pp. 263–265. https://doi.org/10.6028/jres.049.027
2. Robinson S. M. Stability theory for systems of inequality constraints. Part I: linear systems. SIAM Journal on Numerical Analysis, 1975, vol. 12, no. 5, pp. 754–769. https://doi.org/10.1137/0712056
3. Fedorov V. V. Numerical Methods of Maximin. Moscow, Nauka Publ., 1979. 280 p. (in Russian).
4. Ioffe A. D. Regular points of Lipschitz functions. Transactions of the American Mathematical Society, 1979, vol. 251, pp. 61–69. https://doi.org/10.1090/s0002-9947-1979-0531969-6
5. Luderer B., Minchenko L., Satsura T. Multivalued Analysis and Nonlinear Programming Problems with Perturbations. Dordrecht, Kluwer Acad. Publ., 2002, 220 p. https://doi.org/10.1007/978-1-4757-3468-3
6. Pang J. S. Error bounds in mathematical programming. Mathematical Programming, 1997, vol. 79, no. 1–3, pp. 299– 332. https://doi.org/10.1007/bf02614322
7. Wu Z. L., Ye J. J. Sufficient conditions for error bounds. SIAM Journal on Optimization, 2001, vol. 12, no. 2, pp. 421–435. https://doi.org/10.1137/s1052623400371557
8. Bosch P., Jourani A., Henrion R. Sufficient conditions for error bounds and applications. Applied Mathematics and Optimization, 2004, vol. 50, no. 2, pp. 161–181. https://doi.org/10.1007/s00245-004-0799-5
9. Fabian M. J., Henrion R., Kruger A. Y., Outrata J. V. Error Bounds: Necessary and Sufficient Conditions. Set-Valued and Variational Analysis, 2010, vol. 18, no. 2, pp. 121–149. https://doi.org/10.1007/s11228-010-0133-0
10. Minchenko L. I., Stakhovski S. M. On relaxed constant rank regularity condition in mathematical programming. Optimization, 2011, vol. 60, no. 4, pp. 429–440. https://doi.org/10.1080/02331930902971377
11. Minchenko L., Stakhovski S. Parametric nonlinear programming problems under relaxed constant rank regularity condition. SIAM Journal on Optimization, 2011, vol. 21, no. 1, pp. 314–332. https://doi.org/10.1137/090761318
12. Minchenko L., Tarakanov A. On error bounds for quasinormal programs. Journal of Optimization Theory and Applications, 2011, vol. 148, no. 3, pp. 571–579. https://doi.org/10.1007/s10957-010-9768-0
13. Minchenko L. I., Stakhovskii S. M. On the generalization of the Mangasarian-Fromovitz constraint. Doklady BGUIR, 2010, vol. 8, pp. 104–109 (in Russian).
14. Kruger A. Y., Minchenko L. I., Outrata J. V. On relaxing the Mangasarain–Fromovitz constaint qualication. Positivity, 2014, vol. 18, no. 1, pp. 1–17. ttps://doi.org/10.1007/s11117-013-0238-4
15. Andreani R., Haeser G., Schuverdt M. L., Silva P. J. S. Two new weak constraint qualifications and applications. SIAM Journal on Optimization, 2012, vol. 22, no. 3, pp. 1109–1125. https://doi.org/10.1137/110843939
16. Guo L., Zhang J., Lin G.-H. New results on constraint qualifications for nonlinear extremum problems and extensions. Journal of Optimization Theory and Applications, 2014, vol. 163, no. 3, pp. 737–754. https://doi.org/10.1007/s10957-013-0510-6
17. Ye J. J., Zhou J. Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems. Mathematical Programming, 2018, vol. 171, no. 1–2, pp. 361–395. https://doi.org/10.1007/s10107-017-1193-9
18. Mangasarian O. L., Fromovitz S. The Fritz-John necessary optimality conditions in presence of equality and inequality constraints. Journal of Mathematical Analysis and Applications, 1967, vol. 17, no. 1, pp. 37–47. https://doi.org/10.1016/0022-247x(67)90163-1
19. Janin R. Direction derivative of the marginal function in nonlinear programming. Mathematical Programming Study, 1984, vol. 21, pp. 127–138. https://doi.org/10.1007/bfb0121214
20. Leshchev E. A., Minchenko L. I. Weakly regular mathematical programming problems. Vestsі Natsyianal’nai aka- demіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2014, vol. 2, pp. 64–70 (in Russian).
21. Bertsekas D. P., Ozdaglar A. E. The relation between pseudonormality and quasiregularity in constrained optimization. Optimization Methods and Software, 2004, vol. 19, no. 5, pp. 493–506. https://doi.org/10.1080/10556780410001709420
22. Clarke F. Optimization and non-smooth analysis. New York, Willey, 1983. 280 p.
23. Mordukhovich B. S. Variational Analysis and Generalized Differentiation I. Basic Theory. Berlin, Springer, 2005. 1057 p. https://doi.org/10.1007/3-540-31247-1
24. Rockafellar R. T., Wets R. J.-B. Variational Analysis. Berlin, Springer, 1998, 749 p. https://doi.org/10.1007/978-3-642-02431-3
25. Gorokhovik V. V. Finite Dimensional Optimization Problems. Minsk, BSU Publishing Center, 2007. 239 p. (in Russian).
26. Minchenko L., Leschov A. On strong and weak second-order necessary optimality conditions for nonlinear programming. Optimization, 2016, vol. 65, no. 9, pp. 1693–1702. https://doi.org/10.1080/02331934.2016.1179300
Review
Views: 965
Email this article 