Rational Solutions of High-Order Algebraic Ordinary Differential Equations

This paper considers algebraic ordinary differential equations(AODEs) and study their polynomial and rational solutions. The authors first prove a sufficient condition for the existence of a bound on the degree of the possible polynomial solutions to an AODE. An AODE satisfying this condition is called noncritical. Then the authors prove that some common classes of low-order AODEs are noncritical. For rational solutions, the authors determine a class of AODEs, which are called maximally comparable, such that the possible poles of any rational solutions are recognizable from their coefficients. This generalizes the well-known fact that any pole of rational solutions to a linear ODE is contained in the set of zeros of its leading coefficient. Finally, the authors develop an algorithm to compute all rational solutions of certain maximally comparable AODEs, which is applicable to 78.54% of the AODEs in Kamke's collection of standard differential equations.     

Resultant elimination via implicit equation interpolation

It is well known that resultant elimination is an effective method of solving multivariate polynomial equations. In this paper, instead of computing the target resultants via variable by variable elimination, the authors combine multivariate implicit equation interpolation and multivariate resultant elimination to compute the reduced resultants, in which the technique of multivariate implicit equation interpolation is achieved by some high probability algorithms on multivariate polynomial interpolation and univariate rational function interpolation. As an application of resultant elimination, the authors illustrate the proposed algorithm on three well-known unsolved combinatorial geometric optimization problems. The experiments show that the proposed approach of resultant elimination is more efficient than some existing resultant elimination methods on these difficult problems.     

Discovering non-terminating inputs for multi-path polynomial programs

This paper investigates the termination problems of multi-path polynomial programs （MPPs） with equational loop guards. To establish sufficient conditions for termination and nontermination simultaneously, the authors propose the notion of strong/weak non-termination which under/over- approximates non-termination. Based on polynomial ideal theory, the authors show that the set of all strong non-terminating inputs （SNTI） and weak non-terminating inputs （WNTI） both correspond to tile real varieties of certain polynomial ideals. Furthermore, the authors prove that the variety of SNTI is computable, and under some sufficient conditions the variety of WNTI is also computable. Then by checking the computed SNTI and WNTI varieties in parallel, termination properties of a consid- ered MPP can be asserted. As a consequence, the authors establish a new framework for termination analysis of MPPs.     

Distributed Algorithm for Robust Resource Allocation with Polyhedral Uncertain Allocation Parameters

This paper studies a distributed robust resource allocation problem with nonsmooth objective functions under polyhedral uncertain allocation parameters. In the considered distributed robust resource allocation problem, the (nonsmooth) objective function is a sum of local convex objective functions assigned to agents in a multi-agent network. Each agent has a private feasible set and decides a local variable, and all the local variables are coupled with a global affine inequality constraint, which is subject to polyhedral uncertain parameters. With the duality theory of convex optimization, the authors derive a robust counterpart of the robust resource allocation problem. Based on the robust counterpart, the authors propose a novel distributed continuous-time algorithm, in which each agent only knows its local objective function, local uncertainty parameter, local constraint set, and its neighbors’ information. Using the stability theory of differential inclusions, the authors show that the algorithm is able to find the optimal solution under some mild conditions. Finally, the authors give an example to illustrate the efficacy of the proposed algorithm.     

Exact Bivariate Polynomial Factorization over Q by Approximation of Roots

Factorization of polynomials is one of the foundations of symbolic computation.Its applications arise in numerous branches of mathematics and other sciences.However,the present advanced programming languages such as C++ and J++,do not support symbolic computation directly.Hence,it leads to difficulties in applying factorization in engineering fields.In this paper,the authors present an algorithm which use numerical method to obtain exact factors of a bivariate polynomial with rational coefficients.The proposed method can be directly implemented in efficient programming language such C++ together with the GNU Multiple-Precision Library.In addition,the numerical computation part often only requires double precision and is easily parallelizable.     

多项式光滑的半监督支持向量分类机

为了处理半监督支持向量分类优化中的非凸非光滑问题,引入一族多项式光滑函数来逼近非凸的目标函数,给出的多项式函数在样本的高密度区逼近精度高,逼近精度低时出现在样本的低密度区,同时可以根据不同的精度要求选择不同的逼近函数.采用BFGS算法求解模型.在人工数据和UCI数据集上的实验结果显示,算法不仅能保证标号数据很少时的分类精度,而且不因标号数据的增多而明显提高分类性能,因此给出的分类器性能是稳定的.     

A simplified rational representation for positive-dimensional polynomial systems and SHEPWM equations solving

The paper is concerned with the improvement of the rational representation theory for solving positive-dimensional polynomial systems. The authors simplify the expression of rational representation set proposed by Tan and Zhang (2010), obtain the simplified rational representation with less rational representation sets, and hence reduce the complexity for representing the variety of a positive-dimensional ideal. As an application, the authors compute a “nearly” parametric solution for the SHEPWM problem with a fixed number of switching angles.     

The Fitzpatrick-Neville-Type Algorithm for Multivariate Vector-Valued Osculatory Rational Interpolation

In this paper,the authors first apply the Fitzpatrick algorithm to multivariate vectorvalued osculatory rational interpolation.Then based on the Fitzpatrick algorithm and the properties of an Hermite interpolation basis,the authors present a Fitzpatrick-Neville-type algorithm for multivariate vector-valued osculatory rational interpolation.It may be used to compute the values of multivariate vector-valued osculatory rational interpolants at some points directly without computing the interpolation function explicitly.     

An adaptive Lagrangian algorithm for optimal portfolio deleveraging with cross-impact

This paper considers the problem of optimal portfolio deleveraging, which is a crucial problem in finance. Taking the permanent and temporary price cross-impact into account, the authors establish a quadratic program with box constraints and a singly quadratic constraint. Under some assumptions, the authors give an optimal trading priority and show that the optimal solution must be achieved when the quadratic constraint is active. Further, the authors propose an adaptive Lagrangian algorithm for the model, where a piecewise quadratic root-finding method is used to find the Lagrangian multiplier. The convergence of the algorithm is established. The authors also present some numerical results, which show the usefulness of the algorithm and validate the optimal trading priority.     

An affine scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming

This paper proposes an arlene scaling derivative-free trust region method with interior backtracking technique for bounded-constrained nonlinear programming. This method is designed to get a stationary point for such a problem with polynomial interpolation models instead of the objective function in trust region subproblem. Combined with both trust region strategy and line search technique, at each iteration, the affine scaling derivative-free trust region subproblem generates a backtracking direction in order to obtain a new accepted interior feasible step. Global convergence and fast local convergence properties are established under some reasonable conditions. Some numerical results are also given to show the effectiveness of the proposed algorithm.     

退火进化规划算法及其收敛性

基于排序的选择方式在一定程度上会导致种群搜索范围变窄,进化规划算法过早收敛。针对此问题,将退火概率与适应度结合的选择方式引入进化规划算法的选择操作,形成了退火进化规划算法(AEP)。然后利用非时齐Markov链对退火进化规划算法进行了描述,并证明了其全局收敛性。数值实验表明,退火进化规划算法能保证种群的全局收敛性,且收敛速度较快,可较好地避免早熟收敛和局部极值。     

最优组合重新参数化

提出了一种最优的曲线重新参数化方法.该方法采用分段有理线性函数作为重新参数化函数来增加自由度.其中一个自由度用于保证连续性条件的满足,其余的自由度用于达到L2范数下的最优参数化.在不改变参数区问和参数域的情况下,得到在任意参数节点集上的C1连续有理参数化的显式表示形式.相对于新的参数,目标函数是线性的,最优值能够通过求解一个二次方程得到.最后用实例验证了新方法的有效性.     

Computing the Determinant of a Matrix with Polynomial Entries by Approximation

Computing the determinant of a matrix with the univariate and multivariate polynomial entries arises frequently in the scientific computing and engineering fields. This paper proposes an effective algorithm to compute the determinant of a matrix with polynomial entries using hybrid symbolic and numerical computation. The algorithm relies on the Newton’s interpolation method with error control for solving Vandermonde systems. The authors also present the degree matrix to estimate the degree of variables in a matrix with polynomial entries, and the degree homomorphism method for dimension reduction. Furthermore, the parallelization of the method arises naturally.     

Adaptive Numerical Approach for Optimal Control of a Single Train

This paper considers the optimal control problem of a single train, which is formulated as an optimal control problem of nonlinear systems with switching controller. The switching sequence and the switching time are decision variables to be chosen optimally. Generally speaking, it is very difficult to solve this problem analytically due to its nonlinear nature, the complexity of the controller,and the existence of system state and control input constraints. To obtain the numerical solution, by introducing binary functions for every value of the control input, relaxing the binary functions, and imposing a penalty function on the relaxation, the problem is transformed into a parameter optimization problem, which can be efficiently solved by using any gradient-based numerical approach. Then, the authors propose an adaptive numerical approach to solve this problem. Convergence results indicate that any optimal solution of the parameter optimization problem is also an optimal solution of the original problem. Finally, an optimal control problem of a single train illustrates that the adaptive numerical approach proposed by us is less time-consuming and obtains a better cost function value than the existing approaches.     

求解度约束最小生成树的快速近似算法

针对带有度约束的最小生成树问题,给出了一种快速近似算法.首先给出了快速近似算法的核心思想:在不违反度约束和不形成圈的前提下,每次加入权最小的边.其次给出了实现快速近似算法的具体步骤,并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数,证明了算法的有效性定理.大量的数值试验表明该近似算法性能良好.最后在此算法的基础上,给出了求解TSP问题的一种快速近似算法.     

光滑支持向量机多项式函数的研究

为了找到多项式光滑支持向量机(polynomial smooth support vector machine,PSSVM)中性能更好的光滑函数,将正号函数变形并展开为多项式级数,得到一类光滑函数。证明了这类函数的性能,它既能满足任意阶光滑的要求,也能达到任意给定的逼近精度。用Newton-Armijo算法求解相应的PSSVM模型,实验结果表明,随着多项式光滑函数阶数的提高,逼近精度和相应PSSVM模型的分类性能也相应提高。     

Convergence of Distributed Gradient-Tracking-Based Optimization Algorithms with Random Graphs

This paper studies distributed convex optimization over a multi-agent system, where each agent owns only a local cost function with convexity and Lipschitz continuous gradients. The goal of the agents is to cooperatively minimize a sum of the local cost functions. The underlying communication networks are modelled by a sequence of random and balanced digraphs, which are not required to be spatially or temporally independent and have any special distributions. The authors use a distributed gradient-tracking-based optimization algorithm to solve the optimization problem. In the algorithm,each agent makes an estimate of the optimal solution and an estimate of the average of all the local gradients. The values of the estimates are updated based on a combination of a consensus method and a gradient tracking method. The authors prove that the algorithm can achieve convergence to the optimal solution at a geometric rate if the conditional graphs are uniformly strongly connected, the global cost function is strongly convex and the step-sizes don't exceed some upper bounds.     

Simplifying the nonlinear continuous time-cost tradeoff problem

Equivalent simplification is an effective method for solving large-scale complex problems. In this paper, the authors simplify a classic project scheduling problem, which is the nonlinear continuous time-cost tradeoff problem (TCTP). Simplifying TCTP is a simple path problem in a critical path method (CPM) network. The authors transform TCTP into a simple activity float problem and design a complex polynomial algorithm for its solution. First, the authors discover relationships between activity floats and path lengths by studying activity floats from the perspective of path instead of time. Second, the authors perform simplification and improve the efficiency and accuracy of the solution by deleting redundant activities and narrowing the duration intervals of non-redundant activities. Finally, the authors compare our method with current methods. The relationships between activity floats and path lengths provide new approaches for other path and correlative project problems.     

双系统合作式协同进化算法求解不可分解函数

针对不可分解函数求解问题,基于合作式协同进化(cooperative co-evolutionary,CC)框架,发展一种双系统协同进化算法。该算法给出一种双系统A,B的 CC框架新结构形式及其相应的协调机制,以增加算法的多样性和收敛性;给出双系统A,B各自求解的两种算法,例如差异进化、改进粒子群算法选择原则和匹配方式,使该两种算法具互补性,并且与双系统A,B各自角色相匹配,目的是提高基于CC框架双系统算法的计算性能。经不可分解函数集(维数D=1 000)测试表明,本文算法计算性能(计算精度和标准差)与其他3种典型算法相比,对于其中某些函数求解占优,总体上4种算法对函数集的求解各有所长,具有互补性。     

考虑姿态禁忌约束的航天器安全姿态跟踪控制

针对航天器姿态跟踪过程中的姿态约束问题,提出了一种基于势函数的安全姿态机动控制算法。与姿态定点机动的姿态约束问题不同,引入误差四元数和误差角速度,建立了航天器姿态跟踪误差模型。采用四元数描述了姿态禁忌区域,并根据禁止姿态最小允许角构造了一种新的规避高斯势函数。利用规避势函数和吸引势函数得到安全姿态机动控制器,对于无扰动和有扰动的情况分别分析了闭环控制系统的Lyapunov稳定性。最后,对于有约束的姿态跟踪情况进行了计算机数值仿真。仿真结果表明,所提出的控制方法既能实现姿态跟踪的目的,又能确保航天器在机动过程中不会进入姿态禁忌区域。