Skip to main content
SpringerLink
Log in

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

  • Published:
Applied Mathematics and Optimization Submit manuscript

Abstract

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  \(1/\sqrt{r}\) , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC1 function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.

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

Access this article

Log in via an institution

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. Ahuja, R.K., Orlin, J.B.: Inverse optimization. Oper. Res. 49, 771–183 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  2. Ahuja, R.K., Orlin, J.B.: Combinatorial algorithms for inverse network flow problems. Networks 40, 181–187 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)

    MATH  Google Scholar 

  4. Burkard, R.E., Lin, Y., Zhang, J.: Weight reduction problems with certain bottleneck objectives. Eur. J. Oper. Res. 153, 191–199 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  5. Burton, W.R., Toint, Ph.L.: On an instance of the inverse shortest paths problem. Math. Program. 53, 45–61 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  6. Cai, M.C., Yang, X.G., Zhang, J.: The complexity analysis of the inverse center location problem. J. Global Optim. 15, 213–218 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  7. Carr, S., Lovejoy, W.: The inverse newsvendor problem: choosing an optimal demand portfolio for capacitated resources. Manag. Sci. 46, 912–927 (2000)

    Article  Google Scholar 

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

    MATH  Google Scholar 

  9. Dembo, R., Rosen, D.: The practice of portfolio replication: a practical overview of forward and inverse problems. Ann. Oper. Res. 85, 267–284 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  10. Facchinei, F.: Minimization of SC 1 functions and the Maratos effect. Oper. Res. Lett. 17, 131–137 (1995)

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  13. Golshtein, E.G., Tretyakov, N.V.: Modified Lagrangians and Monotone Maps in Optimization. Wiley, New York (1989)

    Google Scholar 

  14. Hartley, M.J., Bakshi, G.S.: Markowitz models of portfolio selection: the inverse problem. (October 1998)

  15. Heuberger, C.: Inverse combinatorial optimization: a survey on problems, methods and results. J. Comb. Optim. 8, 329–361 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993)

    Google Scholar 

  17. Hiriart-Urruty, J.-B., Strodiot, J.J., Nguyen, V.H.: Generalized Hessian matrix and second-order optimality conditions for problems with C1,1 data. Appl. Math. Optim. 11, 43–56 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  18. Iyengar, G., Kang, W.: Inverse conic programming and applications. Oper. Res. Lett. 33, 319–330 (2005)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  22. Rockafellar, R.T.: A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5, 354–373 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  23. Rockafellar, R.T.: The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12, 555–562 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  24. Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974)

    MATH  Google Scholar 

  25. Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, New York (1998)

    Book  MATH  Google Scholar 

  26. Shapiro, A.: On concepts of directional differentiability. J. Optim. Theory Appl. 66, 477–487 (1990)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  28. Sun, D., Sun, J., Zhang, L.: The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114, 349–391 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  29. Zhang, J., Liu, Z.: Calculating some inverse linear programming problems. J. Comput. Appl. Math. 72, 261–273 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  30. Zhang, J., Liu, Z.: A further study on inverse linear programming problems. J. Comput. Appl. Math. 106, 345–359 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  31. Zhang, J., Ma, Z.: Solution structure of some inverse combinatorial optimization problems. J. Comb. Optim. 3, 127–139 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  32. Zhao, X., Sun, D.F., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. Optimization (Online) (2008)

Download references

Author information

Authors and Affiliations

  1. United International College, Beijing Normal University–Hong Kong Baptist University, Zhuhai, China

    Jianzhong Zhang

  2. School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, China

    Liwei Zhang

Authors
  1. Jianzhong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Liwei Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liwei Zhang.

Additional information

The research of Jianzhong Zhang is supported by University Grant Council of Hong Kong under the grant CERG CityU 9041091 and CUHK 103105. The research of Liwei Zhang is supported by the National Natural Science Foundation of China under project No. 10771026 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhang, J., Zhang, L. An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems. Appl Math Optim 61, 57 (2010). https://doi.org/10.1007/s00245-009-9075-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00245-009-9075-z

Keywords

Search

Navigation