A geometrical interpretation of the without-exception feasibility of PL homotopy methods

PL homotopy methods are effective methods to locate zerces (or fixed points) of highly nonlinear mappings. Due to the lexicographical system, the methods are feasible without exceptions. This paper presents a geometrical interpretation of the without-exception feasibility.An invited talk at the 13th International Symposium on Mathematical Programming, Aug. 29–Sep. 2, 1988, Tokyo. The work is supported in part by the Foundation of Zhongshan University, Advanced Research Centre and in part by the National Natural Science Foundation of China.     

On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

On the Haefliger-Hirsch-Wu invariants for embeddings and immersions

We prove beyond the metastable dimension the PL cases of the classical theorems due to Haefliger, Harris, Hirsch and Weber on the deleted product criteria for embeddings and immersions. The isotopy and regular homotopy versions of the above theorems are also improved. We show by examples that they cannot be improved further. These results have many interesting corollaries, e.g.? 1) Any closed homologically 2-connected smooth 7-manifold smoothly embeds in .? 2) If and then the set of PL embeddings up to PL isotopy is in 1-1 correspondence with?. Received: July 6, 2000     

Homotopy types of locally linear representation forms

Summary The authors of [6] investigated certain locally linear actions of a cyclic groupG of odd order on homotopy spheres, the so-calledG-representation forms [16]. In particular, several conditions on a dimension function were described that made sure that it can be realized as the dimension function of aG-representation form. It remained unclear, whether all homotopy types with those dimension functions would support a locally linear structure. It is the aim of this note to show that this is not the case, i.e., to give examples of homotopy representations [17] with the same dimension functions some of which support a locally linear structure with stably trivial tangent bundle and others do not. The main tools are formulated as general splitting principles for fixed point and restriction functors that may have some interest in their own right, too. Part of the work with this paper was assembled while the authors were visiting Institut Mittag-Leffler at Djursholm, Sweden, whose support is gratefully acknowledged. This article was processed by the author using the LATEX style filecljour1 from Springer-Verlag.     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.     

Computing curve intersection by homotopy methods

Intersection problems are fundamental in computational geometry, geometric modeling and design and manufacturing applications, and can be reduced to solving polynomial systems. This paper introduces two homotopy methods, i.e. polyhedral homotopy method and linear homotopy method, to compute the intersections of two plane rational parametric curves. Extensive numerical examples show that computing curve intersection by homotopy methods has better accuracy, efficiency and robustness than by the Ehrlich–Aberth iteration method. Finally, some other applications of homotopy methods are also presented.     

Computing curve intersection by homotopy methods

Intersection problems are fundamental in computational geometry, geometric modeling and design and manufacturing applications, and can be reduced to solving polynomial systems. This paper introduces two homotopy methods, i.e. polyhedral homotopy method and linear homotopy method, to compute the intersections of two plane rational parametric curves. Extensive numerical examples show that computing curve intersection by homotopy methods has better accuracy, efficiency and robustness than by the Ehrlich-Aberth iteration method. Finally, some other applications of homotopy methods are also presented.     

关于向量标号单纯算法的基本理论——对《解法》一书的若干意见

§1.引言 在《非线性方程组的数值解法》(简称解法)的第七章和第四章中,有些论述不够妥当. 考虑到一些院校已经或准备选用它作为计算数学专业研究生和高年级学生的教材和参考书,影响较大,故将自己的意见提出来,与作者和读者商榷.     

求解混合三角多项式方程组的直接GBQ方法

许多科学与工程领域,我们经常需要求混合三角多项式方程组的全部解.一般来说,混合三角多项式方程组可以通过变量替换及增加二次多项式转化为多项式方程组,进而利用数值方法进行求解,但这种转化会增大问题的规模从而增加计算量.在本文中,我们不将问题转化,考虑利用直接同伦方法求解,并给出基于GBQ方法构造的初始方程组及同伦定理的证明.数值实验结果表明我们构造的直接同伦方法较已有的直接同伦方法更加有效.     

Augmented Lagrangian Homotopy Method for the Regularization of Total Variation Denoising Problems

This paper presents a homotopy procedure which improves the solvability of mathematical programming problems arising from total variational methods for image denoising. The homotopy on the regularization parameter involves solving a sequence of equality-constrained optimization problems where the positive regularization parameter in each optimization problem is initially large and is reduced to zero. Newton’s method is used to solve the optimization problems and numerical results are presented.     

A spline smoothing homotopy method for nonconvex nonlinear programming

Homotopy methods are globally convergent under weak conditions and robust; however, the efficiency of a homotopy method is closely related with the construction of the homotopy map and the path tracing algorithm. Different homotopies may behave very different in performance even though they are all theoretically convergent. In this paper, a spline smoothing homotopy method for nonconvex nonlinear programming is developed using cubic spline to smooth the max function of the constraints of nonlinear programming. Some properties of spline smoothing function are discussed and the global convergence of spline smoothing homotopy under the weak normal cone condition is proven. The spline smoothing technique uses a smooth constraint instead of m constraints and acts also as an active set technique. So the spline smoothing homotopy method is more efficient than previous homotopy methods like combined homotopy interior point method, aggregate constraint homotopy method and other probability one homotopy methods. Numerical tests with the comparisons to some other methods show that the new method is very efficient for nonlinear programming with large number of complicated constraints.     

An explicit series approximation to the optimal exercise boundary of American put options

This paper derives an explicit series approximation solution for the optimal exercise boundary of an American put option by means of a new analytical method for strongly nonlinear problems, namely the homotopy analysis method (HAM). The Black–Sholes equation subject to the moving boundary conditions for an American put option is transferred into an infinite number of linear sub-problems in a fixed domain through the deformation equations. Different from perturbation/asymptotic approximations, the HAM approximation can be applicable for options with much longer expiry. Accuracy tests are made in comparison with numerical solutions. It is found that the current approximation is as accurate as many numerical methods. Considering its explicit form of expression, it can bring great convenience to the market practitioners.     

Double power laws,fractals and self-similarity

Power law (PL) distributions have been largely reported in the modeling of distinct real phenomena and have been associated with fractal structures and self-similar systems. In this paper, we analyze real data that follows a PL and a double PL behavior and verify the relation between the PL coefficient and the capacity dimension of known fractals. It is to be proved a method that translates PLs coefficients into capacity dimension of fractals of any real data.     

An adaptive homotopy approach for non-selfadjoint eigenvalue problems

This paper presents adaptive algorithms for eigenvalue problems associated with non-selfadjoint partial differential operators. The basis for the developed algorithms is a homotopy method which departs from a well-understood selfadjoint problem. Apart from the adaptive grid refinement, the progress of the homotopy as well as the solution of the iterative method are adapted to balance the contributions of the different error sources. The first algorithm balances the homotopy, discretization and approximation errors with respect to a fixed stepsize τ in the homotopy. The second algorithm combines the adaptive stepsize control for the homotopy with an adaptation in space that ensures an error below a fixed tolerance ε. The outcome of the analysis leads to the third algorithm which allows the complete adaptivity in space, homotopy stepsize as well as the iterative algebraic eigenvalue solver. All three algorithms are compared in numerical examples.     

Stable Homotopy Monomorphisms

It is well known that the concept of monomorphism in a category can be defined using an appropriate pullback diagram. In the homotopy category of TOP pullbacks do not generally exist. This motivated Michael Mather to introduce another notion of homotopy pullback which does exist. The aim of this paper is to investigate the modified notion of homotopy monomorphism obtained by applying the pullback characterization using Mather's homotopy pullback. The main result of Section 1 shows that these modified homotopy monomorphisms are exactly those homotopy monomorphisms (in the usual sense) which are homotopy pullback stable, hence the terminology “stable” homotopy monomorphism. We also link these stable homotopy monomorphisms to monomorphisms and products in the track homotopy category over a fixed space. In Section 2 we answer the question: when is a (weak) fibration also a stable homotopy monomorphism? In the final section it is shown that the class of (weak) fibrations with this additional property coincides with the class of “double” (weak) fibrations. The double (weak) covering homotopy property being introduced here is a stronger version of the (W) CHP in which the final maps of the homotopies involved play the same role as the initial maps.     

On normal invariants of certain manifolds

A method is presented for computing the set of homotopy classes [X, G/PL], where X is a finite CW complex satisfying certain homological conditions. The result obtained is applied to compute normal invariants of products of projective spaces.     

Modified block iterative method for solving convex feasibility problem,equilibrium problems and variational inequality problems

The purpose of this paper is by using the modified block iterative method to propose an algorithm for finding a common element in the intersection of the set of common fixed points of an infinite family of quasi-φ-asymptotically nonexpansive and the set of solutions to an equilibrium problem and the set of solutions to a variational inequality. Under suitable conditions some strong convergence theorems are established in 2-uniformly convex and uniformly smooth Banach spaces. As applications we utilize the results presented in the paper to solving the convex feasibility problem (CFP) and zero point problem of maximal monotone mappings in Banach spaces. The results presented in the paper improve and extend the corresponding results announced by many authors.     

Triangulate flat cones on simplices

The convex hull of the vertices of a simplex and a point lying on the hyperplane spanned by the simplex is called a flat cone on the simplex. This paper proposes a natural way to simplicially triangulate flat cones on simplices and develops its applications to PL homotopy methods. This work is supported in part by the Fund of the National Committee of Education of China and in part by the National Natural Science Foundation of China.     

How do path generation methods affect the accuracy of quasi-Monte Carlo methods for problems in finance?

Quasi-Monte Carlo (QMC) methods are important numerical tools in computational finance. Path generation methods (PGMs), such as Brownian bridge and principal component analysis, play a crucial role in QMC methods. Their effectiveness, however, is problem-dependent. This paper attempts to understand how a PGM interacts with the underlying function and affects the accuracy of QMC methods. To achieve this objective, we develop efficient methods to assess the impact of PGMs. The first method is to exploit a quadratic approximation of the underlying function and to analyze the effective dimension and dimension distribution (which can be done analytically). The second method is to carry out a QMC error analysis on the quadratic approximation, establishing an explicit relationship between the QMC error and the PGM. Equalities and bounds on the QMC errors are established, in which the effect of the PGM is separated from the effect of the point set (in a similar way to the Koksma–Hlawka inequality). New measures for quantifying the accuracy of QMC methods combining with PGMs are introduced. The usefulness of the proposed methods is demonstrated on two typical high-dimensional finance problems, namely, the pricing of mortgage-backed securities and Asian options (with zero strike price). It is found that the success or failure of PGMs that do not take into account the underlying functions (such as the standard method, Brownian bridge and principal component analysis) strongly depends on the problem and the model parameters. On the other hand, the PGMs that take into account the underlying function are robust and powerful. The investigation presents new insight on PGMs and provides constructive guidance on the implementation and the design of new PGMs and new QMC rules.