Tropical linear algebra and its applications
Alexander E.
Guterman,
Faculty of Algebra,
Dept of Mathematics and Mechanics,
LMSU
Place: Moscow
The Rome-Moscow school of
Matrix Methods and Applied Linear Algebra
19th September - 3th
October 2010, University of Rome “Tor Vergata”
10th - 24th October 2010, Lomonosov Moscow State University
Seminars
Hilbert 17-th problem in matrices
Florin Radulescu,
Faculty of Sciences,
Dept of Mathematics,
TV
Place: Rome
Tropical algebra
(sometimes called max or min algebra) is a set of real
numbers equipped with the maximum operation instead of usual addition
and addition instead of usual multiplication. Under these operations
this is an algebraic structure called a semiring. Such structures
naturally appear in modern scheduling theory, control theory,
optimization, dynamical systems and networks. Tropical arithmetic
allows to reduce difficult non-linear problems to the linear
problems but over tropical semiring. Therefore, to investigate these
problems it is necessary to develop linear algebra in the tropical
case. This subject is very actual nowdays and it will be a main topic
of our considerations.
RECOMMENDED LITERATURE:
1. F. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat,
Synchronization and
linearity. John Wiley and Sons, New York, 1992.
2. M. Akian, S. Gaubert, A. Guterman, Linear
independence over tropical
semirings and beyond, Contemporary Mathematics, AMS,
Vol. 495, 2009, 1-33.
3. C.G. Cassandras, S. Lafortune, Introduction to
Discrete Event Systems,
Kluwer Academic Publishers, Boston, 1999.
4. R.A. Cuninghame-Green, Minimax Algebra. Lecture
Notes in Economics and
Mathematical Systems, Vol. 166, Springer-Verlag,
Berlin, 1979.
5. S. Gaubert, Methods and applications of
(max,+)-linear algebra.
Lecture Notes in Computer Science, Vol. 1200,
Springer-Verlag, Berlin, 1997.
6. J.S. Golan, Semirings and their Applications.
Kluwer Academic
Publishers, Dordrecht, 1999.
7. J. Gunawardena, ed. Idempotency. Publication of the
Newton Institute,
Cambridge University Press, Cambridge, U.K., 1998.
8. V.N. Kolokoltsov, V.P. Maslov, Idempotent Analysis
and its
Applications. Kluwer Academic Publishers, Dordrecht,
1997.
It is required that stidents know some
basic linear algebra:
vectors, matrices, rank, determinant, eigenvalues and eigenvectors.
We present a deep conjecture in Von Neumann algebras whose text could be eventually reformulated only in terms of of noncommutative, trace positive polynomials
Operator matrix methods in the theory of Operator Algebras
Laszlo Zsido,
Faculty of Sciences,
Dept of Mathematics,
TV
Place: Rome
Matrices of
linear operators can be represented as linear operators and so matrices
of operator algebras can be considered again operators algebras. But
completing an operator to an operator matrix, it can be "made", for
example, self-adjoint or positive, allowing thus the reduction of
certain proofs or computations to particular situations.
We think to present certain relevant applications of operator matrices in the theory of operator algebras
Canonical form for pairs of Hermitian symmetric matrices
Mauro Nacinovich,
Faculty of Sciences,
Dept of Mathematics,
TV
Place: Rome
We consider
Hermitian symmetric matrices H under the standard action a^*Ha of the
complex linear group.
Rank and signature give a complete set of
discrete invariants for a single Hermitian symmetric matrix. For a pair
(H_1,H_2) of Hermitian symmetric matrices, a complete set of invariants
consists of the rank r, defined as the complement of the dimension of
the intersection of their two kernels; of a set of minimal indices,
that are positive integers that appear only when no
linear combination aH_1+bH_2 has rank r;
and by some relative eigenvalues, with multiplicities, of H_2 with
respect to H_1, that can be real, complex or infinity (they are points
of the complex projective line).
This description is related to a canonical biorthogonal decomposition. The case of larger sets of linearly independent Hermitian matrices is an open question in algebra.
Matrix Structures and Global Optimization
Stefano Fanelli
Faculty of Sciences,
Dept of Mathematics,
TV
Place: Rome
Abstract
Deterministic Non
Linear Global Optimization is an important area of research in
Computational Mathematics. The author et alii showed in [1],[2] that
BFGS- type methods of low-complexity are able to obtain satisfactory
results in the determination of local minima (maxima). For twice
continuosly differentiable functions (see [1], [2], [3], [4]) the
utilization of structured matrices can play an important role in the
local optimizations, by approximating the Hessian of the ob jective
function. BFGS-type algorithms with O(n) complexity per step, in
particular, are very efficient for solving large scale problems (see
[5],[6]). It is important to stress that the classical BFGS method has
O(n^2) complexity per iteration and therefore cannot be implemented
effectively to minimize functions with a large number of variables.
BFGS-type methods can be applied in the frame of a global optimization
scheme, by maintaining the well known efficiency of the fast
transform-based algorithms utilized in the local searches.
More precisely, by
the utilization of suitable terminal repel lers and tunneling
techniques one can build algorithms based on a sequence of cycles,
where each cycle has two phases, i.e. a local optimization phase and a
tunneling one. The main aim of these procedures is to build a monotone
sequence of local minima (maxima), by determining a set of possible
candidates for the global minimum (maximum).
Unfortunately, the
utilization of scalar repellers is unsuitable, when the dimension n of
the problem assumes values of operational interest. A repeller
structured matrix, based on the sum of a diagonal matrix and a low rank
one ([7], [8]), can be constructed to overcome the latter difficulty. In
this way, the application of a BFGS-type method can be effectively
extended to the tunneling phases and hence to the whole global
optimization scheme ([9]).
References
[1] Di Fiore C., Fanelli S., Lepore F., Zellini P.:
Matrix algebras in quasi-Newton methods for unconstrained optimization. Numer. Math.,
94, 479-500, 2003.
[2] Bortoletti A., Di Fiore C., Fanelli S., Zellini
P.: A new class of quasi-Newtonian methods for optimal
learning in MLP-networks. IEEE Trans. Neural Networks, 14, 263-273, 2003.
[3] Di Fiore C., Fanelli S., Zellini P.: Low
complexity minimization algorithms. Numer. Linear Algebra with
Appl., 12, 755-768, 2005. 1
[4] Di Fiore C., Fanelli S., Zellini P.: Low
complexity secant quasi-Newton minimization algorithms for nonconvex
functions. J. of Comp. and Appl. Mathematics, 210, 167-174, 2007.
[5] Di Fiore C., Fanelli S., Zellini P.: An efficient
generalization of Battiti-Shanno’s quasi-Newton algorithm for
optimal learning in MLP-networks. In: Neural Information Processing,
Springer Verlag, Calcutta, 1, 483-488, 2004.
[6] Chai J.F., Chan R.H., Di Fiore C.: Minimization of
a detailed- preserving regularization functional for impulse noise
removal. Journal of Math. Imaging Vis., 29, pp. 79-91, (2007).
[7] Oseledets I., Tyrtyshnikov E.: A unifying approach
to the construction of circulant preconditioners. Linear Algebra and
its Appl., 418, 435-449, 2006.
[8] Tyrtyshnikov E.: Private communication.
[9] Fanelli S.: A BFGS-type algorithm for
box-constrained global optimization. J. Optim. Theory Appl., to
appear.