A new heuristic approach for non-convex optimization problems

In this work a new optimization method, called the heuristic Kalman algorithm (HKA), is presented. This new algorithm is proposed as an alternative approach for solving continuous, non-convex optimization problems. The principle of HKA is to explicitly consider the optimization problem as a measurement process designed to give an estimate of the optimum. A specific procedure, based on the Kalman estimator, was developed to improve the quality of the estimate obtained through the measurement process. The main advantage of HKA, compared to other metaheuristics, lies in the small number of parameters that need to be set by the user. Further, it is shown that HKA converges almost surely to a near-optimal solution. The efficiency of HKA was evaluated in detail using several non-convex test problems, both in the unconstrained and constrained cases. The results were then compared to those obtained via other metaheuristics. The numerical experiments show that HKA is a promising approach for solving non-convex optimization problems, particularly in terms of computation time and success ratio.     

A matrix-free line-search algorithm for nonconvex optimization

In this paper, we have developed a new algorithm for solving nonconvex large-scale problems. The new algorithm performs explicit matrix modifications adaptively, mimicing the implicit modifications used by trust-region methods. Thus, it shares the equivalent theoretical strength of trust-region approaches, without needing to accommodate an explicit step-size constraint. We show that the algorithm is well suited for solving very large-scale nonconvex problems whenever Hessian-vector products are available. The numerical results on the CUTEr problems demonstrate the effectiveness of this approach in the context of a line-search method for large-scale unconstrained nonconvex optimization. Moreover, applications in deep-learning problems further illustrate the usefulness of this algorithm. It does not share any of the prohibitive traits of popular matrix-free algorithms such as truncated conjugate gradient (CG) due to the difficult nature of deep-learning problems. Thus the proposed algorithm serves to bridge the gap between the needs of data-mining community and existing state-of-the-art approaches embraced foremost by the optimization community. Moreover, the proposed approach can be realized with minimal modification to the CG algorithm itself with negligible storage and computational overhead.     

一种求解混合整数非线性规划问题的模拟退火算法

通过适当处理离散变量，将求解无约束非凸ＮＬＰ问题的高效模拟退火全局优化算法推广到求解一般非凸混合整数非线性规划问题。数值计算结果表明，文中模拟退火算法在适用性、解的质量和计算效率等方面优于其它方法，是求解一般非凸ＭＩＮＬＰ问题的一种有效的全局优化算法。     

On the use of reduced models obtained through identification for feedback optimal control problems in a heat convection–diffusion problem

This paper deals with the use of reduced models for solving some optimal control problems. More precisely, the reduced model is obtained through the modal identification method. The test case which the algorithms is tested on is based on the flow over a backward-facing step. Though the reduction for the velocity fields for different Reynolds numbers is treated elsewhere [1], only the convection–diffusion equation for the energy problem is treated here. The model reduction is obtained through the solution of a gradient-type optimization problem where the objective function gradient is computed through the adjoint-state method. The obtained reduced models are validated before being coupled to optimal control algorithms. In this paper the feedback optimal control problem is considered. A Riccati equation is solved along with the Kalman gain equation. Additionally, a Kalman filter is performed to reconstruct the reduced state through previous and actual measurements. The numerical test case shows the ability of the proposed approach to control systems through the use of reduced models obtained by the modal identification method.     

Trust-region algorithms for training responses: machine learning methods using indefinite Hessian approximations

ABSTRACT

Machine learning (ML) problems are often posed as highly nonlinear and nonconvex unconstrained optimization problems. Methods for solving ML problems based on stochastic gradient descent are easily scaled for very large problems but may involve fine-tuning many hyper-parameters. Quasi-Newton approaches based on the limited-memory Broyden-Fletcher-Goldfarb-Shanno (BFGS) update typically do not require manually tuning hyper-parameters but suffer from approximating a potentially indefinite Hessian with a positive-definite matrix. Hessian-free methods leverage the ability to perform Hessian-vector multiplication without needing the entire Hessian matrix, but each iteration's complexity is significantly greater than quasi-Newton methods. In this paper we propose an alternative approach for solving ML problems based on a quasi-Newton trust-region framework for solving large-scale optimization problems that allow for indefinite Hessian approximations. Numerical experiments on a standard testing data set show that with a fixed computational time budget, the proposed methods achieve better results than the traditional limited-memory BFGS and the Hessian-free methods.     

Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting

The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.     

A hybrid differential evolution algorithm based on particle swarm optimization for nonconvex economic dispatch problems

This paper presents the design and application of an efficient hybrid heuristic search method to solve the practical economic dispatch problem considering many nonlinear characteristics of power generators, and their operational constraints, such as transmission losses, valve-point effects, multi-fuel options, prohibited operating zones, ramp rate limits and spinning reserve. These practical operation constraints which can usually be found at the same time in realistic power system operations make the economic load dispatch problem a nonsmooth optimization problem having complex and nonconvex features with heavy equality and inequality constraints.The proposed approach combines in the most effective way the properties of two of the most popular evolutionary optimization techniques now in use for power system optimization, the Differential Evolution (DE) and Particle Swarm Optimization (PSO) algorithms. To improve the global optimization property of DE, the PSO procedure is integrated as additional mutation operator.The effectiveness of the proposed algorithm (termed DEPSO) is demonstrated by solving four kinds of ELD problems with nonsmooth and nonconvex solution spaces. The comparative results with some of the most recently published methods confirm the effectiveness of the proposed strategy to find accurate and feasible optimal solutions for practical ELD problems.     

Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems

A new hybrid algorithm is being introduced for solving Mixed Integer Nonlinear Programming ( ) problems which arise from study of many real-life engineering problems such as the minimum cost development of oil fields and the optimization of a multiproduct batch plant. This new algorithm employs both the Genetic Algorithm and a modified grid search method interfacing in such a way that the resulting hybrid algorithm is capable of solving many problems efficiently and accurately. Testings indicate that this algorithm is efficient and robust even for some ill-conditioned problems with nonconvex constraints.     

Assigning cells to switches in cellular mobile networks using taboosearch

The design of wireless telecommunications networks is a complex process, which requires solving simultaneously many difficult combinatorial optimization problems. We propose a taboo-search approach dedicated to one of the aforementioned design optimization problems, namely the cell assignment problem. Our approach defines a series of moves applicable to an initial solution in order to improve the cost and establish the feasibility of the solution. For this purpose, we identify a gain structure with update procedures to efficiently choose the best solution in the current neighborhood. The results are generally good in comparison with those obtained through other heuristic methods.     

A bias-corrected estimator for nonlinear systems with output-error type model structures

Parametric identification of linear time-invariant (LTI) systems with output-error (OE) type of noise model structures has a well-established theoretical framework. Different algorithms, like instrumental-variables based approaches or prediction error methods (PEMs), have been proposed in the literature to compute a consistent parameter estimate for linear OE systems. Although the prediction error method provides a consistent parameter estimate also for nonlinear output-error (NOE) systems, it requires to compute the solution of a nonconvex optimization problem. Therefore, an accurate initialization of the numerical optimization algorithms is required, otherwise they may get stuck in a local minimum and, as a consequence, the computed estimate of the system might not be accurate. In this paper, we propose an approach to obtain, in a computationally efficient fashion, a consistent parameter estimate for output-error systems with polynomial nonlinearities. The performance of the method is demonstrated through a simulation example.     

Using Conical Regularization in Calculating Lagrangian Estimates in Quadratic Optimization Problems

For nonconvex quadratic optimization problems, the authors consider calculation of global extreme value estimates on the basis of Lagrangian relaxation of the original problems. On the boundary of the feasible region of the estimate problem, functions of the problem are discontinuous, ill-conditioned, which imposes certain requirements on the computational algorithms. The paper presents a new approach taking into account these features, based on the use of conical regularizations of convex optimization problems. It makes it possible to construct an equivalent unconditional optimization problem whose objective function is defined on the entire space of problem variables and satisfies the Lipschitz condition.     

Nonsmooth computational mechanics algorithms, quasidifferentiability and related topics

Several extensions of smooth computational mechanics algorithms for the treatment of nonsmooth and possible nonconvex problems are briefly discussed in this paper. A potential or dissipation energy minimization problem approach is used for the structural analysis problem, so as to make the link with mathematical optimization techniques straightforward. Variational inequality problems, hemivariational inequality problems and systems of variational inequalities can be treated by the methods reviewed in this paper. The use of quasidifferentiable and codifferentiable optimization techniques is proposed for the solution of the more general class of nonconvex, possibly nonsmooth problems. Established and new directions in path-following techniques are discussed and are linked with nonsmooth mechanics algorithms.     

On convex transformability and the solution of nonconvex problems via the dual of Falk

In structural optimization, most successful sequential approximate optimization (SAO) algorithms solve a sequence of strictly convex subproblems using the dual of Falk. Previously, we have shown that, under certain conditions, a nonconvex nonlinear (sub)problem may also be solved using the Falk dual. In particular, we have demonstrated this for two nonconvex examples of approximate subproblems that arise in popular and important structural optimization problems. The first is used in the SAO solution of the weight minimization problem, while the topology optimization problem that results from volumetric penalization gives rise to the other. In both cases, the nonconvex subproblems arise naturally in the consideration of the physical problems, so it seems counter productive to discard them in favor of using standard, but less well-suited, strictly convex approximations. Though we have not required that strictly convex transformations exist for these problems in order that they may be solved via a dual approach, we have noted that both of these examples can indeed be transformed into strictly convex forms. In this paper we present both the nonconvex weight minimization problem and the nonconvex topology optimization problem with volumetric penalization as instructive numerical examples to help motivate the use of nonconvex approximations as subproblems in SAO. We then explore the link between convex transformability and the salient criteria which make nonconvex problems amenable to solution via the Falk dual, and we assess the effect of the transformation on the dual problem. However, we consider only a restricted class of problems, namely separable problems that are at least C ¹ continuous, and a restricted class of transformations: those in which the functions that represent the mapping are each continuous, monotonic and univariate.     

A hybrid differential evolution approach based on surrogate modelling for scheduling bottleneck stages

Surrogate modelling based optimization has attracted much attention due to its ability of solving expensive-to-evaluate optimization problems, and a large majority of successful applications from various fields have been reported in literature. However, little effort has been devoted to solve scheduling problems through surrogate modelling, since evaluation for a given complete schedule of these complex problems is computationally cheap in most cases. In this paper, we develop a hybrid approach for solving the bottleneck stage scheduling problem (BSP) using the surrogate modelling technique. In our approach, we firstly transform the original problem into an expensive-to-evaluate optimization problem by cutting the original schedule into two partial schedules using decomposition, then a surrogate model is introduced to, quickly but crudely, evaluate a given partial schedule. Based on the surrogate model, we propose a differential evolution (DE) algorithm for solving BSPs in which a novel mechanism is developed to efficiently utilize the advantage of the surrogate model to enhance the performance of DE. Also, an improved adaptive proximity-based method is introduced to balance the exploration and exploitation during the evolutionary process of DE. Considering that data for training the surrogate model is generated at different iteration of DE, we adopt an incremental extreme learning machine as the surrogate model to reduce the computational cost while preserving good generalization performance. Extensive computational experiments demonstrate that significant improvements have been obtained by the proposed surrogate-modelling based approach.     

Hybrid multi-objective shape design optimization using Taguchi’s method and genetic algorithm

This research is based on a new hybrid approach, which deals with the improvement of shape optimization process. The objective is to contribute to the development of more efficient shape optimization approaches in an integrated optimal topology and shape optimization area with the help of genetic algorithms and robustness issues. An improved genetic algorithm is introduced to solve multi-objective shape design optimization problems. The specific issue of this research is to overcome the limitations caused by larger population of solutions in the pure multi-objective genetic algorithm. The combination of genetic algorithm with robust parameter design through a smaller population of individuals results in a solution that leads to better parameter values for design optimization problems. The effectiveness of the proposed hybrid approach is illustrated and evaluated with test problems taken from literature. It is also shown that the proposed approach can be used as first stage in other multi-objective genetic algorithms to enhance the performance of genetic algorithms. Finally, the shape optimization of a vehicle component is presented to illustrate how the present approach can be applied for solving multi-objective shape design optimization problems.     

Optimizing Frequencies in a Transit Network: a Nonlinear Bi-level Programming Approach

We consider the problem of optimizing the frequencies of transit lines in an urban transportation network. The problem is formulated first as a nonlinear nonconvex mixed integer programming problem and then it is converted into a bi-level Min–Min nonconvex optimization problem. This problem is solved by a projected (sub)gradient algorithm, where a (sub)gradient is obtained at each iteration by solving the lower level problem. Computational results obtained with this algorithm are presented for the transit networks of the cities of Stockholm, Sweden, Winnipeg, Man., Canada and Portland, OR, U.S.A.     

An interval algorithm for multi-objective optimization

This paper presents an interval algorithm for solving multi-objective optimization problems. Similar to other interval optimization techniques, [see Hansen and Walster (2004)], the interval algorithm presented here is guaranteed to capture all solutions, namely all points on the Pareto front. This algorithm is a hybrid method consisting of local gradient-based and global direct comparison components. A series of example problems covering convex, nonconvex, and multimodal Pareto fronts is used to demonstrate the method.     

Cubature Kalman Filter Under Minimum Error Entropy With Fiducial Points for INS/GPS Integration

Traditional cubature Kalman filter(CKF)is a preferable tool for the inertial navigation system(INS)/global positioning system(GPS)integration under Gaussian noises.The CKF,however,may provide a significantly biased estimate when the INS/GPS system suffers from complex non-Gaussian disturbances.To address this issue,a robust nonlinear Kalman filter referred to as cubature Kalman filter under minimum error entropy with fiducial points(MEEF-CKF)is proposed.The MEEF-CKF behaves a strong robustness against complex nonGaussian noises by operating several major steps,i.e.,regression model construction,robust state estimation and free parameters optimization.More concretely,a regression model is constructed with the consideration of residual error caused by linearizing a nonlinear function at the first step.The MEEF-CKF is then developed by solving an optimization problem based on minimum error entropy with fiducial points(MEEF)under the framework of the regression model.In the MEEF-CKF,a novel optimization approach is provided for the purpose of determining free parameters adaptively.In addition,the computational complexity and convergence analyses of the MEEF-CKF are conducted for demonstrating the calculational burden and convergence characteristic.The enhanced robustness of the MEEF-CKF is demonstrated by Monte Carlo simulations on the application of a target tracking with INS/GPS integration under complex nonGaussian noises.     

Kalman filtering: a new approach for building global approximations. Application to the inverse optimization of an explosively formed penetrator (EFP)

As the use of approximations is often the only way to deal with the optimization of complex structures, this paper discusses the use of Kalman filtering as a new approach for building global approximations. Basic ideas and procedures of Kalman filters are first recalled. Next, key elements of how to implement the method for design problems are described. Finally, in order to evaluate the performance of the approach, an inverse problem which consists in optimizing a warhead with respect to constraints on the resulting projectile is studied. It is shown that global approximations are convenient for the solution of complex optimization problems and that Kalman filtering techniques appear to be an interesting strategy for the construction of global approximations in structural optimization.     

Nonsmooth optimization techniques for semisupervised classification

We apply nonsmooth optimization techniques to classification problems, with particular reference to the TSVM (Transductive Support Vector Machine) approach, where the considered decision function is nonconvex and nondifferentiable and then difficult to minimize. We present some numerical results obtained by running the proposed method on some standard test problems drawn from the binary classification literature.