Article Contents
Article Contents

Numerical solution of an obstacle problem with interval coefficients

• In this work we propose a novel numerical method for a finite-dimensional optimization problem arising from the discretization of an infinite-dimensional constrained optimization problem, called an obstacle problem, with interval coefficients. In this method, the two different ways of characterizing the optimal solutions, i.e., minimizing the mid-point and one end-point (the worst-case scenario) or the mid-point and the width of the objective interval, are formulated as a single constrained multi-objective minimization problem and the KKT conditions of the optimization problem defining the Pareto optimal solution to the multi-objective problem are of the form of a Linear Complementarity Problem (LCP) which is shown to have a unique solution. The LCP is the approximated by a non-linear equation using an interior penalty approach. We prove that the penalty equation is uniquely solvable and its solution converges to that of LCP as the penalty constant approaches to zero. Numerical results are presented to demonstrate the usefulness of the numerical method proposed.

Mathematics Subject Classification: Primary: 65K15, 90C70; Secondary: 65G99, 90C29.

 Citation:

• Figure 1.  Computed optimal solution of Test 1 when $\theta = 0$

Figure 2.  Computed optimal solution of Test 1 when $\theta = 0.5$

Figure 3.  Computed optimal solution of Test 2 when $\theta = 0$

Figure 4.  Computed optimal solution of Test 2 when $\theta = 0.5$

Figure 5.  Computed solution at $\lambda = 0.5$; (a) and solution at $\theta = 0$, (b) difference between solutions of $\theta = 0$ and 0.5

•  [1] A. K. Bhurjee and G. Panda, Efficient solution of interval optimization problem, Math. Meth. Oper. Res., 76 (2012), 273-288.  doi: 10.1007/s00186-012-0399-0. [2] A. Bensoussan and J. L. Lions, Applications of Variational Inequalities in Stochastic Control, North-Holland, Amsterdam-New York-Oxford, 1978. [3] S. Chanas and D. Kuchta, Multiobjective programming in optimization of interval objective functions – A generalized approach, European Journal of Operations Research, 94 (1996), 594-598. [4] W. Chen and S. Wang, A penalty method for a fractional order parabolic variational inequality governing American put option valuation, Computers and Mathematics with Applications, 67 (2014), 77-90.  doi: 10.1016/j.camwa.2013.10.007. [5] J. Cheng, Z. Liu, Z. Wu, M. Tang and J. Tan, Direct optimization of uncertain structure based on degree of interval constraint violation, Computer & Structures, 164 (2016), 83-94. [6] S.-T. Liu and R.-T. Wang, A numerical solution method to interval quadratic programming, Appl. Math. Comput., 189 (2007), 1274-1281.  doi: 10.1016/j.amc.2006.12.007. [7] A. Damgaard, Computation of reservation prices of options with proportional transaction costs, Journal of Economic Dynamics and Control, 30 (2006), 415-444.  doi: 10.1016/j.jedc.2005.03.001. [8] F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Vol. Ⅰ, Springer Series in Operations Research, Springer-Verlag, New York, 2003. [9] M. C. Ferris and J. S. Pang, Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997), 669-713.  doi: 10.1137/S0036144595285963. [10] A. Forsgren, P. E. Gill and M. H. Wright, Interior methods for nonlinear optimization, SIAM Rev., 44 (2002), 525-597.  doi: 10.1137/S0036144502414942. [11] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York-Berlin-Heidelberg-Tokyo, 1984. doi: 10.1007/978-3-662-12613-4. [12] J. Haslinger and M. Miettinen, Finite Element Method for Hemivariational Inequalities, Kluwer Academic Publisher, Dordrecht-Boston-London, 1999. doi: 10.1007/978-1-4757-5233-5. [13] B. Hu and S. Wang, A novel approach in uncertain programming part Ⅰ: New arithmetic and order relations for interval numbers, J. Ind. Manag. Optim., 2 (2006), 351-371.  doi: 10.3934/jimo.2006.2.351. [14] B. Hu and S. Wang, A novel approach in uncertain programming part Ⅱ: A class of constrained nonlinear programming problems with interval objective functions, J. Ind. Manag. Optim., 4 (2006), 373-385.  doi: 10.3934/jimo.2006.2.373. [15] C. C. Huang and S. Wang, A power penalty approach to a nonlinear complementarity problem, Operations Research Letters, 38 (2010), 72-76.  doi: 10.1016/j.orl.2009.09.009. [16] C. C. Huang and S. Wang, A penalty method for a mixed nonlinear complementarity problem, Nonlinear Analysis, 75 (2012), 588-597.  doi: 10.1016/j.na.2011.08.061. [17] H. Ishibuchi and H. Tanaka, Multiobjective programming in optimization of interval objective function, European Journal of Operations Research, 48 (1990), 219-225. [18] B. Kheirfam and M. Moslemi, On the extension of an arc-search interior-point algorithm for semidefinite optimization, Numerical Algebra, Control & Optimization, 8 (2018), 261-275.  doi: 10.3934/naco.2018015. [19] D. Kinderlehrer and  G. Stampacchia,  An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980. [20] E. Kropat and G. W. Weber, Fuzzy target-environment networks and fuzzy-regression approaches, Numerical Algebra, Control & Optimization, 8 (2018), 135-155.  doi: 10.3934/naco.2018008. [21] D. C. Lesmana and S. Wang, An upwind finite difference method for a nonlinear Black-Scholes equation governing European option valuation under transaction costs, Applied Mathematics & Computation, 219 (2013), 8811-8828.  doi: 10.1016/j.amc.2012.12.077. [22] D. C. Lesmana and S. Wang, Penalty approach to a nonlinear obstacle problem governing American put option valuation under transaction costs, Applied Mathematics & Computation, 251 (2015), 318-330.  doi: 10.1016/j.amc.2014.11.060. [23] D. C. Lesmana and S. Wang, A numerical scheme for pricing American options with transaction costs under a jump diffusion process, J. Ind. Manag. Optim., 13 (2017), 1793-1813.  doi: 10.3934/jimo.2017019. [24] D. Li and M. Fukushima, Smoothing Newton and quasi-Newton methods for mixed complementarity problems, Computational Optimization and Applications, 17 (2000), 203-230.  doi: 10.1023/A:1026502415830. [25] W. Li and S. Wang, Pricing American options under proportional transaction costs using a penalty approach and a finite difference scheme, J. Ind. Manag. Optim., 9 (2013), 365-398.  doi: 10.3934/jimo.2013.9.365. [26] W. Li and S. Wang, A numerical method for pricing European options with proportional transaction costs, J. Glob. Optim., 60 (2014), 59-78.  doi: 10.1007/s10898-014-0155-5. [27] W. Li and S. Wang, Pricing European options with proportional transaction costs and stochastic volatility using a penalty approach and a finite volume scheme, Computers & Mathematics with Applications, 73 (2017), 2454-2469.  doi: 10.1016/j.camwa.2017.03.024. [28] W. Li, M. Xia and H. Li, New method for computing the upper bound of optimal value in interval quadratic program, J. Comp. Appl. Math., 288 (2015), 70-80.  doi: 10.1016/j.cam.2015.03.055. [29] S.-T. Liu and R.-T. Wang, A numerical solution method to interval quadratic programming, Appl. Math. Comput., 189 (2007), 1274-1281.  doi: 10.1016/j.amc.2006.12.007. [30] X. Liu, Z. Zhang and L. Yin, A multi-objective optimization method for uncertain structure based on nonlinear interval number programming method, Mechanics Based Design of Structure & Machines, 45 (2016), 25-42. [31] A. D. Muradova, G. K. Tairidis and G. E. Stavroulakis, Adaptive Neuro-Fuzzy vibration control of a smart plate, Numerical Algebra, Control & Optimization, 7 (2017), 251-271.  doi: 10.3934/naco.2017017. [32] B. F. Nielsen, O. Skavhaug and A. Tveito, Penalty and front-fixing methods for the numerical solution of American option problems, J. Comp. Fin., 5 (2001), 69-97. [33] J. M. Ortega and  W. C. Rheinboldt,  Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, 1970. [34] F. A. Potra and Y. Ye, Interior-point methods for nonlinear complementarity problems, Journal of Optimization Theory & Applications, 88 (1996), 617-642.  doi: 10.1007/BF02192201. [35] S. Ruzika and M. M. Wiecek, Approximation methods in multiobjective programming, Journal of Optimization Theory & Application, 126 (2005), 473-501.  doi: 10.1007/s10957-005-5494-4. [36] S. Wang, A penalty method for a finite-dimensional obstacle problem with derivative constraints, Optim. Lett., 8 (2014), 1799-1811.  doi: 10.1007/s11590-013-0651-4. [37] S. Wang, A penalty approach to a discretized double obstacle problem with derivative constraints, J. Glob. Optim., 62 (2015), 775-790.  doi: 10.1007/s10898-014-0262-3. [38] S. Wang, An interior penalty method for a large-scale finite-dimensional nonlinear double obstacle problem, Applied Mathematical Modelling, 58 (2018), 217-228.  doi: 10.1016/j.apm.2017.07.038. [39] S. Wang and X. Q. Yang, A power penalty method for linear complementarity problems, Operations Research Letters, 36 (2008), 211-214.  doi: 10.1016/j.orl.2007.06.006. [40] S. Wang, X. Q. Yang and K. L. Teo, Power penalty method for a linear complementarity problem arising from American option valuation, Journal of Optimization Theory & Applications, 129 (2006), 227-254.  doi: 10.1007/s10957-006-9062-3. [41] S. Wang and K. Zhang, An interior penalty method for a finite-dimensional linear complementarity problem in financial engineering, Optim. Lett., 12 (2018), 1161-1178.  doi: 10.1007/s11590-016-1050-4. [42] S. Wang, S. Zhang and Z. Fang, A superconvergent fitted finite volume method for Black-Scholes equations governing European and American option valuation, Numerical Partial Differential Equations, 31 (2015), 1190-1208.  doi: 10.1002/num.21941. [43] H.-C. Wu, The Karush-Kuhn-Tucker conditions in multiobjective programming problems with interval-valued objective functions, European Journal of Operations Research, 196 (2009), 49-60.  doi: 10.1016/j.ejor.2008.03.012. [44] K. Zhang and S. Wang, Convergence property of an interior penalty approach to pricing American option, J. Ind. Manag. Optim., 7 (2011), 435-447.  doi: 10.3934/jimo.2011.7.435.

Figures(5)