Convergence of Bieberbach polynomials in domains with interior cusps

We extend the results on the uniform convergence of Bieberbach polynomials for domains with certain interior zero angles (outward pointing cusps) and show that they play a special role in the problem. Namely, we construct a Keldysh-type example on the divergence of Bieberbach polynomials at an outward pointing cusp and discuss thecritical order of tangency at this interior zero angle, separating the convergent behavior of Bieberbach polynomials from the divergent one for sufficiently thin cusps. Research of both authors was supported in part by the National Science Foundation grant DMS-9707359. Research of the second author was also supported in part by the National Science Foundation grant DMS-9970659.     

On critical orientations in the kedem-sharir motion planning algorithm

We discuss a technical problem arising in the motion planning algorithm of Kedem and Sharir [KS], and propose a way to overcome it without increasing the asymptotic complexity of the algorithm The first author was supported by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The second author was partly supported by the Fund for Basic Research administered by the Israeli Academy of Sciences, by National Science Foundation Grants CCR-91-22103 and CCR-93-11127, and by grants from the U.S.-Israeli Binational Science Foundation, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. The third author was partly supported by the Interdisciplinary Program at Tel-Aviv University. The third author’s current address is: Department of Computer Science, MIT, Boston, MA, USA.     

A complementarity approach to a quasistatic multi-rigid-body contact problem

In this paper, we study the problem of predicting the quasistatic planar motion of a passive rigid body in frictional contact with a set of active rigid bodies. The active bodies can be thought of as the links of a mechanism or robot manipulator whose positions can be actively controlled by actuators. The passive body can be viewed as a grasped object, which moves only in response to contact forces and other external forces such as those due to gravity. We formulate this problem as a certain uncoupled complementarity problem, and show that it belongs to the class of NP-complete problems. Finally, numerical results of our proposed linear programming-based solution algorithm for this class of problems are presented and compared to the only other currently available solution algorithm.The research of this author was based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739.The research of this author was partially supported by the National Science Foundation under grant IRI-9304734, the Texas Advanced Technology Program under grant 999903-095, and the Texas Advanced Research Program under grant 999903-078.     

Computing the link center of a simple polygon

The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n ²), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author has been supported by the Canadian National Science and Engineering Research Council, Grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author has been supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgments can be obtained from the tenth author upon request.     

Nonobtuse Tetrahedral Partitions that Refine Locally Towards Fichera-Like Corners

Linear tetrahedral finite elements whose dihedral angles are all nonobtuse guarantee the validity of the discrete maximum principle for a wide class of second order elliptic and parabolic problems. In this paper we present an algorithm which generates nonobtuse face-to-face tetrahedral partitions that refine locally towards a given Fichera-like corner of a particular polyhedral domain. The first author was supported by the Swedish Foundation for Strategic Research, the second author was supported by Grant No. 49051 of the Academy of Finland, the third author was supported by Grant No. A 1019201 of the Academy of Sciences of the Czech Republic and by Institutional Research Plan AV0Z 10190503.     

A real algorithm for the Hermitian eigenvalue decomposition

Modifying complex plane rotations, we derive a new Jacobi-type algorithm for the Hermitian eigendecomposition, which uses only real arithmetic. When the fast-scaled rotations are incorporated, the new algorithm brings a substantial reduction in computational costs. The new method has the same convergence properties and parallelism as the symmetric Jacobi algorithm. Computational test results show that it produces accurate eigenvalues and eigenvectors and achieves great reduction in computational time.The work of this author was supported in part by the National Science Foundation grant CCR-8813493 and by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.The work of this author was supported in part by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.     

Complete solution of a family of quartic Thue equations

This paper evolved from a visit of the first author to the University of Debrecen, Hungary, which was supported by the Austrian-Hungarian Science Cooperation project Nr. 10-U-3. Research of the second author was partially supported by Hungarian National Foundation for Scientific Research Grant 1641/90.     

Modifications and implementation of the ellipsoid algorithm for linear programming

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAG29-77-G-0114 and the National Science Foundation under Grant MCS-8006065.The work of this author was supported in part by the National Science Foundation under Grant ECS-7921279.     

Some remarks on a problem of J. D. Monk

In this paper we give a partial answer to a question of J. D. Monk on the size of independent families in product of interval algebras and for some related questions.The first author was supported by the United States Israel Binational Science Foundation, Publication 370The second author was supported by the Hungarian National Foundation for Scientific Research grant No. 1908     

Necessary Conditions for Impulsive Nonlinear Optimal Control Problems without a priori Normality Assumptions

First-order and second-order necessary conditions of optimality for an impulsive control problem that remain informative for abnormal control processes are presented and derived. One of the main features of these conditions is that no a priori normality assumptions are required. This feature follows from the fact that these conditions rely on an extremal principle which is proved for an abstract minimization problem with equality constraints, inequality constraints, and constraints given by an inclusion in a convex cone. Two simple examples illustrate the power of the main result.The first author was partially supported by the Russian Foundation for Basic Research Grant 02-01-00334. The second author was partially supported by the Russian Foundation for Basic Research Grant 00-01-00869. The third author was partially supported by Fundacao para a Ciencia e Tecnologia and by INVOTAN Grant.     

Computing the geodesic center of a simple polygon

The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon withn vertices in timeO(n logn).Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Part of the work on this paper by the first two authors has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Work on this paper by the third author has been supported by the Fonds zur Förderung der wissenschaftlichen Forschung (FWF), Project S32/01.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

Inexact primal-dual interior point iteration for linear programs in function spaces

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.The research of this author was supported by an Overseas Research Scholarship of the Ministry of Education, Science and Culture of Japan.The research of this author was supported by National Science Foundation grants #DMS-9024622 and #DMS-9321938, North Atlantic Treaty Organization grant #CRG 920067, and an allocation of computing resources from the North Carolina Supercomputing Program.The research of this author was supported by North Atlantic Treaty Organization grant #CRG 920067.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration     

Recurrence of the integral of a smooth conditionally periodic function

We prove that the integral of a smooth multifrequency conditionally periodic function with zero mean oscillates. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 737–748, May, 1998. The author wishes to express his deep gratitude to S. V. Konyagin for fruitful discussions, verification of the results, and the correction of some misprints. This research was supported by the Russian Foundation for Basic Research under grants No. 96-01-00378 and No. 96-15-96072 and by the EFAKOD Foundation.     

Strongly meager and strong measure zero sets

 In this paper we present two consistency results concerning the existence of large strong measure zero and strongly meager sets. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID="ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658 Received: 6 January 1999 / Revised version: 20 July 1999 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID=" ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658     

Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization

In a recent paper (Ref. 1), the author proposed a trust-region algorithm for solving the problem of minimizing a nonlinear function subject to a set of equality constraints. The main feature of the algorithm is that the penalty parameter in the merit function can be decreased whenever it is warranted. He studied the behavior of the penalty parameter and proved several global and local convergence results. One of these results is that there exists a subsequence of the iterates generated by the algorithm that converges to a point that satisfies the first-order necessary conditions.In the current paper, we show that, for this algorithm, there exists a subsequence of iterates that converges to a point that satisfies both the first-order and the second-order necessary conditions.This research was supported by the Rice University Center for Research on Parallel Computation, Grant R31853, and the REDI Foundation.     

Some Geometrical Aspects of Efficient Points in Vector Optimization

We study efficient point sets in terms of extreme points, positive support points and strongly positive exposed points. In the case when the ordering cone has a bounded base, we prove that the efficient point set of a weakly compact convex set is contained in the closed convex hull of its strongly positive exposed points, thereby extending the Phelps theorem. We study also the density of positive proper efficient point sets. This research was supported by a Central Research Grant of Hong Kong Polytechnic University, Grant G-T 507. Research of the first author was also supported by the National Natural Science Foundation of P.R. China, Grant 10361008, and the Natural Science Foundation of Yunnan Province, China, Grant 2003A002M. Research of the second author was also supported by the Natural Science Foundation of Chongqing. Research of the third author was supported by a research grant from Australian Research Counsil.     

Scattering in a Forked-Shaped Waveguide

We consider wave scattering in a forked-shaped waveguide which consists of two finite and one half-infinite intervals having one common vertex. We describe the spectrum of the direct scattering problem and introduce an analogue of the Jost function. In case of the potential which is identically equal to zero on the half-infinite interval, the problem is reduced to a problem of the Regge type. For this case, using Hermite-Biehler classes, we give sharp results on the asymptotic behavior of resonances, that is, the corresponding eigenvalues of the Regge-type problem. For the inverse problem, we obtain sufficient conditions for a function to be the S-function of the scattering problem on the forked-shaped graph with zero potential on the half-infinite edge, and present an algorithm that allows to recover potentials on the finite edges from the corresponding Jost function. It is shown that the solution of the inverse problem is not unique. Some related general results in the spectral theory of operator pencils are also given. This work was supported by the grant UM1-2567-OD-03 from the Civil Research and Development Foundation (CRDF). YL was partially supported by the NSF grants 0338743, 0354339 and 0754705, by the Research Board and Research Council of the University of Missouri, and by the EU Marie Curie “Transfer of Knowledge” program.     

Shortest paths algorithms: Theory and experimental evaluation

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.