Skip to main content
SpringerLink
Log in

The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

The focus of this paper is on studying an inverse second-order cone quadratic programming problem, in which the parameters in the objective function need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with cone constraints, and its dual, which has fewer variables than the original one, is a semismoothly differentiable (SC 1) convex programming problem with both a linear inequality constraint and a linear second-order cone constraint. We demonstrate the global convergence of the augmented Lagrangian method with an exact solution to the subproblem and prove that the convergence rate of primal iterates, generated by the augmented Lagrangian 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. Furthermore, a semismooth Newton method with Armijo line search is constructed to solve the subproblems in the augmented Lagrangian approach. Finally, numerical results are reported to show the effectiveness of the augmented Lagrangian method with both an exact solution and an inexact solution to the subproblem for solving the inverse second-order cone quadratic programming problem.

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

  • Ahuja RK, Orlin JB (2001) Inverse optimization. Oper Res 49:771–783

    Article  Google Scholar 

  • Ahuja RK, Orlin JB (2002) Combinatorial algorithms for inverse network flow problems. Networks 40:181–187

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Bertsekas DP (1975a) Combined primal-dual and penalty methods for constrained minimization. SIAM J Control 13:521–544

    Article  Google Scholar 

  • Bertsekas DP (1975b) On the method of multipliers for convex programming. IEEE Trans Autom Control AC-20:385–388

    Article  Google Scholar 

  • Bertsekas DP (1976) On penalty and multiplier methods for constrained minimization. SIAM J Control Optim 14:216–235

    Article  Google Scholar 

  • Burton WR, Toint PL (1992) On an instance of the inverse shortest paths problem. Math Program 53:45–61

    Article  Google Scholar 

  • Buys JD (1972) Dual algorithms for constrained optimization problems. PhD Thesis, University of Leiden, Leiden, The Netherlands

  • Cai MC, Yang XG, Zhang J (1999) The complexity analysis of the inverse center location problem. J Glob Optim 15:213–218

    Article  Google Scholar 

  • Dutta J (2005) Generalized derivatives and nonsmooth optimization, a finite dimensional tour. TOP 13:185–279

    Article  Google Scholar 

  • Clarke FH (1983) Optimization and nonsmooth analysis. Wiley, New York

    Google Scholar 

  • Facchinei F, Pang J-S (2003) Finite-dimensional variational inequalities and complementarity problems, vols. I, II. Springer, New York

    Google Scholar 

  • Golshtein EG, Tretyakov NV (1989) Modified Lagrangians and monotone maps in optimization. Wiley, New York

    Google Scholar 

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

    Article  Google Scholar 

  • Hestences MR (1969) Multiplier and gradient methods. J Optim Theory Appl 4:303–320

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Liu YJ, Zhang LW (2008) Convergence of the augmented Lagrangian method for nonlinear optimization problems over second order cones. J Comput Appl Math 139:557–575

    Google Scholar 

  • Lobo MS, Vandenberghe L, Boyd S (1998) Application of second order cone programming. Linear Algebra Appl 284:193–228

    Article  Google Scholar 

  • Meng F, Sun D, Zhao G (2005) Semismoothness of solutions to generalized equations and the Moreau–Yosida regularization. Math Program, Ser B 104:561–581

    Article  Google Scholar 

  • Mordukhovich B (2005) Discussion. TOP 13:287–290

    Article  Google Scholar 

  • Moguerza MJ, Prieto FJ (2003) An augmented Lagrangian interior-point method using directions of negative curvature. Math Program, Ser A 95:573–616

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Olivares A, Moguerza JM (2009) Improving directions of negative curature in an efficient manner. Ann Oper Res 166:183–201

    Article  Google Scholar 

  • Pang JS, Sun DF, Sun J (2003) Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems. Math Oper Res 28:272–284

    Article  Google Scholar 

  • Powell MJD (1969) A method for nonlinear constraints in minimization problems. Optimization. Academic Press, New York

    Google Scholar 

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

    Article  Google Scholar 

  • Rockafellar RT (1973a) A dual approach to solving nonlinear programming problems by unconstrained optimization. Math Program 5:354–373

    Article  Google Scholar 

  • Rockafellar RT (1973b) The multiplier method of Hestenes and Powell applied to convex programming. J Optim Theory Appl 12:555–562

    Article  Google Scholar 

  • Rockafellar RT (1974) Conjugate duality and optimization. SIAM, Philadelphia

    Book  Google Scholar 

  • Rockafellar RT, Wets RJ-B (1998) Variational analysis. Springer, New York

    Book  Google Scholar 

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

    Article  Google Scholar 

  • Shapiro A (2006) Discussion. TOP 14:39–41

    Article  Google Scholar 

  • Shapiro A, Sun J (2004) Some properties of the augmented Lagrangian in cone constrained optimization. Math Oper Res 29(3):479–491

    Article  Google Scholar 

  • Sturm JF (1998) Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones. Communications Research Laboratory, McMaster University, Hamilton, Canada, August 1998

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

    Article  Google Scholar 

  • Venderbei RH, Yurttan H (1998) Using LOQO to solve second order cone programming problems. Report SOR 98-09, Princeton Univesity

  • Xiao X, Zhang L, Zhang J (2009) A smoothing Newton method for a type of inverse semi-definite quadratic programming problem. J Comput Appl Math 223:485–498

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Zhang J, Liu Z, Ma Z (2000) Some reverse location problems. Eur J Oper Res 124:77–88

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Zhang J, Zhang L (2010) An augmented Lagrangian method for a type of inverse quadratic programming problems. Appl Math Optim 61:57–83

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Yi Zhang & Liwei Zhang

  2. School of Management, University of Southampton, Southampton, Highfield Southampton, SO17 1BJ, UK

    Yue Wu

Authors
  1. Yi 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

  3. Yue Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liwei Zhang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhang, Y., Zhang, L. & Wu, Y. The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones. TOP 22, 45–79 (2014). https://doi.org/10.1007/s11750-011-0227-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-011-0227-3

Keywords

Mathematics Subject Classification (2000)

Search

Navigation