Eigenvalue Multiplicity Estimate in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (such as linear and quadratic programming) and has many applications in engineering. Typically, the optimal eigenvalue multiplicity associated with a linear matrix inequality is larger than one. Algorithms based on prior knowledge of the optimal eigenvalue multiplicity for solving the underlying problem have been shown to be efficient. In this paper, we propose a scheme to estimate the optimal eigenvalue multiplicity from points close to the solution. With some mild assumptions, it is shown that there exists an open neighborhood around the minimizer so that our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to incorporate this result into a generalization of an existing local method for solving the semidefinite programming problem. Finally, a numerical example is included to illustrate the results.     

Mixed dominating matrices

We characterize the class of matrices for which the set of supports of nonnegative vectors in the null space can be determined by the signs of the entries of the matrix. This characterization is in terms of mixed dominating matrices, which are defined by the nonexistence of square submatrices that have nonzeros of opposite sign in each row. The class of mixed dominating matrices is contained in the class of L-matrices from the theory of sign-solvability, and generalizes the class of S-matrices. We give a polynomial-time algorithm to decide if a matrix is mixed dominating. We derive combinatorial conditions on the face lattice of a Gale transform of a matrix in this class.     

Relative asymptotics for orthogonal matrix polynomials

In this paper we study sequences of matrix polynomials that satisfy a non-symmetric recurrence relation. To study this kind of sequences we use a vector interpretation of the matrix orthogonality. In the context of these sequences of matrix polynomials we introduce the concept of the generalized matrix Nevai class and we give the ratio asymptotics between two consecutive polynomials belonging to this class. We study the generalized matrix Chebyshev polynomials and we deduce its explicit expression as well as we show some illustrative examples. The concept of a Dirac delta functional is introduced. We show how the vector model that includes a Dirac delta functional is a representation of a discrete Sobolev inner product. It also allows to reinterpret such perturbations in the usual matrix Nevai class. Finally, the relative asymptotics between a polynomial in the generalized matrix Nevai class and a polynomial that is orthogonal to a modification of the corresponding matrix measure by the addition of a Dirac delta functional is deduced.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

Perturbation theory for games in normal form and stochastic games

In this paper, the effect on values and optimal strategies of perturbations of game parameters (payoff function, transition probability function, and discount factor) is studied for the class of zero-sum games in normal form and for the class of stationary, discounted, two-person, zero-sum stochastic games.A main result is that, under certain conditions, the value depends on these parameters in a pointwise Lipschitz continuous way and that the sets of -optimal strategies for both players are upper semicontinuous multifunctions of the game parameters.Extensions to general-sum games and nonstationary stochastic games are also indicated.     

Bifurcation of a Whitney-Smooth Family of Coisotropic Invariant Tori of a Hamiltonian System under Small Deformations of a Symplectic Structure

We investigate the influence of small deformations of a symplectic structure and perturbations of the Hamiltonian on the behavior of a completely integrable Hamiltonian system. We show that a Whitney-smooth family of coisotropic invariant tori of the perturbed system emerges in the neighborhood of a certain submanifold of the phase space.     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

A generalization of simplicial elimination orderings

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P₄ and no 2K₂. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP-hard. We give a polynomial-time algorithm for optimally coloring the vertices of such a graph when it is perfect. © 1996 John Wiley & Sons, Inc.     

Critical Objective Size and Calmness Modulus in Linear Programming

This paper introduces the concept of critical objective size associated with a linear program in order to provide operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping under uniqueness of nominal optimal solution and perturbations of all coefficients. Our starting point is an upper bound on this modulus given in Cánovas et al. (4). In this paper we prove that this upper bound is attained if and only if the norm of the objective function coefficient vector is less than or equal to the critical objective size. This concept also allows us to obtain operative lower bounds on the calmness modulus. We analyze in detail an illustrative example in order to explore some strategies that can improve the referred upper and lower bounds.     

Perturbations of Jordan matrices

We consider perturbations of a large Jordan matrix, either random and small in norm or of small rank. In the case of random perturbations we obtain explicit estimates which show that as the size of the matrix increases, most of the eigenvalues of the perturbed matrix converge to a certain circle with centre at the origin. In the case of finite rank perturbations we completely determine the spectral asymptotics as the size of the matrix increases.     

Stability of Differential-Algebraic Equations under Uncertainty

We consider a linear time-invariant homogeneous system of first-order ordinary differential equations with a noninvertible matrix multiplying the derivative of the unknown vector function and with perturbed coefficients. We introduce a class of perturbations of the coefficient matrices of the system and determine conditions on the perturbations of this class under which they do not affect the internal structure of the system. We obtain sufficient conditions for the robust stability of the system under such perturbations.     

Invariant surfaces of standard two-dimensional systems with conservative first approximation of the third order

We simultaneously study two classes of two-dimensional time-periodic systems of differential equations with a small positive parameter, namely, systems with “slow” or “fast” time whose first-approximation systems are autonomous and conservative and do not contain terms of order higher than three. Thus, the corresponding unperturbed systems have one, two, or three rest points.For the perturbations, we indicate explicit conditions, independent of the small parameter, under which every original system of either class with coefficients three times continuously differentiable with respect to the phase variables and the parameter in a neighborhood of zero has finitely many two-dimensional invariant surfaces homeomorphic to tori for all sufficiently small parameter values. We also give formulas for these surfaces.     

Finite dimensional approximation of nonlinear problems

Summary We continue here the study of a general method of approximation of nonlinear equations in a Banach space yet considered in [2]. In this paper, we give fairly general approximation results for the solutions in a neighborhood of a simple limit point. We the apply the previous analysis to the study of Galerkin approximations for a class of variationally posed nonlinear problems and to a mixed finite element method for the NavierStokes equations.This work has been completed during a visit at the Université Pierre et Marie Curic and at the Ecole PolytechniqueSupported by the Fonds National Suisse de la Recherche Scientifique     

Stationary equilibria in cyclic games: Search and structure

The existence of optimal stationary strategies for a cyclic game played on the vertices of a bipartite graph up to the first cycle with the payoff of one player to the other equaling the sum of the maximal and minimal local payoffs on this cycle is proved. This result implies that the problem belongs to the class NP ∩ co-NP; -a polynomial algorithm that yields optimal strategies for ergodic extensions of matrix games is given. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 913–921, June, 2000.     

Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t−1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 consists of playing the same mixed action at every stage, irrespective of past play. Furthermore, for games in which player 1 has a simple optimal strategy, we characterize the set of stationary optimal strategies for player 2.     

Reconstruction of the Hermitian matrix by its spectrum and spectra of some number of its perturbations

Explicit formulas for matrix elements of the Hermitian matrix are found through a spectrum of this matrix and spectra of some number of its perturbations. A dependence of sufficient number of perturbations from the structure of the matrix and the kind of perturbations is established. It is shown that for arbitrary matrix needed number of perturbations is of N², where N is an order of the matrix. In the case, when the number and locations of zero elements of the matrix is known, needed number of perturbations decreases essentially.     

Avoiding unfairness of Owen allocations in linear production processes

This paper deals with cooperation situations in linear production problems in which a set of goods are to be produced from a set of resources so that a certain benefit function is maximized, assuming that resources not used in the production plan have no value by themselves. The Owen set is a well-known solution rule for the class of linear production processes. Despite their stability properties, Owen allocations might give null payoff to players that are necessary for optimal production plans. This paper shows that, in general, the aforementioned drawback cannot be avoided allowing only allocations within the core of the cooperative game associated to the original linear production process, and therefore a new solution set named EOwen is introduced. For any player whose resources are needed in at least one optimal production plan, the EOwen set contains at least one allocation that assigns a strictly positive payoff to such player.     

On the spectral theory of trees with finite cone type

We study basic spectral features of graph Laplacians associated with a class of rooted trees which contains all regular trees. Trees in this class can be generated by substitution processes. Their spectra are shown to be purely absolutely continuous and to consist of finitely many bands. The main result gives stability of the absolutely continuous spectrum under sufficiently small radially label symmetric perturbations for non-regular trees in this class. In sharp contrast, the absolutely continuous spectrum can be completely destroyed by arbitrary small radially label symmetric perturbations for regular trees in this class.     

Completely mixed games and M-matrices

Any non-singular M-matrix is a completely mixed matrix game with positive value. We exploit this property to give game-theoretic proofs of several well-known characterizations of such matrices. The same methods yield also many theorems on S₀-irreducible matrices that are closely related to M-matrices.     

An affine model for the actions in an integrable system with monodromy

We give a standard model for the flat affine geometry defined by the local action variables of a completely integrable system. We are primarily interested in the affine structure in the neighborhood of a critical value with nontrivial monodromy.