A perturbation approach for an inverse quadratic programming problem over second-order cones

Zhang, Yi; Zhang, Liwei; Wu, Jia; Zhang, Jianzhong

doi:10.1090/S0025-5718-2014-02848-2

A perturbation approach for an inverse quadratic programming problem over second-order cones
HTML articles powered by AMS MathViewer

by Yi Zhang, Liwei Zhang, Jia Wu and Jianzhong Zhang PDF

Math. Comp. 84 (2015), 209-236 Request permission

Abstract:

This paper is devoted to studying a type of inverse second-order cone quadratic programming problems, in which the parameters in both the objective function and the constraint set of a given second-order cone quadratic programming problem need to be adjusted as little as possible so that a known feasible solution becomes optimal. This inverse problem can be written as a minimization problem with second-order cone complementarity constraints and a positive semidefinite cone constraint. Applying the duality theory, we reformulate this problem as a linear second-order cone complementarity constrained optimization problem with a semismoothly differentiable objective function, which has fewer variables than the original one. A perturbed problem is proposed with the help of the projection operator over second-order cones, whose feasible set and optimal solution set are demonstrated to be continuous and outer semicontinuous, respectively, as the parameter decreases to zero. A smoothing Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. Finally, the numerical results are reported to show the effectiveness for the smoothing Newton method to solve the inverse second-order cone quadratic programming problem.

References

Ravindra K. Ahuja and James B. Orlin, Inverse optimization, Oper. Res. 49 (2001), no. 5, 771–783. MR 1860425, DOI 10.1287/opre.49.5.771.10607
F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program. 95 (2003), no. 1, Ser. B, 3–51. ISMP 2000, Part 3 (Atlanta, GA). MR 1971381, DOI 10.1007/s10107-002-0339-5
D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Programming 53 (1992), no. 1, Ser. A, 45–61. MR 1151764, DOI 10.1007/BF01585693
M. C. Cai, X. G. Yang, and J. Z. Zhang, The complexity analysis of the inverse center location problem, J. Global Optim. 15 (1999), no. 2, 213–218. MR 1714066, DOI 10.1023/A:1008360312607
Jein-Shan Chen, Defeng Sun, and Jie Sun, The $SC^1$ property of the squared norm of the SOC Fischer-Burmeister function, Oper. Res. Lett. 36 (2008), no. 3, 385–392. MR 2424468, DOI 10.1016/j.orl.2007.08.005
Xiaojun Chen and Masao Fukushima, A smoothing method for a mathematical program with $P$-matrix linear complementarity constraints, Comput. Optim. Appl. 27 (2004), no. 3, 223–246. MR 2035714, DOI 10.1023/B:COAP.0000013057.54647.6d
Frank H. Clarke, Optimization and nonsmooth analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication. MR 709590
Zvi Drezner and Horst W. Hamacher (eds.), Facility location, Springer-Verlag, Berlin, 2002. Applications and theory. MR 1933965, DOI 10.1007/978-3-642-56082-8
Francisco Facchinei, Houyuan Jiang, and Liqun Qi, A smoothing method for mathematical programs with equilibrium constraints, Math. Program. 85 (1999), no. 1, Ser. A, 107–134. MR 1689366, DOI 10.1007/s101070050048
Francisco Facchinei and Jong-Shi Pang, Finite-dimensional variational inequalities and complementarity problems. Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003. MR 1955648
Masao Fukushima, Zhi-Quan Luo, and Paul Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim. 12 (2001/02), no. 2, 436–460. MR 1885570, DOI 10.1137/S1052623400380365
Garud Iyengar and Wanmo Kang, Inverse conic programming with applications, Oper. Res. Lett. 33 (2005), no. 3, 319–330. MR 2108284, DOI 10.1016/j.orl.2004.04.007
Houyuan Jiang and Daniel Ralph, Smooth SQP methods for mathematical programs with nonlinear complementarity constraints, SIAM J. Optim. 10 (2000), no. 3, 779–808. MR 1774773, DOI 10.1137/S1052623497332329
Jianlin Jiang and Xiaoming Yuan, A Barzilai-Borwein-based heuristic algorithm for locating multiple facilities with regional demand, Comput. Optim. Appl. 51 (2012), no. 3, 1275–1295. MR 2891938, DOI 10.1007/s10589-010-9392-9
Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph, Mathematical programs with equilibrium constraints, Cambridge University Press, Cambridge, 1996. MR 1419501, DOI 10.1017/CBO9780511983658
Fanwen Meng, Defeng Sun, and Gongyun Zhao, Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization, Math. Program. 104 (2005), no. 2-3, Ser. B, 561–581. MR 2179251, DOI 10.1007/s10107-005-0629-9
Li Qun Qi and Jie Sun, A nonsmooth version of Newton’s method, Math. Programming 58 (1993), no. 3, Ser. A, 353–367. MR 1216791, DOI 10.1007/BF01581275
Liqun Qi, Defeng Sun, and Guanglu Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program. 87 (2000), no. 1, Ser. A, 1–35. MR 1734657, DOI 10.1007/s101079900127
R. Tyrrell Rockafellar and Roger J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR 1491362, DOI 10.1007/978-3-642-02431-3
Stefan Scholtes and Michael Stöhr, Exact penalization of mathematical programs with equilibrium constraints, SIAM J. Control Optim. 37 (1999), no. 2, 617–652. MR 1670641, DOI 10.1137/S0363012996306121
Stefan Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim. 11 (2001), no. 4, 918–936. MR 1855214, DOI 10.1137/S1052623499361233
Jie Sun, Defeng Sun, and Liqun Qi, A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems, SIAM J. Optim. 14 (2003), no. 3, 783–806. MR 2085943, DOI 10.1137/S1052623400379620
Defeng Sun, The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications, Math. Oper. Res. 31 (2006), no. 4, 761–776. MR 2281228, DOI 10.1287/moor.1060.0195
Defeng Sun, Jie Sun, and Liwei Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Math. Program. 114 (2008), no. 2, Ser. A, 349–391. MR 2393047, DOI 10.1007/s10107-007-0105-9
Jia Wu, Liwei Zhang, and Yi Zhang, A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations, J. Global Optim. 55 (2013), no. 2, 359–385. MR 3015981, DOI 10.1007/s10898-012-9880-9
Xiantao Xiao and Liwei Zhang, Solving a class of inverse QP problems by a smoothing Newton method, J. Comput. Math. 27 (2009), no. 6, 787–801. MR 2583394, DOI 10.4208/jcm.2009.09-m2674
Xiantao Xiao, Liwei Zhang, and Jianzhong Zhang, A smoothing Newton method for a type of inverse semi-definite quadratic programming problem, J. Comput. Appl. Math. 223 (2009), no. 1, 485–498. MR 2463131, DOI 10.1016/j.cam.2008.01.028
X. Xiao, L.Zhang and J. Zhang, On convergence of augmented Lagrange method for inverse semidefinite quadratic programming problems, Journal of Industrial and Management Optimization 52(2009), 319-339.
Jianzhong Zhang and Zhenhong Liu, Calculating some inverse linear programming problems, J. Comput. Appl. Math. 72 (1996), no. 2, 261–273. MR 1406213, DOI 10.1016/0377-0427(95)00277-4
Jianzhong Zhang and Zhenhong Liu, A further study on inverse linear programming problems, J. Comput. Appl. Math. 106 (1999), no. 2, 345–359. MR 1696416, DOI 10.1016/S0377-0427(99)00080-1
Jianzhong Zhang, Zhenhong Liu, and Zhongfan Ma, Some reverse location problems, European J. Oper. Res. 124 (2000), no. 1, 77–88. MR 1778308, DOI 10.1016/S0377-2217(99)00122-8
Jianzhong Zhang and Liwei Zhang, An augmented Lagrangian method for a class of inverse quadratic programming problems, Appl. Math. Optim. 61 (2010), no. 1, 57–83. MR 2575314, DOI 10.1007/s00245-009-9075-z
Jianzhong Zhang, Liwei Zhang, and Xiantao Xiao, A perturbation approach for an inverse quadratic programming problem, Math. Methods Oper. Res. 72 (2010), no. 3, 379–404. MR 2739050, DOI 10.1007/s00186-010-0323-4
Yi Zhang, Liwei Zhang, and Jia Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued Var. Anal. 19 (2011), no. 4, 609–646. MR 2836713, DOI 10.1007/s11228-011-0190-z
Y. Zhang, J. Wu and L. Zhang, First order necessary optimality conditions for mathematical programs with second-order cone complementarity constraints, submitted.