Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Authors: Yi Zhang, Liwei Zhang, Jia Wu and Jianzhong Zhang
Journal: Math. Comp. 84 (2015), 209-236
MSC (2010): Primary 90C26, 90C33; Secondary 49M15, 49M20
DOI: https://doi.org/10.1090/S0025-5718-2014-02848-2
Published electronically: July 18, 2014
MathSciNet review: 3266958
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Ravindra K. Ahuja and James B. Orlin, Inverse optimization, Oper. Res. 49 (2001), no. 5, 771-783. MR 1860425 (2002i:90097), https://doi.org/10.1287/opre.49.5.771.10607
  • [2] 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 (2004j:90060), https://doi.org/10.1007/s10107-002-0339-5
  • [3] 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 (93e:90063), https://doi.org/10.1007/BF01585693
  • [4] 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 (2000e:90029), https://doi.org/10.1023/A:1008360312607
  • [5] 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 (2009g:90123), https://doi.org/10.1016/j.orl.2007.08.005
  • [6] 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 (2005a:90159), https://doi.org/10.1023/B:COAP.0000013057.54647.6d
  • [7] 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 (85m:49002)
  • [8] Zvi Drezner and Horst W. Hamacher (eds.), Facility location, Springer-Verlag, Berlin, 2002. Applications and theory. MR 1933965 (2003e:90003)
  • [9] 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 (2000f:90065), https://doi.org/10.1007/s101070050048
  • [10] 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 (2004g:90003a)
  • [11] 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 (electronic). MR 1885570 (2002m:90084), https://doi.org/10.1137/S1052623400380365
  • [12] Garud Iyengar and Wanmo Kang, Inverse conic programming with applications, Oper. Res. Lett. 33 (2005), no. 3, 319-330. MR 2108284 (2005g:90101), https://doi.org/10.1016/j.orl.2004.04.007
  • [13] Houyuan Jiang and Daniel Ralph, Smooth SQP methods for mathematical programs with nonlinear complementarity constraints, SIAM J. Optim. 10 (2000), no. 3, 779-808 (electronic). MR 1774773 (2001f:90073), https://doi.org/10.1137/S1052623497332329
  • [14] 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, https://doi.org/10.1007/s10589-010-9392-9
  • [15] Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996. MR 1419501 (97j:90002)
  • [16] 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 (2006m:90173), https://doi.org/10.1007/s10107-005-0629-9
  • [17] 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 (94b:90077), https://doi.org/10.1007/BF01581275
  • [18] 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 (2001e:90113)
  • [19] 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 (98m:49001)
  • [20] Stefan Scholtes and Michael Stöhr, Exact penalization of mathematical programs with equilibrium constraints, SIAM J. Control Optim. 37 (1999), no. 2, 617-652 (electronic). MR 1670641 (99k:90179), https://doi.org/10.1137/S0363012996306121
  • [21] Stefan Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim. 11 (2001), no. 4, 918-936 (electronic). MR 1855214 (2002g:90138), https://doi.org/10.1137/S1052623499361233
  • [22] 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 (2005g:90098), https://doi.org/10.1137/S1052623400379620
  • [23] 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 (2007m:90060), https://doi.org/10.1287/moor.1060.0195
  • [24] 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 (2009c:90077), https://doi.org/10.1007/s10107-007-0105-9
  • [25] 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, https://doi.org/10.1007/s10898-012-9880-9
  • [26] 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 (2011a:90079), https://doi.org/10.4208/jcm.2009.09-m2674
  • [27] 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 (2010a:90067), https://doi.org/10.1016/j.cam.2008.01.028
  • [28] 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.
  • [29] Jianzhong Zhang and Zhenhong Liu, Calculating some inverse linear programming problems, J. Comput. Appl. Math. 72 (1996), no. 2, 261-273. MR 1406213 (97d:90056), https://doi.org/10.1016/0377-0427(95)00277-4
  • [30] 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 (2000c:90047), https://doi.org/10.1016/S0377-0427(99)00080-1
  • [31] Jianzhong Zhang, Zhenhong Liu, and Zhongfan Ma, Some reverse location problems, European J. Oper. Res. 124 (2000), no. 1, 77-88. MR 1778308 (2001j:90039), https://doi.org/10.1016/S0377-2217(99)00122-8
  • [32] 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 (2011b:90155), https://doi.org/10.1007/s00245-009-9075-z
  • [33] 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 (2011j:90119), https://doi.org/10.1007/s00186-010-0323-4
  • [34] 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 (2012j:90180), https://doi.org/10.1007/s11228-011-0190-z
  • [35] Y. Zhang, J. Wu and L. Zhang, First order necessary optimality conditions for mathematical programs with second-order cone complementarity constraints, submitted.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C26, 90C33, 49M15, 49M20

Retrieve articles in all journals with MSC (2010): 90C26, 90C33, 49M15, 49M20


Additional Information

Yi Zhang
Affiliation: Department of Mathematics, School of Science, East China University of Science and Technology, Shanghai, 200237, China.
Email: zhangyi8407@163.com

Liwei Zhang
Affiliation: School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China.
Email: lwzhang@dlut.edu.cn

Jia Wu
Affiliation: School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China.
Email: wujia@dlut.edu.cn

Jianzhong Zhang
Affiliation: Division of Science and Technology, Beijing Normal University-Hong Kong Baptist University United International College, Zhuhai, 519085, China.
Email: jzzhang@uic.edu.hk

DOI: https://doi.org/10.1090/S0025-5718-2014-02848-2
Keywords: Inverse optimization, second-order cone quadratic programming, perturbation approach, smoothing Newton method.
Received by editor(s): March 18, 2011
Received by editor(s) in revised form: May 13, 2013
Published electronically: July 18, 2014
Additional Notes: The first author was supported by the Fundamental Research Funds for the Central Universities under project no. 222201314037 and the China Postdoctoral Science Foundation funded project no. 2013M541479
The second author was supported by the National Natural Science Foundation of China under project nos. 11071029, 91130007 and 91330206.
The third author was supported by the National Natural Science Foundation of China under project no. 11301049 and the China Postdoctoral Science Foundation funded project no. 2013M541217
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society