On the Global Convergence of a Projective Trust Region Algorithm for Nonlinear Equality Constrained Optimization

A trust-region sequential quadratic programming (SQP) method is developed and analyzed for the solution of smooth equality constrained optimization problems. The trust-region SQP algorithm is based on filter line search technique and a composite-step approach, which decomposes the overall step as sum of a vertical step and a horizontal step. The algorithm includes critical modifications of horizontal step computation. One orthogonal projective matrix of the Jacobian of constraint functions is employed in trust-region subproblems. The orthogonal projection gives the null space of the transposition of the Jacobian of the constraint function. Theoretical analysis shows that the new algorithm retains the global convergence to the first-order critical points under rather general conditions. The preliminary numerical results are reported.     

A Stochastic Algorithm for Constrained Global Optimization

We present a stochastic algorithm to solve numerically the problem of finding the global minimizers of a real valued function subject to lower and upper bounds. This algorithm looks for the global minimizers following the paths of a suitable system of stochastic differential equations. Numerical experience on several test problems known in literature is shown.     

Convergence of a Simulated Annealing Algorithm for Continuous Global Optimization

In this paper a simulated annealing algorithm for continuous global optimization will be considered. The algorithm, in which a cooling schedule based on the distance between the function value in the current point and an estimate of the global optimum value is employed, has been first introduced in Bohachevsky, Johnson and Stein (1986) [2], but without any proof of convergence. Here it will be proved that, under suitable assumptions, the algorithm is convergent     

A Smoothing Objective Penalty Function Algorithm for Inequality Constrained Optimization Problems

In this article, a smoothing objective penalty function for inequality constrained optimization problems is presented. The article proves that this type of the smoothing objective penalty functions has good properties in helping to solve inequality constrained optimization problems. Moreover, based on the penalty function, an algorithm is presented to solve the inequality constrained optimization problems, with its convergence under some conditions proved. Two numerical experiments show that a satisfactory approximate optimal solution can be obtained by the proposed algorithm.     

On the Convergence of a Population-Based Global Optimization Algorithm

In global optimization, a typical population-based stochastic search method works on a set of sample points from the feasible region. In this paper, we study a recently proposed method of this sort. The method utilizes an attraction-repulsion mechanism to move sample points toward optimality and is thus referred to as electromagnetism-like method (EM). The computational results showed that EM is robust in practice, so we further investigate the theoretical structure. After reviewing the original method, we present some necessary modifications for the convergence proof. We show that in the limit, the modified method converges to the vicinity of global optimum with probability one.     

On the Convergence of a Population-Based Global Optimization Algorithm

In global optimization, a typical population-based stochastic search method works on a set of sample points from the feasible region. In this paper, we study a recently proposed method of this sort. The method utilizes an attraction-repulsion mechanism to move sample points toward optimality and is thus referred to as electromagnetism-like method (EM). The computational results showed that EM is robust in practice, so we further investigate the theoretical structure. After reviewing the original method, we present some necessary modifications for the convergence proof. We show that in the limit, the modified method converges to the vicinity of global optimum with probability one.     

An Ideal Penalty Function for Constrained Optimization

A well known approach to constrained optimization is via a sequenceof unconstrained minimization calculations applied to a penaltyfunction. This paper shown how it is posiible to generalizePowell's penelty function to solve constrained problems withboth equality and inequality constraints. The resulting methodsare equivalent to the Hestenes' method of multipliers, and ageneralization of this to inequality constraints suggested byRockafellar. Local duality results (not all of which have appearedbefore) for these methods are reviewed, with particular emphasison those of practical importance. It is shown that various strategiesfor varying control parameters are possible, all of which canbe viewed as Newton or Newton-like iterations applied to thedual problem. Practical strategies for guaranteeing convergenceare also discussed. A wide selection of numerical evidence isreported, and the algorithms are compared both amongst themselvesand with other penalty function methods. The new penalty functionis well conditioned, without singularities, and it is not necessaryfor the control parameters to tend to infinity in order to forceconvergence. The rate of convergence is rapid and high accuracyis achieved in few unconstrained minimizations.; furthermorethe computational effort for successive minimizations goes downrapidly. The methods are very easy to program efficiently, usingan established quasi-Newton subroutine for unconstrained minimization.     

使用非单调线搜索正割方法解约束优化的整体收敛性

基于Powell和Yuan所建议的近似Fetcher罚函数作为函数使用单调线搜索的技术,本文提供了一类正割方法解约束优化。在合理的条件下,证明了所提供的算法的整体收敛性和收敛速率。     

基于双参数罚函数求解约束优化问题的一个新算法

对于含约束不等式的最优化问题给出了一种双参数罚函数形式,在文[7]的拟牛顿算法的基础上提出了一个同时改变双参数罚函数的新算法,研究了它的收敛性,数值实验表明了该算法是有效的.     

Convergence of the Simulated Annealing Algorithm for Continuous Global Optimization

A class of simulated annealing algorithms for continuous global optimization is considered in this paper. The global convergence property is analyzed with respect to the objective value sequence and the minimum objective value sequence induced by simulated annealing algorithms. The convergence analysis provides the appropriate conditions on both the generation probability density function and the temperature updating function. Different forms of temperature updating functions are obtained with respect to different kinds of generation probability density functions, leading to different types of simulated annealing algorithms which all guarantee the convergence to the global optimum.     

一个求总极值的变测度算法及其收敛性

利用积分中值定理阐述了积分型方法的实质,指出了其优点与不足,提出相应的改进方法—变测度算法,并对变测度算法的收敛性进行了证明.     

Global Convergence of a Nonmonotone Trust Region Algorithm with Memory for Unconstrained Optimization

In this paper, we consider a trust region algorithm for unconstrained optimization problems. Unlike the traditional memoryless trust region methods, our trust region model includes memory of the past iteration, which makes the algorithm less myopic in the sense that its behavior is not completely dominated by the local nature of the objective function, but rather by a more global view. The global convergence is established by using a nonmonotone technique. The numerical tests are also given to show the efficiency of our proposed method.     

Proof of Convergence for a Global Optimization Algorithm for Problems with Ordinary Differential Equations

A deterministic spatial branch and bound global optimization algorithm for problems with ordinary differential equations in the constraints has been developed by Papamichail and Adjiman [A rigorous global optimization algorithm for problems with ordinary differential equations. J. Glob. Optim. 24, 1–33]. In this work, it is shown that the algorithm is guaranteed to converge to the global solution. The proof is based on showing that the selection operation is bound improving and that the bounding operation is consistent. In particular, it is shown that the convex relaxation techniques used in the algorithm for the treatment of the dynamic information ensure bound improvement and consistency are achieved.     

Annealing a Genetic Algorithm for Constrained Optimization

In this paper, we adapt a genetic algorithm for constrained optimization problems. We use a dynamic penalty approach along with some form of annealing, thus forcing the search to concentrate on feasible solutions as the algorithm progresses. We suggest two different general-purpose methods for guaranteeing convergence to a globally optimal (feasible) solution, neither of which makes any assumptions on the structure of the optimization problem. The former involves modifying the GA evolution operators to yield a Boltzmann-type distribution on populations. The latter incorporates a dynamic penalty along with a slow annealing of acceptance probabilities. We prove that, with probability one, both of these methods will converge to a globally optimal feasible state.     

变差积分型约束总极值问题的不连续罚途径

结合积分途径运用不连续精确罚函数来求解全局约束最小化问题,进一步,提出了约束变差积分的一般形式并证明了其分析性质,同时也给出并证明了其全局最优性条件,并由此设计了一个新算法.基于Monte-Carlo模拟技术,运用交叉熵方法和重要样本实现了该算法,数值实验也说明了这个新算法是有效的.     

Second-Order Smoothing Objective Penalty Function for Constrained Optimization Problems

In this article, a novel objective penalty function as well as its second-order smoothing is introduced for constrained optimization problems (COP). It is shown that an optimal solution to the second-order smoothing objective penalty optimization problem is an optimal solution to the original optimization problem under some mild conditions. Based on the second-order smoothing objective penalty function, an algorithm that has better convergence is introduced. Numerical examples illustrate that this algorithm is efficient in solving COP.     

Theoretical Convergence Analysis of a General Division–deletion Algorithm for Solving Global Search Problems

Presented in this paper is the prototype of a very general algorithm referred to as Division – Deletion Algorithm (DDA) for solving the most general global search problem. Various necessary conditions, sufficient conditions, and necessary and sufficient conditions for the convergence of the algorithm are proposed and analyzed. As an example of its application, we demonstrate that the convergence of a standard Hansen’s interval algorithm for unconstrained global optimization simply follows from this general theory.     

Global Convergence of a Modified Gradient Projection Method for Convex Constrained Problems

In this paper, the continuously differentiable optimization problem min{f（x） ： x∈Ω}, where Ω ∈ R^n is a nonempty closed convex set, the gradient projection method by Calamai and More （Math. Programming, Vol.39. P.93-116, 1987） is modified by memory gradient to improve the convergence rate of the gradient projection method is considered. The convergence of the new method is analyzed without assuming that the iteration sequence {x^k} of bounded. Moreover, it is shown that, when f（x） is pseudo-convex （quasiconvex） function, this new method has strong convergence results. The numerical results show that the method in this paper is more effective than the gradient projection method.     

一个解不等式约束优化问题的初始点任意而不需罚函数的SQP算法(英文)

本文构造了一解不等式约束优化问题的非单调SQP方法 ,与类似的算法比较 ,它有以下特点 :( 1 )初始点任意 ,并不用罚函数 ;( 2 )有限步后必产生可行点 ;( 3)在每次迭代 ,只需解一个二次规划子问题 ;( 4)不需要严格互补条件 ,在较弱的条件下 ,算法超线性收敛 .     

Existence of Global Minima for Constrained Optimization

We present a unified approach to establishing the existence of global minima of a (non)convex constrained optimization problem. Our results unify and generalize previous existence results for convex and nonconvex programs, including the Frank-Wolfe theorem, and for (quasi) convex quadratically constrained quadratic programs and convex polynomial programs. For example, instead of requiring the objective/constraint functions to be constant along certain recession directions, we only require them to linearly recede along these directions. Instead of requiring the objective/constraint functions to be convex polynomials, we only require the objective function to be a (quasi)convex polynomial over a polyhedral set and the constraint functions to be convex polynomials or the composition of coercive functions with linear mappings.We thank Professor Dimitri Bertsekas for his comments and support in the writing of this paper.