Globally convergent homotopy algorithm for solving the KKT systems to the principal-agent bilevel programming

In this paper, a constraint set swelling homotopy (CSSH) algorithm for solving the single-level non-convex programming problem with designing piecewise linear contractual function which is equivalent to the principal-agent model with integral operator is proposed, and the existence and global convergence is proven under some mild conditions. As a comparison, a piecewise constant contract is also designed for solving the single-level non-convex programming problem with the corresponding discrete distributions. And some numerical tests are done by the proposed homotopy algorithm as well as by using fmincon in Matlab, LOQO and MINOS. The numerical results show that the CSSH algorithm is robust, feasible and effective.     

Homotopy approach for solving constrained optimization problems

A homotopy approach for solving constrained parameter optimization problems is examined. The first-order necessary conditions, with the complementarity conditions represented using a technique due to Mangasarian (1967) are solved. The equations are augmented to avoid singularities which occur when the active constraint changes. The Chow-Yorke (1978) algorithm is used to track the homotopy path leading to the solution to the desired problem at the terminal point. A simple example which illustrates the technique and an application to a fuel optimal orbital transfer problem are presented     

A Homotopy Approach to Solving Nonlinear Rational Expectation Problems

Many numerical methods have been developed in an attempt to find solutions to nonlinear rational expectations models. Because these algorithms are numerical in nature, they rely heavily on computing power and take sizeable cycles to solve. In this paper we present a numerical tool known as homotopy theory that can be applied to these methods. Homotopy theory reduces the computing time associated with an iterative algorithm by using a rational expectation problem with known solutions and transforming it into the problem at hand. If this transformation is performed slowly, homotopy theory also helps the global convergence properties of the numerical algorithm. We apply homotopy theory to Den Haan and Marcet's Parameterized Expectation Approach to show how homotopies improve the computing speed and global convergence properties of this algorithm.     

A double homotopy method for decentralised control design

An iterative algorithm that is based on the idea of two homotopy paths is proposed for output feedback decentralised ?_∞ control design. The approach follows a bilinear matrix inequality (BMI) formulation of the decentralised control problem. Along one homotopy path the BMI problem, which is non-convex, is locally linearised and solved. Along the second homotopy path the controller is deformed at each step so that in the end it attains a decentralised structure. The proposed computational algorithm can also be applied to obtain reduced-order decentralised controllers. Numerical examples are used to demonstrate the efficacy of the proposed algorithm.     

Computing shortest words via shortest loops on hyperbolic surfaces

Given a loop on a surface, its homotopy class can be specified as a word consisting of letters representing the homotopy group generators. One of the interesting problems is how to compute the shortest word for a given loop. This is an NP-hard problem in general. However, for a closed surface that allows a hyperbolic metric and is equipped with a canonical set of fundamental group generators, the shortest word problem can be reduced to finding the shortest loop that is homotopic to the given loop, which can be solved efficiently. In this paper, we propose an efficient algorithm to compute the shortest words for loops given on triangulated surface meshes. The design of this algorithm is inspired and guided by the work of Dehn and Birman–Series. In support of the shortest word algorithm, we also propose efficient algorithms to compute shortest paths and shortest loops under hyperbolic metrics using a novel technique, called transient embedding, to work with the universal covering space. In addition, we employ several techniques to relieve the numerical errors. Experimental results are given to demonstrate the performance in practice.     

High-dimensional homotopy curve tracking on a shared-memory multiprocessor

Results are reported for a series of experiments involving numerical curve tracking on a shared-memory parallel computer. Several algorithms exist for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, that is, with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then the tracking of some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. A parallel version of HOMPACK is implemented on a shared-memory parallel computer with various levels and degrees of parallelism (e.g., linear algebra, function, and Jacobian matrix evaluation), and a detailed study is presented for each of these levels with respect to the speedup in execution time obtained with the parallelism, the time spent implementing the parallel code, and the extra memory allocated by the parallel algorithm.     

求解量子系统时间最优控制问题的同伦算法研究

针对数值求解量子系统时间最优控制问题中反复调用梯度算法导致计算量大的问题,本文提出一类同伦算法用以快速求解量子系统的时间最优控制问题.与已有算法不同,这一算法通过引入同伦变量在减小终端时间的方向上搜索最优解.在这一算法中,可通过自由函数构造保真度函数对控制变量的梯度方向,也可通过方向函数引导算法的搜索方向,以加快算法的搜索速度.本文将这一算法用于求解量子系统态转移和门变换的时间最优控制问题.仿真结果表明这一算法的有效性.     

Nonlocal automated comparative static analysis

This paper reviews work on the development of a program Nasa for the automated comparative static analysis of parameterized nonlinear systems over parameter intervals. Nasa incorporates a fast and efficient algorithm Feed for the automatic evaluation of higher-order partial derivatives, as well as an adaptive homotopy continuation algorithm for obtaining all required initial conditions. Applications are envisioned for fields such as economics where models tend to be complex and closed-form solutions are difficult to obtain.     

一种基于同伦函数的迭代法—同伦迭代法

§１．引言 工程中的许多问题常常最后可归结为求解一组非线性多项式代数方程．对非线性多项式方程组的求解,可采用符号求解和数值求解两种方式．符号求解可求出问题的封闭形式的解析解,当然是最理想的,但其难度往往也是很大的,随着问题数学模型的增大,消元过程变得愈加复杂,使得即使采用计算机也无法进行下去．因此,对于复杂的大规模问题,仍只能采用数值迭代法进行数值求解． 传统的数值迭代法存在的最大问题是方法的有效性依赖于初值的选取．初值选取不当常导致迭代过程不收敛,而且一次只能求出问题的一个数值解．山提出的区间分…     

Symbolic integration using homotopy methods

The homotopy algorithm is a powerful method for indefinite integration of total derivatives. By combining these ideas with straightforward Gaussian elimination, we construct an algorithm for the optimal symbolic integration that contain terms that are not total derivatives. The optimization consists of minimizing the number of terms that remain unintegrated. Further, the algorithm imposes an ordering of terms so that the differential order of these remaining terms is minimal. A different method for the summation of difference expressions is presented in Appendix B.