Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

The error bound property for a solution set defined by a set-valued mapping refers to an inequality that bounds the distance between vectors closed to a solution of the given set by a residual function. The error bound property is a Lipschitz-like/calmness property of the perturbed solution mapping, or equivalently the metric subregularity of the underlining set-valued mapping. It has been proved to be extremely useful in analyzing the convergence of many algorithms for solving optimization problems, as well as serving as a constraint qualification for optimality conditions. In this paper, we study the error bound property for the solution set of a very general second-order cone complementarity problem (SOCCP). We derive some sufficient conditions for error bounds of SOCCP which is verifiable based on the initial problem data.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aubin, J.-P.: Lipschitz behavior of solutions to convex minimization problems. Math. Oper. Res. 9, 87–111 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bonnans, J.F., Ramŕez, H.: Perturbation analysis of second-order cone programming problems. Math. Program. 104, 205–227 (2005)

    Article  MathSciNet  Google Scholar 

  4. Chen, J.-S., Chen, X., Tseng, P.: Analysis of nonsmooth vector-valued functions associated with second-order cone. Math. Program. 101, 95–117 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, J.-S., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104, 293–327 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  6. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience, New York (1983)

    MATH  Google Scholar 

  7. Clarke, F.H., Ledyaev, YuS, Stern, R.J., Wolenski, P.R.: Nonsmooth Analysis and Control Theory. Springer, New York (1998)

    MATH  Google Scholar 

  8. Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings. Springer, Heidelberg (2014)

    Book  MATH  Google Scholar 

  9. Fabian, M.J., Henrion, R., Kruger, A.Y., Outrata, J.V.: Error bounds: necessary and sufficient conditions. Set-Valued Var. Anal. 18, 121–149 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. Facchinei, F., Fischer, A., Herrich, M.: An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions. Math. Program. 146, 1–36 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  11. Flegel, M.L., Kanzow, C., Outrata, J.V.: Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints. Set-Valued Anal. 15, 139–162 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gfrerer, H.: First order and second order characterizations of metric subregularity and calmness of constraint set mappings. SIAM J. Optim. 21, 1439–1474 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gfrerer, H.: On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs. Set-Valued Var. Anal. 21, 151–176 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gfrerer, H.: Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints. SIAM J. Optim. 24, 898–931 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gfrerer, H., Klatte, D.: Lipschitz and Hölder stability of optimization problems and generalized equations. Math. Program. 158, 35–75 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gfrerer, H., Ye, J.J.: New constraint qualifications for mathematical programs with equilibrium constraints via variational analysis. SIAM J. Optim. 27, 842–865 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  17. Guo, L., Ye, J.J., Zhang, J.: Mathematical programs with geometric constraints in Banach spaces: enhanced optimality, exact penalty, and sensitivity. SIAM J. Optim. 23, 2295–2319 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  18. Guo, L., Zhang, J., Lin, G.-H.: New results on constraint qualifications for nonlinear extremum problems and extensions. J. Optim. Theory Appl. 163, 737–754 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hayashi, S., Yamashita, N., Fukushima, M.: Robust Nash equilibria and second-order cone complementarity problems. J. Nonlinear Conv. Anal. 6, 283–296 (2005)

    MathSciNet  MATH  Google Scholar 

  20. Jiang, Y., Liu, Y.J., Zhang, L.W.: Variational geometry of the complementarity set for second order cone. Set-Valued Var. Anal. 23, 399–414 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  21. Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization: Regularity, Calculus, Methods and Applications. Kluwer Academic Publishers, Dordrecht (2002)

    MATH  Google Scholar 

  22. Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  23. Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, Vol. I: Basic Theory, Vol. II: Applications. Springer, Berlin (2006)

    Book  Google Scholar 

  24. Ng, K.F., Zheng, X.Y.: Global error bounds with fractional exponents. Math. Program. 88, 357–370 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  25. Outrata, J.V., Sun, D.F.: On the coderivative of the projection operator onto the second-order cone. Set-Valued Anal. 16, 999–1014 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  26. Pang, J.S.: Error bounds in mathematical programming. Math. Program. 79, 299–332 (1997)

    MathSciNet  MATH  Google Scholar 

  27. Robinson, S.M.: Stability theory for systems of inequality constraints, part I: linear systems. SIAM J. Numer. Anal. 12, 754–769 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  28. Robinson, S.M.: Stability theory for systems of inequality constraints, part II: differentiable nonlinear systems. SIAM J. Numer. Anal. 13, 497–513 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  29. Robinson, S.M.: Some continuity properties of polyhedral multifunctions. Math. Program. Stud. 14, 206–214 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  30. Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  31. Wu, Z.L., Ye, J.J.: Sufficient conditions for error bounds. SIAM J. Optim. 12, 421–435 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  32. Wu, Z.L., Ye, J.J.: On error bounds for lower semicontinuous functions. Math. Program. 92, 301–314 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  33. Wu, Z.L., Ye, J.J.: First-order and second-order conditions for error bounds. SIAM J. Optim. 14, 621–645 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  34. Ye, J.J.: Constraint qualification and necessary optimality conditions for optimization problems with variational inequality constraints. SIAM J. Optim. 10, 943–962 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  35. Ye, J.J., Ye, X.Y.: Necessary optimality conditions for optimization problems with variational inequality constraints. Math. Oper. Res. 22, 977–997 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  36. Ye, J.J., Zhou, J.C.: First-order optimality conditions for mathematical programs with second-order cone complementarity constraints. SIAM J. Optim. 26, 2820–2846 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  37. Ye, J.J., Zhou, J.C.: Exact formula for the proximal/regular/limiting normal cone of the second-order cone complementarity set. Math. Program. 162, 33–50 (2017)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the two anonymous referees for their helpful comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, University of Victoria, Victoria, BC, V8W 2Y2, Canada

    Jane J. Ye

  2. Department of Statistics, School of Mathematics and Statistics, Shandong University of Technology, Zibo, 255049, People’s Republic of China

    Jinchuan Zhou

Authors
  1. Jane J. Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinchuan Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jane J. Ye.

Additional information

J. J. Ye: The research of this author was partially supported by NSERC. J. Zhou: This author’s work is supported by National Natural Science Foundation of China (11771255, 11101248) and Shandong Province Natural Science Foundation (ZR2016AM07).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ye, J.J., Zhou, J. Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems. Math. Program. 171, 361–395 (2018). https://doi.org/10.1007/s10107-017-1193-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-017-1193-9

Keywords

Mathematics Subject Classification

Search

Navigation