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

A regularized strong duality for nonsymmetric semidefinite least squares problem

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The nonsymmetric semidefinite least squares problem (NSDLS) is to find a nonsymmetric semidefinite matrix which is closest to a given matrix in Frobenius norm. It is an extension of the semidefinite least squares problem (SDLS) and has important application in the area of robotics and automation. In this note, by developing the minimal representation of the underlying cone with the linear constraints, we obtain a regularized strong duality with low-dimensional projection for NSDLS. Further, we study the generalized differential properties and nonsingularity of the first order optimality system about the dual problem. These theoretical results demonstrate that we can solve NSDLS as good as the current Lagrangian dual approaches to SDLS.

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. Bertsekas D.P., Nedić A.N., Ozdaglar E.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003)

    MATH  Google Scholar 

  2. Borsdorf R., Higham N.J.: A preconditioned Newton algorithm for the nearest correlation matrix. IMA J. Numer. Anal. 30(1), 94–107 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Borwein J., Wolkowicz H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83, 495–530 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  4. Boyd S., Xiao L.: Least-squares covariance matrix adjustments. SIAM J. Matrix Anal. Appl. 27(2), 532–546 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  5. Deutsch F.: Best Approximation in Inner Product Spaces. CMS Books Math./Ouvrages Math. SMC 7. Springer, New York (2001)

    Google Scholar 

  6. Higham N.J.: Computing the nearest correlation matrix: a problem from finance. IMA J. Numer. Anal. 22(3), 329–343 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  7. Horn R.A., Johnson C.A.: Matrix Analysis. Cambridge University Press, Cambridge (1986)

    Google Scholar 

  8. Krislock, N.: Numerical solution of semidefinite constrained least squares problems. Master’s thesis, University of British Columbia, Institute of Applied Mathematics, Vancouver, BC, Canada. http://www.iam.ubc.ca/theses/Krislock/NKrislock_MSc_Thesis.pdf (2003)

  9. Krislock N., Lang J., Varah J. et al.: Local compliance estimation via positive semidefinite constrained least squares. IEEE Trans. Robot. Autom. 20, 1007–1011 (2004)

    Google Scholar 

  10. Malick J.: A dual approach to solve semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26(1), 272–284 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  11. Pang J.S., Sun D.F., Sun J.: Semismooth homeomorphisms and strong stability of semidefinite and Lorentz cone complementarity problems. Math. Oper. Res. 28, 39–63 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Pardalos P.M., Wolkowicz H.: Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications Series, vol. 18. American Mathematical Society, New Providence, Rhode Island (1998)

    Google Scholar 

  13. Pataki, G.: A Simple Derivation of a Facial Reduction Algorithm, and Extended Dual Systems. Technical report, Columbia University. http://www.unc.edu/~pataki/papers/fr.pdf (1996)

  14. Pataki G.: On the closedness of the linear image of a closed convex cone. Math. Oper. Res. 32(2), 395–412 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Pólik, I., Terlaky, T.: Exact duality for optimization over symmetric cones, Technical report, McMaster University. http://www.optimization-online.org/DB_HTML/2007/08/1754.html (2007)

  16. Qi H.D., Sun D.F.: A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28(2), 360–385 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Qi H.D.: Local duality of nonlinear semidefinite programming. Math. Oper. Res. 34(1), 124–141 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Qi, H.D., Sun, D.F.: An augmented Lagrangian dual approach for the H-weighted nearest correlation matrix problem. IMA J. Numer. Anal. (2010, to appear)

  19. Ramana M.V., Tunçel L., Wolkowicz H.: Strong duality for semidefinite programming. SIAM J. Optim. 7, 641–662 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ramana M.V., Pardalos P.M.: Semidefinite programming. In: Terlaky, T. (eds) Interior Point methods of Mathematical Programming., pp. 369–398. Kluwer Academic Publishers, Dordrecht (1996)

    Google Scholar 

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

    MATH  Google Scholar 

  22. Sun D.F.: 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 

  23. Toh K.C.: An inexact primal-dual path-following algorithm for convex quadratic SDP. Math. Program. Ser. B. 112(1), 221–254 (2002)

    Article  MathSciNet  Google Scholar 

  24. Tunçel, L., Wolkowicz, H.: Strong duality and minimal representations for cone optimization. Technical report, Waterloo University. http://www.optimization-online.org/DB_HTML/2008/08/2063.html (2008)

  25. Wang Y.N., Xiu N.H., Han J.Y.: On cone of nonsymmetric positive semidefinite matrices. Linear Algebra Appl. 433, 718–736 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  26. Wolkowicz H., Saigal R., Vandenberghe L.: Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, pp. 34–36. Kluwer Academic Publishers, Boston (2000)

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, School of Science, Beijing Jiaotong University, Beijing, 100044, People’s Republic of China

    Yingnan Wang, Naihua Xiu & Ziyan Luo

Authors
  1. Yingnan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Naihua Xiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ziyan Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yingnan Wang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, Y., Xiu, N. & Luo, Z. A regularized strong duality for nonsymmetric semidefinite least squares problem. Optim Lett 5, 665–682 (2011). https://doi.org/10.1007/s11590-010-0233-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-010-0233-7

Keywords

Search

Navigation