Fast convergence of the simplified largest step path following algorithm

Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation ofp Newton steps: the first of these steps is exact, and the other are called “simplified”. In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems. The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-orderp+1 in the number of master iterations, and with a complexity of iterations. Corresponding author. Research done while visiting the Delft Technical University, and supported in part by CAPES — Brazil.     

Approximation of multivariate distribution functions

In the paper the unknown distribution function is approximated with a known distribution function by means of Taylor expansion. For this approximation a new matrix operation — matrix integral — is introduced and studied in [PIHLAK, M.: Matrix integral, Linear Algebra Appl. 388 (2004), 315–325]. The approximation is applied in the bivariate case when the unknown distribution function is approximated with normal distribution function. An example on simulated data is also given.      

Calculations in conformal theory needed for verifying the Alday—Gaiotto—Tachikawa hypothesis

Explicitly verifying the Alday—Gaiotto—Tachikawa (AGT) relation between the conformal blocks controlled by the WN symmetry and U(N) Nekrasov functions requires knowing the Shapovalov matrix and various triple correlators for W-algebra descendants. We collect the simplest expressions of this type for N = 3 and for the two lowest descendant levels together with the detailed derivations, which can now be computerized and used in more general studies of conformal blocks and AGT relations at higher levels.     

Unitary integrals and related matrix models

We briefly review the basic properties of unitary matrix integrals, using three matrix models to analyze their properties: the ordinary unitary, the Brezin—Gross—Witten, and the Harish—Chandra—Itzykson—Zuber models. We especially emphasize the nontrivial aspects of the theory, from the De Witt’Hooft anomaly in unitary integrals to the problem of calculating correlators with the Itzykson-Zuber measure. We emphasize the method of character expansions as a technical tool. Unitary integrals are still insufficiently investigated, and many new results should be expected as this field attracts increased attention.     

Convergence of LR algorithm for a one-point spectrum tridiagonal matrix

We prove convergence for the basic LR algorithm on a real unreduced tridiagonal matrix with a one-point spectrum—the Jordan form is one big Jordan block. First we develop properties of eigenvector matrices. We also show how to deal with the singular case.     

On the covering of syntax-directed translations for context-free grammars

A necessary and sufficient set of conditions is obtained that relates any two context-free grammarsG ₁ andG ₂ with the property that wheneverG ₂ left—or right—coversG ₁, the syntax-directed translations (SDT’s) with underlying grammarG ₁ is a subset of those with underlying grammarG ₂. Also the case thatG ₂ left—or right—coversG ₁ but the SDT’s with underlying grammarG ₁ is not a subset of the SDT’s with underlying grammarG ₂ is considered; in this case an algorithm is described to obtain the syntax-directed translation schema (SDTS) with underlying grammarG ₂ to the given SDTS with underlying grammarG ₁, if it exists.     

A Variant of the Topkis—Veinott Method for Solving Inequality Constrained Optimization Problems

In this paper we give a variant of the Topkis—Veinott method for solving inequality constrained optimization problems. This method uses a linearly constrained positive semidefinite quadratic problem to generate a feasible descent direction at each iteration. Under mild assumptions, the algorithm is shown to be globally convergent in the sense that every accumulation point of the sequence generated by the algorithm is a Fritz—John point of the problem. We introduce a Fritz—John (FJ) function, an FJ1 strong second-order sufficiency condition (FJ1-SSOSC), and an FJ2 strong second-order sufficiency condition (FJ2-SSOSC), and then show, without any constraint qualification (CQ), that (i) if an FJ point z satisfies the FJ1-SSOSC, then there exists a neighborhood N(z) of z such that, for any FJ point y ∈ N(z) \ {z } , f ₀ (y) ≠ f ₀ (z) , where f ₀ is the objective function of the problem; (ii) if an FJ point z satisfies the FJ2-SSOSC, then z is a strict local minimum of the problem. The result (i) implies that the entire iteration point sequence generated by the method converges to an FJ point. We also show that if the parameters are chosen large enough, a unit step length can be accepted by the proposed algorithm. Accepted 21 September 1998     

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.     

On the concentration of eigenvalues of random symmetric matrices

It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e ⁻ t ²32 ^s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces. Research supported in part by a USA — Israel BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a USA — Israel BSF grant and by a Bergmann Memorial Grant.     

The Borel—Bernstein Theorem for multidimensional continued fractions

A central result in the metric theory of continued fractions, the Borel—Bernstein Theorem gives statistical information on the rate of increase of the partial quotients. We introduce a geometrical interpretation of the continued fraction algorithm; then, using this set-up, we generalize it to higher dimensions. In this manner, we can define known multidimensional algorithms such as Jacobi—Perron, Poincaré, Brun, Rauzy induction process for interval exchange transformations, etc. For the standard continued fractions, partial quotients become return times in the geometrical approach. The same definition holds for the multidimensional case. We prove that the Borel—Bernstein Theorem holds for recurrent multidimensional continued fraction algorithms. Supported by a grant from the CNP _q -Brazil, 301456/80, and FINEP/CNP _q /MCT 41.96.0923.00 (PRONEX).     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

An inexact-restoration method for nonlinear bilevel programming problems

We present a new algorithm for solving bilevel programming problems without reformulating them as single-level nonlinear programming problems. This strategy allows one to take profit of the structure of the lower level optimization problems without using non-differentiable methods. The algorithm is based on the inexact-restoration technique. Under some assumptions on the problem we prove global convergence to feasible points that satisfy the approximate gradient projection (AGP) optimality condition. Computational experiments are presented that encourage the use of this method for general bilevel problems. This work was supported by PRONEX-Optimization (PRONEX—CNPq/FAPERJ E-26/171.164/2003—APQ1), FAPESP (Grants 06/53768-0 and 05-56773-1) and CNPq.     

A note on slant submanifolds of nearly trans-Sasakian manifolds

The geometry of slant submanifolds of a nearly trans-Sasakian manifold is studied when the tensor field Q is parallel. It is proved that Q is not parallel on the submanifold unless it is anti-invariant and thus the result of [CABRERIZO, J. L.—CARRIAZO, A.—FERNANDEZ, L. M.—FERNANDEZ, M.: Slant submanifolds in Sasakian manifolds, Glasg. Math. J. 42 (2000), 125–138] and [GUPTA, R. S.—KHURSHEED HAIDER, S. M.—SHARFUDIN, A.: Slant submanifolds of a trans-Sasakian manifold, Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 47 (2004), 45–57] are generalized.     

Subclasses of generalized inverses of matrices

Summary Structure of allg-inverses of a matrix in a weak sense is shown. Characterizations of main subclasses ofg-inverses are investigated thoroughly. The dualities among subclasses and the relation betweeng-inverses and projections are stressed. The Gauss-Markov theorem reduces to a duality of two types ofg-inverses A preliminary Japanese version was published by the author in theProc. Inst. Statist. Math., Vol. 17, (1969) with the title “Generalized inverses of matrices—Part 1”.     

Closed-form solution of a maximization problem

According to the characterization of eigenvalues of a real symmetric matrix A, the largest eigenvalue is given by the maximum of the quadratic form 〈xA, x〉 over the unit sphere; the second largest eigenvalue of A is given by the maximum of this same quadratic form over the subset of the unit sphere consisting of vectors orthogonal to an eigenvector associated with the largest eigenvalue, etc. In this study, we weaken the conditions of orthogonality by permitting the vectors to have a common inner product r where 0 ≤ r < 1. This leads to the formulation of what appears—from the mathematical programming standpoint—to be a challenging problem: the maximization of a convex objective function subject to nonlinear equality constraints. A key feature of this paper is that we obtain a closed-form solution of the problem, which may prove useful in testing global optimization software. Computational experiments were carried out with a number of solvers. We dedicate this paper to the memory of our great friend and colleague, Gene H. Golub.     

Relaxation techniques for strictly convex network problems

Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments —aimed at the improved efficiency of the algorithm — are presented. This research was supported in part by National Science Foundation Grant No. DCR-8401098-A0l.     

An efficient algorithm for the generalized centro-symmetric solution of matrix equation <Emphasis Type="Italic">A X B</Emphasis> = <Emphasis Type="Italic">C</Emphasis>

In this paper, an iterative algorithm is constructed for solving linear matrix equation AXB = C over generalized centro-symmetric matrix X. We show that, by this algorithm, a solution or the least-norm solution of the matrix equation AXB = C can be obtained within finite iteration steps in the absence of roundoff errors; we also obtain the optimal approximation solution to a given matrix X ₀ in the solution set of which. In addition, given numerical examples show that the iterative method is efficient.     

Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

Improved Self-Stabilizing Algorithms for L(2, 1)-Labeling Tree Networks

The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In a previous paper—presented at the 23rd IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, Innsbruck, Austria—we presented, to the best of our knowledge, the first self-stabilizing algorithm which {Δ +  2}-L(2, 1)-labels rooted trees. That algorithm was shown to require an exponential number of moves to stabilize on a global solution (which is not uncommon in self-stabilizing systems). In this paper, we present two self-stabilizing algorithms which {Δ +  2}-L(2, 1)-label a given rooted tree T in only O(nh) moves (where h is the height and n is the number of nodes in the tree T) under a central scheduler. We also show how the algorithms may be adapted to unrooted trees, dynamic topology changes, and consider the correctness of the protocols under the distributed scheduler model.     

Coxian representations of generalized Erlang distributions

This paper studies Coxian representations of generalized Erlang distributions. A nonlinear program is derived for computing the parameters of minimal Coxian representations of generalized Erlang distributions. The nonlinear program is also used to characterize the triangular order and the admissible region of generalized Erlang distributions. It is shown that the admissible region associated with a triangular order may not be convex. For generalized Erlang distributions of ME-order 3, a minimal Coxian representation is found explicitly. In addition, an algorithm is developed for computing a special type of ordered Coxian representations - the bivariate Coxian representation - for generalized Erlang distributions.