• 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

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.
Citation: 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
References:
[1]

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

[2]

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

[3]

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

[4]

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

[5]

M. Cai, X. 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

[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.  doi: 10.1016/j.orl.2007.08.005.  Google Scholar

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

[8]

Ejiri Takeshi, "A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints,", Master thesis, (2007).   Google Scholar

[9]

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

[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.  doi: 10.1023/A:1018359900133.  Google Scholar

[11]

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

[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.  doi: 10.1007/978-3-642-45780-7_7.  Google Scholar

[13]

M. Grant and S. Boyd, "CVX Users' Guide,", 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 and 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]

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.  doi: 10.1023/A:1024787424532.  Google Scholar

[18]

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

[19]

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

[20]

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

[21]

R. Rockafellar and R. Wets, "Variational Analysis,", Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[22]

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

[23]

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

[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.  doi: 10.1016/j.cam.2008.01.028.  Google Scholar

[25]

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

[26]

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

[27]

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

[28]

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

[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.  doi: 10.1007/s00245-009-9075-z.  Google Scholar

[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.  doi: 10.1007/s00186-010-0323-4.  Google Scholar

[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.  doi: 10.1007/s11228-011-0190-z.  Google Scholar

show all references

References:
[1]

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

[2]

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

[3]

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

[4]

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

[5]

M. Cai, X. 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

[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.  doi: 10.1016/j.orl.2007.08.005.  Google Scholar

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

[8]

Ejiri Takeshi, "A Smoothing Method for Mathematical Programs with Second-Order Cone Complementarity Constraints,", Master thesis, (2007).   Google Scholar

[9]

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

[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.  doi: 10.1023/A:1018359900133.  Google Scholar

[11]

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

[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.  doi: 10.1007/978-3-642-45780-7_7.  Google Scholar

[13]

M. Grant and S. Boyd, "CVX Users' Guide,", 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 and 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]

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.  doi: 10.1023/A:1024787424532.  Google Scholar

[18]

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

[19]

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

[20]

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

[21]

R. Rockafellar and R. Wets, "Variational Analysis,", Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[22]

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

[23]

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

[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.  doi: 10.1016/j.cam.2008.01.028.  Google Scholar

[25]

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

[26]

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

[27]

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

[28]

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

[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.  doi: 10.1007/s00245-009-9075-z.  Google Scholar

[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.  doi: 10.1007/s00186-010-0323-4.  Google Scholar

[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.  doi: 10.1007/s11228-011-0190-z.  Google Scholar

[1]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[2]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHum approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[3]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[4]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[5]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[6]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[7]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[8]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[9]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[10]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[11]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[12]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[13]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[14]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

[15]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[16]

Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

[17]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[18]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031

[19]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[20]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]