GOSAC: global optimization with surrogate approximation of constraints

We introduce GOSAC, a global optimization algorithm for problems with computationally expensive black-box constraints and computationally cheap objective functions. The variables may be continuous, integer, or mixed-integer. GOSAC uses a two-phase optimization approach. The first phase aims at finding a feasible point by solving a multi-objective optimization problem in which the constraints are minimized simultaneously. The second phase aims at improving the feasible solution. In both phases, we use cubic radial basis function surrogate models to approximate the computationally expensive constraints. We iteratively select sample points by minimizing the computationally cheap objective function subject to the constraint function approximations. We assess GOSAC’s efficiency on computationally cheap test problems with integer, mixed-integer, and continuous variables and two environmental applications. We compare GOSAC to NOMAD and a genetic algorithm (GA). The results of the numerical experiments show that for a given budget of allowed expensive constraint evaluations, GOSAC finds better feasible solutions more efficiently than NOMAD and GA for most benchmark problems and both applications. GOSAC finds feasible solutions with a higher probability than NOMAD and GOSAC.     

一类新的信赖域算法的全局收敛性

本文对于无约束最优化问题提出了一类非单调的信赖域算法，它是通常的单调信赖域算法的推广。当目标函数是有下界的连续可微函数，而且它的二阶导数的近似的模是线性地依赖于迭代次数时，我们证明了新算法的整体收敛性。     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

Nonmonotonic trust region algorithm

A nonmonotonic trust region method for unconstrained optimization problems is presented. Although the method allows the sequence of values of the objective function to be nonmonotonic, convergence properties similar to those for the usual trust region method are proved under certain conditions, including conditions on the approximate solutions to the subproblem. To make the solution satisfy these conditions, an algorithm to solve the subproblem is also established. Finally, some numerical results are reported which show that the nonmonotonic trust region method is superior to the usual trust region method according to both the number of gradient evaluations and the number of function evaluations.The authors would like to thank Professor L. C. W. Dixon for his useful suggestions.     

一种解无约束优化问题的新的非单调自适应信赖域方法

本文提出了一种解无约束优化问题的新的非单调自适应信赖域方法.这种方法借助于目标函数的海赛矩阵的近似数量矩阵来确定信赖域半径.在通常的条件下,给出了新算法的全局收敛性以及局部超线性收敛的结果,数值试验验证了新的非单调方法的有效性.     

A NEW DERIVATIVE FREE OPTIMIZATION METHOD BASED ON CONIC INTERPOLATION MODEL

In this paper, a new derivative free trust region method is developed basedon the conic interpolation model for the unconstrained optimization. The conic inter-polation model is built by means of the quadratic model function, the collinear scalingformula, quadratic approximation and interpolation. All the parameters in this model axedetermined by objective function interpolation condition. A new derivative free method isdeveloped based upon this model and the global convergence of this new method is provedwithout any information on gradient.     

A derivative-free optimization algorithm based on conditional moments

In this paper we propose a derivative-free optimization algorithm based on conditional moments for finding the maximizer of an objective function. The proposed algorithm does not require calculation or approximation of any order derivative of the objective function. The step size in iteration is determined adaptively according to the local geometrical feature of the objective function and a pre-specified quantity representing the desired precision. The theoretical properties including convergence of the method are presented. Numerical experiments comparing with the Newton, Quasi-Newton and trust region methods are given to illustrate the effectiveness of the algorithm.     

On the global convergence of trust region algorithms for unconstrained minimization

Many trust region algorithms for unconstrained minimization have excellent global convergence properties if their second derivative approximations are not too large [2]. We consider how large these approximations have to be, if they prevent convergence when the objective function is bounded below and continuously differentiable. Thus we obtain a useful convergence result in the case when there is a bound on the second derivative approximations that depends linearly on the iteration number.     

A Kriging-based constrained global optimization algorithm for expensive black-box functions with infeasible initial points

In many engineering optimization problems, the objective and the constraints which come from complex analytical models are often black-box functions with extensive computational effort. In this case, it is necessary for optimization process to use sampling data to fit surrogate models so as to reduce the number of objective and constraint evaluations as soon as possible. In addition, it is sometimes difficult for the constrained optimization problems based on surrogate models to find a feasible point, which is the premise of further searching for a global optimal feasible solution. For this purpose, a new Kriging-based Constrained Global Optimization (KCGO) algorithm is proposed. Unlike previous Kriging-based methods, this algorithm can dispose black-box constrained optimization problem even if all initial sampling points are infeasible. There are two pivotal phases in KCGO algorithm. The main task of the first phase is to find a feasible point when there is no feasible data in the initial sample. And the aim of the second phase is to obtain a better feasible point under the circumstances of fewer expensive function evaluations. Several numerical problems and three design problems are tested to illustrate the feasibility, stability and effectiveness of the proposed method.     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.     

Constructing composite search directions with parameters in quadratic interpolation models

In this paper, we introduce the weighted composite search directions to develop the quadratic approximation methods. The purpose is to make fully use of the information disclosed by the former steps to construct possibly more promising directions. Firstly, we obtain these composite directions based on the properties of simplex methods and use them to construct trust region subproblems. Then, these subproblems are solved in the algorithm to find solutions of some benchmark optimization problems. The computation results show that for most tested problems, the improved quadratic approximation methods can obviously reduce the number of function evaluations compared with the existing ones. Finally, we conclude that the algorithm will perform better if the composite directions approach the previous steepest descent direction of the sub-simplex so far. We also point out the potential applications of this improved quadratic interpolation method in business intelligence systems.     

Global and mid-range function approximation for engineering optimization

Global and mid-range approximation concepts are used in engineering optimisation in those cases were the commonly used local approximations are not available or applicable. In this paper the response surface method is discussed as a method to build both global and mid-range approximations of the objective and constraint functions. In this method analysis results in multiple design points are fitted on a chosen approximation model function by means of regression techniques. Especially global approximations rely heavily on appropriate choices of the model functions. This builds a serious bottleneck in applying the method. In mid-range approximations the model selection is much less critical. The response surface method is illustrated at two relatively simple design problems. For building global approximations a new method was developed by Sacks and co-workers, especially regarding the nature of computer experiments. Here, the analysis results in the design sites are exactly predicted, and model selection is more flexible compared to the response surface method. The method will be applied to an analytical test function and a simple design problem. Finally the methods are discussed and compared.     

Evaluation of nondominated solution sets for k-objective optimization problems: An exact method and approximations

Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63–82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k (⩾3) dimensional integration.In this paper, we suggest a theoretical framework for obtaining IPF for k (⩾3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.     

On memory gradient method with trust region for unconstrained optimization

In this paper we present a new memory gradient method with trust region for unconstrained optimization problems. The method combines line search method and trust region method to generate new iterative points at each iteration and therefore has both advantages of line search method and trust region method. It sufficiently uses the previous multi-step iterative information at each iteration and avoids the storage and computation of matrices associated with the Hessian of objective functions, so that it is suitable to solve large scale optimization problems. We also design an implementable version of this method and analyze its global convergence under weak conditions. This idea enables us to design some quick convergent, effective, and robust algorithms since it uses more information from previous iterative steps. Numerical experiments show that the new method is effective, stable and robust in practical computation, compared with other similar methods.     

A trust region affine scaling method for bound constrained optimization

We study a new trust region affine scaling method for general bound constrained optimization problems. At each iteration, we compute two trial steps. We compute one along some direction obtained by solving an appropriate quadratic model in an ellipsoidal region. This region is defined by an affine scaling technique. It depends on both the distances of current iterate to boundaries and the trust region radius. For convergence and avoiding iterations trapped around nonstationary points, an auxiliary step is defined along some newly defined approximate projected gradient. By choosing the one which achieves more reduction of the quadratic model from the two above steps as the trial step to generate next iterate, we prove that the iterates generated by the new algorithm are not bounded away from stationary points. And also assuming that the second-order sufficient condition holds at some nondegenerate stationary point, we prove the Q-linear convergence of the objective function values. Preliminary numerical experience for problems with bound constraints from the CUTEr collection is also reported.     

求解非光滑凸规划的一种混合束方法

提出一种求解非光滑凸规划问题的混合束方法. 该方法通过对目标函数增加迫近项, 且对可行域增加信赖域约束进行迭代, 做为迫近束方法与信赖域束方法的有机结合, 混合束方法自动在二者之间切换, 收敛性分析表明该方法具有全局收敛性. 最后的数值算例验证了算法的有效性．     

A new nonmonotone adaptive trust region method based on simple quadratic models

Based on simple quadratic models of the trust region subproblem, we combine the trust region method with the nonmonotone and adaptive techniques to propose a new nonmonotone adaptive trust region algorithm for unconstrained optimization. Unlike traditional trust region method, our trust region subproblem is very simple by using a new scale approximation of the minimizing function??s Hessian. The new method needs less memory capacitance and computational complexity. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large scale unconstrained problems.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

A New Nonmonotonic Trust Region Algorithm for A Class of Unconstrained Nonsmooth Optimization

This paper presents a new trust region algorithm for solving a class of composite nonsmooth optimizations. It is distinguished by the fact that this method does not enforce strict monotonicity of the objective function values at successive iterates and that this method extends the existing results for this type of nonlinear optimization with smooth, or piecewise smooth, or convex objective functions or their composition. It is proved that this algorithm is globally convergent under certain conditions. Finally, some numerical results for several optimization problems are reported which show that the nonmonotonic trust region method is competitive with the usual trust region method.     

A New Nonmonotonic Trust Region Algorithm for A Class of Unconstraied Nonsmooth Optimization

This paper preasents a new trust region algorithm for solving a class of composite nonsmooth optimizations.It is distinguished by the fact that this method does not enforce strict monotonicity of the objective function values at successive itereates and that this method extends the existing results for this type of nonlinear optimization with smooth ,or piecewis somooth,or convex objective functions or their composition It is pyoved that this algorithm is globally convergent under certain conditions.Finally,some numerical results for several optimization problems are reported which show that the nonmonotonic trust region method is competitive with the usual trust region method.