从数值最优化方法到学习最优化方法

传统最优化问题的求解方法主要是以梯度法为基础的数值最优化方法,它是解析与数值计算相结合的迭代求解方法,是一种基于固定模式的最优化方法.算法的迭代过程实质上是对迭代点进行非线性变换的过程,该非线性变换是通过一系列方向和步长来实现.对于最优化问题的每一个实例,都需要从头到尾执行整个算法,计算复杂度是固定的.一旦算法被程序实现,算法的效率(计算精度和复杂度)就被固定.人工智能解决问题的方法都具有学习功能.随着人工智能,特别是深度学习的兴起,学习类方法在一些领域取得了巨大的成功,如图像识别(特别是人脸识别、车牌识别、手写字符识别等)、网络攻击防范、自然语言处理、自动驾驶、金融、医疗等.本文从新的视角研究传统的数值最优化方法和智能优化方法,分析其特点,由此引出学习最优化方法,并对它们进行了对比,提出了学习最优化方法的设计思路.最后,以组合最优化为例,对该类方法的设计原理进行阐述.     

基于信赖域技术的处理带线性约束优化的内点算法

基于信赖域技术,本文提出了一个求解带线性等式和非负约束优化问题的内点算法,其特点是:为了求得搜索方向,算法在每一步迭代时仅需要求解一线性方程组系统,从而避免了求解带信赖域界的子问题,然后利用非精确的Armijo线搜索法来得到下一个迭代内点. 从数值计算的观点来看,这种技巧可减少计算量.在适当的条件下,文中还证明了该算法所产生的迭代序列的每一个聚点都是原问题的KKT点.     

随机椭圆最优控制问题的随机配置方法

本文讨论求解随机系数泊松方程约束最优控制问题的有效数值方法.通过应用有限元方法和随机配置法,将原最优控制问题离散转化为最优化问题,再利用交替方向乘子法求解最优化问题.之后,对所提出的算法进行了收敛性分析,并通过数值实验验证了算法的有效性.     

解无约束优化问题的一个新的带线搜索的信赖域算法

在传统信赖域方法的基础上, 提出了求解无约束最优化问题的一个新的带线搜索的信赖域算法. 该算法采用大步长 Armijo 线搜索技术获得迭代步长, 克服了每次迭代求解信赖域子问题时计算量较大的缺点, 因而适用于求解大型的优化问题. 在适当的条件下, 我们证明了算法的全局收敛性. 数值实验结果表明本文所提出的算法是有效的.     

退化抛物型方程的一个初值反演问题

研究了一类重构退化抛物型方程初值的反问题.这类问题在应用科学的若干领域有着重要的应用.数值求解该问题的关键是构造相应正问题的高阶差分格式.然而,由于退化边界上的主项系数为零,目前广泛用于求解经典热传导方程的虚拟点法不能应用于该模型.该文提出了一种构造二阶精度差分格式的新方法,并证明了该方法的稳定性和收敛性.为了加快收敛速度,采用共轭梯度法求逆问题的数值解,并对算法的效率和精度进行了数值验证.     

解非线性约束方程的拉格朗日全局投影方法

基于最优化方法求解约束非线性方程组的一个突出困难是计算 得到的仅是该优化问题的稳定点或局部极小点,而非方程组的解点.由此引出的问题是如何从一个稳定点出发得到一个相对于方程组解更好的点. 该文采用投影型算法,推广了Nazareth-Qi$^{[8,9]}$ 求解无约束非线性方程组的拉格朗日全局算法(Lagrangian Global-LG)于约束方程上; 理论上证明了从优化问题的稳定点出发,投影LG方法可寻找到一个更好的点. 数值试验证明了LG方法的有效性.     

竞争市场均衡问题的内点算法

本文应用最优化方法求解经济学中的经典问题-竞争市场均衡问题.本文对Ye的算法(Ye首先提出了解Fisher问题的原始-对偶路径跟踪算法)做了改进,分别给出了步长调整和迭代方向分解后的原始-对偶路径跟踪算法,并对算法做了理论证明和复杂性分析.最后分析了初始点的求法,做了初步的数值计算.计算结果表明算法能在有效时间内求得问题的解.     

多目标最优化的一种积分型实现算法

在文[1]中给出了求解多目标最优化的一种积分总极值的概念性算法．本文利用数论中的一致分布佳点集列，较为简便的得出了多目标最优化的积分总极值的实现算法和算法终止准则．并经过有关函数数值计算表明该算法是有效的，可用来求解多目标最优化问题的有效解．     

凸二次函数优化问题在快速多极边界元法中的应用

利用快速多极边界元法(FMM-BEM)求解大规模工程问题最终结为稀疏线性方程组的求解,因此,采用更好的方法求解线性方程组可以提高边界元法的计算效率.本文利用最优化数值技术处理,将稀疏线性方程组的求解等价为求解一个凸二次函数极小化的问题,并利用最优化理论及相关数学理论证明了其解的存在唯一性,为该理论的形成和发展奠定了理论基础.     

无网格介点法:一种具有h-p-d适应性的无网格法

提出了一种新型无网格法,即无网格介点(MIP)法.MIP法采用移动最小二乘核近似,有利于提高数值方法的计算稳定性,而且算法更为简便.MIP法采用局部介点近似技术,使得这种方法不仅具有一般的h适应性,而且具有p-d适应性,从而使方法在数值实施上更具有灵活性.数值算例结果表明,MIP法具有计算简单,效率高,精度高的优点,而且显示出对多种求解问题具有广泛适用的特性.     

Investigation of various solution strategies for the time-spectral method for incompressible,viscous flows

Time-spectral methods show a huge potential for decreasing computation time of time-periodic flows. While time-spectral methods are often used for compressible flows, applications to incompressible flows are rare. This paper presents an extension of the time-spectral method (TSM) to incompressible, viscous fluid flows using a pressure-correction algorithm in a finite volume flow solver.Several algorithmic treatments of the time-spectral operator in a pressure-correction algorithm have been investigated. Initially the single time instances were solved using the Jacobi method as preconditioner. While the existing fluid code is easily adapted, the solver shows a fast degradation in stability. Thus the solution matrix was reordered with respect to time and a block Gauss–Seidel preconditioner was applied. The single time blocks were directly solved using the Cholesky algorithm. The solver is more robust, but the current implementation is inefficient. To alleviate this problem an approach, coupling all time instances and control volumes, was developed. For the complete time and spatial system two different treatments in the preconditioner were researched.To outline the advantages and disadvantages of the proposed solution strategies the laminar flow around the pitching NACA0012 airfoil was investigated. Moreover, unsteady simulations using first and second order time-stepping techniques were used and the time-spectral results were compared to regular time-stepping approaches. It is shown that the time-spectral implementations solving the whole temporal-spatial system are faster than the regular time-stepping schemes. The efficiency of the time-spectral solver decreases with increasing number of harmonics. Furthermore, with a small number of harmonics the lift coefficient over time is not accurately predicted.     

Matrix-free monolithic homotopy continuation with application to computational aerodynamics

A matrix-free monolithic homotopy continuation algorithm is developed which allows for approximate numerical solutions to nonlinear systems of equations without the need to solve a linear system, thereby avoiding the formation of any Jacobian or preconditioner matrices. The algorithm can converge from an arbitrary starting guess, under suitable conditions, and can give a sufficiently accurate approximation to the converged solution such that a rapid locally convergent method such as Newton’s method will converge successfully. Several forms of the algorithm are presented, as are augmentations to the algorithms which can lead to improved efficiency or stability. The method is validated and the stability and efficiency are investigated numerically based on a computational aerodynamics flow solver.     

Domain Decomposition Preconditioners for Discontinuous Galerkin Discretizations of Compressible Fluid Flows

In this article we consider the application of Schwarz-type domain decomposition preconditioners to the discontinuous Galerkin finite element approximation of the compressible Navier-Stokes equations. To discretize this system of conservation laws, we exploit the (adjoint consistent) symmetric version of the interior penalty discontinuous Galerkin finite element method. To define the necessary coarse-level solver required for the definition of the proposed preconditioner, we exploit ideas from composite finite element methods, which allow for the definition of finite element schemes on general meshes consisting of polygonal (agglomerated) elements. The practical performance of the proposed preconditioner is demonstrated for a series of viscous test cases in both two- and three-dimensions.     

Multiscale Domain Decomposition Methods for Elliptic Problems with High Aspect Ratios

Abstract In this paper we study some nonoverlapping domain decomposition methods for solving a classof elliptic problems arising from composite materials and flows in porous media which contain many spatialscales. Our preconditioner differs from traditional domain decomposition preconditioners by using a coarsesolver which is adaptive to small scale heterogeneous features. While the convergence rate of traditional domaindecomposition algorithms using coarse solvers based on linear or polynomial interpolations may deteriorate inthe presence of rapid small scale oscillations or high aspect ratios, our preconditioner is applicable to multiple-scale problems without restrictive assumptions and seems to have a convergence rate nearly independent ofthe aspect ratio within the substructures. A rigorous convergence analysis based on the Schwarz framework iscarried out, and we demonstrate the efficiency and robustness of the proposed preconditioner through numericalexperiments which include problems with multipl     

An algebraic multifrontal preconditioner that exploits the low‐rank property

We present an algebraic structured preconditioner for the iterative solution of large sparse linear systems. The preconditioner is based on a multifrontal variant of sparse LU factorization used with nested dissection ordering. Multifrontal factorization amounts to a partial factorization of a sequence of logically dense frontal matrices, and the preconditioner is obtained if structured factorization is used instead. This latter exploits the presence of low numerical rank in some off‐diagonal blocks of the frontal matrices. An algebraic procedure is presented that allows to identify the hierarchy of the off‐diagonal blocks with low numerical rank based on the sparsity of the system matrix. This procedure is motivated by a model problem analysis, yet numerical experiments show that it is successful beyond the model problem scope. Further aspects relevant for the algebraic structured preconditioner are discussed and illustrated with numerical experiments. The preconditioner is also compared with other solvers, including the corresponding direct solver. Copyright © 2015 John Wiley & Sons, Ltd.     

Banded target matrices and recursive FSAI for parallel preconditioning

In this paper we propose a parallel preconditioner for the CG solver based on successive applications of the FSAI preconditioner. We first compute an FSAI factor G _out for coefficient matrix A, and then another FSAI preconditioner is computed for either the preconditioned matrix $S = G_{\rm out} A G_{\rm out}^T$ or a sparse approximation of S. This process can be iterated to obtain a sequence of triangular factors whose product forms the final preconditioner. Numerical results onto large SPD matrices arising from geomechanical models account for the efficiency of the proposed preconditioner which provides a reduction of the iteration number and of the CPU time of the iterative phase with respect to the original FSAI preconditioner. The proposed preconditioner reveals particularly efficient for accelerating an iterative procedure to find the smallest eigenvalues of SPD matrices, where the increased setup cost of the RFSAI preconditioner does not affect the overall performance, being a small percentage of the total CPU time.     

A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems

We present a parallel preconditioned iterative solver for large sparse symmetric positive definite linear systems. The preconditioner is constructed as a proper combination of advanced preconditioning strategies. It can be formally seen as being of domain decomposition type with algebraically constructed overlap. Similar to the classical domain decomposition technique, inexact subdomain solvers are used, based on incomplete Cholesky factorization. The proper preconditioner is shown to be near optimal in minimizing the so‐called K‐condition number of the preconditioned matrix. The efficiency of both serial and parallel versions of the solution method is illustrated on a set of benchmark problems in linear elasticity. Copyright © 2002 John Wiley & Sons, Ltd.     

Augmented Lagrangian-based preconditioners for steady buoyancy driven flow

In this paper, we apply the augmented Lagrangian (AL) approach to steady buoyancy driven flow problems. Two AL preconditioners are developed based on the variable’s order, specifically whether the leading variable is the velocity or the temperature variable. Correspondingly, two non-augmented Lagrangian (NAL) preconditioners are also considered for comparison. An eigenvalue analysis for these two pairs of preconditioners is conducted to predict the rate of convergence for the GMRES solver. The numerical results show that the AL preconditioner pair is insensitive with respect to the mesh size, Rayleigh number, and Prandtl number in terms of GMRES iterations, resulting in a significantly more robust preconditioner pair compared to the NAL pair. Accordingly, the AL pair performs much better than the NAL pair in terms of computational time. For the AL pair, the preconditioner with velocity as the leading variable gives slightly better efficiency than the one with temperature as the leading variable.     

Preconditioning systems arising from the KKR Green function method using block-circulant matrices

Recently, a linearly scaling method for the calculation of the electronic structure based on the Korringa–Kohn–Rostoker Green function method has been proposed. The method uses the transpose free quasi minimal residual method (TFQMR) to solve linear systems with multiple right hand sides. These linear systems depend on the energy-level under consideration and the convergence rate deteriorates for some of these energy points. While traditional preconditioners like ILU are fairly useful for the problem, the computation of the preconditioner itself is often relatively hard to parallelize. To overcome these difficulties, we develop a new preconditioner that exploits the strong structure of the underlying systems. The resulting preconditioner is block-circulant and thus easy to compute, invert and parallelize. The resulting method yields a dramatic speedup of the computation compared to the unpreconditioned solver, especially for critical energy levels.     

Fast iterative solver for convection‐diffusion systems with spectral elements

We introduce a solver and preconditioning technique based on Domain Decomposition and the Fast Diagonalization Method that can be applied to tensor product based discretizations of the steady convection–diffusion equation. The method is based on a Robin–Robin interface preconditioner coupled to a fast diagonalization solver which is used to efficiently eliminate the interior degrees of freedom and perform subsidiary subdomain solves. Using a spectral element discretization, we first apply our technique to constant wind problems, and then propose a means for applying the technique as a preconditioner for variable wind problems. We demonstrate that iteration counts are mildly dependent on changes in mesh size and convection strength. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011