Descent Direction Stochastic Approximation Algorithm with Adaptive Step Sizes

A stochastic approximation (SA) algorithm with new adaptive step sizes for solving unconstrained minimization problems in noisy environment is proposed. New adaptive step size scheme uses ordered statistics of fixed number of previous noisy function values as a criterion for accepting good and rejecting bad steps. The scheme allows the algorithm to move in bigger steps and avoid steps proportional to $1/k$ when it is expected that larger steps will improve the performance. An algorithm with the new adaptive scheme is defined for a general descent direction. The almost sure convergence is established. The performance of new algorithm is tested on a set of standard test problems and compared with relevant algorithms. Numerical results support theoretical expectations and verify efficiency of the algorithm regardless of chosen search direction and noise level. Numerical results on problems arising in machine learning are also presented. Linear regression problem is considered using real data set. The results suggest that the proposed algorithm shows promise.     

A robust descent type algorithm for geophysical inversion through adaptive regularization

A robust descent type algorithm through adaptive regularization is designed to solve a geophysical inverse problem. The scheme uses a regularized descent direction which is obtained through minimization of smoothed functional in every iterative step. The step length factor is chosen using Armijo's rule. Numerical experiment conducted to invert synthetic and field geophysical data demonstrates a high order of robustness in retrieving the model parameters.     

An Adaptive Nonmonotone Projected Barzilai-Borwein Gradient Method with Active Set Prediction for Nonnegative Matrix Factorization

In this paper, we first present an adaptive nonmonotone term to improve the efficiency of nonmonotone line search, and then an active set identification technique is suggested to get more efficient descent direction such that it improves the local convergence behavior of algorithm and decreases the computation cost. By means of the adaptive nonmonotone line search and the active set identification technique, we put forward a global convergent gradient-based method to solve the nonnegative matrix factorization (NMF) based on the alternating nonnegative least squares framework, in which we introduce a modified Barzilai-Borwein (BB) step size. The new modified BB step size and the larger step size strategy are exploited to accelerate convergence. Finally, the results of extensive numerical experiments using both synthetic and image datasets show that our proposed method is efficient in terms of computational speed.     

求解阵列天线自适应滤波问题的一种调比随机逼近算法

提出了求解阵列天线自适应滤波问题的一种调比随机逼近算法.每一步迭代中,算法选取调比的带噪负梯度方向作为新的迭代方向.相比已有的其他随机逼近算法,这个算法不需要调整稳定性常数,在一定程度上解决了稳定性常数选取难的问题.数值仿真实验表明,算法优于已有的滤波算法,且比经典Robbins-Monro （RM）算法具有更好的稳定性.     

CFD-based optimization of fuel injection strategies in a diesel engine using an adaptive gradient method

A computationally efficient computational fluid dynamics (CFD)-based optimization method with the capability of finding optimal engine operating conditions with respect to emissions and fuel consumption has been developed. The approach taken uses a steepest descent method for an adaptive cost function, where the line search is performed with a backtracking algorithm. The backtracking algorithm utilizes quadratic and cubic polynomials to accelerate the convergence, and the initial backtracking step employs an adaptive step size mechanism which depends on the steepness of the search direction. The adaptive cost function is based on the penalty method such that the penalty term is stiffened after every line search. The engine simulations are performed with a KIVA-3-based CFD code which is equipped with well-established spray, combustion and emission models. The application of this optimization tool is demonstrated for a non-road, medium-speed DI diesel engine which, for these simulations, utilizes a multi-orifice, asynchronous injection system. It has been demonstrated that this new injection method has a large potential for reducing emissions while maintaining a low fuel consumption. In addition, this optimization approach is computationally very efficient when good enough initial values are available.     

A shift‐adaptive meshfree method for solving a class of initial‐boundary value problems with moving boundaries in one‐dimensional domain

A new shift‐adaptive meshfree method for solving a class of time‐dependent partial differential equations (PDEs) in a bounded domain (one‐dimensional domain) with moving boundaries and nonhomogeneous boundary conditions is introduced. The radial basis function (RBF) collocation method is combined with the finite difference scheme, because, unlike with Kansa's method, nonlinear PDEs can be converted to a system of linear equations. The grid‐free property of the RBF method is exploited, and a new adaptive algorithm is used to choose the location of the collocation points in the first time step only. In fact, instead of applying the adaptive algorithm on the entire domain of the problem (like with other existing adaptive algorithms), the new adaptive algorithm can be applied only on time steps. Furthermore, because of the radial property of the RBFs, the new adaptive strategy is applied only on the first time step; in the other time steps, the adaptive nodes (obtained in the first time step) are shifted. Thus, only one small system of linear equations must be solved (by LU decomposition method) rather than a large linear or nonlinear system of equations as in Kansa's method (adaptive strategy applied to entire domain), or a large number of small linear systems of equations in the adaptive strategy on each time step. This saves a lot in time and memory usage. Also, Stability analysis is obtained for our scheme, using Von Neumann stability analysis method. Results show that the new method is capable of reducing the number of nodes in the grid without compromising the accuracy of the solution, and the adaptive grading scheme is effective in localizing oscillations due to sharp gradients or discontinuities in the solution. The efficiency and effectiveness of the proposed procedure is examined by adaptively solving two difficult benchmark problems, including a regularized long‐wave equation and a Korteweg‐de Vries problem. © 2016Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1622–1646, 2016     

An adaptive discretization algorithm for the weak approximation of stochastic differential equations

Numerical methods with fixed step size have limitations if they are applied for example to stiff stochastic differential equations where the step size is forced to be very small. In this paper, an adaptive step size control algorithm for the weak approximation of stochastic differential equations is introduced. The proposed algorithm calculates an estimation of the local error in order to determine the optimal step size such that the local error is bounded by some given tolerances. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Local Convergence of the Affine-Scaling Interior-Point Algorithm for Nonlinear Programming

This paper addresses the local convergence properties of the affine-scaling interior-point algorithm for nonlinear programming. The analysis of local convergence is developed in terms of parameters that control the interior-point scheme and the size of the residual of the linear system that provides the step direction. The analysis follows the classical theory for quasi-Newton methods and addresses q-linear, q-superlinear, and q-quadratic rates of convergence.     

An adaptive finite element algorithm with reliable and efficient error control for linear parabolic problems

An efficient and reliable a posteriori error estimate is derived for linear parabolic equations which does not depend on any regularity assumption on the underlying elliptic operator. An adaptive algorithm with variable time-step sizes and space meshes is proposed and studied which, at each time step, delays the mesh coarsening until the final iteration of the adaptive procedure, allowing only mesh and time-step size refinements before. It is proved that at each time step the adaptive algorithm is able to reduce the error indicators (and thus the error) below any given tolerance within a finite number of iteration steps. The key ingredient in the analysis is a new coarsening strategy. Numerical results are presented to show the competitive behavior of the proposed adaptive algorithm.

     

An Adaptive Fast Interface Tracking Method

An adaptive numerical scheme is developed for the propagation of an interface in a velocity field based on the fast interface tracking method proposed in [2]. A multiresolution stategy to represent the interface instead of point values, allows local grid refinement while controlling the approximation error on the interface. For time integration, we use an explicit Runge-Kutta scheme of second-order with a multiscale time step, which takes longer time steps for finer spatial scales. The implementation of the algorithm uses a dynamic tree data structure to represent data in the computer memory. We briefly review first the main algorithm, describe the essential data structures, highlight the adaptive scheme, and illustrate the computational efficiency by some numerical examples.     

A primal—dual affine-scaling potential-reduction algorithm for linear programming

We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A new regularized quasi-Newton method for unconstrained optimization

In this paper, we propose a new regularized quasi-Newton method for unconstrained optimization. At each iteration, a regularized quasi-Newton equation is solved to obtain the search direction. The step size is determined by a non-monotone Armijo backtracking line search. An adaptive regularized parameter, which is updated according to the step size of the line search, is employed to compute the next search direction. The presented method is proved to be globally convergent. Numerical experiments show that the proposed method is effective for unconstrained optimizations and outperforms the existing regularized Newton method.     

A linearized difference scheme for semilinear parabolic equations with nonlinear absorbing boundary conditions

A novel three level linearized difference scheme is proposed for the semilinear parabolic equation with nonlinear absorbing boundary conditions. The solution of this problem will blow up in finite time. Hence this difference scheme is coupled with an adaptive time step size, i.e., when the solution tends to infinity, the time step size will be smaller and smaller. Furthermore, the solvability, stability and convergence of the difference scheme are proved by the energy method. Numerical experiments are also given to demonstrate the theoretical second order convergence both in time and in space in L_∞-norm.     

Adaptive finite element procedures for elastoplastic problems at finite strains

A major difficulty in the context of adaptive analysis of geometrically nonlinear problems is to provide a robust remeshing procedure that accounts both for the error caused by the spatial discretization and for the error due to the time discretization. For stability problems, such as strain localization and necking, it is essential to provide a step–size control in order to get a robust algorithm for the solution of the boundary value problem. For this purpose we developed an easy to implement step–size control algorithm. In addition we will consider possible a posteriori error indicators for the spatial error distribution of elastoplastic problems at finite strains. This indicator is adopted for a density–function–based adaptive remeshing procedure. Both error indicators are combined for the adaptive analysis in time and space. The performance of the proposed method is documented by means of representative numerical examples.     

A nonparametric variable step-size NLMS algorithm for transversal filters

A nonparametric adaptive filtering approach is proposed in this paper. The algorithm is obtained by exploiting a time-varying step size in the traditional NLMS weight update equation. The step size is adjusted according to the square of a time-averaging estimate of the autocorrelation of a priori and a posteriori error. Therefore, the new algorithm has more effective sense proximity to the optimum solution independent of uncorrelated measurement noise. Moreover, this algorithm has fast convergence at the early stages of adaptation and small final misadjustment at steady-state process. It works reliably and is easy to implement since the update function is nonparametric. Furthermore, the experimental results in system identification applications are presented to illustrate the principle and efficiency of the proposed algorithm.     

An efficient step size control for continuation methods

In solving a nonlinear equation by the use of a continuation method one of the crucial problems is the choice of the step sizes. We present a model for the total computational cost of a standard numerical continuation process and solve the problem of optimal step size control for this model. Using the theoretical results as a basis, we develop an adaptive step size algorithm for Newton's method. This procedure is computationally inexpensive and it gives quite satisfactory results compared to some other numerical experiments found in the literature.     

An algorithm for linearly constrained nonlinear programming problems

In this paper an algorithm for solving a linearly constrained nonlinear programming problem is developed. Given a feasible point, a correction vector is computed by solving a least distance programming problem over a polyhedral cone defined in terms of the gradients of the “almost” binding constraints. Mukai's approximate scheme for computing the step size is generalized to handle the constraints. This scheme provides an estimate for the step size based on a quadratic approximation of the function. This estimate is used in conjunction with Armijo line search to calculate a new point. It is shown that each accumulation point is a Kuhn-Tucker point to a slight perturbation of the original problem. Furthermore, under suitable second order optimality conditions, it is shown that eventually only one trial is needed to compute the step size.     

考虑客户满意度的计划外来船靠泊调度模型及算法

为解决船舶临时请求靠港而调整调度的特殊需求,建立了以客户满意度最大和额外作业成本最小为目标的双目标优化模型,利用改进模拟植物生长算法予以求解,求解中采取确定-随机策略确定初始生长点,以固定步长和变步长混合方式构建邻域,并融入分层非支配排序方法。确定兼顾船公司和港口方利益的调度方案时,利用Pareto前沿分布特点,对船公司和港口方的偏向度进行量化,选择偏向度差值最小的方案。最后,以我国某集装箱码头为例,验证了本文模型和算法的可行性。计算结果与NSGA-II算法进行对比,证明了文中改进模拟植物生长算法的有效性。本文成果可以为提高港口管理效率提供技术支持。     

Long-term adaptive symplectic numerical integration of linear stochastic oscillators driven by additive white noise

Numerical Algorithms - In this paper, we present an adaptive variable step size numerical scheme for the integration of linear stochastic oscillator equations driven by additive Brownian white...     

An algorithm and efficient data structures for the binary knapsack problem

A branch-and-bound algorithm for the binary knapsack problem is presented which uses a combined stack and deque for storing the tree and the corresponding LP-relaxation. A reduction scheme is used to reduce the problem size. The algorithm was implemented in FORTRAN. Computational experience is based on 600 randomly generated test problems with up to 9000 zero-one variables. The average solution times (excluding an initial sorting step) increase linearly with problem size and compare favorably with other codes designed to solve binary knapsack problems.