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.  Google Scholar

[2]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

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

[7]

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

[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.   Google Scholar

[9]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[22]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

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

[7]

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

[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.   Google Scholar

[9]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

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

[22]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

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

[2]

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

[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[4]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196

[5]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[6]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[7]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[9]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[10]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[11]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[12]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[13]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[14]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[15]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[16]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[17]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[18]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[19]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[20]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]