[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Equivalent Conditions for Jacobian Nonsingularity in Linear Symmetric Cone Programming

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

In this paper we consider the linear symmetric cone programming (SCP). At a Karush-Kuhn-Tucker (KKT) point of SCP, we present the important conditions equivalent to the nonsingularity of Clarke’s generalized Jacobian of the KKT nonsmooth system, such as primal and dual constraint nondegeneracy, the strong regularity, and the nonsingularity of the B-subdifferential of the KKT system. This affirmatively answers an open question by Chan and Sun (SIAM J. Optim. 19:370–396, 2008).

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chan, Z., Sun, D.: Constraint nondegeneracy, strong regularity and nonsingularity in semidefinite programming. SIAM J. Optim. 19, 370–396 (2008)

    Article  MathSciNet  Google Scholar 

  2. Eaves, B.C.: On the basic theorem of complementarity. Math. Program. 1, 68–75 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  3. Gowda, M.S., Sznajder, R., Tao, J.: Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 393, 203–232 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  4. Pang, J.-S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  5. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vols. I and II. Springer, New York (2003)

    Google Scholar 

  6. Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)

    MATH  Google Scholar 

  7. Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77, 111–128 (1997)

    MathSciNet  MATH  Google Scholar 

  8. Bonnans, J.F., Shapiro, A.: Nondegeneracy and quantitative stability of parameterized optimization problems with multiple solutions. SIAM J. Optim. 8, 940–946 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  9. Flegel, M.L., Kanzow, C.: Equivalence of two nondegeneracy conditions for semidefinite programs. J. Optim. Theory Appl. 135, 381–397 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  10. Kanzow, C., Ferenczi, I., Fukushima, M.: On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity. SIAM J. Optim. 20, 297–320 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Shapiro, A.: First and second order analysis of nonlinear semidefinite programs. Math. Program. 77, 301–320 (1997)

    MATH  Google Scholar 

  12. Sun, D.: The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31, 761–776 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Yıldırım, E.A.: An interior-point perspective on sensitivity analysis in semidefinite programming. Math. Oper. Res. 28, 649–676 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  14. Pataki, G.: The geometry of semidefinite programming. In: Wolkowicz, H., Vandenberghe, L., Saigal, R. (eds.) Handbook of Semidefinite Programming, pp. 29–65. Kluwer, Dordrecht (2000)

    Google Scholar 

  15. Pataki, G., Tunçel, L.: On the generic properties of convex optimization problems in conic form. Math. Program. A 89, 449–457 (2001)

    Article  MATH  Google Scholar 

  16. Yıldırım, E.A.: Unifying optimal partition approach to sensitivity analysis in conic optimization. J. Optim. Theory Appl. 122, 405–423 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  17. Shapiro, A., Fan, M.K.H.: On eigenvalue optimization. SIAM J. Optim. 5, 552–569 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  18. Wang, Y.: Perturbation analysis of optimization problems over symmetric cones. Ph.D. Thesis, Dalian University of Technology (2008)

  19. Koecher, M.: The Minnesota Notes on Jordan Algebras and Their Applications. Springer, Berlin (1999). Edited and Annotated by A. Brieg and S. Walcher

    MATH  Google Scholar 

  20. Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford University Press, London (1994)

    MATH  Google Scholar 

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

    MATH  Google Scholar 

  22. Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977)

    Article  MathSciNet  Google Scholar 

  23. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

    MATH  Google Scholar 

  25. Sun, D., Sun, J.: Löwner’s operator and spectral functions on Euclidean Jordan algebras. Math. Oper. Res. 33, 421–445 (2008)

    Article  MathSciNet  Google Scholar 

  26. Kong, L.C., Sun, J., Xiu, N.H.: A regularized smoothing Newton method for symmetric cone complementarity problems. SIAM J. Optim. 19, 1028–1047 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kong, L.C., Tunçel, L., Xiu, N.H.: Clarke generalized Jacobian of the projection onto symmetric cones. Set-Valued Var. Anal. 17, 135–151 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  28. Sun, D., Sun, J.: Semismooth matrix valued functions. Math. Oper. Res. 27, 150–169 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  29. Baes, M.: Spectral functions and smoothing techniques on Jordan algebras. Ph.D. Thesis, Université Catholique de Louvain (2006)

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

    Google Scholar 

  31. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    MATH  Google Scholar 

  32. Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5, 43–62 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  33. Robinson, S.M.: Local structure of feasible sets in nonlinear programming. Part III: Stability and sensitivity. Math. Program. Stud. 30, 45–66 (1987)

    MATH  Google Scholar 

  34. Robinson, S.M.: Local structure of feasible sets in nonlinear programming. Part II: Nondegeneracy. Math. Program. Stud. 22, 217–230 (1984)

    MATH  Google Scholar 

  35. Robinson, S.M.: Constraint nondegeneracy in variational analysis. Math. Oper. Res. 28, 201–232 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  36. Shapiro, A.: Sensitivity analysis of generalized equations. J. Math. Sci. 115, 2554–2565 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  37. Clarke, F.H.: On the inverse function theorem. Pac. J. Math. 64, 97–102 (1976)

    MATH  Google Scholar 

  38. Gowda, M.S.: Inverse and implicit function theorems for H-differentiable and semismooth functions. Optim. Methods Softw. 19, 443–461 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  39. Kummer, B.: Lipschitzian inverse functions, directional derivatives, and applications in C 1,1 optimization. J. Optim. Theory Appl. 70, 559–580 (1991)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Beijing Jiaotong University, Beijing, 100044, P.R. China

    Lingchen Kong & Naihua Xiu

  2. Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

    Lingchen Kong & Levent Tunçel

Authors
  1. Lingchen Kong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Levent Tunçel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Naihua Xiu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lingchen Kong.

Additional information

Communicated by M. Fukushima.

The work was partly supported by a Discovery Grant from NSERC, and the National Natural Science Foundation of China (10831006) and the National Basic Research Program of China (2010CB732501). The authors thank two anonymous referees for their very useful comments. In particular, one of the referees pointed out a gap in our original proof of Proposition 2.7.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kong, L., Tunçel, L. & Xiu, N. Equivalent Conditions for Jacobian Nonsingularity in Linear Symmetric Cone Programming. J Optim Theory Appl 148, 364–389 (2011). https://doi.org/10.1007/s10957-010-9758-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-010-9758-2

Keywords

Search

Navigation