American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk
  • JIMO Home
  • This Issue
  • Next Article
    Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function
January  2013, 9(1): 171-189. doi: 10.3934/jimo.2013.9.171

A perturbation approach for an inverse linear second-order cone programming

Yi Zhang 1, , Yong Jiang 2, , Liwei Zhang 3, and  Jiangzhong Zhang 4,

1. 

Department of Mathematics, School of Science, East China University of Science and Technology, Shanghai, 200237, China
2. 

School of Science, Shenyang Aerospace University, Shenyang, 110136, China
3. 

Institute of ORCT, School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, China
4. 

Division of Science and Technology, Beijing Normal University-Hong Kong, Baptist University United International College, Zhuhai, 519085, China

Received  April 2011 Revised  June 2012 Published  December 2012

A type of inverse linear second-order cone programming problems is discussed, in which the parameters in both the objective function and the constraint set of a given linear second-order cone programming need to be adjusted as little as possible so that a known feasible solution becomes optimal. This inverse problem can be formulated as a minimization problem with second-order cone complementarity constraints. With the help of the smoothed Fischer-Burmeister function over second-order cones, we construct a smoothing approximation of the formulated problem whose feasible set and optimal solution set are demonstrated to be continuous and outer semicontinuous respectively at the perturbed parameter $\varepsilon=0$. A damped Newton method is employed 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 of the damped Newton method for solving the inverse linear second-order cone programming.
Keywords: damped Newton method., Inverse optimization, linear second-order cone programming, perturbation approach.
Mathematics Subject Classification: Primary: 90C26, 90C33; Secondary: 49M15, 49M2.
Citation: Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
References:
[1]

R. Ahuja and J. Orlin, Inverse optimization, Operations Research, 49 (2001), 771-783. doi: 10.1287/opre.49.5.771.10607.

[2]

R. Ahuja and J. Orlin, Combinatorial algorithms for inverse network flow problems, Networks, 40 (2002), 181-187. doi: 10.1002/net.10048.

[3]

F. Alizadeh and D. Goldfarb, Second order cone programming, Mathematical Programming, 95 (2003), 3-51. doi: 10.1007/s10107-002-0339-5.

[4]

W. Burton and P. Toint, On an instance of the inverse shortest paths problem, Mathematical Programming, 53 (1992), 45-61. doi: 10.1007/BF01585693.

[5]

M. Cai, X. Yang and J. Zhang, The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218. doi: 10.1023/A:1008360312607.

[6]

J. Chen, D. Sun and J. Sun, The $SC^1$ property of the squared norm of the SOC Fischer-Burmeister function, Operations Research Letters, 36 (2008), 385-392. doi: 10.1016/j.orl.2007.08.005.

[7]

X. Chen and M. Fukushima, A smoothing method for a mathematical program with P-matrix linear complementarity constraints, Computational Optimization and Applications, 27 (2004), 223-246. doi: 10.1023/B:COAP.0000013057.54647.6d.

[8]

Ejiri Takeshi, "A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints," Master thesis, Kyoto University in Kyoto, 2007.

[9]

F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Mathematical Programming, 85 (1999), 107-134. doi: 10.1007/s101070050048.

[10]

M. Fukushima, Z. Luo and J. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints, Computational Optimization and Applications, 10 (1998), 5-34. doi: 10.1023/A:1018359900133.

[11]

M. Fukushima, Z. Luo and P. Tseng, Smoothing functions for second-order cone complimentarity problems, SIAM Journal on Optimization, 12 (2001), 436-460. doi: 10.1137/S1052623400380365.

[12]

M. Fukushima and J. Pang, Convergence of a smoothing continuation method for mathematical problems with complementarity constraints, Lecture Notes in Economics and Mathematical Systems, 477 (1999), 105-116. doi: 10.1007/978-3-642-45780-7_7.

[13]

M. Grant and S. Boyd, "CVX Users' Guide,", Available from: , (). 

[14]

C. Heuberger, Inverse combinatorial optimization: a survey on problems, methods and results, Journal of Combinatorial Optimization, 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b.

[15]

G. Iyengar and W. Kang, Inverse conic programming and applications, Operations Research Letters, 33 (2005), 319-330. doi: 10.1016/j.orl.2004.04.007.

[16]

H. Jiang and D. Ralph, Smooth SQP methods for mathematical programs with nonlinear complementarity constraints, SIAM Journal on Optimization, 10 (2000), 779-808. doi: 10.1137/S1052623497332329.

[17]

G. Lin and M. Fukushima, Some exact penalty results for nonlinear programs and their applications to mathematical programs with equilibrium constraints, Journal of Optimization Theory and Applications, 118 (2003), 67-80. doi: 10.1023/A:1024787424532.

[18]

G. Lin and M. Fukushima, A modified relaxation scheme for mathematical prgrams with complementarity constraints, Annals of Operations Research, 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z.

[19]

Z. Luo, J. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, United Kingdom, 1996. doi: 10.1017/CBO9780511983658.

[20]

L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research, 18 (1993), 227-244. doi: 10.1287/moor.18.1.227.

[21]

R. Rockafellar and R. Wets, "Variational Analysis," Springer-Verlag, New York, 1998. doi: 10.1007/978-3-642-02431-3.

[22]

S. Scholtes and M. Stöhr, Exact penalization of mathematical programs with equilibrium constraints, SIAM Journal on Control and Optimization, 37 (1999), 617-652. doi: 10.1137/S0363012996306121.

[23]

S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 25 (2001), 1-22. doi: 10.1137/S1052623499361233.

[24]

X. Xiao, L. Zhang and J. Zhang, A smoothing Newton method for a type of inverse semi-definite quadratic programming problem, Journal of Computational and Applied Mathematics, 223 (2009), 485-498. doi: 10.1016/j.cam.2008.01.028.

[25]

J. Zhang and Z. Liu, Calculating some inverse linear programming problems, Journal of Computational and Applied Mathematics, 72 (1996), 261-273. doi: 10.1016/0377-0427(95)00277-4.

[26]

J. Zhang and Z. Liu, A further study on inverse linear programming problems, Journal of Computational and Applied Mathematics, 106 (1999), 345-359. doi: 10.1016/S0377-0427(99)00080-1.

[27]

J. Zhang, Z. Liu and Z. Ma, Some reverse location problems, European Journal of Operations Research, 124 (2000), 77-88. doi: 10.1016/S0377-2217(99)00122-8.

[28]

J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems, Journal of Combinatorial Optimization, 3 (1999), 127-139. doi: 10.1023/A:1009829525096.

[29]

J. Zhang and L. Zhang, An augmented Lagrangian method for a class of inverse quadratic programming problems, Applied Mathematics and Optimization, 61 (2010), 57-83. doi: 10.1007/s00245-009-9075-z.

[30]

J. Zhang, L. Zhang and X. Xiao, A Perturbation approach for an inverse quadratic programming problem, Mathematical Methods of Operations Research, 72 (2010), 379-404. doi: 10.1007/s00186-010-0323-4.

[31]

Y. Zhang, L. Zhang and J. Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued and Variational Analysis, 19 (2011), 609-646. doi: 10.1007/s11228-011-0190-z.

show all references

References:
[1]

R. Ahuja and J. Orlin, Inverse optimization, Operations Research, 49 (2001), 771-783. doi: 10.1287/opre.49.5.771.10607.

[2]

R. Ahuja and J. Orlin, Combinatorial algorithms for inverse network flow problems, Networks, 40 (2002), 181-187. doi: 10.1002/net.10048.

[3]

F. Alizadeh and D. Goldfarb, Second order cone programming, Mathematical Programming, 95 (2003), 3-51. doi: 10.1007/s10107-002-0339-5.

[4]

W. Burton and P. Toint, On an instance of the inverse shortest paths problem, Mathematical Programming, 53 (1992), 45-61. doi: 10.1007/BF01585693.

[5]

M. Cai, X. Yang and J. Zhang, The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218. doi: 10.1023/A:1008360312607.

[6]

J. Chen, D. Sun and J. Sun, The $SC^1$ property of the squared norm of the SOC Fischer-Burmeister function, Operations Research Letters, 36 (2008), 385-392. doi: 10.1016/j.orl.2007.08.005.

[7]

X. Chen and M. Fukushima, A smoothing method for a mathematical program with P-matrix linear complementarity constraints, Computational Optimization and Applications, 27 (2004), 223-246. doi: 10.1023/B:COAP.0000013057.54647.6d.

[8]

Ejiri Takeshi, "A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints," Master thesis, Kyoto University in Kyoto, 2007.

[9]

F. Facchinei, H. Jiang and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Mathematical Programming, 85 (1999), 107-134. doi: 10.1007/s101070050048.

[10]

M. Fukushima, Z. Luo and J. Pang, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints, Computational Optimization and Applications, 10 (1998), 5-34. doi: 10.1023/A:1018359900133.

[11]

M. Fukushima, Z. Luo and P. Tseng, Smoothing functions for second-order cone complimentarity problems, SIAM Journal on Optimization, 12 (2001), 436-460. doi: 10.1137/S1052623400380365.

[12]

M. Fukushima and J. Pang, Convergence of a smoothing continuation method for mathematical problems with complementarity constraints, Lecture Notes in Economics and Mathematical Systems, 477 (1999), 105-116. doi: 10.1007/978-3-642-45780-7_7.

[13]

M. Grant and S. Boyd, "CVX Users' Guide,", Available from: , (). 

[14]

C. Heuberger, Inverse combinatorial optimization: a survey on problems, methods and results, Journal of Combinatorial Optimization, 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b.

[15]

G. Iyengar and W. Kang, Inverse conic programming and applications, Operations Research Letters, 33 (2005), 319-330. doi: 10.1016/j.orl.2004.04.007.

[16]

H. Jiang and D. Ralph, Smooth SQP methods for mathematical programs with nonlinear complementarity constraints, SIAM Journal on Optimization, 10 (2000), 779-808. doi: 10.1137/S1052623497332329.

[17]

G. Lin and M. Fukushima, Some exact penalty results for nonlinear programs and their applications to mathematical programs with equilibrium constraints, Journal of Optimization Theory and Applications, 118 (2003), 67-80. doi: 10.1023/A:1024787424532.

[18]

G. Lin and M. Fukushima, A modified relaxation scheme for mathematical prgrams with complementarity constraints, Annals of Operations Research, 133 (2005), 63-84. doi: 10.1007/s10479-004-5024-z.

[19]

Z. Luo, J. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, United Kingdom, 1996. doi: 10.1017/CBO9780511983658.

[20]

L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Mathematics of Operations Research, 18 (1993), 227-244. doi: 10.1287/moor.18.1.227.

[21]

R. Rockafellar and R. Wets, "Variational Analysis," Springer-Verlag, New York, 1998. doi: 10.1007/978-3-642-02431-3.

[22]

S. Scholtes and M. Stöhr, Exact penalization of mathematical programs with equilibrium constraints, SIAM Journal on Control and Optimization, 37 (1999), 617-652. doi: 10.1137/S0363012996306121.

[23]

S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 25 (2001), 1-22. doi: 10.1137/S1052623499361233.

[24]

X. Xiao, L. Zhang and J. Zhang, A smoothing Newton method for a type of inverse semi-definite quadratic programming problem, Journal of Computational and Applied Mathematics, 223 (2009), 485-498. doi: 10.1016/j.cam.2008.01.028.

[25]

J. Zhang and Z. Liu, Calculating some inverse linear programming problems, Journal of Computational and Applied Mathematics, 72 (1996), 261-273. doi: 10.1016/0377-0427(95)00277-4.

[26]

J. Zhang and Z. Liu, A further study on inverse linear programming problems, Journal of Computational and Applied Mathematics, 106 (1999), 345-359. doi: 10.1016/S0377-0427(99)00080-1.

[27]

J. Zhang, Z. Liu and Z. Ma, Some reverse location problems, European Journal of Operations Research, 124 (2000), 77-88. doi: 10.1016/S0377-2217(99)00122-8.

[28]

J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems, Journal of Combinatorial Optimization, 3 (1999), 127-139. doi: 10.1023/A:1009829525096.

[29]

J. Zhang and L. Zhang, An augmented Lagrangian method for a class of inverse quadratic programming problems, Applied Mathematics and Optimization, 61 (2010), 57-83. doi: 10.1007/s00245-009-9075-z.

[30]

J. Zhang, L. Zhang and X. Xiao, A Perturbation approach for an inverse quadratic programming problem, Mathematical Methods of Operations Research, 72 (2010), 379-404. doi: 10.1007/s00186-010-0323-4.

[31]

Y. Zhang, L. Zhang and J. Wu, Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints, Set-Valued and Variational Analysis, 19 (2011), 609-646. doi: 10.1007/s11228-011-0190-z.

[1]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[2]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[3]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
[4]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[5]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[6]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[7]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[8]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[9]

Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050
[10]

Qilin Wang, Shengji Li, Kok Lay Teo. Continuity of second-order adjacent derivatives for weak perturbation maps in vector optimization. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 417-433. doi: 10.3934/naco.2011.1.417
[11]

Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108
[12]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010
[13]

Willy Sarlet, Tom Mestdag. Compatibility aspects of the method of phase synchronization for decoupling linear second-order differential equations. Journal of Geometric Mechanics, 2022, 14 (1) : 91-104. doi: 10.3934/jgm.2021019
[14]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951
[15]

Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021032
[16]

Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068
[17]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[18]

Osama Moaaz, Omar Bazighifan. Oscillation criteria for second-order quasi-linear neutral functional differential equation. Discrete and Continuous Dynamical Systems - S, 2020, 13 (9) : 2465-2473. doi: 10.3934/dcdss.2020136
[19]

Qi Hong, Jialing Wang, Yuezheng Gong. Second-order linear structure-preserving modified finite volume schemes for the regularized long wave equation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6445-6464. doi: 10.3934/dcdsb.2019146
[20]

Hongwei Lou. Second-order necessary/sufficient conditions for optimal control problems in the absence of linear structure. Discrete and Continuous Dynamical Systems - B, 2010, 14 (4) : 1445-1464. doi: 10.3934/dcdsb.2010.14.1445

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (70)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy