American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Optimality conditions of fenchel-lagrange duality and farkas-type results for composite dc infinite programs
  • JIMO Home
  • This Issue
  • Next Article
    Inverse single facility location problem on a tree with balancing on the distance of server to clients
March  2022, 18(2): 1261-1274. doi: 10.3934/jimo.2021018

Solution method for discrete double obstacle problems based on a power penalty approach

Kai Zhang 1,, , Xiaoqi Yang 2, and  Song Wang 1,3,

1. 

Shenzhen Audencia Business School, WeBank Institute of Fintech, Shenzhen University, Shenzhen 518060, China
2. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Kowloon, Hong Kong, China
3. 

Department of Mathematics and Statistics, Curtin University, GPO Box U1987, Perth, WA 6845, Australia

* Corresponding author: Kai Zhang

Received  July 2020 Revised  October 2020 Published  March 2022 Early access  December 2020

We develop a power penalty approach to a finite-dimensional double obstacle problem. This problem is first approximated by a system of nonlinear equations containing two penalty terms. We show that the solution to this penalized equation converges to that of the original obstacle problem at an exponential rate when the coefficient matrices are $ M $-matrices. Numerical examples are presented to confirm the theoretical findings and illustrate the efficiency and effectiveness of the new method.

Keywords: Double obstacle problem, penalty method, convergence rate, complementarity problem, numerical optimization.
Mathematics Subject Classification: Primary: 90C33, 90-08; Secondary: 65K15.
Citation: Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1261-1274. doi: 10.3934/jimo.2021018
References:
[1]

C. Avramescu, A generalization of Miranda's theorem, Semin. Fixed Point Theory Cluj-Napoca, 3 (2002), 121-127. 

[2]

O. Bokanowski, S. Maroso and H. Zidani, Some convergence results for Howard's algorithm, SIAM J. Numer. Anal., 47 (2009), 3001-3026.  doi: 10.1137/08073041X.

[3]

L. A. Caffarelli and R. J. McCann, Free boundaries in optimal transport and Monge-Ampere obstacle problems, Ann. Math., 171 (2010), 673-730.  doi: 10.4007/annals.2010.171.673.

[4]

M. Dai and F. Yi, Finite-horizon optimal investment with transaction costs: A parabolic double obstacle problem, J. Differ. Equ., 246 (2009), 1445-1469.  doi: 10.1016/j.jde.2008.11.003.

[5]

J. E. Dennis Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983.

[6]

G. Duvaut and J.-L. Lions, Inequalities in Mechanics and Physics, Springer-Verlag, Berlin, 1976.

[7]

D. Han and J. W. L. Wan, Multigrid methods for second order Hamilton–Jacobi–Bellman and Hamilton–Jacobi–Bellman–Isaacs equations, SIAM J. Sci. Comput., 35 (2013), S323–S344. doi: 10.1137/120881476.

[8]

T. Kärkkäinen, K. Kunisch and P. Tarvainen, Augmented Lagrangian active set methods for obstacle problems, J. Optim. Theory Appl., 119 (2003), 499-533.  doi: 10.1023/B:JOTA.0000006687.57272.b6.

[9]

R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities I, Numer. Math., 69 (1994), 167-184.  doi: 10.1007/BF03325426.

[10]

P. Kovalov and V. Linetsky, Valuing convertible bonds with stock price, volatility, interest rate, and default risk, FDIC Center for Financial Research Working Paper Series, 2008.

[11]

Y. Peres, O. Schramm, S. Sheffield and D. B. Wilson, Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc., 22 (2009), 167-210.  doi: 10.1090/S0894-0347-08-00606-1.

[12]

Z. Sun, Z. Liu and X. Yang, On power penalty methods for linear complementarity problems arising from American option pricing, J. Glob. Optim., 63 (2015), 165-180.  doi: 10.1007/s10898-015-0291-6.

[13]

S. Wang and X. Yang, A power penalty method for a bounded nonlinear complementarity problem, Optimization, 64 (2015), 2377-2394.  doi: 10.1080/02331934.2014.967236.

[14]

S. Wang, X. Q. Yang and K. L. Teo, Power penalty method for a linear complementarity problem arising from American option valuation, J. Optim. Theory Appl., 129 (2006), 227-254.  doi: 10.1007/s10957-006-9062-3.

[15]

J. H. Witte and C. Reisinger, A penalty method for the numerical solution of Hamilton-Jacobi-Bellman (HJB) equations in finance, SIAM J. Numer. Anal., 49 (2011), 213-231.  doi: 10.1137/100797606.

[16]

K. Zhang and X. Yang, A power penalty method for discrete HJB equations, Optim. Lett., 14 (2020), 1419-1433.  doi: 10.1007/s11590-019-01517-7.

[17]

K. Zhang, X. Q. Yang, S. Wang and K. L. Teo, Numerical performance of penalty method for American option pricing, Optim. Methods Softw., 25 (2010), 737-752.  doi: 10.1080/10556780903051930.

[18]

J.-X. Zhao and S. Wang, An interior penalty approach to a large-scale discretized obstacle problem with nonlinear constraints, Numer. Algorithms, 85 (2020), 571-589.  doi: 10.1007/s11075-019-00827-2.

[19]

Y. Y. Zhou, S. Wang and X. Q. Yang, A penalty approximation method for a semilinear parabolic double obstacle problem, J. Glob. Optim., 60 (2014), 531-550.  doi: 10.1007/s10898-013-0122-6.

show all references

References:
[1]

C. Avramescu, A generalization of Miranda's theorem, Semin. Fixed Point Theory Cluj-Napoca, 3 (2002), 121-127. 

[2]

O. Bokanowski, S. Maroso and H. Zidani, Some convergence results for Howard's algorithm, SIAM J. Numer. Anal., 47 (2009), 3001-3026.  doi: 10.1137/08073041X.

[3]

L. A. Caffarelli and R. J. McCann, Free boundaries in optimal transport and Monge-Ampere obstacle problems, Ann. Math., 171 (2010), 673-730.  doi: 10.4007/annals.2010.171.673.

[4]

M. Dai and F. Yi, Finite-horizon optimal investment with transaction costs: A parabolic double obstacle problem, J. Differ. Equ., 246 (2009), 1445-1469.  doi: 10.1016/j.jde.2008.11.003.

[5]

J. E. Dennis Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983.

[6]

G. Duvaut and J.-L. Lions, Inequalities in Mechanics and Physics, Springer-Verlag, Berlin, 1976.

[7]

D. Han and J. W. L. Wan, Multigrid methods for second order Hamilton–Jacobi–Bellman and Hamilton–Jacobi–Bellman–Isaacs equations, SIAM J. Sci. Comput., 35 (2013), S323–S344. doi: 10.1137/120881476.

[8]

T. Kärkkäinen, K. Kunisch and P. Tarvainen, Augmented Lagrangian active set methods for obstacle problems, J. Optim. Theory Appl., 119 (2003), 499-533.  doi: 10.1023/B:JOTA.0000006687.57272.b6.

[9]

R. Kornhuber, Monotone multigrid methods for elliptic variational inequalities I, Numer. Math., 69 (1994), 167-184.  doi: 10.1007/BF03325426.

[10]

P. Kovalov and V. Linetsky, Valuing convertible bonds with stock price, volatility, interest rate, and default risk, FDIC Center for Financial Research Working Paper Series, 2008.

[11]

Y. Peres, O. Schramm, S. Sheffield and D. B. Wilson, Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc., 22 (2009), 167-210.  doi: 10.1090/S0894-0347-08-00606-1.

[12]

Z. Sun, Z. Liu and X. Yang, On power penalty methods for linear complementarity problems arising from American option pricing, J. Glob. Optim., 63 (2015), 165-180.  doi: 10.1007/s10898-015-0291-6.

[13]

S. Wang and X. Yang, A power penalty method for a bounded nonlinear complementarity problem, Optimization, 64 (2015), 2377-2394.  doi: 10.1080/02331934.2014.967236.

[14]

S. Wang, X. Q. Yang and K. L. Teo, Power penalty method for a linear complementarity problem arising from American option valuation, J. Optim. Theory Appl., 129 (2006), 227-254.  doi: 10.1007/s10957-006-9062-3.

[15]

J. H. Witte and C. Reisinger, A penalty method for the numerical solution of Hamilton-Jacobi-Bellman (HJB) equations in finance, SIAM J. Numer. Anal., 49 (2011), 213-231.  doi: 10.1137/100797606.

[16]

K. Zhang and X. Yang, A power penalty method for discrete HJB equations, Optim. Lett., 14 (2020), 1419-1433.  doi: 10.1007/s11590-019-01517-7.

[17]

K. Zhang, X. Q. Yang, S. Wang and K. L. Teo, Numerical performance of penalty method for American option pricing, Optim. Methods Softw., 25 (2010), 737-752.  doi: 10.1080/10556780903051930.

[18]

J.-X. Zhao and S. Wang, An interior penalty approach to a large-scale discretized obstacle problem with nonlinear constraints, Numer. Algorithms, 85 (2020), 571-589.  doi: 10.1007/s11075-019-00827-2.

[19]

Y. Y. Zhou, S. Wang and X. Q. Yang, A penalty approximation method for a semilinear parabolic double obstacle problem, J. Glob. Optim., 60 (2014), 531-550.  doi: 10.1007/s10898-013-0122-6.

Figure 1.  Solution $ U(s) $ with $ N = 99 $. The solution is obtained with the lower order penalty method ($ k = 2 $). Tolerance $ \varepsilon = 10^{-6} $ is chosen for the Newton iteration. The smoothing interval is chosen to be $ (0,10^{-3}) $. $ \lambda = 10^{3} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Solution $ u(x,y) $ with the mesh grid $ 60 \times 60 $, obtained with the lower order penalty method ($ k = 2 $). Tolerance is set to be $ 10^{-6} $. $ \epsilon = 10^{-3} $. $ \lambda = 10^{3} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The lower coincidence sets (dot '$ \cdot $') and the upper coincidence sets (star '$ \ast $') of solution $ u(x,y) $ on the mesh grid $ 60 \times 60 $. The solution is obtained with the lower order penalty method ($ k = 2 $). Tolerance $ \varepsilon = 10^{-6} $ is chosen for the Newton iteration. The smoothing interval is chosen to be $ (0,10^{-3}) $. $ \lambda = 10^{3} $
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Results computed by the power penalty method. Tolerance $ \varepsilon = 10^{-6} $ is chosen for the Newton iteration. The smoothing parameter $ \epsilon = 10^{-3} $. 'Ra' stands for ratio
$k=1$ $k=2$
$\lambda_{i}$ $[x_{\lambda_{i}}]_{1}$ $[x_{\lambda_{i}}]_{4}$ $\Vert x-x_{\lambda_{i}}\Vert_{\infty}$ Ra $\lambda_{i}$ $[x_{\lambda_{i}}]_{1}$ $[x_{\lambda_{i}}]_{4}$ $\Vert x-x_{\lambda_{i}}\Vert_{\infty}$ Ra
$10^{2}$ $0.5119$ $5.3052$ $6.25\times10^{-1}$ $10^{2}$ $0.9985$ $5.0011$ $2.81\times10^{-1}$
$10^{3}$ $0.9430$ $5.0327$ $6.49\times10^{-2}$ $0.98$ $10^{3}$ $0.9998$ $5.0002$ $2.85\times10^{-3}$ $1.99$
$10^{4}$ $0.9942$ $5.0033$ $6.59\times10^{-3}$ $0.99$ $10^{4}$ $0.9999$ $5.0001$ $4.93\times10^{-5}$ $1.76$
$10^{5}$ $0.9994$ $5.0003$ $6.60\times10^{-4}$ $1.00$ $10^{5}$ $1.0000$ $5.0000$ $6.90\times10^{-6}$ $1.69$
Table Options

Download as excel

$k=1$ $k=2$
$\lambda_{i}$ $[x_{\lambda_{i}}]_{1}$ $[x_{\lambda_{i}}]_{4}$ $\Vert x-x_{\lambda_{i}}\Vert_{\infty}$ Ra $\lambda_{i}$ $[x_{\lambda_{i}}]_{1}$ $[x_{\lambda_{i}}]_{4}$ $\Vert x-x_{\lambda_{i}}\Vert_{\infty}$ Ra
$10^{2}$ $0.5119$ $5.3052$ $6.25\times10^{-1}$ $10^{2}$ $0.9985$ $5.0011$ $2.81\times10^{-1}$
$10^{3}$ $0.9430$ $5.0327$ $6.49\times10^{-2}$ $0.98$ $10^{3}$ $0.9998$ $5.0002$ $2.85\times10^{-3}$ $1.99$
$10^{4}$ $0.9942$ $5.0033$ $6.59\times10^{-3}$ $0.99$ $10^{4}$ $0.9999$ $5.0001$ $4.93\times10^{-5}$ $1.76$
$10^{5}$ $0.9994$ $5.0003$ $6.60\times10^{-4}$ $1.00$ $10^{5}$ $1.0000$ $5.0000$ $6.90\times10^{-6}$ $1.69$
Table 2.  Total number of iterations for the linear penalty ($ k = 1 $), lower order penalty ($ k = 2 $), and modified policy methods with $ N = 99 $. Tolerance is set to be $ 10^{-6} $. $ \epsilon = 10^{-3} $. $ \lambda $ is set to be $ 10^{6} $ and $ 10^{3} $ for $ k = 1 $ and $ k = 2 $, respectively
$ k=1 $ $ k=2 $ Modified policy iter.
Iterations 9 12 88
Table Options

Download as excel

$ k=1 $ $ k=2 $ Modified policy iter.
Iterations 9 12 88
Table 3.  Comparison of computational efficiency among power penalty methods, Gauss-Seidel iteration method and active set method. Tolerance is set to be $ 10^{-6} $. $ \epsilon = 10^{-3} $. $ \lambda $ is set to be $ 10^{6} $ and $ 10^{3} $ for $ k = 1 $ and $ k = 2 $, respectively
$k=1$ $k=2$ Gauss-Seidel Active set
$N=49$ Iterations 11 16 426 Failed
Time (s) 1.26 1.89 32.81 Failed
$N=59$ Iterations 15 17 740 17
Time (s) 7.78 8.96 198.7 6.43
Table Options

Download as excel

$k=1$ $k=2$ Gauss-Seidel Active set
$N=49$ Iterations 11 16 426 Failed
Time (s) 1.26 1.89 32.81 Failed
$N=59$ Iterations 15 17 740 17
Time (s) 7.78 8.96 198.7 6.43
[1]

Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022017
[2]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[3]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092
[4]

Song Wang. Numerical solution of an obstacle problem with interval coefficients. Numerical Algebra, Control and Optimization, 2020, 10 (1) : 23-38. doi: 10.3934/naco.2019030
[5]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911
[6]

L’ubomír Baňas, Amy Novick-Cohen, Robert Nürnberg. The degenerate and non-degenerate deep quench obstacle problem: A numerical comparison. Networks and Heterogeneous Media, 2013, 8 (1) : 37-64. doi: 10.3934/nhm.2013.8.37
[7]

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

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

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[10]

Lekbir Afraites. A new coupled complex boundary method (CCBM) for an inverse obstacle problem. Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : 23-40. doi: 10.3934/dcdss.2021069
[11]

Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241
[12]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[13]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391
[14]

Radouen Ghanem, Billel Zireg. Numerical solution of bilateral obstacle optimal control problem, where the controls and the obstacles coincide. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 275-300. doi: 10.3934/naco.2020002
[15]

Pierre Fabrie, Elodie Jaumouillé, Iraj Mortazavi, Olivier Piller. Numerical approximation of an optimization problem to reduce leakage in water distribution systems. Mathematical Control and Related Fields, 2012, 2 (2) : 101-120. doi: 10.3934/mcrf.2012.2.101
[16]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[17]

Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial and Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049
[18]

Daniel Morales-Silva, David Yang Gao. Complete solutions and triality theory to a nonconvex optimization problem with double-well potential in $\mathbb{R}^n $. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 271-282. doi: 10.3934/naco.2013.3.271
[19]

Jun Lai, Ming Li, Peijun Li, Wei Li. A fast direct imaging method for the inverse obstacle scattering problem with nonlinear point scatterers. Inverse Problems and Imaging, 2018, 12 (3) : 635-665. doi: 10.3934/ipi.2018027
[20]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021080

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (429)
  • HTML views (479)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy