A Tikhonov regularized penalty function approach for solving polylinear programming problems. (English) Zbl 1375.65082
Summary: This paper suggests a new regularized penalty method for poly-linear functions. Until our knowledge it is the first time that a regularization approach solution for poly-linear programming is reported in the literature. We propose a penalty function depending on two parameters \(\mu\) and \(\delta\) for ensuring the strong convexity and the existence of a unique solution involving equality and inequality constraints. We prove that if the penalty parameter \(\mu\) tends to zero then the solution of the original problem converges to a unique solution with the minimal weighted norm. We introduce a recurrent procedure based on the projection-gradient method for finding the extremal points and we also prove the convergence of the method. We develop an example for game theory and additional example for portfolio optimization employing the proposed regularization method for Markov chains involving the definition of a poly-linear function.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C05 | Linear programming |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
Keywords:
Tikhonov regularization; poly-linear programming; ill-posed problem; Markov chains; projection-gradient method; convergenceReferences:
| [1] | Tikhonov, A. N.; Arsenin, V. Y., Solution of Ill-Posed Problems (1977), Washington: Winston & Sons · Zbl 0354.65028 |
| [2] | Tikhonov, A. N.; Goncharsky, A. V.; Stepanov, V. V.; Yagola, A. G., Numerical Methods for the Solution of Ill-Posed Problems (1995), Kluwer Academic Publishers · Zbl 0831.65059 |
| [3] | Clempner, J. B.; Poznyak, A. S., Solving the pareto front for nonlinear multiobjective Markov chains using the minimum Euclidian distance optimization method, Math. Comput. Simulation, 119, 142-160 (2016) · Zbl 1527.90196 |
| [4] | Trejo, K. K.; Clempner, J. B.; Poznyak, A. S., Computing the stackelberg/nash equilibria using the extraproximal method: convergence analysis and implementation details for Markov chains games, Int. J. Appl. Math. Comput. Sci., 25, 2, 337-351 (2015) · Zbl 1406.91023 |
| [5] | Morozov, V. A., (Nashed, Z., Methods for Solving Incorrectly Posed Problems (1984), Springer-Verlag New York) · Zbl 0549.65031 |
| [7] | Fastrich, B.; Paterlini, S.; Winker, P., Constructing optimal sparse portfolios using regularization methods, Comput. Manag. Sci., 12, 3, 417-434 (2015) · Zbl 1355.91077 |
| [8] | Sánchez, E. M.; Clempner, J. B.; Poznyak, A. S., Solving the mean-variance customer portfolio in Markov chains using Iterated Quadratic/Lagrange Programming: A credit-card customer-credit limits approach, Expert Syst. Appl., 42, 12, 5315-5327 (2015) |
| [9] | Sánchez, E. M.; Clempner, J. B.; Poznyak, A. S., A priori-knowledge/actor-critic reinforcement learning architecture for computing the mean-variance customer portfolio: The case of bank marketing campaigns, Eng. Appl. Artif. Intell., 46, Part A, 82-92 (2015) |
| [10] | Nieminen, T.; Kangas, J.; Kettunen, L., Use of Tikhonov regularization to improve the accuracy of position estimates in inertial navigation, Int. J. Navig. Obs., 2011, 10 (2011), Article ID 450269 |
| [11] | Luo, X.-P., Tikhonov regularization methods for inverse variational inequalities, Optim. Lett., 8, 3, 877-887 (2014) · Zbl 1310.90113 |
| [12] | Trejo, K. K.; Clempner, J. B.; Poznyak, A. S., An optimal strong equilibrium solution for cooperative Multi-Leader-Follower Stackelberg Markov chains games, Kibernetika, 52, 2, 258-279 (2016) · Zbl 1374.35201 |
| [13] | Trejo, K. K.; Clempner, J. B.; Poznyak, A. S., Computing the Lp-strong nash equilibrium for Markov chains games, Appl. Math. Model., 41, 399-418 (2017) · Zbl 1443.91041 |
| [14] | Borsdorff, T.; Hasekamp, O. P.; Wassmann, A.; Landgraf, J., Insights into Tikhonov regularization: application to trace gas column retrieval and the efficient calculation of total column averaging kernels, Atmos. Meas. Tech., 7, 523-535 (2014) |
| [15] | Salahi, M., Regularization tools and robust optimization for ill-conditioned least squares problem: a computational comparison, Appl. Math. Comput., 217, 7985-7990 (2011) · Zbl 1219.65043 |
| [16] | Chen, Z.; Xiang, C.; Zhao, K.; Liu, X. S., Convergence analysis of Tikhonov-type regularization algorithms for multiobjective optimization problems, Appl. Math. Comput., 211, 167-172 (2009) · Zbl 1162.90551 |
| [17] | Yin, J.-F., Preconditioner based on the Sherman-Morrison formula for regularized least squares problems, Appl. Math. Comput., 215, 3007-3016 (2009) · Zbl 1192.65036 |
| [18] | Chung, J.; Nagy, J. G.; O’Leary, D. P., A weighted-GCV method for Lanczos-hybrid regularization, Electron. Trans. Numer. Anal., 28, 149-167 (2008) · Zbl 1171.65029 |
| [19] | Gongsheng, L.; Jinqing, L.; Xiaoping, F.; Yu, M., A new gradient regularization algorithm for source term inversion in 1D solute transportation with final observations, Appl. Math. Comput., 196, 646-660 (2008) · Zbl 1135.65372 |
| [20] | Hansen, P. C.; Jensen, T. K., Smoothing-norm preconditioning for regularizing minimum-residual methods, SIAM J. Matrix Anal. Appl., 29, 1-14 (2006) · Zbl 1154.65028 |
| [21] | Lampe, J.; Reichel, L.; Voss, H., Large-scale Tikhonov regularization via reduction by orthogonal projection, Linear Algebra Appl., 436, 8, 2845-2865 (2012) · Zbl 1241.65044 |
| [22] | Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 43-71 (1982) · Zbl 0478.65016 |
| [23] | Reichel, L.; Sgallari, F.; Ye, Q., Tikhonov regularization based on generalized Krylov subspace methods, Appl. Numer. Math., 62, 9, 1215-1228 (2012) · Zbl 1246.65068 |
| [24] | Bauer, F.; Pereverzev, S. V., An utilization of a rough approximation of a noise covariance within the framework of multi-parameter regularization, Int. J. Tomogr. Simul., 4, 1-12 (2006) · Zbl 1133.62321 |
| [25] | Lu, Y.; Shen, L.; Xu, Y., Multi-parameter regularization methods for high-resolution image reconstruction with displacement errors, IEEE Trans. Circuits Syst. I, 54, 1788-1799 (2007) · Zbl 1374.94240 |
| [26] | Xu, P.; Fukuda, Y.; Liu, Y. M., Multiple parameter regularization: Numerical solutions and applications to the determination of geopotential from precise satellite orbits, J. Geod., 80, 17-27 (2006) |
| [27] | Poznyak, A. S.; Najim, K.; Gomez-Ramirez, E., Self-Learning Control of Finite Markov Chains (2000), Marcel Dekker: Marcel Dekker New York · Zbl 0960.93001 |
| [28] | Clempner, J. B.; Poznyak, A. S., Simple computing of the customer lifetime value: A fixed local-optimal policy approach, J. Syst. Sci. Syst. Eng., 23, 4, 439-459 (2014) |
| [29] | Donatelli, M.; Reichel, L., Square smoothing regularization matrices with accurate boundary conditions, J. Comput. Appl. Math., 272, 334-349 (2014) · Zbl 1294.65099 |
| [30] | Dykes, L.; Reichel, L., On the reduction of Tikhonov minimization problems and the construction of regularization matrices, Numer. Algorithms, 60, 683-696 (2012) · Zbl 1254.65049 |
| [31] | Hearn, T. A.; Reichel, L., Application of denoising methods to regularization of illposed problems, Numer. Algorithms, 66, 761-777 (2014) · Zbl 1297.65043 |
| [32] | Neuman, A.; Reichel, L.; Sadok, H., Implementations of range restricted iterative methods for linear discrete ill-posed problems, Linear Algebra Appl., 436, 3974-3990 (2012) · Zbl 1241.65045 |
| [33] | Cao, H.; Pereverzev, S. V.; Sincich, E., Discretized Tikhonov regularization for Robin boundaries localization, Appl. Math. Comput., 226, 374-385 (2014) · Zbl 1372.35358 |
| [34] | Novati, P.; Russo, M. R., A GCV based Arnoldi-Tikhonov regularization method, BIT Numer. Math., 54, 2, 501-521 (2014) · Zbl 1317.65104 |
| [35] | Gazzola, S.; Nagy, J. G., Generalized Arnoldi-Tikhonov Method for Sparse Reconstruction., SIAM J. Sci. Comput., 36, 2, B225-B247 (2014) · Zbl 1296.65061 |
| [36] | Bazán, F. S.V., Simple and efficient determination of the Tikhonov regularization parameter chosen by the generalized discrepancy principle for discrete Ill-posed problems, J. Sci. Comput., 63, 1, 163-184 (2015) · Zbl 1323.65038 |
| [37] | Yang, X. J.; Wang, L., A modified Tikhonov regularization method, J. Comput. Appl. Math., 288, 180-192 (2015) · Zbl 1328.65096 |
| [38] | Rajan, M. P.; Reddy, G. D., A variant of Tikhonov regularization for parabolic PDE with space derivative multiplied by a small parameter \(\epsilon \), Appl. Math. Comput., 259, 412-426 (2015) · Zbl 1390.35121 |
| [39] | Zangwill, W. I., Nonlinear Programming: A Unified Approach (1969), Prentice-Halt: Prentice-Halt Englewood Cliffs · Zbl 0191.49101 |
| [40] | Garcia, C. B.; Zangwill, W. I., Pathways to Solutions, Fixed Points and Equilibria (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 0512.90070 |
| [41] | Poznyak, A. S., Advanced Mathematical tools for Automatic Control Engineers. Deterministic technique, Vol. 1 (2008), Elsevier: Elsevier Amsterdam, Oxford |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
