On simple bounds for eigenvalues of symmetric tridiagonal matrices

How much can be said about the location of the eigenvalues of a symmetric tridiagonal matrix just by looking at its diagonal entries? We use classical results on the eigenvalues of symmetric matrices to show that the diagonal entries are bounds for some of the eigenvalues regardless of the size of the off-diagonal entries. Numerical examples are given to illustrate that our arithmetic-free technique delivers useful information on the location of the eigenvalues.

Exercise sheet 5

Exercises and solutions in LaTex

Exercise sheet 5 pdf

Exercises and solutions in PDF

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented.

On the solution of the extended linear complementarity problem

The extended linear complementarity problem (XLCP) has been introduced in a recent paper by Mangasarian and Pang. In the present research, minimization problems with simple bounds associated to this problem are defined. When the XLCP is solvable, their solutions are global minimizers of the associated problems. Sufficient conditions that guarantee that stationary points of the associated problems are solutions of the XLCP will be proved. These theoretical results support the conjecture that local methods for box constrained optimization applied to the associated problems could be efficient tools for solving the XLCP. (C) 1998 Elsevier B.V. All rights reserved.

Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization

At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, in practice, one might not be able to solve the subproblem up to the required precision. This may be due to different reasons. One of them is that the presence of an excessively large penalty parameter could impair the performance of the box-constraint optimization solver. In this paper a practical strategy for decreasing the penalty parameter in situations like the one mentioned above is proposed. More generally, the different decisions that may be taken when, in practice, one is not able to solve the Augmented Lagrangian subproblem will be discussed. As a result, an improved Augmented Lagrangian method is presented, which takes into account numerical difficulties in a satisfactory way, preserving suitable convergence theory. Numerical experiments are presented involving all the CUTEr collection test problems.

A Review on Repeated Games and Reputations with Incomplete Information

In this project we review the effects of reputation within the context of game theory. This is done through a study of two key papers. First, we examine a paper from Fudenberg and Levine: Reputation and Equilibrium Selection in Games with a Patient Player (1989). We add to this a review Gossner’s Simple Bounds on the Value of a Reputation (2011). We look specifically at scenarios in which a long-run player faces a series of short-run opponents, and how the former may develop a reputation. In turn, we show how reputation leads directly to both lower and upper bounds on the long-run player’s payoffs.

A Review on Repeated Games and Reputations with Incomplete Information

In this project we review the effects of reputation within the context of game theory. This is done through a study of two key papers. First, we examine a paper from Fudenberg and Levine: Reputation and Equilibrium Selection in Games with a Patient Player (1989). We add to this a review Gossner’s Simple Bounds on the Value of a Reputation (2011). We look specifically at scenarios in which a long-run player faces a series of short-run opponents, and how the former may develop a reputation. In turn, we show how reputation leads directly to both lower and upper bounds on the long-run player’s payoffs.

Series representations of the remainders in the expansions for certain functions with applications

We present a summary of the series representations of the remainders in the expansions in ascending powers of t of 2/(et+1)2/(et+1) , sech t and coth t and establish simple bounds for these remainders when t>0t>0 . Several applications of these expansions are given which enable us to deduce some inequalities and completely monotonic functions associated with the ratio of two gamma functions. In addition, we derive a (presumably new) quadratic recurrence relation for the Bernoulli numbers Bn.

An Indirect Genetic Algorithm for a Nurse Scheduling Problem

This paper describes a Genetic Algorithms approach to a manpower-scheduling problem arising at a major UK hospital. Although Genetic Algorithms have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical Genetic Algorithms paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.

A new algorithm and refined bounds for extended gcd computation

Extended gcd computation is interesting itself. It also plays a fundamental role in other calculations. We present a new algorithm for solving the extended gcd problem. This algorithm has a particularly simple description and is practical. It also provides refined bounds on the size of the multipliers obtained.

Lower Bounds on the State Complexity of Geometric Goppa Codes

We reinterpret the state space dimension equations for geometric Goppa codes. An easy consequence is that if deg G less than or equal to n-2/2 or deg G greater than or equal to n-2/2 + 2g then the state complexity of C-L(D, G) is equal to the Wolf bound. For deg G is an element of [n-1/2, n-3/2 + 2g], we use Clifford's theorem to give a simple lower bound on the state complexity of C-L(D, G). We then derive two further lower bounds on the state space dimensions of C-L(D, G) in terms of the gonality sequence of F/F-q. (The gonality sequence is known for many of the function fields of interest for defining geometric Goppa codes.) One of the gonality bounds uses previous results on the generalised weight hierarchy of C-L(D, G) and one follows in a straightforward way from first principles; often they are equal. For Hermitian codes both gonality bounds are equal to the DLP lower bound on state space dimensions. We conclude by using these results to calculate the DLP lower bound on state complexity for Hermitian codes.

Metastability bounds on the two Higgs doublet model

In the two Higgs doublet model, there is the possibility that the vacuum where the universe resides in is metastable. We present the tree-level bounds on the scalar potential parameters which have to be obeyed to prevent that situation. Analytical expressions for those bounds are shown for the most used potential, that with a softly broken Z(2) symmetry. The impact of those bounds on the model's phenomenology is discussed in detail, as well as the importance of the current LHC results in determining whether the vacuum we live in is or is not stable. We demonstrate how the vacuum stability bounds can be obtained for the most generic CP-conserving potential, and provide a simple method to implement them.

Exact tests for correlation and for the slope in simple linear regressions without making assumptions

We present an exact test for whether two random variables that have known bounds on their support are negatively correlated. The alternative hypothesis is that they are not negatively correlated. No assumptions are made on the underlying distributions. We show by example that the Spearman rank correlation test as the competing exact test of correlation in nonparametric settings rests on an additional assumption on the data generating process without which it is not valid as a test for correlation.We then show how to test for the significance of the slope in a linear regression analysis that invovles a single independent variable and where outcomes of the dependent variable belong to a known bounded set.

Exact lower bounds to the ground-state energy of spin systems: The two-dimensional S=1/2 antiferromagnetic Heisenberg model

We present a very simple but fairly unknown method to obtain exact lower bounds to the ground-state energy of any Hamiltonian that can be partitioned into a sum of sub-Hamiltonians. The technique is applied, in particular, to the two-dimensional spin-1/2 antiferromagnetic Heisenberg model. Reasonably good results are easily obtained and the extension of the method to other systems is straightforward.