弱拟法锥条件下非凸优化问题的同伦算法

本文给出弱拟法锥条件的定义,并针对非线性组合同伦方程,得到在弱拟法锥条件下求解约束非凸优化问题的同伦内点算法.证明了该算法对于可行域的某个子集中几乎所有的点,同伦路径存在,并且同伦路径收敛于问题的K-K-T点,通过数值例子验证了该算法是有效的.     

Globally Convergent,Iterative Path-Following for Algebraic Equations

Homotopy methods are of great importance for the solution of systems of equations. It is a major problemto ensure well-defined iterations along the homotopy path. Many investigations have considered the complexityof path-following methods depending on the unknown distance of some given path to the variety of ill-posed problems.It is shown here that there exists a construction method for safe paths for a single algebraic equation. A safepath may be effectively determined with bounded effort. Special perturbation estimates for the zeros together withconvergence conditions for Newton’s method in simultaneous mode allow our method to proceed on the safe path.This yields the first globally convergent, never-failing, uniformly iterative path-following algorithm. The maximumnumber of homotopy steps in our algorithm reaches a theoretical bound forecast by Shub and Smale i.e., the numberof steps is at most quadratic in the condition number. A constructive proof of the fundamental theorem of algebrameeting demands by Gauß, Kronecker and Weierstraß is a consequence of our algorithm.     

Rational obstruction theory and rational homotopy sets

We develop an obstruction theory for homotopy of homomorphisms between minimal differential graded algebras. We assume that has an obstruction decomposition given by and that f and g are homotopic on . An obstruction is then obtained as a vector space homomorphism . We investigate the relationship between the condition that f and g are homotopic and the condition that the obstruction is zero. The obstruction theory is then applied to study the set of homotopy classes . This enables us to give a fairly complete answer to a conjecture of Copeland-Shar on the size of the homotopy set [A,B] whenA and B are rational spaces. In addition, we give examples of minimal algebras (and hence of rational spaces) that have few homotopy classes of self-maps. Received February 22, 1999; in final form July 7, 1999 / Published online September 14, 2000     

Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers

We present a new probabilistic method for solving systems of polynomial equations and inequations. Our algorithm computes the equidimensional decomposition of the Zariski closure of the solution set of such systems. Each equidimensional component is encoded by a generic fiber, that is a finite set of points obtained from the intersection of the component with a generic transverse affine subspace. Our algorithm is incremental in the number of equations to be solved. Its complexity is mainly cubic in the maximum of the degrees of the solution sets of the intermediate systems counting multiplicities.Our method is designed for coefficient fields having characteristic zero or big enough with respect to the number of solutions. If the base field is the field of the rational numbers then the resolution is first performed modulo a random prime number after we have applied a random change of coordinates. Then we search for coordinates with small integers and lift the solutions up to the rational numbers. Our implementation is available within our package Kronecker from version 0.166, which is written in the Magma computer algebra system.     

Complexity of Bezout’s Theorem VI: Geodesics in the Condition (Number) Metric

We introduce a new complexity measure of a path of (problems, solutions) pairs in terms of the length of the path in the condition metric which we define in the article. The measure gives an upper bound for the number of Newton steps sufficient to approximate the path discretely starting from one end and thus produce an approximate zero for the endpoint. This motivates the study of short paths or geodesics in the condition metric. This work was partly supported by an NSERC Discovery Grant.     

Modules over motivic cohomology

For fields of characteristic zero, we show that the homotopy category of modules over the motivic ring spectrum representing motivic cohomology is equivalent to Voevodsky's big category of motives. The proof makes use of some highly structured models for motivic stable homotopy theory, motivic Spanier-Whitehead duality, the homotopy theories of motivic functors and of motivic spaces with transfers as introduced from ground up in this paper. Working with rational coefficients, we extend the equivalence for fields of characteristic zero to all perfect fields by employing the techniques of alterations and homotopy purity in motivic homotopy theory.     

Solution of Delay Differential Equation by Means of Homotopy Analysis Method

The algorithm of approximate analytical solution for delay differential equations (DDE) is obtained via homotopy analysis method (HAM) and modified homotopy analysis method (MHAM). Various examples of linear, nonlinear and system of initial value problems of DDE are solved and the results obtained show that these algorithms are accurate and efficient for the DDE. The convergence of this algorithm is also proved.     

A smoothing homotopy method for variational inequality problems on polyhedral convex sets

In this paper, based on the Robinson’s normal equation and the smoothing projection operator, a smoothing homotopy method is presented for solving variational inequality problems on polyhedral convex sets. We construct a new smoothing projection operator onto the polyhedral convex set, which is feasible, twice continuously differentiable, uniformly approximate to the projection operator, and satisfies a special approximation property. It is computed by solving nonlinear equations in a neighborhood of the nonsmooth points of the projection operator, and solving linear equations with only finite coefficient matrices for other points, which makes it very efficient. Under the assumption that the variational inequality problem has no solution at infinity, which is a weaker condition than several well-known ones, the existence and global convergence of a smooth homotopy path from almost any starting point in $R^n$ are proven. The global convergence condition of the proposed homotopy method is same with that of the homotopy method based on the equivalent KKT system, but the starting point of the proposed homotopy method is not necessarily an interior point, and the efficiency is more higher. Preliminary test results show that the proposed method is practicable, effective and robust.     

Finding Mixed Cells in the Mixed Volume Computation

In practice, finding mixed cells in certain polyhedral subdivisions plays a dominating role when a polyhedral homotopy is employed to approximate all isolated zeros of polynomial systems. This paper gives a new algorithm for the mixed cell computation via a new formulation of the underlying linear programming problems. Numerical results show that the algorithm provides a major advance in the speed of computation with much less memory requirements.     

解非凸规划问题动边界组合同伦方法

本文给出了一个新的求解非凸规划问题的同伦方法,称为动边界同伦方程,并在较弱的条件下,证明了同伦路径的存在性和大范围收敛性．与已有的拟法锥条件、伪锥条件下的修正组合同伦方法相比,同伦构造更容易,并且不要求初始点是可行集的内点,因此动边界组合同伦方法比修正组合同伦方法及弱法锥条件下的组合同伦内点法和凝聚约束同伦方法更便于应用．     

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 intrinsic homotopy for intersecting algebraic varieties

Recently we developed a diagonal homotopy method to compute a numerical representation of all positive dimensional components in the intersection of two irreducible algebraic sets. In this paper, we rewrite this diagonal homotopy in intrinsic coordinates, which reduces the number of variables, typically in half. This has the potential to save a significant amount of computation, especially in the iterative solving portion of the homotopy path tracker. Three numerical experiments all show a speedup of about a factor two.     

Complete intersections in rational homotopy theory

We investigate various homotopy invariant formulations of commutative algebra in the context of rational homotopy theory. The main subject is the complete intersection condition, where we show that a growth condition implies a structure theorem and that modules have multiply periodic resolutions.     

André-Quillen cohomology and rational homotopy of function spaces

We develop a simple theory of André-Quillen cohomology for commutative differential graded algebras over a field of characteristic zero. We then relate it to the homotopy groups of function spaces and spaces of homotopy self-equivalences of rational nilpotent CW-complexes. This puts certain results of Sullivan in a more conceptual framework.     

Fast Linear Homotopy to Find Approximate Zeros of Polynomial Systems

We prove a new complexity bound, polynomial on the average, for the problem of finding an approximate zero of systems of polynomial equations. The average number of Newton steps required by this method is almost linear in the size of the input (dense encoding). We show that the method can also be used to approximate several or all the solutions of non-degenerate systems, and prove that this last task can be done in running time which is linear in the Bézout number of the system and polynomial in the size of the input, on the average.     

The Distribution of Condition Numbers of Rational Data of Bounded Bit Length

We prove that rational data of bounded input length are uniformly distributed (in the classical sense of H. Weyl, in [42]) with respect to the probability distribution of condition numbers of numerical analysis. We deal both with condition numbers of linear algebra and with condition numbers for systems of multivariate polynomial equations. For instance, we prove that for a randomly chosen n\times n rational matrix M of bit length O(n ⁴ log n) + log w , the condition number k(M) satisfies k(M) ≤ w n ^5/2 with probability at least 1-2w ^-1 . Similar estimates are established for the condition number μ_ norm of M. Shub and S. Smale when applied to systems of multivariate homogeneous polynomial equations of bounded input length. Finally, we apply these techniques to estimate the probability distribution of the precision (number of bits of the denominator) required to write approximate zeros of systems of multivariate polynomial equations of bounded input length. March 7, 2001. Final version received: June 7, 2001.     

On the geometry of paths generated by PL homotopy methods

PL homotopy methods are effective numerical methods for highly nonlinear problems. It is widely believed that the feasibility of a PL homotopy method depends on the nondegeneracy condition that the zero set (or the fixed point set in the case of finding fixed points instead of zeroes) of the PL approximation of the homotopy does not intersect the triangulation's skeletons of co-dimensions two and above. This paper shows that, although the sections of the PL approximation's zero set tracked by the PL homotopy method are of dimension one (while other sections may have higher dimensions), the paths generated by the pivoting method are potentially and essentially of dimension two. It makes pathcrossing a safe thing. Thus, this paper first sets up the without exception feasibility of PL homotopy methods geometrically.This work is supported in part by the Foundation of Zhongshan University Advanced Research Centre.     

Finding Mixed Cells in the Mixed Volume Computation

In practice, finding mixed cells in certain polyhedral subdivisions plays a dominating role when a polyhedral homotopy is employed to approximate all isolated zeros of polynomial systems. This paper gives a new algorithm for the mixed cell computation via a new formulation of the underlying linear programming problems. Numerical results show that the algorithm provides a major advance in the speed of computation with much less memory requirements. March 17, 2000. Final version received: November 2, 2000. Online publication: February 20, 2001.     

A constraint shifting homotopy method for general non-linear programming

In this article, a constraint shifting homotopy method (CSHM) is proposed for solving non-linear programming with both equality and inequality constraints. A new homotopy is constructed, and existence and global convergence of a homotopy path determined by it are proven. All problems that can be solved by the combined homotopy interior point method (CHIPM) can also be solved by the proposed method. In contrast to the combined homotopy infeasible interior point method (CHIIPM), it needs a weaker regularity condition. And the starting point in the proposed method is not necessarily a feasible point or an interior point, so it is more convenient to be implemented than CHIPM and CHIIPM. Numerical results show that the proposed algorithm is feasible and effective.     

Sull'omotopia uniforme

Summary Following in the classical theory's footsteps, it is possible to construct a ? rational homotopy theory ?. To this purpose, we take all the uniform maps f: I _Q ⁿ →S (where I_Q is the closed unit interval of the rational line equipped with the standard metric uniformity) as paths of a uniform space S. This brings us to the definition of the rational homotopy groups Q_n(S, U_Q, x) and enables us to consider the related exact sequences. All these objects are uniform invariants. The main problem which arises now is to find a suitable space S* in order that its classical homotopy groups Π_n(S*,x) are isomorphic to the classical ones of S. We are able to reach an answer to this question if S is a metrizable uniform space. Since considering the completion Ŝ of S serves no useful purpose (as it is shown by a simple example), we prove that the required space is the ? rational path completion ? S* of S, with S⊆S*⊆Ŝ. We finally recall that the rational uniform homotopy is a special case of regular homotopy, which has been defined and widely investigated in[1].

---

---

Entrata in Redazione il 5 gennaio 1978.

---

Lavoro svolto nell'ambito del gruppo GNSAGA del CNR.