×

A parameter method for linear algebra and optimization with uncertainties. (English) Zbl 07150149

Summary: Systems of linear equations are studied with uncertainties in the coefficients, often representing imprecise data. Such imprecisions are seen as orders of magnitude. The orders of magnitude are not functionally modelled in terms of \(O(.)\) or \(o(.)\), but within nonstandard analysis as neutrices and external numbers, convex external sets of nonstandard real numbers.
In this setting, linear systems with external coefficients are solved by a parameter method. This method assigns a parameter to each imprecision and specifies its range. Then we obtain an ordinary linear system and solve by common methods. At the end we substitute each parameter by its range. We present general solution formulas, for an arbitrary number of equations and variables. We illustrate with a concrete system that the parameter method gives more precise results, under more general conditions, than dealing with propagation of errors in direct Gauss-Jordan elimination or the Cramer rule.
We apply the results to linear optimization with uncertainties. In a general setting, nearly optimal solutions are obtained and the shape of the domains of validity of the nearly optimal solutions.

MSC:

03H05 Nonstandard models in mathematics
15A06 Linear equations (linear algebraic aspects)
65G40 General methods in interval analysis
90C05 Linear programming
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Diener, F.; Diener, M., Nonstandard analysis in practice (1995), Berlin: Springer-Verlag · Zbl 0848.26015
[2] Dinis, B.; Van Den Berg, Ip., Axiomatics for the external numbers of nonstandard analysis, J Logic Anal, 9, 7, 1-47 (2017) · Zbl 1423.03262
[3] Van Der Corput, Jg., Introduction to the neutrix calculus, J Anal Math, 7, 1, 291-398 (1959)
[4] Justino, J.; Van Den Berg, Ip., Cramer’s rule applied to flexible systems of linear equations, Electron J Linear Algebra, 24, 126-152 (2012) · Zbl 1253.15007
[5] Clifford, Aa., Multivariate error analysis: a handbook of error propagation and calculation in many-parameter systems (1973), New York: Wiley
[6] Kall, P.; Mayer, J., Stochastic linear programming: models, theory, and computation (2011), Boston (MA): Springer · Zbl 1211.90003
[7] Saltelli, A.; Ratto, M.; Andres, T., Global sensitivity analysis: the primer (2008), Hoboken (NJ): Wiley · Zbl 1161.00304
[8] Luhandjula, Mk., Fuzzy optimization: milestones and perspectives, Fuzzy Sets Syst, 274, 1, 4-11 (2015) · Zbl 1373.90003
[9] Tanaka, H.; Asai, K., Fuzzy linear programming problems with fuzzy numbers, Fuzzy Sets Sys North-Holland, 13, 1, 1-10 (1984) · Zbl 0546.90062
[10] Borrelli, F.; Bemporad, A.; Morari, M., A geometric algorithm for multi-parametric linear programming, J Optim Theory Appl, 118, 3, 515-540 (2003) · Zbl 1061.90086
[11] Charitopoulos, Vm; Papageorgiou, Lg; Dua, V., Multi-parametric linear programming under global uncertainty, AIChE J, 63, 9, 3871-3895 (2017)
[12] Gal, T.; Nedoma, J., Multiparametric linear programming, Manage Sci, 18, 7, 406-422 (1972) · Zbl 0237.90037
[13] Gollmer, R., On linear multiparametric optimization with parameter-dependent constraints matrix, Optimization, 16, 1, 15-28 (1985) · Zbl 0564.90074
[14] Alefeld, G.; Mayer, G., Interval analysis: theory and applications, J Comput Appl Math, 121, 1-2, 421-464 (2000) · Zbl 0995.65056
[15] Alparslan Gök, Sz; Miquel, S.; Tijs, S., Cooperation under interval uncertainty, Math Method Oper Res, 69, 1, 99-109 (2009) · Zbl 1159.91310
[16] Gabrel, V.; Murat, C.; Remli, N., Linear programming with interval right hand-sides, Inter Trans Oper Res, 17, 3, 397-408 (2010) · Zbl 1187.90188
[17] Hansen, E.; Walster, Gw., Global optimization using interval analysis (2004), New York: Marcel Dekker, New York · Zbl 1103.90092
[18] Hladík, M.Robust optimal solutions in interval linear programming with forall-exists quantifiers. 2014. arXiv:1403.7427v1 [math.OC]. · Zbl 1346.90574
[19] Moore, Re; Kearfott, Rb; Cloud, Mj., Introduction to interval analysis (2009), Philadelphia: SIAM · Zbl 1168.65002
[20] Neumaier, A., Interval methods for systems of equations (1990), Cambridge: Cambridge University Press, Cambridge · Zbl 0706.15009
[21] Dinis, B.; Van Den Berg, Ip., Algebraic properties of external numbers, J Logic Anal, 3, 9, 1-30 (2011) · Zbl 1285.03079
[22] Petrich, M, Reilly, N.Completely regular semigroups. Vol. 23. Wiley-Interscience; 1999. (Canadian Mathematical Society Series of Monographs and Advanced Texts). · Zbl 0967.20034
[23] Dinis, B.; Van Den Berg, Ip., Characterization of distributivity in a solid, Indagationes Math, 29, 2, 580-600 (2018) · Zbl 1437.12005
[24] Van Den Berg, Ip; Neves, V., The strength of nonstandard analysis (2007), Wien: Springer-Verlag · Zbl 1117.03074
[25] Van Den Berg, Ip., A decomposition theorem for neutrices, Annal Pure Appl Logic, 161, 7, 851-865 (2010) · Zbl 1223.03056
[26] Chinneck, Jw; Ramadan, K., Linear programming with interval coefficients, J Oper Res Soc, 51, 2, 209-220 (2000) · Zbl 1107.90420
[27] Justino, J.Nonstandard linear algebra with error analysis [PhD thesis]. University of Évora; 2013.
[28] Nelson, E., Internal set theory: a new approach to nonstandard analysis, Bull Am Math Soc, 83, 6, 1165-1198 (1977) · Zbl 0373.02040
[29] Diener, F.; Reeb, G., Analyse nonstandard (1989), Paris: Hermann · Zbl 0682.26010
[30] Lyantse, W.; Kudryk, T., Introduction to nonstandard analysis (1997), Lviv: VNTL Publishers, Lviv · Zbl 1102.46313
[31] Kanovei, V.; Reeken, M., Nonstandard analysis, axiomatically (2004), Berlin: Springer-Verlag · Zbl 1058.03002
[32] Taylor, Jr., An introduction to error analysis: the study of uncertainties in physical measurements (1997), Sausalito (CA): University Science Books
[33] Batson, Rg., Necessary and sufficient conditions for boundedness of extreme points of unbounded convex sets, J Math Anal Appl, 130, 2, 365-374 (1988) · Zbl 0639.52003
[34] Rockafellar, Rt., Convex analysis (1970), Princeton (NJ): Princeton University Press · Zbl 0193.18401
[35] Mokhtar, Sb; John, Jj; Hanif, Ds., Linear programming and network flows (2010), Hoboken (NJ): Wiley · Zbl 1200.90002
[36] Tran, Vn.Optimization with flexible objectives and constraints [PhD thesis]. University of Évora; 2017.
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.