×

A new notion of error bounds: necessary and sufficient conditions. (English) Zbl 1480.49021

The paper demonstrates how minimal time functions can be treated in the framework of the existence of error bounds for a finite system of convex inequalities. A new notion of local error bounds called generalized local error bounds with respect to a closed convex subset \(F\) of the Euclidean space \(\mathcal{R}^n\) satisfying \(0\in F\) is introduced and studied. The primary goal of this work is to establish several necessary and sufficient conditions for the existence of generalized local error bounds with respect to \(F\).
The main results are divided into the following parts. First, necessary conditions for the existence of generalized local error bounds with respect to \(F\) for a finite system of convex inequalities in terms of normal cones and end sets are established. If, in addition, \(F\) is a bounded closed convex set containing the origin as an interior point, then it is shown that under additional stronger assumptions on \(F\), these necessary conditions become sufficient conditions. Further, a generalized invariant-point theorem where the classical distance is replaced by the minimal time function is provided. The obtained results are then used to prove another sufficient condition for the existence of a generalized local error bound with respect to \(F\).
The paper is well organized and structured but in some places not easy to understand due to a complicated notation. The main theorems are accompanied with simple examples illustrating the theory.

MSC:

49J53 Set-valued and variational analysis
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Azé, D.; Corvellec, J-N, On the sensitivity analysis of Hoffman constants for systems of linear inequalities, SIAM J. Optim., 12, 913-927 (2002) · Zbl 1014.65046 · doi:10.1137/S1052623400375853
[2] Chuong, TD; Jeyakumar, V., Characterizing robust local error bounds for linear inequality systems under data uncertainty, Linear Algebra Appl., 489, 199-216 (2016) · Zbl 1328.49026 · doi:10.1016/j.laa.2015.10.011
[3] Colombo, G.; Goncharov, VV; Mordukhovich Boris, S., Well-posedness of minimal time problems with constant dynamics in Banach spaces, Set Valued Anal., 18, 349-372 (2010) · Zbl 1219.49014 · doi:10.1007/s11228-010-0151-y
[4] Colombo, G.; Wolenski, PR, Variational analysis for a class of minimal time functions in Hilbert spaces, J. Convex Anal., 11, 335-361 (2004) · Zbl 1059.49028
[5] Colombo, G.; Wolenski, PR, The subgradient formula for the minimal time function in the case of constant dynamics in Hilbert space, J. Glob. Optim., 28, 269-282 (2004) · Zbl 1152.49308 · doi:10.1023/B:JOGO.0000026460.10505.dd
[6] Dancs, S.; Hegedus, M.; Medvegyev, P., A general ordering and fixed-point principle in complete metric space, Acta Sci. Math. Szeged., 46, 381-388 (1983) · Zbl 0532.54030
[7] Durea, M.; Panţiruc, M.; Strugariu, R., Minimal time function with respect to a set of directions: basic properties and applications, Optim. Methods Softw., 31, 535-561 (2016) · Zbl 1342.49021 · doi:10.1080/10556788.2015.1121488
[8] Durea, M.; Panţiruc, M.; Strugariu, R., A new of directional regularity for mappings and applications to optimization, SIAM J. Optim., 27, 1204-1229 (2017) · Zbl 1516.49016 · doi:10.1137/16M1067342
[9] Fabian, MJ; Henrion, R.; Kruger, AY; Outrata, JV, Error bounds: necessary and sufficient conditions, Set Valued Var. Anal., 18, 121-149 (2010) · Zbl 1192.49018 · doi:10.1007/s11228-010-0133-0
[10] Gfrerer, H., On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs, Set Valued Var. Anal., 21, 151-176 (2013) · Zbl 1321.49031 · doi:10.1007/s11228-012-0220-5
[11] Ha, TXD, Slopes, error bounds and weak sharp pareto minima of a vector-valued map, J. Optim. Theory Appl., 176, 634-649 (2018) · Zbl 1393.49014 · doi:10.1007/s10957-018-1240-6
[12] He, Y.; Ng, KF, Subdifferentials of a minimum time function in Banach spaces, J. Math. Anal. Appl., 321, 896-910 (2006) · Zbl 1108.46032 · doi:10.1016/j.jmaa.2005.09.009
[13] Hoffman, AJ, On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Stand., 49, 263-265 (1952) · doi:10.6028/jres.049.027
[14] Hu, H., Characterizations of the strong basic constraint qualifications, Math. Oper. Res., 30, 956-965 (2005) · Zbl 1278.90310 · doi:10.1287/moor.1050.0154
[15] Hu, H., Characterizations of local and global error bounds for convex inequalities in Banach spaces, SIAM J. Optim., 18, 309-321 (2007) · Zbl 1176.90642 · doi:10.1137/050644872
[16] Ioffe, AD, Variational Analysis of Regular Mappings. Springer Monographs in Mathematics. Theory and applications (2017), Cham: Springer, Cham · Zbl 1381.49001 · doi:10.1007/978-3-319-64277-2
[17] Ivanov, GE; Thibault, L., Infimal convolution and optimal time control problem III: minimal time projection set, SIAM J. Optim., 28, 30-44 (2018) · Zbl 1381.49012 · doi:10.1137/16M1110212
[18] Jiang, Y.; He, Y., Subdifferentials of a minimum time function in normed spaces, J. Math. Anal. Appl., 358, 410-418 (2009) · Zbl 1176.49024 · doi:10.1016/j.jmaa.2009.05.016
[19] Jourani, A., Hoffman’s error bound, local controllability and sensitivity analysis, SIAM J. Control Optim., 38, 947-970 (2000) · Zbl 0945.46023 · doi:10.1137/S0363012998339216
[20] Kruger, AY, Error bounds and metric subregularity, Optimization, 64, 49-79 (2015) · Zbl 1311.49043 · doi:10.1080/02331934.2014.938074
[21] Kruger, AY; López, MA; Théra, M., Perturbation of error bounds, Math. Program. Ser. A, 168, 533-554 (2018) · Zbl 1391.49051 · doi:10.1007/s10107-017-1129-4
[22] Lewis, AS; Pang, JS; Crouzeix, JP; Martinez Legaz, JE; Volle, M., Error bounds for convex inequality systems, Generalized Convexity, Generalized Monotonicity, 75-110 (1998), New York: Springer, New York · Zbl 0953.90048 · doi:10.1007/978-1-4613-3341-8_3
[23] Li, G., On the asymptotic well behaved functions and global error bound for convex polynomials, SIAM J. Optim., 20, 1923-1943 (2010) · Zbl 1208.90135 · doi:10.1137/080733668
[24] Li, MH; Meng, KW; Yang, XQ, On error bound moduli for locally Lipschitz and regular functions, Math. Program. Ser. A, 171, 463-487 (2018) · Zbl 1397.65095 · doi:10.1007/s10107-017-1200-1
[25] Mordukhovich, BS; Nam, NM, Applications of variational analysis to a generalized Fermat-Torricelli problem, J. Optim. Theory Appl., 148, 431-454 (2011) · Zbl 1211.90287 · doi:10.1007/s10957-010-9761-7
[26] Mordukhovich, BS; Nam, NM, An Easy Path to Convex Analysis and Applications. Synthesis Lectures on Mathematics and Statistics (2014), Williston: Morgan & Claypool Publishers, Williston · Zbl 1284.49002
[27] Nam, NM; Villalobos, MC; An, NT, Minimal time functions and the smallest intersecting ball problem with unbounded dynamics, J. Optim. Theory Appl., 154, 768-791 (2012) · Zbl 1271.90085 · doi:10.1007/s10957-012-0048-z
[28] Nam, NM; Zalinescu, C., Variational analysis of directional minimal time functions and applications to location problems, Set Valued Var. Anal., 21, 405-430 (2013) · Zbl 1321.49028 · doi:10.1007/s11228-013-0232-9
[29] Ngai, HV, Global error bounds for systems of convex polynomials over polyhedral constraints, SIAM J. Optim., 25, 521-539 (2015) · Zbl 1339.49013 · doi:10.1137/13090599X
[30] Ngai, HV; Théra, M., Error bounds for convex differentiable inequality systems in Banach spaces, Math. Program. Ser. B, 104, 465-482 (2005) · Zbl 1089.49028 · doi:10.1007/s10107-005-0624-1
[31] Ngai, HV; Théra, M., Directional metric regularity of multifunctions, Math. Oper. Res., 40, 969-991 (2015) · Zbl 1331.49024 · doi:10.1287/moor.2014.0705
[32] Ngai, HV; Tron, NH; Tinh, PN, Directional Holder metric subregularity and application to tangent cones, J. Convex Anal., 24, 417-457 (2017) · Zbl 1373.49044
[33] Pang, J-S, Error bounds in mathematical programming, Math. Program. Ser. B, 79, 299-332 (1997) · Zbl 0887.90165
[34] Rockafellar, RR; Wets, RJ-B, Variational Analysis. Grundlehren Series (Fundamental Principles of Mathematical Sciences) (1998), Berlin: Springer, Berlin · Zbl 0888.49001
[35] Robinson, SM, An application of error bound for convex programming in a linear space, SIAM J. Control. Optim., 13, 271-273 (1975) · Zbl 0297.90072 · doi:10.1137/0313015
[36] Zalinescu, C., Convex Analysis in General Vector Spaces (2002), Singapore: World Scientific, Singapore · Zbl 1023.46003 · doi:10.1142/5021
[37] Zheng, XY; Ng, KF, Metric regularity and constraint qualifications for convex inequalities on Banach spaces, SIAM J. Optim., 14, 757-772 (2004) · Zbl 1079.90103 · doi:10.1137/S1052623403423102
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.