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

Kai Zhang; Xiaoqi Yang; Song Wang

doi:10.3934/jimo.2021018

Article Contents

2022, Volume 18, Issue 2: 1261-1274. Doi: 10.3934/jimo.2021018

This issue Previous Article Inverse single facility location problem on a tree with balancing on the distance of server to clients Next Article Optimality conditions of fenchel-lagrange duality and farkas-type results for composite dc infinite programs

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

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
^* Corresponding author: Kai Zhang

Received: June 30, 2020

Revised: September 30, 2020

Early access: December 2020

Published: March 2022

Abstract Full Text(HTML) Figure(3) / Table(3) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C33, 90-08; Secondary: 65K15.

Citation:

Full Text(HTML)

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} $

Download: Full-size image 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} $

Download: Full-size image 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} $

Download: Full-size image 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$

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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
$N=49$	Time (s)	1.26	1.89	32.81	Failed
$N=59$	Iterations	15	17	740	17
$N=59$	Time (s)	7.78	8.96	198.7	6.43

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.