A BFGS-SQP method for nonsmooth,nonconvex, constrained optimization and its evaluation using relative minimization profiles

We propose an algorithm for solving nonsmooth, nonconvex, constrained optimization problems as well as a new set of visualization tools for comparing the performance of optimization algorithms. Our algorithm is a sequential quadratic optimization method that employs Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton Hessian approximations and an exact penalty function whose parameter is controlled using a steering strategy. While our method has no convergence guarantees, we have found it to perform very well in practice on challenging test problems in controller design involving both locally Lipschitz and non-locally-Lipschitz objective and constraint functions with constraints that are typically active at local minimizers. In order to empirically validate and compare our method with available alternatives—on a new test set of 200 problems of varying sizes—we employ new visualization tools which we call relative minimization profiles. Such profiles are designed to simultaneously assess the relative performance of several algorithms with respect to objective quality, feasibility, and speed of progress, highlighting the trade-offs between these measures when comparing algorithm performance.     

Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions

We consider the use of a curvature-adaptive step size in gradient-based iterative methods, including quasi-Newton methods, for minimizing self-concordant functions, extending an approach first proposed for Newton's method by Nesterov. This step size has a simple expression that can be computed analytically; hence, line searches are not needed. We show that using this step size in the BFGS method (and quasi-Newton methods in the Broyden convex class other than the DFP method) results in superlinear convergence for strongly convex self-concordant functions. We present numerical experiments comparing gradient descent and BFGS methods using the curvature-adaptive step size to traditional methods on deterministic logistic regression problems, and to versions of stochastic gradient descent on stochastic optimization problems.     

Total pressure losses minimization in turbomachinery cascades using the exact Hessian

A method for the design of turbomachinery cascades with minimum total pressure losses, subject to constraints on the minimum blade thickness and flow turning, is presented. It is based on the Newton–Lagrange method which requires the computation of first- and second-order sensitivities of the objective function and the constraints, with respect to the design variables. The computation of the exact Hessian of the function which expresses the difference in total pressure between the inlet to and the outlet from the cascade, is new in the literature. To compute the Hessian, the direct differentiation of the viscous flow equations is used for the first-order sensitivities of the functional and the flow-related constraints, followed by the discrete adjoint method. Since the objective function is defined along boundaries other than those controlled by the design variables, it is challenging to investigate the significance of all terms comprising the exact second-order sensitivity expressions. All these terms were temporarily computed using automatic differentiation and those which proved to be significant are hand-differentiated to minimize CPU cost and memory requirements. Insignificant terms are eliminated, giving rise to the so-called “exact” Hessian matrix. An “exactly” initialized quasi-Newton method was also programmed and tested. In the latter, at the first cycle, the exact gradients and Hessians are computed and used; during the subsequent optimization cycles, the discrete adjoint method provides the exact gradient whereas the Hessian is updated as in quasi-Newton methods. The comparison of the efficiency of the aforementioned methods depends on the number of design variables used; the “exactly” initialized quasi-Newton method constantly outperforms its conventional variant in terms of CPU cost, particularly in non-convex and/or constrained optimization problems.     

L-Broyden methods: a generalization of the L-BFGS method to the limited-memory Broyden family

The paper derives a multiplicative update equation for the convex Broyden family of quasi-Newton (QN) updates. The well-known multiplicative Broyden-fletcher-Goldfarb-Shanno (BFGS) update is a special case of this. Using a self-scaling parameter, the formula is extended to the SR1 update. It is shown that for each Broyden update, a pair of multiplicative update formulae can be defined (coincident in the case of Davidon-fletcher-Powell (DFP)). The multiplicative updates are used to define limited-memory QN algorithms, denoted the L-Broyden methods, of which L-BFGS is a special case. Numerical results show that the L-Broyden methods are competitive with extensions of the variable storage conjugate gradients limited memory QN method to other Broyden updates, but that L-BFGS with Shanno scaling remains the most efficient and reliable method in the L-Broyden family.     

Using a spectral scaling structured BFGS method for constrained nonlinear least squares

In this paper, we use a spectral scaled structured BFGS formula for approximating projected Hessian matrices in an exact penalty approach for solving constrained nonlinear least-squares problems. We show this spectral scaling formula has a good self-correcting property. The reported numerical results show that the use of the spectral scaling structured BFGS method outperforms the standard structured BFGS method.     

Aerodynamic Shape Optimization Using First and Second Order Adjoint and Direct Approaches

This paper focuses on discrete and continuous adjoint approaches and direct differentiation methods that can efficiently be used in aerodynamic shape optimization problems. The advantage of the adjoint approach is the computation of the gradient of the objective function at cost which does not depend upon the number of design variables. An extra advantage of the formulation presented below, for the computation of either first or second order sensitivities, is that the resulting sensitivity expressions are free of field integrals even if the objective function is a field integral. This is demonstrated using three possible objective functions for use in internal aerodynamic problems; the first objective is for inverse design problems where a target pressure distribution along the solid walls must be reproduced; the other two quantify viscous losses in duct or cascade flows, cast as either the reduction in total pressure between the inlet and outlet or the field integral of entropy generation. From the mathematical point of view, the three functions are defined over different parts of the domain or its boundaries, and this strongly affects the adjoint formulation. In the second part of this paper, the same discrete and continuous adjoint formulations are combined with direct differentiation methods to compute the Hessian matrix of the objective function. Although the direct differentiation for the computation of the gradient is time consuming, it may support the adjoint method to calculate the exact Hessian matrix components with the minimum CPU cost. Since, however, the CPU cost is proportional to the number of design variables, a well performing optimization scheme, based on the exactly computed Hessian during the starting cycle and a quasi Newton (BFGS) scheme during the next cycles, is proposed.     

两相流空隙率测量的ERT技术新算法研究

基于BFGS最优化方法,提出一种新型的ERT图像重建算法:改进的BFGS算法.新算法采取了不精确搜索方向,并用单位矩阵近似代替目标函数的Hessian矩阵,以减小计算量,提高算法的重建速度.将新算法应用于两相流空隙率的测量.数值实验证明,新算法重建图像的质量优于目前常用的灵敏度系数法,空隙率测量的最大绝对误差可小于8%,获取一个空隙率测量值的时间小于0.1s.     

Structured symmetric rank-one method for unconstrained optimization

In this paper, we investigate a symmetric rank-one (SR1) quasi-Newton (QN) formula in which the Hessian of the objective function has some special structure. Instead of approximating the whole Hessian via the SR1 formula, we consider an approach which only approximates part of the Hessian matrix that is not easily acquired. Although the SR1 update possesses desirable features, it is unstable in the sense that, it may not retain positive definiteness and may become undefined. Therefore, we describe some safeguards to overcome these difficulties. Since the structured SR1 method provides a more accurate Hessian approximation, therefore the proposed method reduces significantly the computational efforts needed in solving a problem. The results of a series of experiments on a typical set of standard unconstrained optimization problems are reported, which show that the structured SR1 method exhibits a clear improvement in numerical performance over some existing QN algorithms.     

A Memetic Chaotic Gravitational Search Algorithm for unconstrained global optimization problems

Metaheuristic optimization algorithms address two main tasks in the process of problem solving: i) exploration (also called diversification) and ii) exploitation (also called intensification). Guaranteeing a trade-off between these operations is critical to good performance. However, although many methods have been proposed by which metaheuristics can achieve a balance between the exploration and exploitation stages, they are still worse than exact algorithms at exploitation tasks, where gradient-based mechanisms outperform metaheuristics when a local minimum is approximated. In this paper, a quasi-Newton method is introduced into a Chaotic Gravitational Search Algorithm as an exploitation method, with the purpose of improving the exploitation capabilities of this recent and promising population-based metaheuristic. The proposed approach, referred to as a Memetic Chaotic Gravitational Search Algorithm, is used to solve forty-five benchmark problems, both synthetic and real-world, to validate the method. The numerical results show that the adding of quasi-Newton search directions to the original (Chaotic) Gravitational Search Algorithm substantially improves its performance. Also, a comparison with the state-of-the-art algorithms: Particle Swarm Optimization, Genetic Algorithm, Rcr-JADE, COBIDE and RLMPSO, shows that the proposed approach is promising for certain real-world problems.     

An investigation of Newton-Sketch and subsampled Newton methods

ABSTRACT

Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.     

Matrix-free algorithm for the optimization of multidisciplinary systems

Multidisciplinary engineering systems are usually modeled by coupling software components that were developed for each discipline independently. The use of disparate solvers complicates the optimization of multidisciplinary systems and has been a long-standing motivation for optimization architectures that support modularity. The individual discipline feasible (IDF) formulation is particularly attractive in this respect. IDF achieves modularity by introducing optimization variables and constraints that effectively decouple the disciplinary solvers during each optimization iteration. Unfortunately, the number of variables and constraints can be significant, and the IDF constraint Jacobian required by most conventional optimization algorithms is prohibitively expensive to compute. Furthermore, limited-memory quasi-Newton approximations, commonly used for large-scale problems, exhibit linear convergence rates that can struggle with the large number of design variables introduced by the IDF formulation. In this work, we show that these challenges can be overcome using a reduced-space inexact-Newton-Krylov algorithm. The proposed algorithm avoids the need for the explicit constraint Jacobian and Hessian by using a Krylov iterative method to solve the Newton steps. The Krylov method requires matrix-vector products, which can be evaluated in a matrix-free manner using second-order adjoints. The Krylov method also needs to be preconditioned, and a key contribution of this work is a novel and effective preconditioner that is based on approximating a monolithic solution of the (linearized) multidisciplinary system. We demonstrate the efficacy of the algorithm by comparing it with the popular multidisciplinary feasible formulation on two test problems.     

A matrix-free quasi-Newton method for solving large-scale nonlinear systems

One of the widely used methods for solving a nonlinear system of equations is the quasi-Newton method. The basic idea underlining this type of method is to approximate the solution of Newton’s equation by means of approximating the Jacobian matrix via quasi-Newton update. Application of quasi-Newton methods for large scale problems requires, in principle, vast computational resource to form and store an approximation to the Jacobian matrix of the underlying problem. Hence, this paper proposes an approximation for Newton-step based on the update of approximation requiring a computational effort similar to that of matrix-free settings. It is made possible by approximating the Jacobian into a diagonal matrix using the least-change secant updating strategy, commonly employed in the development of quasi-Newton methods. Under suitable assumptions, local convergence of the proposed method is proved for nonsingular systems. Numerical experiments on popular test problems confirm the effectiveness of the approach in comparison with Newton’s, Chord Newton’s and Broyden’s methods.     

基于Givens变换矩阵的时间结构信号盲源分离新算法

对于时间结构信号的盲源分离(Blind Source Separation,BSS),独立成分分析(Independent Component Analysis,ICA)是十分有效的方法。在对观测信号白化处理后,ICA的关键是寻找去除高阶相关性的正交分离矩阵。鉴于任意维数正交矩阵可以表示为Givens变换矩阵的乘积,提出了一种新的时间结构信号盲源分离算法。首先,利用Givens变换矩阵参数化表示正交分离矩阵,减少了要估计参数的个数;其次,以多步时延协方差矩阵的联合近似对角化为目标函数,将盲源分离问题转化为无约束优化问题,并利用拟牛顿法中的BFGS算法对Givens变换矩阵中的参数进行估计,得到分离矩阵;最后,以实际的混合语音信号分离做仿真实验,验证了该算法对时间结构信号的盲源分离是有效的。     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。     

A nonmonotone ODE-based method for unconstrained optimization

This paper presents a new hybrid algorithm for unconstrained optimization problems, which combines the idea of the IMPBOT algorithm with the nonmonotone line search technique. A feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step, via a modified limited-memory BFGS two loop recursion that requires only matrix–vector products, thus reducing the computations and storage. Furthermore, when the trial step is not accepted, the proposed method performs a line search along it using a modified nonmonotone scheme, thus a larger stepsize can be yielded in each line search procedure. Under some reasonable assumptions, the convergence properties of the proposed algorithm are analysed. Numerical results are also reported to show the efficiency of this proposed method.     

基于Givens矩阵和联合非线性不相关的盲源分离新算法

针对源信号统计独立的盲源分离(Blind Source Separation,BSS)问题,提出了一种基于Givens矩阵和联合非线性不相关的盲源分离新算法.由于分离信号独立性的度量是影响算法有效性的重要因素,因此首先提出了一种改进的度量独立性的方法,该方法以独立源信号的联合非线性不相关来度量独立性;其次,结合Givens矩阵可以对分离矩阵施加正交性约束且能减少要估计参数个数的性质,将盲源分离问题转化成无约束优化问题,并利用拟牛顿法中的BFGS算法求解该无约束优化问题,得到分离矩阵;最后,通过模拟混合信号和真实语音混合信号的分离实验验证了该算法的有效性.     

A new two-step gradient-type method for large-scale unconstrained optimization

In this paper, we propose some improvements on a new gradient-type method for solving large-scale unconstrained optimization problems, in which we use data from two previous steps to revise the current approximate Hessian. The new method which we considered, resembles to that of Barzilai and Borwein (BB) method. The innovation features of this approach consist in using approximation of the Hessian in diagonal matrix form based on the modified weak secant equation rather than the multiple of the identity matrix in the BB method. Using this approach, we can obtain a higher order accuracy of Hessian approximation when compares to other existing BB-type method. By incorporating a simple monotone strategy, the global convergence of the new method is achieved. Practical insights into the effectiveness of the proposed method are given by numerical comparison with the BB method and its variant.     

Experimental Evaluation of Agent-based Approaches to Solving Multi-mode Resource-Constrained Project Scheduling Problem

ABSTRACT

In this paper, a rank-based nonparametric statistical test for measuring the effect of cooperation between optimization agents solving the multi-mode resource-constrained project scheduling problem is presented. To solve this NP-hard optimization problem, different methods are applied including population- and agent-based approaches. One of them is a team of asynchronous agents composed of multiple optimization agents, management agents, and common memories, which through interactions produce solutions of hard optimization problems. Optimization agents represent different methods including local search, path relinking, or tabu search. Interactions are managed through various cooperation strategies based on applying heuristics, reinforcement learning, or population learning.     

Preconditioning the Matrix Exponential Operator with Applications

The idea of preconditioning is usually associated with solution techniques for solving linear systems or eigenvalue problems. It refers to a general method by which the original system is transformed into one which admits the same solution but which is easier to solve. Following this principle we consider in this paper techniques for preconditioning the matrix exponential operator, e ^A y ₀, using different approximations of the matrix A. These techniques are based on using generalized Runge Kutta type methods. Preconditioners based on the sparsity structure of the matrix, such as diagonal, block diagonal, and least-squares tensor sum approximations are presented. Numerical experiments are reported to compare the quality of the schemes introduced.     

On improving normal boundary intersection method for generation of Pareto frontier

Gradient-based methods, including Normal Boundary Intersection (NBI), for solving multi-objective optimization problems require solving at least one optimization problem for each solution point. These methods can be computationally expensive with an increase in the number of variables and/or constraints of the optimization problem. This paper provides a modification to the original NBI algorithm so that continuous Pareto frontiers are obtained “in one go,” i.e., by solving only a single optimization problem. Discontinuous Pareto frontiers require solving a significantly fewer number of optimization problems than the original NBI algorithm. In the proposed method, the optimization problem is solved using a quasi-Newton method whose history of iterates is used to obtain points on the Pareto frontier. The proposed and the original NBI methods have been applied to a collection of 16 test problems, including a welded beam design and a heat exchanger design problem. The results show that the proposed approach significantly reduces the number of function calls when compared to the original NBI algorithm.