Polynomiality of infeasible-interior-point algorithms for linear programming

Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm solves the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.The original title was Polynomiality of the Kojima—Megiddo—Mizuno infeasible-interior-point algorithm for linear programming.Research performed while visiting Cornell University (April 1992 – January 1993) as an Overseas Research Scholar of the Ministry of Science, Education and Culture of Japan.     

A primal—dual infeasible-interior-point algorithm for linear programming

As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.Part of this research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contract N00014-91-C-0026 is acknowledged.Supported by Grant-in-Aids for Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Encouragement of Young Scientist (03740125) and Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.     

Scalar Products of Symmetric Functions and Matrix Integrals

We present relations between Hirota-type bilinear operators, scalar products on spaces of symmetric functions, and integrals defining matrix-model partition functions. Using the fermionic Fock space representation, we prove an expansion of an associated class of KP and 2-Toda tau functions _r,n in a series of Schur functions generalizing the hypergeometric series and relate it to the scalar product formulas. We show how special cases of such tau functions can be identified as formal series for partition functions. A closed form expansion of log _r,n in terms of Schur functions is derived.     

Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. In this paper we give partial answers — affirmative and negative ones — to the general problem of determining if, for a function f mapping every end of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

Clean triangulations

A polyhedron on a surface is called a clean triangulation if each face is a triangle and each triangle is a face. LetS _p (resp.N _p ) be the closed orientable (resp. nonorlentable) surface of genusp. If (S) is the smallest possible number of triangles in a clean triangulation ofS, the results are: (N ₁)=20, (S ₁)=24, lim(S _p )p ^–1=4, lim(N _p )p ^–1=2 forp.     

On exact D-optimal designs for regression models with correlated observations

Let ^* be an exact D-optimal design for a given regression model Y = X + Z . In this paper sufficient conditions are given for sesigning how the covariance matrix of Z may be changed so that not only ^* remains D-optimal but also that the best linear unbiased estimator (BLUE) of stays fixed for the design ^*, although the covariance matrix of Z * is changed. Hence under these conditions a best, according to D-optimality, BLUE of is known for the model with the changed covariance matrix. The results may also be considered as determination of exact D-optimal designs for regression models with special correlated observations where the covariance matrices are not fully known. Various examples are given, especially for regression with intercept term, polynomial regression, and straight-line regression. A real example in electrocardiography is treated shortly.     

Birth times,death times and time substitutions in Markov chains

Summary Given a Markov chain (X _n ) _n0, random times are studied which are birth times or death times in the sense that the post- and pre- processes are independent given the present (X _–1, X ) at time and the conditional post- process (birth times) or the conditional pre- process (death times) is again Markovian. The main result for birth times characterizes all time substitutions through homogeneous random sets with the property that all points in the set are birth times. The main result for death times is the dual of this and appears as the birth time theorem with the direction of time reversed.Part of this work was done while the author was visiting the Department of Mathematics, University of California at San DiegoThe support of The Danish Natural Science Research Council is gratefully acknowledged     

Hypercubic 4 and 5-Designs from Double-Error-Correcting BCH Codes

An ordered orthogonal array OOA(, k, n) is a binary 2 ^k × n matrix with the property that for each complete -set of columns, each possible -tuple occurs in exactly 2 ^k– rows of those columns (for definition of a complete -set, see below). Constructions of OOA(, k, n) for = 4 and = 5 are given.     

Generalized Tjurina numbers of an isolated complete intersection singularity

We define a series of non-negative integer valued invariants the generalized Tjurina numbers, of an analytic n-dimensional isolated complete intersection singularity. The Tjurina number equals ⁽¹⁾. We show that all these numbers are bounded by the Milnor number by establishing explicit formulas for the differences –^(p) involving the mixed Hodge numbers of the cohomology of the link and a new range of analytic invariants for (X,x). This generalizes earlier results of Looijenga and Steenbrink on the relation between the Milnor number and the Tjurina number. We show that singularities satisfying =⁽¹⁾==^(n–1) behave cohomologically like weighted homogeneous singularities, and we expect this to be a criterion for weighted homogeneity.Mathematics Subject Classification (2000): 32S10, 32S35, 32C36, 14E15The author gratefully acknowledges financial support from Carlsbergfondet.     

The asymptotic stability of one-parameter methods for neutral differential equations

This paper deals with the asymptotic stability of theoretical solutions and numerical methods for systems of neutral differential equationsx=Ax(t–)+Bx(t)+Cx(t–), whereA, B, andC are constant complexN ×N matrices, and >0. A necessary and sufficient condition such that the differential equations are asymptotically stable is derived. We also focus on the numerical stability properties of adaptations of one-parameter methods. Further, we investigate carefully the characterization of the stability region.     

Frobenius-Perron operators and approximation of invariant measures for set-valued dynamical systems

A set-valued dynamical systemF on a Borel spaceX induces a set-valued operatorF onM(X) — the set of probability measures onX. We define arepresentation ofF, each of which induces an explicitly defined selection ofF; and use this to extend the notions of invariant measure and Frobenius-Perron operators to set-valued maps. We also extend a method ofS. Ulam to Markov finite approximations of invariant measures to the set-valued case and show how this leads to the approximation ofT-invariant measures for transformations , whereT corresponds to the closure of the graph of .     

Existence theorems for optimal control problems involving functional differential equations

This paper extends some existence theorems of Cesari for optimal control problems to systems whose dynamics is described by functional differential equations of finitely-retarded type. We show that the proper choice of state space is the spaceE ¹×C[–, 0], where >0 represents the time-lag of the system, and that it is necessary to choose initial conditions from a compact set inC[–, 0] as well as to employ the usual growth condition.This research was accomplished in the frame of research project AFOSR-942-65 at the University of Michigan. In particular, the author would like to thank Professor L. Cesari (University of Michigan) and Professor N. Chafee (Brown University) for many helpful remarks during the preparation of the research, which forms part of the author's doctoral dissertation written at the University of Michigan.     

Stochastic Methods for Ill-Posed Problems

This paper is devoted to the numerical analysis of ill-posed problems of evolution equations in Banach spaces using certain classes of stochastic one-step methods. The linear stability properties of these methods are studied. Regularisation is given by the choice of the regularisation parameter as = , where _n is the stepsize and provides the convergence on smooth initial data. The case of the approximation of well-posed problems is also considered.     

Finite Extensions of Topogenities

Let X = Y Z, Y Z = Ø, < be a topogenity on Y, a topology on X. A (<, )-extension is a topogenity < on X such that < ¦Y = <, (<) = . We establish some properties of (<, )-extensions and construct all of them in the case of a finite Z.     

On the Contractivity and Asymptotic Stability of Systems of Delay Differential Equations of Neutral Type

In this paper we investigate both the contractivity and the asymptotic stability of the solutions of linear systems of delay differential equations of neutral type (NDDEs) of the form y(t) = Ly(t) + M(t)y(t – (t)) + N(t)y(t – (t)). Asymptotic stability properties of numerical methods applied to NDDEs have been recently studied by numerous authors. In particular, most of the obtained results refer to the constant coefficient version of the previous system and are based on algebraic analysis of the associated characteristic polynomials. In this work, instead, we play on the contractivity properties of the solutions and determine sufficient conditions for the asymptotic stability of the zero solution by considering a suitable reformulation of the given system. Furthermore, a class of numerical methods preserving the above-mentioned stability properties is also presented.     

A globally convergent primal—dual interior point algorithm for convex programming

In this paper, we study the global convergence of a large class of primal—dual interior point algorithms for solving the linearly constrained convex programming problem. The algorithms in this class decrease the value of a primal—dual potential function and hence belong to the class of so-called potential reduction algorithms. An inexact line search based on Armijo stepsize rule is used to compute the stepsize. The directions used by the algorithms are the same as the ones used in primal—dual path following and potential reduction algorithms and a very mild condition on the choice of the centering parameter is assumed. The algorithms always keep primal and dual feasibility and, in contrast to the polynomial potential reduction algorithms, they do not need to drive the value of the potential function towards — in order to converge. One of the techniques used in the convergence analysis of these algorithms has its root in nonlinear unconstrained optimization theory.Research supported in part by NSF Grant DDM-9109404.     

Theoretical convergence of large-step primal—dual interior point algorithms for linear programming

This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. Theoretically, Rule G ensures the global convergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iteration polynomial-time computational complexity. Both rules depend only on the lengths of the steps from the current iterates in the primal and dual spaces to the respective boundaries of the primal and dual feasible regions. They rely neither on neighborhoods of the central trajectory nor on potential function. These rules allow large steps without performing any line search. Rule G is especially flexible enough for implementation in practically efficient primal—dual interior point algorithms.Part of the research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contracts N00014-87-C-0820 and N00014-91-C-0026 is acknowledged.     

An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd ^k andv ^k rather than a primal—dual interior point (x ^k ,s ^k ), where and fori = 1, 2,,n. Only one element ofd ^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx ^k ands ^k are not needed explicitly in the algorithm, whereasd ^k andv ^k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x ^k, s^k) and (d ^k, v^k) with improving primal—dual potential function values. Moreover, no approximation ofd ^k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Das Zeitverhalten von einfachen offenen exponentiellen Warteschlangensystemen mit unendlich vielen Warteplätzen

Zusammenfassung Die zeitabhängige (instationäre) Lösung für die Zustandswahrscheinlichkeiten und für einige Kenngrößen von Warteschlangensystemen mit einer Bedienungsstation, unendlich vielen Warteplätzen, exponentiellem Zu- und Abgang und beliebigem Anfangszustand wird bestimmt. Die ZustandswahrscheinlichkeitenP _v (), d. h. die Wahrscheinlichkeiten für Einheiten im System zur Zeit, ergeben sich als Integrale, in denen modifizierteSessel-Funktionen 1. Art auftreten. Der ErwartungswertL () und die VarianzV() der Zahl von Einheiten im System lassen sich als Integrale darstellen, in denen nur die ZustandswahrscheinlichkeitP ₀() auftritt.Für<1 und erreichen die Systeme einen stationären Zustand (für den die Lösung bekannt ist); für1 und giltP _v ()0 für alle, L(),V().Ist>1, dann wachsenL() undV() für große linear mit; ihre Asymptoten werden berechnet. Ist=1, dann wachsenL() und die Standardabweichung() für große mit ; einfache Näherungsformeln werden gefunden.

---

Summary The time dependent solution is determined for the state probabilities and for some characteristic values of queuing systems with a single server, an infinite number of waiting places, exponentially distributed inter-arrival and service times, and any initial state. The state probabilitiesP _v (), i.e. the probabilities for units in the system at time, are given in the form of integrals in which modifiedBessel functions of the first kind occur. Integrating the state probalityP ₀() over leads to the meanL() and the varianceV() of the number of units in the system.For<1 and the systems tend to a steady state (for which the solution is known); for1 and we haveP _v ()0 for all, L(),V().If>1 asymptotic expansions for large are found givingL() andV() proportional to. If=1 simple approximate formulas for large are obtained givingL() and the standard deviation() proportional to .

---

---

Vorgel. v.:J. Nitsche.     

Global and Superlinear Convergence of a Restricted Class of Self-Scaling Methods with Inexact Line Searches, for Convex Functions

This paper studies the convergence properties of algorithms belonging to the class of self-scaling (SS) quasi-Newton methods for unconstrained optimization. This class depends on two parameters, say _k and _k , for which the choice _k =1 gives the Broyden family of unscaled methods, where _k =1 corresponds to the well known DFP method. We propose simple conditions on these parameters that give rise to global convergence with inexact line searches, for convex objective functions. The q-superlinear convergence is achieved if further restrictions on the scaling parameter are introduced. These convergence results are an extension of the known results for the unscaled methods. Because the scaling parameter is heavily restricted, we consider a subclass of SS methods which satisfies the required conditions. Although convergence for the unscaled methods with _k 1 is still an open question, we show that the global and superlinear convergence for SS methods is possible and present, in particular, a new SS-DFP method.