×

Duality and separation theorems in idempotent semimodules. (English) Zbl 1042.46004

Summary: We consider subsemimodules and convex subsets of semimodules over semirings with an idempotent addition. We introduce a nonlinear projection on subsemimodules: the projection of a point is the maximal approximation from below of the point in the subsemimodule. We use this projection to separate a point from a convex set. We also show that the projection minimizes the analogue of Hilbert’s projective metric. We develop more generally a theory of dual pairs for idempotent semimodules. We obtain as a corollary duality results between the row and column spaces of matrices with entries in idempotent semirings. We illustrate the results by showing polyhedra and half-spaces over the max-plus semiring.

MSC:

46A20 Duality theory for topological vector spaces
06F07 Quantales
46A55 Convex sets in topological linear spaces; Choquet theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Akian, M.; Gaubert, S.; Kolokoltsov, V., Invertibility of functional Galois connections, C.R. Acad. Sci. Paris Ser. I, 335, 1-6 (2002) · Zbl 1022.06001
[2] Aliprantis, C. D.; Border, K. C., Infinite Dimensional Analysis. A Hitchiker’s Guide (1999), Springer · Zbl 0938.46001
[3] Baccelli, F.; Cohen, G.; Olsder, G. J.; Quadrat, J. P., Synchronization and Linearity-an Algebra for Discrete Event Systems (1992), Wiley · Zbl 0824.93003
[4] Birkhoff, G., (Lattice Theory. Lattice Theory, American Mathematical Society Colloquium Publications, vol. XXV (1940), AMS: AMS Providence, RI)
[5] Blyth, T. S.; Janowitz, M. F., Residuation Theory (1972), Pergamon Press · Zbl 0301.06001
[6] Bourbaki, N., Espaces Vectoriels Topologiques. Éléments de Mathématique (1964), Livre V. Hermann · Zbl 0482.46001
[7] Cao, Z. Q.; Kim, K. H.; Roush, F. W., Incline Algebra and Applications (1984), Ellis Horwood · Zbl 0541.06009
[8] Carré, B. A., An algebra for network routing problems, J. Inst. Math. Appl., 7, 273-294 (1971) · Zbl 0219.90020
[9] Carré, B. A., Graphs and Networks (1979), The Clarendon Press, Oxford University Press: The Clarendon Press, Oxford University Press New York
[10] Cohen, G.; Dubois, D.; Quadrat, J. P.; Viot, M., A linear system theoretic view of discrete event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control, 30, 210-220 (1985) · Zbl 0557.93005
[11] Cohen, G.; Gaubert, S.; Quadrat, J. P., Kernels, images and projections in dioids, (Proceedings of WODES’96 (1996), IEE: IEE Edinburgh) · Zbl 0957.93056
[12] Cohen, G.; Gaubert, S.; Quadrat, J. P., Linear projectors in the max-plus algebra, (5th IEEE Mediterranean Conference on Control and Systems (1997), Paphos: Paphos Cyprus) · Zbl 0957.93056
[13] Cohen, G.; Gaubert, S.; Quadrat, J. P., Max-plus algebra and system theory: where we are and where to go now, Annu. Rev. Control, 23, 207-219 (1999)
[14] Cohen, G.; Gaubert, S.; Quadrat, J. P., Separation theorem for max-plus semimodules, (Menaldi, J. L.; Rofman, E.; Sulem, A., Proceedings of “Optimal Control and Partial Differential Equations” (2001), IOS Press) · Zbl 1054.46500
[15] G. Cohen, S. Gaubert, J.-P. Quadrat, I. Singer, Max-plus convex sets and functions, ESI, Vienna, 2003, Preprint 1341. Also arXiv:math.FA/0308166; G. Cohen, S. Gaubert, J.-P. Quadrat, I. Singer, Max-plus convex sets and functions, ESI, Vienna, 2003, Preprint 1341. Also arXiv:math.FA/0308166 · Zbl 1093.26005
[16] R.A. Cuninghame-Green, Process synchronization in a steelworks-a problem of feasibility, in: J. Banbury, J. Maitland (Eds.), Proceedings of the 2nd International Conference on Operations research, Aix-en-Provence, France, 1961; R.A. Cuninghame-Green, Process synchronization in a steelworks-a problem of feasibility, in: J. Banbury, J. Maitland (Eds.), Proceedings of the 2nd International Conference on Operations research, Aix-en-Provence, France, 1961
[17] Cuninghame-Green, R. A., Describing industrial processes with interference and approximating their steady state behavior, Oper. Res. Quat., 13, 1, 95-100 (1962)
[18] Cuninghame-Green, R. A., Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166 (1979), Springer · Zbl 0399.90052
[19] Cuninghame-Green, R. A., Minimax algebra and applications, Adv. Imaging Electron Phys. (1995) · Zbl 0845.04007
[20] M.L. Dubreil-Jacotin, L. Lesieur, R. Croisot, Leçons sur la Théorie des Treillis, des Structures Algébriques Ordonnées, et des Treillis géométriques, vol. XXI of Cahiers Scientifiques, Gauthier Villars, Paris, 1953; M.L. Dubreil-Jacotin, L. Lesieur, R. Croisot, Leçons sur la Théorie des Treillis, des Structures Algébriques Ordonnées, et des Treillis géométriques, vol. XXI of Cahiers Scientifiques, Gauthier Villars, Paris, 1953 · Zbl 0051.26005
[21] S. Gaubert, Théorie des systèmes linéaires dans les dioı̈des, Thèse, École des Mines de Paris, 1992; S. Gaubert, Théorie des systèmes linéaires dans les dioı̈des, Thèse, École des Mines de Paris, 1992
[22] Gaubert, S.; Plus, M., Methods and applications of (max,+) linear algebra, (Reischuk, R.; Morvan, M., STACS’97, LNCS, vol. 1200 (1997), Springer: Springer Lübeck) · Zbl 1498.15034
[23] Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M.; Scott, D. S., A Compendium of Continuous Lattices (1980), Springer · Zbl 0452.06001
[24] Golan, J. S., The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science, vol. 54 (1992), Longman Sci & Tech · Zbl 0780.16036
[25] Gondran, M.; Minoux, M., Valeurs propres et vecteurs propres dans les dioı̈des et leur interprétation en théorie des graphes, EDF, Bulletin de la Direction des Etudes et Recherches, Serie C, Mathématiques Informatique, 2, 25-41 (1977)
[26] Gondran, M.; Minoux, M., Linear algebra in dioids: a survey of recent results, Ann. Discrete Math., 19, 147-164 (1984) · Zbl 0568.08001
[27] Gondran, M.; Minoux, M., Graphes, Dioı̈des et semi-anneaux (2002), TEC & DOC: TEC & DOC Paris · Zbl 1025.90034
[28] (Gunawardena, J., Idempotency (1998), Publications of the Newton Institute, Cambridge University Press)
[29] Hasse, M., Über die Behandlung graphentheoretischer Probleme unter Verwendung der Matrizenrechnung, Wiss. Z. Techn. Univ. Dresden, 10, 1313-1316 (1961) · Zbl 0101.16605
[30] Kim, K. H., Boolean Matrix Theory and Applications (1982), Marcel Dekker: Marcel Dekker New York
[31] V. Kolokoltsov, personal communication, 1999; V. Kolokoltsov, personal communication, 1999
[32] Kolokoltsov, V.; Maslov, V., Idempotent Analysis and Applications (1997), Kluwer Academic Publishers · Zbl 0941.93001
[33] Korbut, A. A., Extremal spaces, Dokl. Akad. Nauk SSSR, 164, 1229-1231 (1965) · Zbl 0135.34201
[34] Litvinov, G. L.; Shpiz, G. B., Nuclear semimodules and kernel theorems in idempotent analysis: an algebraic approach, Dokl. Math. Sci. (2002), Also math.FA/0206026 · Zbl 1246.46063
[35] Litvinov, G. L.; Maslov, V. P.; Shpiz, G. B., Linear functionals on idempotent spaces: an algebraic approach, Dokl. Math., 58, 3, 389-391 (1998) · Zbl 0970.46003
[36] Litvinov, G. L.; Maslov, V. P.; Shpiz, G. B., Idempotent functional analysis: an algebraic approach, Math. Notes, 69, 5, 696-729 (2001), Also reprint arXiv:math.FA/0009128 · Zbl 1017.46034
[37] V. Maslov, S. Samborskiı̆ (Eds.), Idempotent Analysis, Adv. in Sov. Math., vol. 13, AMS, RI, 1992; V. Maslov, S. Samborskiı̆ (Eds.), Idempotent Analysis, Adv. in Sov. Math., vol. 13, AMS, RI, 1992
[38] V.P. Maslov, Méthodes Opératorielles, Mir. Moscou. French Transl. 1987, 1973; V.P. Maslov, Méthodes Opératorielles, Mir. Moscou. French Transl. 1987, 1973
[39] Max Plus, Linear systems in (max,+)-algebra, in: Proceedings of the 29th Conference on Decision and Control, Honolulu, 1990; Max Plus, Linear systems in (max,+)-algebra, in: Proceedings of the 29th Conference on Decision and Control, Honolulu, 1990 · Zbl 0699.90094
[40] P. Moller, Théorie algébrique des Systèmes à Événements Discrets, Thèse, École des Mines de Paris, 1988; P. Moller, Théorie algébrique des Systèmes à Événements Discrets, Thèse, École des Mines de Paris, 1988
[41] Romanovskiı̆, I. V., Optimization of stationary control of discrete deterministic process in dynamic programming, Kibernetika, 3, 2, 66-78 (1967)
[42] Samborskiı̆, S. N.; Shpiz, G. B., Convex sets in the semimodule of bounded functions, (Idempotent Analysis (1992), Amer. Math. Soc: Amer. Math. Soc Providence, RI), 135-137 · Zbl 0896.47030
[43] Vorob’ev, N. N., An extremal matrix algebra, Dokl. Akad. Nauk SSSR, 152, 24-27 (1963) · Zbl 0168.02602
[44] Vorob’ev, N. N., Extremal algebra of positive matrices, Elektron. Informationsverarbeit. Kybernetik, 3, 39-71 (1967) · Zbl 0168.02603
[45] Vorob’ev, N. N., Extremal algebra of non-negative matrices, Elektron. Informationsverarbeit. Kybernetik, 6, 303-311 (1970)
[46] Wagneur, E., Moduloids and pseudomodules. 1. Dimension theory, Discrete Math., 98, 57-73 (1991) · Zbl 0757.06008
[47] E. Wagneur, personal communication, 1991; E. Wagneur, personal communication, 1991
[48] Yoeli, M., A note on a generalization of Boolean matrix theory, Amer. Math. Monthly, 68, 552-557 (1961) · Zbl 0115.02103
[49] K. Zimmermann, Extremálnı́ Algebra, Ekonomický ùstav C̆SAV, Praha (in Czech), 1976; K. Zimmermann, Extremálnı́ Algebra, Ekonomický ùstav C̆SAV, Praha (in Czech), 1976
[50] Zimmermann, K., A general separation theorem in extremal algebras, Ekonom.-Mat. Obzor, 13, 2, 179-201 (1977)
[51] Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structures (1981), North Holland · Zbl 0466.90045
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.