A class of polynomial variable metric algorithms for linear optimization

In the paper, the behaviour of interior point algorithms is analyzed by using a variable metric method approach. A class of polynomial variable metric algorithms is given achieving O ((n/β)L) iterations for solving a canonical form linear optimization problem with respect to a wide class of Riemannian metrics, wheren is the number of dimensions and β a fixed value. It is shown that the vector fields of several interior point algorithms for linear optimization is the negative Riemannian gradient vector field of a linear a potential or a logarithmic barrier function for suitable Riemannian metrics. Research Partially supported by the Hungarian National Research Foundation, Grant Nos. OTKA-T016413 and OTKA-2116.     

Quasi-Newton ABS methods for solving nonlinear algebraic systems of equations

This paper is concerned with the solution of nonlinear algebraic systems of equations. For this problem, we suggest new methods, which are combinations of the nonlinear ABS methods and quasi-Newton methods. Extensive numerical experiments compare particular algorithms and show the efficiency of the proposed methods.The authors are grateful to Professors C. G. Broyden and E. Spedicato for many helpful discussions.     

Discrete groups of slow subgroup growth

It is known that the subgroup growth of finitely generated linear groups is either polynomial or at least $n^{\frac{{\log n}}{{\log \log n}}} $ . In this paper we prove the existence of a finitely generated group whose subgroup growth is of type $n^{\frac{{\log n}}{{(\log \log n)^2 }}} $ . This is the slowest non-polynomial subgroup growth obtained so far for finitely generated groups. The subgroup growth typen ^logn is also realized. The proofs involve analysis of the subgroup structure of finite alternating groups and finite simple groups in general. For example, we show there is an absolute constantc such that, ifT is any finite simple group, thenT has at mostn ^{c logn} subgroups of indexn.     

On a transformation of power series

Изучаются ряды Риман а, рассматривавшиеся ранее в работах [1] и [2]. Пустьa _n (n=1, 2,…) — последов ательность комплекс ных чисел иr _n =a _n +a _2n +…. Предполо жим, чтоΣ¦a _n ¦<∞. Тогда выпо лняются неравенства $$\begin{array}{*{20}c} {\sum\limits_n {\left| {r_n } \right| \leqq } \sum\limits_n {\left| {a_n } \right|} d(n),} & {\sum\limits_n {\left| {a_n } \right|} } \\ \end{array} \leqq \sum\limits_n {\left| {r_n } \right|2^{\omega (n)} ,} $$ гдеd(n) иω(n) — соответств енно число делителей и число простых делителейn. Е сли $$\begin{array}{*{20}c} {F(z) = \sum\limits_n {a_n z^n ,} } & {p_n (z) = \sum\limits_{s|n} {\mu \left( {\frac{n}{s}} \right)z^s ,} } \\ \end{array} $$ то \(F(z) = \sum\limits_n {r_n p_n (z)} \) для ¦z¦<1. В статье с одержатся некоторые результаты о сходимо сти рядов РиманаΣt _n p _n (z) на окружно сти ¦z¦=1. Например, если числаt _n неотрицатель ны, монотонно убывают и \(\sum\limits_n {t_n< \infty } \) , то ряд равн омерно сходится для ¦z¦=1. Сформулированы неко торые новые задачи.     

Aurifeuillian factorizations and the period of the Bell numbers modulo a prime

We show that the minimum period modulo of the Bell exponential integers is for all primes and several larger . Our proof of this result requires the prime factorization of these periods. For some primes the factoring is aided by an algebraic formula called an Aurifeuillian factorization. We explain how the coefficients of the factors in these formulas may be computed.

     

Towards the Hanna Neumann conjecture using Dicks' method

The Hanna Neumann conjecture states that the intersection of two nontrivial subgroups of rankk+1 andl+1 of a free group has rank at mostkl+1. In a recent paper [3] W. Dicks proved that a strengthened form of this conjecture is equivalent to his amalgamated graph conjecture. He used this equivalence to reprove all known upper bounds on the rank of the intersection. We use his method to improve these bounds. In particular we prove an upper bound of 2kl–k–l+1 for the rank of the intersection above (k,l2) improving the earlier 2kl-min(k, l) bound of [1].We prove a special case of the amalgamated graph conjecture in the hope that it may lead to a proof of the general case and thus of the strengthened Hanna Neumann conjecture.Oblatum 6-II-1995 & 19-VI-1995Supported by the NSF grants No. CCR-92-00788 CCR-95-03254 and the (Hungarian) National Scientific Research Fund (OTKA) grant No. F014919. The author was visiting the Computation and Automation Institute of the Hungarian Academy of Sciences while part of this research was done.     

Chapter 6 On the construction of strong complementarity slackness solutions for DEA linear programming problems using a primal-dual interior-point method

A novel approach for solving the DEA linear programming problems using a primaldual interior-point method is presented. The solution found by this method satisfies the Strong Complementarity Slackness Condition (SCSC) and maximizes the product of the positive components among all SCSC solutions. The first property is critical in the use of DEA and the second one contributes significantly to the reliability of the solution.This research was partially supported by NSF Cooperative Agreement No. CCR-88-09615, ARO Grant 9DAAL03-90-G-0093, DOE Grant DEFG05-86-ER25017, and AFOSR Grant 89-0363.Partially supported by Fulbright/LASPAU.     

Norm-graphs and bipartite turán numbers

For everyt>1 and positiven we construct explicit examples of graphsG with |V (G)|=n, |E(G)|c _t ·n ^2–1/t which do not contain a complete bipartite graghK _t,t !+1 This establishes the exact order of magnitude of the Turán numbers ex (n, K _t,s ) for any fixedt and allst!+1, improving over the previous probabilistic lower bounds for such pairs (t, s). The construction relies on elementary facts from commutative algebra.Research supported in part by NSF Grants DMS-8707320 and DMS-9102866.Research supported in part by Hungarian National Foundation for Scientific Research Grant