A potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”

This paper develops an algorithm for solving a standard-form linear program directly from an infeasible “warm start”, i.e., directly from a given infeasible solution \(\hat x\) that satisfies \(A\hat x = b\) but \(\hat x \ngeqslant 0\) . The algorithm is a potential function reduction algorithm, but the potential function is somewhat different than other interior-point method potential functions, and is given by $$F(x,B) = q\ln (c^T x - B) - \sum\limits_{j = 1}^n {\ln (x_j + h_j (c^T x - B))}$$ where \(q = n + \sqrt n\) is a given constant,h is a given strictly positive shift vector used to shift the nonnegativity constaints, andB is a lower bound on the optimal value of the linear program. The duality gapc ^T x ? B is used both in the leading term as well as in the barrier term to help shift the nonnegativity constraints. The algorithm is shown under suitable conditions to achieve a constant decrease in the potential function and so achieves a constant decrease in the duality gap (and hence also in the infeasibility) in O(n) iterations. Under more restrictive assumptions regarding the dual feasible region, this algorithm is modified by the addition of a dual barrier term, and will achieve a constant decrease in the duality gap (and in the infeasibility) in \(O(\sqrt n )\) iterations.     

Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time algorithms for linear programming. We first present an extension of Gonzaga's O(nL) iteration algorithm, that computes dual variables and does not assume a known optimal objective function value. This algorithm uses only affine scaling, and is based on computing the projected gradient of the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j )} $$ wherex is the vector of primal variables ands is the vector of dual slack variables, and q = n + \(\sqrt n \) . The algorithm takes either a primal step or recomputes dual variables at each iteration. We next present an alternate form of Ye's O( \(\sqrt n \) L) iteration algorithm, that is an extension of the first algorithm of the paper, but uses the potential function $$q\ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j ) - \sum\limits_{j - 1}^n {\ln (s_j )} } $$ where q = n + \(\sqrt n \) . We use this alternate form of Ye's algorithm to show that Ye's algorithm is optimal with respect to the choice of the parameterq in the following sense. Suppose thatq = n + n ^t wheret?0. Then the algorithm will solve the linear program in O(n ^r L) iterations, wherer = max{t, 1 ? t}. Thus the value oft that minimizes the complexity bound ist = 1/2, yielding Ye's O( \(\sqrt n \) L) iteration bound.     

Elementary abelian p-subgroups of algebraic groups

Let be an algebraically closed field and let G be a finite-dimensional algebraic group over which is nearly simple, i.e. the connected component of the identity G ⁰ is perfect, C _G(G ⁰)=Z(G ⁰) and G ⁰/Z(G ⁰) is simple. We classify maximal elementary abelian p-subgroups of G which consist of semisimple elements, i.e. for all primes p char .Call a group quasisimple if it is perfect and is simple modulo the center. Call a subset of an algebraic group toral if it is in a torus; otherwise nontoral. For several quasisimple algebraic groups and p=2, we define complexity, and give local criteria for whether an elementary abelian 2-subgroup of G is toral.For all primes, we analyze the nontoral examples, include a classification of all the maximal elementary abelian p-groups, many of the nonmaximal ones, discuss their normalizers and fusion (i.e. how conjugacy classes of the ambient algebraic group meet the subgroup). For some cases, we give a very detailed discussion, e.g. p=3 and G of type E ₆, E ₇ and E ₈. We explain how the presence of spin up and spin down elements influences the structure of projectively elementary abelian 2-groups in Spin(2n, ). Examples of an elementary abelian group which is nontoral in one algebraic group but toral in a larger one are noted.Two subsets of a maximal torus are conjugate in G iff they are conjugate in the normalizer of the torus; this observation, with our discussion of the nontoral cases, gives a detailed guide to the possibilities for the embedding of an elementary abelian p-group in G. To give an application of our methods, we study extraspecial p-groups in E ₈( ).Dedicated to Jacques Tits for his sixtieth birthday     

Interface interactions in modulated phases,and upsilon points

Certain features in Frenkel-Kontorova and other models of phases with a one-dimensional modulation can be analyzed by assuming parallel interfaces separating sets of lattice planes belonging to two different phases, and treating the free energy to create interfaces, as well as the interaction of two, three, or more interfaces, as phenomenological parameters. A strategy employed by Fisher and Szpilka for interacting defects can be extended to the case of interfaces, allowing a systematic study of the phase diagram by ignoring all interface interactions, and then successively taking into account pair, triple, and higher-order terms. The possible phase diagrams which can occur near the point where =0 include: various sorts of endpoints analogous to critical endpoints, an accumulation point of first-order transitions and triple points, and a self-similar structure which we call an upsilon point, which turns out to be an accumulation point of an infinite number of segments of first-order transition lines, each of which terminates in two upsilon points.     

Muonic x-ray intensity measurements on a highT c superconductor

Muonic x-ray spectra from the high-T _c superconductor YBa₂Cu₃O_6.95 have been measured in the superconducting and normal states. No significant differences were found between the two spectra when comparing the intensities of 27 lines.Dedicated to Prof. Dr. H. J. Mang on the occasion of his 60th birthday     

A partially observed control problem for Markov chains

A finite state, continuous time Markov chain is considered and the solution to the filtering problem given when the observation process counts the total number of jumps. The Zakai equation for the unnormalized conditional distribution is obtained and the control problem discussed in separated form with this as the state. A new feature is that, because of the correlation between the state and observation process, the control parameter appears in the diffusion coefficient which multiplies the Poisson noise in the Zakai equation. By introducing a Gâteaux derivative the minimum principle, satisfied by an optimal control, is derived. If the optimal control is Markov, a stochastic integrand can be obtained more explicitly and new forward and backward equations satisfied by the adjoint process are obtained.This research was partially supported by NSERC Grant A7964, the Air Force Office of Scientific Research, United States Air Force, under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-0102.     

Experiments in Solving Mixed Integer Programming Problems on a Small Array of Transputers

The time-consuming process of solving large-scale Mixed Integer Programming problems using the branch-and-bound technique can be speeded up by introducing a degree of parallelism into the basic algorithm. This paper describes the development and implementation of a parallel branch-and-bound algorithm created by adapting a commercial MIP solver. Inherent in the design of this software are certain ad hoc methods, the use of which are necessary in the effective solution of real problems. The extent to which these ad hoc methods can successfully be transferred to a parallel environment, in this case an array of at most nine transputers, is discussed. Computational results on a variety of real integer programming problems are reported.     

Harmonic maps with fixed singular sets

Suppose Ω is a smooth domain in R^m,N is a compact smooth Riemannian manifold, andZ is a fixed compact subset of Ω having finite (m − 3)-dimensional Minkowski content (e.g.,Z ism − 3 rectifiable). We consider various spaces of harmonic mapsu: Ω →N that have a singular setZ and controlled behavior nearZ. We study the structure of such spacesH and questions of existence, uniqueness, stability, and minimality under perturbation. In caseZ = 0,H is a Banach manifold locally diffeomorphic to a submanifold of the product of the boundary data space with a finite-dimensional space of Jacobi fields with controlled singular behavior. In this smooth case, the projection ofu εH tou |ϖΩ is Fredholm of index 0. R. H.’s research partially supported by the National Science Foundation.     

Correlations beyond the horizon

It is a fundamental feature of quantum field theory that correlations between observable quantities occur over all spacetime regions. In particular, in cosmological models with horizons, such correlations will be present in regions which lie outside of each other's horizon. Such correlations may play an important role in processes occurring in the early universe.This essay received the first award from the Gravity Research Foundation, 1992—Ed.     

Orthostructures from sesquilinear forms. A primer

We make a linkage with the ultimate generalization of Hilbert space, anR-module with an orthogonality relation, and certain constructs due to Foulis and Randall and other related structures suggested by Cattaneo, Franco, and Marino.