The Adjoint Newton Algorithm for Large-Scale Unconstrained Optimization in Meteorology Applications

A new algorithm is presented for carrying out large-scale unconstrained optimization required in variational data assimilation using the Newton method. The algorithm is referred to as the adjoint Newton algorithm. The adjoint Newton algorithm is based on the first- and second-order adjoint techniques allowing us to obtain the Newton line search direction by integrating a tangent linear equations model backwards in time (starting from a final condition with negative time steps). The error present in approximating the Hessian (the matrix of second-order derivatives) of the cost function with respect to the control variables in the quasi-Newton type algorithm is thus completely eliminated, while the storage problem related to the Hessian no longer exists since the explicit Hessian is not required in this algorithm. The adjoint Newton algorithm is applied to three one-dimensional models and to a two-dimensional limited-area shallow water equations model with both model generated and First Global Geophysical Experiment data. We compare the performance of the adjoint Newton algorithm with that of truncated Newton, adjoint truncated Newton, and LBFGS methods. Our numerical tests indicate that the adjoint Newton algorithm is very efficient and could find the minima within three or four iterations for problems tested here. In the case of the two-dimensional shallow water equations model, the adjoint Newton algorithm improves upon the efficiencies of the truncated Newton and LBFGS methods by a factor of at least 14 in terms of the CPU time required to satisfy the same convergence criterion.The Newton, truncated Newton and LBFGS methods are general purpose unconstrained minimization methods. The adjoint Newton algorithm is only useful for optimal control problems where the model equations serve as strong constraints and their corresponding tangent linear model may be integrated backwards in time. When the backwards integration of the tangent linear model is ill-posed in the sense of Hadamard, the adjoint Newton algorithm may not work. Thus, the adjoint Newton algorithm must be used with some caution. A possible solution to avoid the current weakness of the adjoint Newton algorithm is proposed.     

Truncated Newton method for sparse unconstrained optimization using automatic differentiation

When solving large complex optimization problems, the user is faced with three major problems. These are (i) the cost in human time in obtaining accurate expressions for the derivatives involved; (ii) the need to store second derivative information; and (iii), of lessening importance, the time taken to solve the problem on the computer. For many problems, a significant part of the latter can be attributed to solving Newton-like equations. In the algorithm described, the equations are solved using a conjugate direction method that only needs the Hessian at the current point when it is multiplied by a trial vector. In this paper, we present a method that finds this product using automatic differentiation while only requiring vector storage. The method takes advantage of any sparsity in the Hessian matrix and computes exact derivatives. It avoids the complexity of symbolic differentiation, the inaccuracy of numerical differentiation, the labor of finding analytic derivatives, and the need for matrix store. When far from a minimum, an accurate solution to the Newton equations is not justified, so an approximate solution is obtained by using a version of Dembo and Steihaug's truncated Newton algorithm (Ref. 1).This paper was presented at the SIAM National Meeting, Boston, Massachusetts, 1986.     

四种无约束优化算法的比较研究

从数值试验的角度 ,通过对 3个测试问题 (其中构造了一个规模大小可变的算例 )的求解 ,对共轭梯度法、BFGS拟牛顿法、DFP拟牛顿法和截断牛顿法进行比较研究 ,根据测试结果的分析 ,显示截断牛顿法在求解大规模优化问题时具有优势 ,从而为大规模寻优算法的研究提供了有益的借鉴 .     

Inexactly constrained discrete adjoint approach for steepest descent-based optimization algorithms

The problem of constrained optimization via the gradient-based discrete adjoint steepest descent method is studied under the assumption that the constraint equations are solved inexactly. Error propagation from the constraint equations to the gradient is studied analytically, as is the convergence rate of the inexactly constrained algorithm as it relates to the exact algorithm. A method is developed for adapting the residual tolerance to which the constraint equations are solved. The adaptive tolerance method is applied to two simple test cases to demonstrate the potential gains in computational efficiency.     

Approximation design of optimal controllers for nonlinear systems with sinusoidal disturbances

This paper considers an infinite-time optimal damping control problem for a class of nonlinear systems with sinusoidal disturbances. A successive approximation approach (SAA) is applied to design feedforward and feedback optimal controllers. By using the SAA, the original optimal control problem is transformed into a sequence of nonhomogeneous linear two-point boundary value (TPBV) problems. The existence and uniqueness of the optimal control law are proved. The optimal control law is derived from a Riccati equation, matrix equations and an adjoint vector sequence, which consists of accurate linear feedforward and feedback terms and a nonlinear compensation term. And the nonlinear compensation term is the limit of the adjoint vector sequence. By using a finite term of the adjoint vector sequence, we can get an approximate optimal control law. A numerical example shows that the algorithm is effective and robust with respect to sinusoidal disturbances.     

Accelerated conjugate gradient algorithm with finite difference Hessian/vector product approximation for unconstrained optimization

In this paper we propose a fundamentally different conjugate gradient method, in which the well-known parameter β_k is computed by an approximation of the Hessian/vector product through finite differences. For search direction computation, the method uses a forward difference approximation to the Hessian/vector product in combination with a careful choice of the finite difference interval. For the step length computation we suggest an acceleration scheme able to improve the efficiency of the algorithm. Under common assumptions, the method is proved to be globally convergent. It is shown that for uniformly convex functions the convergence of the accelerated algorithm is still linear, but the reduction in function values is significantly improved. Numerical comparisons with conjugate gradient algorithms including CONMIN by Shanno and Phua [D.F. Shanno, K.H. Phua, Algorithm 500, minimization of unconstrained multivariate functions, ACM Trans. Math. Softw. 2 (1976) 87–94], SCALCG by Andrei [N. Andrei, Scaled conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl. 38 (2007) 401–416; N. Andrei, Scaled memoryless BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Optim. Methods Softw. 22 (2007) 561–571; N. Andrei, A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization, Appl. Math. Lett. 20 (2007) 645–650], and new conjugacy condition and related new conjugate gradient by Li, Tang and Wei [G. Li, C. Tang, Z. Wei, New conjugacy condition and related new conjugate gradient methods for unconstrained optimization, J. Comput. Appl. Math. 202 (2007) 523–539] or truncated Newton TN by Nash [S.G. Nash, Preconditioning of truncated-Newton methods, SIAM J. on Scientific and Statistical Computing 6 (1985) 599–616] using a set of 750 unconstrained optimization test problems show that the suggested algorithm outperforms these conjugate gradient algorithms as well as TN.     

基于非均匀参数化的自由终端时间最优控制问题求解

针对自由终端时间最优控制问题,提出了一种基于非均匀控制向量参数化的数值解法.将控制时域离散化为不同长度的时间段,各时间段长度作为新的控制变量.通过引入标准化的时间变量,原问题转化为均匀参数化的固定终端时间最优控制问题.建立目标和约束函数的Hamilton函数,通过求解伴随方程获得目标和约束函数的梯度,采用序列二次规划(SQP)获得数值解.针对两个经典的化工过程自由终端时间最优控制问题进行仿真研究,验证了所提出算法的可行性和有效性.     

Computing hyperbolic choreographies

An algorithm is presented for numerical computation of choreographies in spaces of constant negative curvature in a hyperbolic cotangent potential, extending the ideas given in a companion paper [14] for computing choreographies in the plane in a Newtonian potential and on a sphere in a cotangent potential. Following an idea of Diacu, Pérez-Chavela and Reyes Victoria [9], we apply stereographic projection and study the problem in the Poincaré disk. Using approximation by trigonometric polynomials and optimization methods with exact gradient and exact Hessian matrix, we find new choreographies, hyperbolic analogues of the ones presented in [14]. The algorithm proceeds in two phases: first BFGS quasi-Newton iteration to get close to a solution, then Newton iteration for high accuracy.     

An exact algorithm for graph partitioning

An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.     

A method of computing the gradient and the Hessian of the quality criterion in parametric optimization of continuous-discrete stochastic systems

We propose an effective method of numerical determination of the gradient vector and the Hessian matrix of a quadratic quality criterion in parametric optimization of continuous-discrete stochastic dynamic control systems based on the application of adjoint equations. Translated fromDinamicheskie Sistemy, No. 13, 1994, pp. 20–25.     

A method of adjoint operators for solving boundary value problems for second-order ordinary differential equations

In this paper, for a linear boundary value problem we propose a method that reduces the differential problem to a discrete (difference) problem. The difference equations, which are an exact analog of the differential equation, are constructed by an adjoint operator method. The adjoint equations are solved by a factorization method.     

关于多裂纹圆柱体的扭转*

本文在文[1]基础上,导出了含有任意分布裂纹系的圆柱扭曲函数的解析表达式,从而把问题化为以未知位错密度函数表示的奇异积分方程组.文中利用奇异积分方程的数值方法[2,7],对带有多根裂纹的圆柱的抗扭刚度和应力强度因子作了若干数值计算.此外,本文还首次将裂纹切割法[5]推广用于求解矩形柱的扭转,数值结果表明方法是成功的.     

一个高精度收敛的变系数微分方程精确解析法*

文[1]给出精确解析法,可用于求解任意变系数微分方程,所得到的解具有二阶收敛精度.在此基础上,本文以变截面梁弯曲为例,给出一个高精度的算法.不增加工作量的情况下可达到四阶收敛精度.具有计算快,简单等特点,文末给出算例,仅用很少的单元即可获得高的收敛精度,表明了本文理论的正确性.     

Oscillations of mechanical systems that do not become linear when the parameter vanishes : PMM vol. 42, no. 6, 1978, pp. 1039–1048

The results of investigations in [1] are extended to multidimensional systems that become nonlinear at μ = 0. Two-dimensional mechanical systems were investigated in [2,3]. The characteristic equations of systems considered here contain in the critical system either a pair of pure imaginary roots or two zero roots with one or two groups of solutions and n roots with negative real parts in the adjoint system. It is shown that the investigation of such systems necessitates the imposition on the system of some constraints that supplement those specified in [1], The auxilliary function u⁽¹⁾_k (θ) used in the determination of Liapunov's function is derived by a different method than in [1 – 3], In two of the three investigated cases the problem is reduced to the determination of roots of some integral real irrational function. An example is presented.     

Fast sensitivity analysis of defective system

Sensitivity analysis of linear vibration system is of wide interest. In this paper, sensitivity analysis based on non-defective system and defective system is summarized in all cases. Specially, for the defective systems, a fast method for the perturbation problem of state vectors is constructed in terms of the theories of generalized eigenvectors and adjoint matrices. By this method, the state vector derivatives can be expressed by a linear combination of generalized eigenvectors. The expansion coefficients can be obtained without solving large-scale equations based on eigensolutions of original system. Numerical results demonstrate the effectiveness and the stability of the method.     

Singular solution to the problem of minimizing resource consumption

An iterative method of finding a singular solution to the problem of minimizing resource consumption has been developed. This method is based on the information about the finite control structure. A condition for existence of a singular solution is obtained. The limit value for transferring the time between the normal and the singular solutions is found. A relation between the variations of the control switching instants and the variations of the initial conditions of the adjoint system is found. A system of linear algebraic equations relating the variations of the initial conditions of the adjoint system to the deviations of the phase coordinates from a given final state of the system is obtained. The calculation algorithm and the results of modeling and numerical calculations are presented.     

Shape Optimal Design Problem with Convective and Radiative Heat Transfer: Analysis and Implementation

We present a study of an optimal design problem for a coupled system, governed by a steady-state potential flow equation and a thermal equation taking into account radiative phenomena with multiple reflections. The state equation is a nonlinear integro-differential system. We seek to minimize a cost function, depending on the temperature, with respect to the domain of the equations. First, we consider an optimal design problem in an abstract framework and, with the help of the classical adjoint state method, give an expression of the cost function differential. Then, we apply this result in the two-dimensional case to the nonlinear integro-differential system considered. We prove the differentiability of the cost function, introduce the adjoint state equation, and give an expression of its exact differential. Then, we discretize the equations by a finite-element method and use a gradient-type algorithm to decrease the cost function. We present numerical results as applied to the automotive industry.     

Numerical solution of the optimal boundary control of transverse vibrations of a beam

Boundary control is an effective means for suppressing excessive structural vibrations. By introducing a quadratic index of performance in terms of displacement and velocity, as well as the control force, and an adjoint problem, it is possible to determine the optimal control. This optimal control is expressed in terms of the adjoint variable by utilizing a maximum principle. With the optimal control applied, the determination of the corresponding displacement and velocity is reduced to solving a set of partial differential equations involving the state variable, as well as the adjoint variable, subject to boundary, initial, and terminal conditions. The set of equations may not be separable and analytical solutions may only be found in special cases. Furthermore, the computational effort to determine an analytic solution may also be excessive. Herein a numerical algorithm is presented, which easily solves the optimal boundary control problem in the space‐time domain. An example of a continuous system is analyzed. This is the case of the vibrating cantilever beam. Using a finite element recurrence scheme, numerical solutions are obtained, which compare the behavior of the controlled and uncontrolled systems. Also, the analytic solution to the problem is compared with the results obtained using the numerical scheme presented. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 558–568, 1999     

A Method for Solving Exact Solution to Two－dimensional Korteweg－de Vires－Burgers Equation

ＡＭｅｔｈｏｄｆｏｒＳｏｌｖｉｎｇＥｘａｃｔＳｏｌｕｔｉｏｎｔｏＴｗｏ－ｄｉｍｅｎｓｉｏｎａｌＫｏｒｔｅｗｅｇ－ｄｅＶｉｒｅｓ－ＢｕｒｇｅｒｓＥｑｕａｔｉｏｎＪｉａｎｇＷｅｉｌｉｎ（姜伟林）ＺｈａｎｇＪｉｅｆａｎｇ（张解放）（ＨｅｎａｎＵｎｉｖｅｒｓ...     

Compact gradient tracking in shape optimization

In the present paper we consider the minimization of gradient tracking functionals defined on a compact and fixed subdomain of the domain of interest. The underlying state is assumed to satisfy a Poisson equation with Dirichlet boundary conditions. We proof that, in contrast to the situation of gradient tracking on the whole domain, the shape Hessian is not strictly H ^1/2-coercive at the optimal domain which implies ill-posedness of the shape problem under consideration. Shape functional and gradient require only knowledge of the Cauchy data of the state and its adjoint on the boundaries of the domain and the subdomain. These data can be computed by means of boundary integral equations when reformulating the underlying differential equations as transmission problems. Thanks to fast boundary element techniques, we derive an efficient algorithm to solve the problem under consideration.