Advanced Search
Article Contents
Article Contents

Inverse quadratic programming problem with $ l_1 $ norm measure

  • * Corresponding author: Lidan Li

    * Corresponding author: Lidan Li 

The third author is supported by the National Natural Science Foundation of China under project grant No.11571059 and No.11731013

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by
  • 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 involving $l_1$ vector norm with a positive semidefinite cone constraint. By utilizing convex optimization theory, we rewrite its first order optimality condition as a generalized equation. Under extremely simple assumptions, we prove that any element of the generalized Jacobian of the equation at its solution is nonsingular. Based on this, we construct an inexact Newton method with Armijo line search to solve the equation and demonstrate its global convergence. Finally, we report the numerical results illustrating effectiveness of the Newton methods.

    Mathematics Subject Classification: Primary: 90C20; Secondary: 90C25.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Numerical results of Problem (5)

    n p iter I-norm-F T-norm-F time(s)
    50 10 4 9.8e+003 9.9e-012 0.06
    100 10 4 7.5e+004 2.8e-007 0.19
    100 20 8 6.6e+004 1.0e-009 0.38
    100 50 8 1.9e+005 8.6e-007 0.39
    500 50 12 9.3e+006 1.1e-013 52.77
    500 100 17 8.2e+006 4.0e-010 79.76
    1000 100 25 7.7e+007 9.2e-009 916.90
    1000 500 30 3.8e+007 6.0e-008 1191.39
    2000 500 34 4.7e+008 3.5e-011 9300.16
     | Show Table
    DownLoad: CSV
  • [1] R. K. Ahuja and J. B. Orlin, Inverse optimization, Oper. Res., 49 (2001), 771-783.  doi: 10.1287/opre.49.5.771.10607.
    [2] R. K. Ahuja and J. B. Orlin, Combinatorial algorithms for inverse network flow problems, Networks, 40 (2002), 181-187.  doi: 10.1002/net.10048.
    [3] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.
    [4] R. E. BurkardY. Lin and J. Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res., 153 (2004), 191-199.  doi: 10.1016/S0377-2217(02)00713-0.
    [5] D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Program., 53 (1992), 45-61.  doi: 10.1007/BF01585693.
    [6] M. C. CaiX. G. Yang and J. Zhang, The complexity analysis of the inverse center location problem, J. Glob. Optim., 15 (1999), 213-218.  doi: 10.1023/A:1008360312607.
    [7] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983.
    [8] F. Facchinei, A. Fischer and C. Kanzow, Inexact newton methods for semismooth equations with applications to variational inequality problems, in Nonlinear Optimization And Applications (eds. G. F and D. G), Plenum press, New York, (1996), 125–139. doi: 10.1007/978-1-4899-0289-4_9.
    [9] C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, J. Combin. Optim., 8 (2004), 329-361.  doi: 10.1023/B:JOCO.0000038914.26975.9b.
    [10] G. Iyengar and W. Kang, Inverse conic programming with applications, Oper. Res. Lett., 33 (2005), 319-330.  doi: 10.1016/j.orl.2004.04.007.
    [11] Y. JiangX. XiaoL. Zhang and J. Zhang, A perturbation approach for a type of inverse linear programming problems, Int. J. Comput. Math., 88 (2011), 508-516.  doi: 10.1080/00207160903513003.
    [12] F. MengD. Sun and G. Zhao, Semismoothness of solutions to generalized equations and the moreau-yosida regularization, Math. Program., 104 (2005), 561-581.  doi: 10.1007/s10107-005-0629-9.
    [13] R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, New York, 1998.
    [14] P. Sonneveld, Cgs, a fast lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10 (1989), 36-52.  doi: 10.1137/0910004.
    [15] D. Sun, A Short Summer School Course on Modern Optimization Theory: Optimality Conditions and Perturbation Analysis, Part I, Part II, Part III, Technical report, National University of Singapore, Singapore, 2006.
    [16] D. Sun, The strong second order sufficient condition and constraint nondegenracy in nonlinear semidefinite programming and their implications, Math. Oper. Res, 31 (2006), 761-776.  doi: 10.1287/moor.1060.0195.
    [17] D. Sun and J. Sun, Semismooth matrix valued functions, Math. Oper. Res., 27 (2002), 150-169.  doi: 10.1287/moor.
    [18] D. SunJ. Sun and L. Zhang, The rate of convergence of the augmented lagrangian method for nonlinear semidefinite proguamming, Math. Program., 114 (2008), 349-391.  doi: 10.1007/s10107-007-0105-9.
    [19] X. XiaoL. Zhang and J. Zhang, A smoothing newton method for a type of inverse semi-definite quadratic programming problem, J. Comput. Appl. Math., 223 (2009), 485-498.  doi: 10.1016/j.cam.2008.01.028.
    [20] E. H. Zarantonello, Projections on convex sets in hilbert space and spectral theory: I and II, in Contributions to Nonlinear Functional Analysis (ed. E. H. Zarantonello), Academic Press, New York, 1971, 237-341.
    [21] J. Zhang and Z. Liu, Calculating some inverse linear programming problems, J. Comput. Appl. Math., 72 (1996), 261-273.  doi: 10.1016/0377-0427(95)00277-4.
    [22] J. Zhang and Z. Liu, A further study on inverse linear programming problems, J. Comput. Appl. Math., 106 (1999), 345-359.  doi: 10.1016/S0377-0427(99)00080-1.
    [23] J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems, J. Combin. Optim., 3 (1999), 127-139.  doi: 10.1023/A:1009829525096.
    [24] J. Zhang and L. Zhang, An augmented lagrangian method for a class of inverse quadratic programming problems, Appl. Math. Optim., 61 (2010), 57-83.  doi: 10.1007/s00245-009-9075-z.
  • 加载中



Article Metrics

HTML views(2392) PDF downloads(322) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint