Rate of convergence of the generalized newton algorithm using the fixed-point approach

This paper shows that the generalized Newton algorithm [GN(r)], developed by Kalaba and Tishler (Ref. 1), can be described as a fixed-point algorithm. In addition to specifying sufficient conditions for convergence of the GN(r), we show that, forr=1, 2, 3, its rate of convergence increases with the order of the derivatives which are used.The authors are indebted to I. Zang for drawing their attention to an error in an earlier draft of this paper. Suggestions and comments by N. Levin and D. Trietsch are also gratefully acknowledged.     

On the use of the table method in constrained optimization

In this paper, we take advantage of the availability of higher-order derivatives through the table method (see Ref. 1) and suggest a simple variant of the Lagrangian method for constrained optimization. Our method, and the software that we currently have can be used to minimize functions with many variables subject to an arbitrary number of constraints.On leave from the Faculty of Management, Tel Aviv University, Tel Aviv, Israel.     

Book Notices

Finding Pareto-minimum vectors among r given vectors, each of dimension m, is a fundamental problem in multiobjective optimization problems or multiple-criteria decision-making problems. Corley and Moon (Ref. 1) have given an algorithm for finding all the Pareto-minimum paths of a multiobjective network optimization problem from the initial node to any other node. It uses another algorithm by Corley and Moon, which actually computes the Pareto-minimum vectors. We observed that the latter algorithm is incorrect. In this note, we correct the algorithm for computing Pareto-minimum vectors and present a modified algorithm.     

PAC fields over finitely generated fields

We prove the following theorem for a finitely generated field K: Let M be a Galois extension of K which is not separably closed. Then M is not PAC over K. Research supported by the Minkowski Center for Geometry at Tel Aviv University, established by the Minerva Foundation. This work constitutes a part of the Ph.D. dissertation of L. Bary-Soroker done at Tel Aviv University under the supervision of Prof. Dan Haran.     

Extremely noncommutative elements in rings

We study rings and K-algebras in which all elements or all noncentral elements have smallest possible centralizer. Our principal result asserts that a ring R must be either finite or commutative if each noncentral element a has centralizer equal to the subring generated by a. Supported by the Natural Sciences and Engineering Research Council of Canada, Grant 3961. Authors’ addresses: Howard E. Bell, Department of Mathematics, Brock University, St. Catharines, Ontario, Canada L2S 3A1; Abraham A. Klein, Sackler Faculty of Exact Sciences, School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel     

Covering numbers for Chevalley groups

LetG be a quasisimple Chevalley group. We give an upper bound for the covering number cn(G) which is linear in the rank ofG, i.e. we give a constantd such that for every noncentral conjugacy classC ofG we haveC ^rd =G, wherer=rankG. Research supported in part by NSERC Canada Grant A7251. Research supported in part by the Hermann Minkowski-Minerva Center for Geometry at Tel Aviv University.     

A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

We describe a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs. The existence of such an algorithm was conjectured in G. Gutin, Paths and cycles in digraphs. Ph. D. thesis, Tel Aviv Univ., 1993. (see also G. Gutin, J Graph Theory 19 (1995) 481–505). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 111–132, 1998     

The potential of greed for independence

The well‐known lower bound on the independence number of a graph due to Caro (Technical Report, Tel‐Aviv University, 1979) and Wei (Technical Memorandum, TM 81 ‐ 11217 ‐ 9, Bell Laboratories, 1981) can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so‐called potential functions p_G: V(G)→?₀ defined on the vertex set of a graph G for which suitably modified versions of the greedy algorithms applied to G yield independent sets I with . We provide examples of such potentials, which lead to bounds improving the bound due to Caro and Wei. Furthermore, suitably adapting the randomized algorithm we give a short proof of Thiele's lower bound on the independence number of a hypergraph (T. Thiele, J Graph Theory 30 (1999), 213–221).     

On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ ^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ ^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed. Work by V. Koltun was supported by NSF CAREER award CCF-0641402. Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Vertical decomposition of arrangements of hyperplanes in four dimensions

We show that, for any collection ℋ ofn hyperplanes in ℜ⁴, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n ⁴ logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning them. Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University.     

Efficient Algorithms for Maximum Regression Depth

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n ^d ) time and O(n ^d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog ² n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results. A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry (1999) M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number 642.065.503. J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology, and Sun Microsystems. M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, by grants from the U.S.–Israeli Binational Science Foundation, the G.I.F., the German–Israeli Foundation for Scientific Research and Development, and the ESPRIT IV LTR project No. 21957 (CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University. J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia.     

A generalized Newton algorithm using higher-order derivatives

This paper presents a general optimization algorithm using first-order torth order derivatives to find the optimum of anr-continuously differentiable function of many variables. This algorithm collapses to the Newton-Raphson algorithm when only first- and second-order derivatives are used. The computation of the required higher-order derivatives are readily available through thetable algorithm. The generalized CES production function is used as an example.     

The Iyengar inequality,revisited

Detailed analysis shows that the famous Iyengar inequality actually says that the Trapezoidal formula is a central algorithm for approximating integrals over an appropriate interval for the class of functions whose derivatives are bounded by a positive number K in L _∞-sense. The inherent nonlinearity from central algorithms reflects the importance of the Iyengar inequality and thus makes familiar linear methods malfunction when one tries to generalize it. It is shown that the generalization depends on a nonlinear system of equations satisfied by a set of free nodes of a perfect spline. Explicit constructions are obtained in the spirit of the Iyengar inequality for the class of functions whose rth (r≤4) derivatives are bounded by a positive number K in L _∞-sense because a closed solution to the nonlinear system is only available for r≤4. Connections with computational mathematics, especially with best interpolation and best quadrature, are discussed. Numerical experiments are also included. AMS subject classification (2000)  65D30, 41A17     

On the exponential temporal decay of solutions and their derivatives for quasilinear parabolic equations

A nonlinear model for temperature evolution in a one-dimensional rod is considered. Integral and uniform pointwise temporal exponential decay estimates for the solution and its derivatives are obtained. A method is demonstrated for derivatives up to the third order but seems to apply for derivatives of any order as well.The results in this paper represent a partial fulfillment of the requirements for the degree of Doctor of Philosophy at Tel Aviv University by Yevgeni Shenker under the guidance of Joseph J. Roseman.     

Projection operators and states in the tensor product of quaternion hilbert modules

Following the construction of tensor product spaces of quaternion Hilbert modules in our previous paper, we define the analogue of a ray (in a complex quantum mechanics) and the corresponding projection operator, and through these the notion of a state and density operators. We find that there is a one-to-one correspondence between a state and an equivalence class of vectors from the tensor product space, which gives us another method to define the gauge transformations.On sabbatical leave from the School of Physics and Astronomy, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel. Work supported in part by a fellowship from the Ambrose Monell Foundation.     

A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization

In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪(r^5/4log ?^?1) for the Nesterov-Todd direction, and 𝒪(r^7/4log ?^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ? is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r^3/4. Some preliminary numerical results are provided as well.     

A counterexample on extreme operators

We give examples of extreme operators in the unit ball ofL(C(X),C(Y)) which are not nice operators (i.e., their adjoints do not carry extreme points into extreme points in the corresponding unit balls.) Such counterexamples exist in fact for every non-dispersed compact Hausdorff spaceX when the scalars are complex. This is part of the author’s Ph.D. thesis, prepared at Tel Aviv University under the supervision of Prof. A. J. Lazar.     

Topological Graphs with No Large Grids

Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants k,l, there exists another constant C(k,l), such that if G has at least C(k,l)n edges, then it contains a k×l-gridlike configuration, that is, it contains k+l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex. Received: April, 2003 Janos Pach and Micha Sharir has been supported by NSF Grants CCR-97-32101 and CCR-00-98246, and by a joint grant from the U.S.–Israel Binational Science Foundation. János Pach has also been supported by PSC-CUNY Research Award 63382-0032 and by OTKA T-032452. Micha Sharir has also been supported by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Géza Tóth has been supported by OTKA-T-038397 and by an award from the New York University Research Challenge Fund.     

Tensor product of quaternion hilbert modules

One of the main problems in the theory of quaternion quantum mechanics has been the construction of a tensor product of quaternion Hilbert modules. A solution to this problem is given by studying the tensor product of quaternion algebras (over the reals) and some of its quotient modules. Real, complex, and (covariant) quaternion scalar products are found in the tensor product spaces. Annihilationcreation operators are constructed, corresponding to the second quantization of the quaternion quantum theory with Bose-Einstein or Fermi-Dirac statistics. The gauge transformations of a tensor product vector and the gauge fields are studied.On Sabbatical leave from the School of Physics and Astronomy, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel. Work supported in part by a fellowship from the Ambrose Monell Foundation.     

On An Extremal Hypergraph Problem Of Brown, Erdős And Sós

Let f_r(n,v,e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi and of Erdős, Frankl and R?dl, we partially resolve a problem raised by Brown, Erdős and Sós in 1973, by showing that for any fixed 2≤k<r, we have