July  2014, 10(3): 965-976. doi: 10.3934/jimo.2014.10.965

A majorized penalty approach to inverse linear second order cone programming problems

1. 

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

Received  October 2012 Revised  July 2013 Published  November 2013

This paper focuses on a type of inverse linear second order cone programming (LSOCP) problems which require us to adjust the parameters in both the objective function and the constraint set of a given LSOCP problem as little as possible so that a known feasible solution becomes optimal one. This inverse problem can be formulated as a linear second order cone complementarity constrained optimization problem and is difficult to solve due to the presence of second order cone complementarity constraint. To solve this difficult problem, we first partially penalize the inverse problem and then propose the majorization approach to the penalized problem by solving a sequence of convex optimization problems with quadratic objective function and simple second order cone constraints. Numerical results demonstrate the efficiency of our approach to inverse LSOCP problems.
Citation: Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
References:
[1]

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

[2]

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

[3]

D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem,, Mathematical Programming, 53 (1992), 45. doi: 10.1007/BF01585693.

[4]

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

[5]

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. doi: 10.1023/B:COAP.0000013057.54647.6d.

[6]

J. de Leeuw, Applications of convex analysis to multidimensional scaling,, in Recent Developments in Statistics (eds. J. R. Barra, (1976), 133.

[7]

J. de Leeuw, Convergence of the majorization method for multidimensional scaling,, Journal of Classification, 5 (1988), 163. doi: 10.1007/BF01897162.

[8]

J. de Leeuw and W. J. Heiser, Convergence of correction matrix algorithms for multidimensional scaling,, in Geometric Representations of Relational Data (eds. J. C. Lingoes, (1977), 735.

[9]

J. de Leeuw, A Decomposition Method for Weighted Least Squares Low-Rank Approximation of Symmetric Matrices,, Department of Statistics, (2006).

[10]

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

[11]

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

[12]

M. Fukushima and J.-S. Pang, Convergence of a smoothing continuation method for mathematical problems with complementarity constraints,, in Ill-posed Variational Problems and Regularization Techniques (eds. M. Thera and R. Tichatschke) (Trier, (1999), 99. doi: 10.1007/978-3-642-45780-7_7.

[13]

Y. Gao and D. F. Sun, A majorized penalty approach for calibrating rank constrained correlation matrix problems,, preprint. Available from: , ().

[14]

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

[15]

G. Iyengar and W. Kang, Inverse conic programming with applications,, Operations Research Letters, 33 (2005), 319. 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. doi: 10.1137/S1052623497332329.

[17]

Y. Jiang, X. T. Xiao, L. W. Zhang and J. Z. Zhang, A perturbation approach for a type of inverse linear programming problems,, International Journal of Computer Mathematics, 88 (2011), 508. doi: 10.1080/00207160903513003.

[18]

H. A. L. Kiers, Setting up alternating least squares and iterative majorization algorithm for solving various matrix optimization problems,, Computational Statistics & Data Analysis, 41 (2002), 157. doi: 10.1016/S0167-9473(02)00142-1.

[19]

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

[20]

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

[21]

D. G. Luenberger, Linear and Nonlinear Programming,, 2nd Edition, (2003).

[22]

Z.-Q. Luo, J.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints,, Cambridge University Press, (1996). doi: 10.1017/CBO9780511983658.

[23]

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

[24]

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

[25]

J. F. Sturm, Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Interior point methods,, Optimization and Methods Software, 11/12 (1999), 625. doi: 10.1080/10556789908805766.

[26]

R. H. Tütüncü, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3,, Mathematical Programming, 95 (2003), 189. doi: 10.1007/s10107-002-0347-5.

[27]

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

[28]

X. T. Xiao, L. W. Zhang and J. Z. Zhang, On convergence of augmented Lagrange method for inverse semi-definite quadratic programming problems,, Journal of Industrial and Management Optimization, 5 (2009), 319. doi: 10.3934/jimo.2009.5.319.

[29]

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

[30]

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

[31]

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

[32]

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

[33]

Y. Zhang, Y. Jiang, L. W. Zhang and J. Z. Zhang, A perturbation approach for an inverse linear second-order cone programming,, Journal of Industrial and Management Optimization, 9 (2013), 171. doi: 10.3934/jimo.2013.9.171.

[34]

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

[35]

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

show all references

References:
[1]

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

[2]

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

[3]

D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem,, Mathematical Programming, 53 (1992), 45. doi: 10.1007/BF01585693.

[4]

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

[5]

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. doi: 10.1023/B:COAP.0000013057.54647.6d.

[6]

J. de Leeuw, Applications of convex analysis to multidimensional scaling,, in Recent Developments in Statistics (eds. J. R. Barra, (1976), 133.

[7]

J. de Leeuw, Convergence of the majorization method for multidimensional scaling,, Journal of Classification, 5 (1988), 163. doi: 10.1007/BF01897162.

[8]

J. de Leeuw and W. J. Heiser, Convergence of correction matrix algorithms for multidimensional scaling,, in Geometric Representations of Relational Data (eds. J. C. Lingoes, (1977), 735.

[9]

J. de Leeuw, A Decomposition Method for Weighted Least Squares Low-Rank Approximation of Symmetric Matrices,, Department of Statistics, (2006).

[10]

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

[11]

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

[12]

M. Fukushima and J.-S. Pang, Convergence of a smoothing continuation method for mathematical problems with complementarity constraints,, in Ill-posed Variational Problems and Regularization Techniques (eds. M. Thera and R. Tichatschke) (Trier, (1999), 99. doi: 10.1007/978-3-642-45780-7_7.

[13]

Y. Gao and D. F. Sun, A majorized penalty approach for calibrating rank constrained correlation matrix problems,, preprint. Available from: , ().

[14]

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

[15]

G. Iyengar and W. Kang, Inverse conic programming with applications,, Operations Research Letters, 33 (2005), 319. 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. doi: 10.1137/S1052623497332329.

[17]

Y. Jiang, X. T. Xiao, L. W. Zhang and J. Z. Zhang, A perturbation approach for a type of inverse linear programming problems,, International Journal of Computer Mathematics, 88 (2011), 508. doi: 10.1080/00207160903513003.

[18]

H. A. L. Kiers, Setting up alternating least squares and iterative majorization algorithm for solving various matrix optimization problems,, Computational Statistics & Data Analysis, 41 (2002), 157. doi: 10.1016/S0167-9473(02)00142-1.

[19]

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

[20]

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

[21]

D. G. Luenberger, Linear and Nonlinear Programming,, 2nd Edition, (2003).

[22]

Z.-Q. Luo, J.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints,, Cambridge University Press, (1996). doi: 10.1017/CBO9780511983658.

[23]

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

[24]

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

[25]

J. F. Sturm, Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Interior point methods,, Optimization and Methods Software, 11/12 (1999), 625. doi: 10.1080/10556789908805766.

[26]

R. H. Tütüncü, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3,, Mathematical Programming, 95 (2003), 189. doi: 10.1007/s10107-002-0347-5.

[27]

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

[28]

X. T. Xiao, L. W. Zhang and J. Z. Zhang, On convergence of augmented Lagrange method for inverse semi-definite quadratic programming problems,, Journal of Industrial and Management Optimization, 5 (2009), 319. doi: 10.3934/jimo.2009.5.319.

[29]

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

[30]

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

[31]

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

[32]

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

[33]

Y. Zhang, Y. Jiang, L. W. Zhang and J. Z. Zhang, A perturbation approach for an inverse linear second-order cone programming,, Journal of Industrial and Management Optimization, 9 (2013), 171. doi: 10.3934/jimo.2013.9.171.

[34]

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

[35]

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

[1]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[2]

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 & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[3]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[4]

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

[5]

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

[6]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[7]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[8]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[9]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[10]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

[11]

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 & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[12]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[13]

Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019

[14]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529

[15]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[16]

Mohsen Tadi. A computational method for an inverse problem in a parabolic system. Discrete & Continuous Dynamical Systems - B, 2009, 12 (1) : 205-218. doi: 10.3934/dcdsb.2009.12.205

[17]

Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems & Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291

[18]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825

[19]

Min Tang. Second order all speed method for the isentropic Euler equations. Kinetic & Related Models, 2012, 5 (1) : 155-184. doi: 10.3934/krm.2012.5.155

[20]

Yong Li, Catalin Trenchea. Partitioned second order method for magnetohydrodynamics in Elsässer variables. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2803-2823. doi: 10.3934/dcdsb.2018106

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]