自动微分方法在XIAMEN软件优化中的应用

比起有限差分方法来,运用自动微分方法计算函数的梯度在计算时间和计算精度方面都具有明显的优势.使用伴随模式计算函数的梯度,在XIAMEN软件优化中得到了明显的加速效果.使用ADG系统自动生成伴随模式,大大降低了伴随模式的开发时间和难度.重点讨论了伴随模式实现的几个关键难题,并给出了几个典型应用的数值结果.     

几种分数阶微分数值解法的比较研究

研究分数阶算法特性,基于抛物线插值方法,对分数阶微分计算设计了一种数值计算方法.明确了几种算法的特点,并进行了数值仿真,对于函数分数阶微分及分数阶微分方程的求解,在计算精度与计算时间开销方面,与迭代方法、线性插值方法进行了比较,结果表明迭代方法的计算精度和时间开销两方面都比较好,抛物线插值方法的计算精度高于线性插值,但线性插值在时间开销方面占优势,研究结果可为实际选择分数阶微分数值计算方法提供科学依据.     

伴随模式生成器

伴随模式生成器(ADG)专门用来自动生成伴随模式,以分析求解函数的梯度和Hessian矩阵向量乘积,其计算复杂性与独立变元的数目无关.ADG系统与其他同类软件最大的不同之处在于采用了最小程序行为分解的模式伴随化方法,以及几种全局的静态相关分析技术.文中首先讨论了相关的概念和方法,然后介绍了ADG系统的基本功能和特色.特别地,文中详细讨论了ADG系统的系统结构和相关技术,包括解决基态值问题的重复计算/数据存储技术和微分代码优化方法.最后给出了几个典型应用和数值测试结果.     

基于小波变换和方向微分的运动模糊方向鉴别研究

针对最小方向微分算法(MinimumDirectionalDerivation,MDD)在运动模糊方向鉴别中计算量大的问题,提出利用小波变换和方向微分相结合的算法鉴别运动模糊方向。首先引入小波变换获得运动模糊图像的低频部分,缩小了计算范围,减小了计算量;然后在利用基于方向微分的加权平均法鉴别模糊方向时,先取步长为10°粗略得到模糊方向,在此模糊方向±10°范围内以0.5°为步长精确鉴别出模糊方向。该方法既能减小计算量,又能提高鉴别精度。仿真结果表明本文算法鉴别运动模糊方向误差小,实时性好,应用范围广。     

自动微分在隐式曲线绘制中的应用

自动微分是用于计算多变量函数的导数和偏导数的一种微分技术,在给定一个多变量光滑函数值的程序代码后,可以很容易地利用自动微分来实现有关导数和偏导数的精确计算。将自动微分技术与泰勒方法相结合应用到计算机图形学领域隐式函数曲线绘制的细分算法中,并与未使用自动微分技术前的隐式曲线绘制方法作比较和分析,展示了自动微分方法在绘制隐式曲线方面的优势。     

自适应非整数步长的分数阶微分掩模的图像纹理增强算法

图像纹理增强是计算机图形学、计算机视觉和模式识别等领域里的一个重要问题.通过分析分数阶微分原理和纹理图像的特性,提出一种自适应非整数步长的分数阶微分掩模算法,并将其应用于纹理图像增强中.利用图像纹理间的高度自相关性自适应地构建局部不规则的自相关掩模区域,剔除相关性较低的像素并降低噪声干扰;同时,突破传统分数阶微分数值计算采用单位步长的思想,分析不规则掩模区域的臂长特征,自适应地估计非整数步长;最后建立局部线性模型实现对非整数步长处的像素灰度值的准确估计,提高分数阶微分数值解的逼近程度.实验结果表明,该算法能够提高分数阶微分解析值的精确度,有效地增强了图像平滑区域中的复杂纹理细节.     

基于OpenCL的自动微分并行实现及其应用

针对如光束平差这样的大规模优化问题,实现基于OpenCL的并行化自动微分。采用更有效的反向计算模式,实现对多参数函数的导数计算。在OpenCL框架下,主机端完成C/C++形式的函数构建以及基于拓扑排序的计算序列生成,设备端按照计算序列完成函数值以及导数的并行计算。测试结果表明,将实现的自动微分应用于光束平差的雅可比矩阵计算后,相比于采用OpenMP的Ceres Solver,运行速度提高了约3.6倍。     

一种新的自适应步长梯度投影法

梯度投影法是一种求解约束优化问题的经典算法.它具有单步计算量低等优点,但其效率受步长规则影响较大.本文提出的一种新的自适应步长规则的梯度投影法.该算法一方面,它无需函数值信息;另一方面,它的步长接受规则比Armijo规则更为宽松,因而可以接受较长的步长以加速收敛.初步的数值实验表面新算法较为高效.     

有向网络分布式优化的Barzilai-Borwein梯度跟踪方法

本文研究有向网络上的分布式优化问题, 其全局目标函数是网络上所有光滑强凸局部目标函数的平均值.受Barzilai-Borwein步长改善梯度方法表现的启发, 本文提出了一种分布式Barzilai-Borwein梯度跟踪方法. 与文献中使用固定步长的分布式梯度算法不同, 所提出的方法中每个智能体利用其局部梯度信息自动地计算其步长. 通过同时使用行随机和列随机权重矩阵, 该方法避免了由特征向量估计引起的计算和通信. 当目标函数是光滑和强凸函数时, 本文证明了该算法产生的迭代序列可以线性地收敛到最优解. 对分布式逻辑回归问题的仿真结果验证了所提出的算法比使用固定步长的分布式梯度算法表现更好     

运动模糊参数的空域鉴别方法

匀速直线运动模糊图像的复原,关键在于点扩散函数参数(运动模糊方向和模糊尺度)的鉴别.为此,提出了一种运动模糊参数的空域鉴别方法,该方法利用3×3微分算子的任意方向微分功能鉴别运动方向,而后求微分图像自相关函数来鉴别运动模糊尺度.在搜索运动方向时将搜索步长分为两层,较大步长做粗略搜索,较小步长做精细搜索.仿真实验过程中,利用改进的维纳滤波器复原模糊图像,结果表明该方法计算复杂度低,鉴别精度高,复原效果好.     

Second-order derivatives of the general-purpose finite element package SEPRAN via source transformation

Second-order derivatives are crucial ingredients to a variety of numerical methods. Often, they are difficult to get with numerical differentiation by divided differencing. Automatic differentiation provides an alternative by a program transformation capable of evaluating Jacobians, Hessians, or higher-order derivatives of functions given in the form of computer programs. SEPRAN is a general-purpose finite element package written in Fortran 77 used in various scientific areas ranging from fluid dynamics to structural mechanics to electromagnetism. By transforming SEPRAN twice using the automatic differentiation tool ADIFOR, second-order derivatives are evaluated without truncation error. Numerical experiments are reported in which second-order derivatives of a flow field with respect to an inflow velocity are computed, demonstrating the feasibility of this approach.     

Performance of automatic differentiation tools in the dynamic simulation of multibody systems

Within the multibody systems literature, few attempts have been made to use automatic differentiation for solving forward multibody dynamics and evaluating its computational efficiency. The most relevant implementations are found in the sensitivity analysis field, but they rarely address automatic differentiation issues in depth. This paper presents a thorough analysis of automatic differentiation tools in the time integration of multibody systems. To that end, a penalty formulation is implemented. First, open-chain generalized positions and velocities are computed recursively, while using Cartesian coordinates to define local geometry. Second, the equations of motion are implicitly integrated by using the trapezoidal rule and a Newton–Raphson iteration. Third, velocity and acceleration projections are carried out to enforce kinematic constraints. For the computation of Newton–Raphson’s tangent matrix, instead of using numerical or analytical differentiation, automatic differentiation is implemented here. Specifically, the source-to-source transformation tool ADIC2 and the operator overloading tool ADOL-C are employed, in both dense and sparse modes. The theoretical approach is backed with the numerical analysis of a 1-DOF spatial four-bar mechanism, three different configurations of a 15-DOF multiple four-bar linkage, and a 16-DOF coach maneuver. Numerical and automatic differentiation are compared in terms of their computational efficiency and accuracy. Overall, we provide a global perspective of the efficiency of automatic differentiation in the field of multibody system dynamics.     

Efficient and accurate derivatives for a software process chain in airfoil shape optimization

When using a Newton-based numerical algorithm to optimize the shape of an airfoil with respect to certain design parameters, a crucial ingredient is the derivative of the objective function with respect to the design parameters. In large-scale aerodynamics, this objective function is an output of a computational fluid dynamics program written in a high-level programming language such as Fortran or C. Numerical differentiation is commonly used to approximate derivatives but is subject to truncation and subtractive cancellation errors. For a particular two-dimensional airfoil, we instead apply automatic differentiation to compute accurate derivatives of the lift and drag coefficients with respect to geometric shape parameters. In automatic differentiation, a given program is transformed into another program capable of computing the original function together with its derivatives. In the problem at hand, the objective function consists of a sequence of programs: a MATLAB program followed by two Fortran 77 programs. It is shown how automatic differentiation is applied to a sequence of programs while keeping the computational complexity within reasonable limits. The derivatives computed by automatic differentiation are compared with approximations based on divided differences.     

The problem of possibilistic-probabilistic optimization

This paper studies the models and methods for solving optimization problems with hybrid possibilistic-probabilistic uncertainty. The models under consideration have a peculiarity that the interaction of fuzzy parameters is described by the weakest t-norm. We propose solution methods that are based on the integration of indirect optimization methods (the design of equivalent problems) and direct (stochastic quasi-gradient) optimization methods. We establish the results for the models that were not considered in the previous publications on the subject. The resulting models and methods allow us to construct the generalized portfolio analysis models that are intended for managing combined (hybrid) uncertainty.     

Exponential Taylor methods: Analysis and implementation

For the time integration of semilinear systems of differential equations, a class of multiderivative exponential integrators is considered. The methods are based on a Taylor series expansion of the semilinearity about the numerical solution, the required derivatives are computed by automatic differentiation. Inserting these derivatives into the variation-of-constants formula results in an exponential integrator which requires the action of the exponential of an augmented Jacobian only.The convergence properties of such exponential integrators are analyzed, and potential sources of numerical instabilities are identified. In particular, it is shown that local linearization gives rise to better stability for stiff problems. A number of numerical experiments illustrate the theoretical results.     

On the implementation of automatic differentiation tools

Automatic differentiation is a semantic transformation that applies the rules of differential calculus to source code. It thus transforms a computer program that computes a mathematical function into a program that computes the function and its derivatives. Derivatives play an important role in a wide variety of scientific computing applications, including numerical optimization, solution of nonlinear equations, sensitivity analysis, and nonlinear inverse problems. We describe the forward and reverse modes of automatic differentiation and provide a survey of implementation strategies. We describe some of the challenges in the implementation of automatic differentiation tools, with a focus on tools based on source transformation. We conclude with an overview of current research and future opportunities.     

Two adaptive Gauss-Legendre type algorithms for the verified computation of definite integrals

We propose a two algorithms for computation of (sharp) enclosures of definite interevals: alocal adaptive algorithm (LAA) and aglobal adaptive algorithm (GAA). Both algorithms are based on Gauss-Legendre quadrature. Error terms are bounded using automatic differentiation in combination with interval evaluations. Several numerical examples are presented; these examples include comparison with an adaptive interval Romberg scheme.     

Looking for narrow interfaces in automatic differentiation using graph drawing

Automatic differentiation is a powerful technique for evaluating derivatives of functions given in the form of a high-level programming language such as Fortran, C, or C++. This technique is superior, in terms of accuracy, to numerical differentiation because it avoids the truncation error involved in divided difference approximations. In automatic differentiation, the program is treated as a potentially very long composition of elementary functions to which the chain rule of differential calculus is applied over and over again. Because of the associativity of the chain rule, there is room for different strategies computing the same numerical results but whose computational cost may vary significantly. Several strategies exploiting high-level structure of the underlying computer code are known to reduce computational cost as opposed to blindly applying automatic differentiation. An example includes “interface contraction” where one takes advantage of the fact that the number of variables passed between subroutines is small compared with the number of propagated directional derivatives. Unfortunately, these so-called narrow interfaces are not immediately available. The present study investigates the use of the VCG graph drawing tool to recognize narrow interfaces in the computational graph, a certain directed acyclic graph used to represent data dependences of variables in the underlying computer code.     

Shape design sensitivity analysis of nonlinear structural systems

A unified approach is presented for shape design sensitivity analysis of nonlinear structural systems that include trusses and beams. Both geometric and material nonlinearities are considered. Design variables that specify the shape of components of built-up structures are treated, using the continuum equilibrium equations and the material derivative concept. To best utilize the basic character of the finite element method, shape design sensitivity information is expressed as domain integrals. For numerical evaluation of shape design sensitivity expressions, two alternative methods are presented: the adjoint variable and direct differentiation methods. Advantages and disadvantages of each method are discussed. Using the domain formulation of shape design sensitivity analysis, and the adjoint variable and direct differentiation methods, design sensitivity expressions are derived in the continuous setting in terms of shape design variations. A numerical method to implement the shape design sensitivity analysis, using established finite element codes, is discussed. Unlike conventional methods, the current approach does not require differentiation of finite element stiffness and mass matrices.