Global convergence and rate of convergence of a method of centers

We consider a method of centers for solving constrained optimization problems. We establish its global convergence and that it converges with a linear rate when the starting point of the algorithm is feasible as well as when the starting point is infeasible. We demonstrate the effect of the scaling on the rate of convergence. We extend afterwards, the stability result of [5] to the infeasible case anf finally, we give an application to semi-infinite optimization problems.     

Random tunneling by means of acceptance-rejection sampling for global optimization

Any global minimization algorithm is made by several local searches performed sequentially. In the classical multistart algorithm, the starting point for each new local search is selected at random uniformly in the region of interest. In the tunneling algorithm, such a starting point is required to have the same function value obtained by the last local minimization. We introduce the class of acceptance-rejection based algorithms in order to investigate intermediate procedures. A particular instance is to choose at random the new point approximately according to a Boltzmann distribution, whose temperatureT is updated during the algorithm. AsT 0, such distribution peaks around the global minima of the cost function, producing a kind of random tunneling effect. The motivation for such an approach comes from recent works on the simulated annealing approach in global optimization. The resulting algorithm has been tested on several examples proposed in the literature.     

A Full Nesterov–Todd Step Infeasible Interior-Point Method for Second-Order Cone Optimization

After a brief introduction to Jordan algebras, we present a primal–dual interior-point algorithm for second-order conic optimization that uses full Nesterov–Todd steps; no line searches are required. The number of iterations of the algorithm coincides with the currently best iteration bound for second-order conic optimization. We also generalize an infeasible interior-point method for linear optimization to second-order conic optimization. As usual for infeasible interior-point methods, the starting point depends on a positive number. The algorithm either finds a solution in a finite number of iterations or determines that the primal–dual problem pair has no optimal solution with vanishing duality gap.     

求解多项式规划的一个全局最优化算法

提出一个求解带箱子约束的一般多项式规划问题的全局最优化算法, 该算法包含两个阶段, 在第一个阶段, 利用局部最优化算法找到一个局部最优解. 在第二阶段, 利用一个在单位球上致密的向量序列, 将多元多项式转化为一元多项式, 通过求解一元多项式的根, 找到一个比当前局部最优解更好的点作为初始点, 回到第一个 阶段, 从而得到一个更好的局部最优解, 通过两个阶段的循环最终找到问题的全局最优解, 并给出了算法收敛性分析. 最后, 数值结果表明了算法是有效的.     

A finite algorithm for solving general quadratic problems

Here we propose a global optimization method for general, i.e. indefinite quadratic problems, which consist of maximizing a non-concave quadratic function over a polyhedron inn-dimensional Euclidean space. This algorithm is shown to be finite and exact in non-degenerate situations. The key procedure uses copositivity arguments to ensure escaping from inefficient local solutions. A similar approach is used to generate an improving feasible point, if the starting point is not the global solution, irrespective of whether or not this is a local solution. Also, definiteness properties of the quadratic objective function are irrelevant for this procedure. To increase efficiency of these methods, we employ pseudoconvexity arguments. Pseudoconvexity is related to copositivity in a way which might be helpful to check this property efficiently even beyond the scope of the cases considered here.     

The use of QP-free algorithm in the limit analysis of slope stability

In many mountainous areas, landslides and slope instabilities frequently occur after heavy rainfall and earthquake, and result in enormous casualties and huge economic losses. In order to mitigate the landslides hazard efficiently, a method is required for a better understanding of stability analysis. Fortunately, upper bound theorem of limit analysis provides a practical and effective upper bound approach to evaluate the stability of slopes. And in this approach, the search for the minimum factor of safety can be formulated as a nonlinear constrained optimization. In general, the SQP-type algorithms are used to solve this optimization problem. However, it is quite time consuming and difficult to search the optimum from an arbitrary starting point based on the SQP-type algorithms. Fortunately, a QP-free algorithm based on penalty function and active-set strategy can be globally convergent toward the KKT points with arbitrary starting point, and the rate of convergence is local superlinear or even quadratic. Two classical problems of slope stability are solved by this QP-free algorithm. The results show that the QP-free algorithm would be the better choice than SQP-type algorithms for solving the nonlinear constrained optimization problem which is derived from the upper bound limit analysis of slope stability.     

Finding the optimal solution to the Huff based competitive location model

In this paper we solve the gravity (Huff) model for the competitive facility location problem. We show that the generalized Weiszfeld procedure converges to a local maximum or a saddle point. We also devise a global optimization procedure that finds the optimal solution within a given accuracy. This procedure is very efficient and finds the optimal solution for 10,000 demand points in less than six minutes of computer time. We also experimented with the generalized Weiszfeld algorithm on the same set of randomly generated problems. We repeated the algorithm from 1,000 different starting solutions and the optimum was obtained at least 17 times for all problems.     

Machine learning for global optimization

In this paper we introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine (although different machine learning tools might be employed) to learn the relationship between the starting point of an algorithm and the final outcome (which is usually related to the function value at the point returned by the procedure). Numerical experiments performed both on classical test functions and on difficult space trajectory planning problems show that the proposed approach can be very effective in identifying good starting points for global optimization.     

New Modified Function Method for Global Optimization

In this paper, a class of global optimization problems is considered. Corresponding to each local minimizer obtained, we introduced a new modified function and construct a corresponding optimization subproblem with one constraint. Then, by applying a local search method to the one-constraint optimization subproblem and using the local minimizer as the starting point, we obtain a better local optimal solution. This process is continued iteratively. A termination rule is obtained which can serve as stopping criterion for the iterating process. To demonstrate the efficiency of the proposed approach, numerical examples are solved.This research was partially supported by the National Science Foundation of China, Grant 10271073.     

复合凸优化的快速邻近点算法

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.     

Testing the topographical global initialization strategy in the framework of an unconstrained optimization method

In general, classical iterative algorithms for optimization, such as Newton-type methods, perform only local search around a given starting point. Such feature is an impediment to the direct use of these methods to global optimization problems, when good starting points are not available. To overcome this problem, in this work we equipped a Newton-type method with the topographical global initialization strategy, which was employed together with a new formula for its key parameter. The used local search algorithm is a quasi-Newton method with backtracking. In this approach, users provide initial sets, instead of starting points. Then, using points sampled in such initial sets (merely boxes in \({\mathbb {R}}^{n}\)), the topographical method selects appropriate initial guesses for global optimization tasks. Computational experiments were performed using 33 test problems available in literature. Comparisons against three specialized methods (DIRECT, MCS and GLODS) have shown that the present methodology is a powerful tool for unconstrained global optimization.     

Fast Global Optimization of Difficult Lennard-Jones Clusters

The minimization of the potential energy function of Lennard-Jones atomic clusters has attracted much theoretical as well as computational research in recent years. One reason for this is the practical importance of discovering low energy configurations of clusters of atoms, in view of applications and extensions to molecular conformation research; another reason of the success of Lennard Jones minimization in the global optimization literature is the fact that this is an extremely easy-to-state problem, yet it poses enormous difficulties for any unbiased global optimization algorithm.In this paper we propose a computational strategy which allowed us to rediscover most putative global optima known in the literature for clusters of up to 80 atoms and for other larger clusters, including the most difficult cluster conformations. The main feature of the proposed approach is the definition of a special purpose local optimization procedure aimed at enlarging the region of attraction of the best atomic configurations. This effect is attained by performing first an optimization of a modified potential function and using the resulting local optimum as a starting point for local optimization of the Lennard Jones potential.Extensive numerical experimentation is presented and discussed, from which it can be immediately inferred that the approach presented in this paper is extremely efficient when applied to the most challenging cluster conformations. Some attempts have also been carried out on larger clusters, which resulted in the discovery of the difficult optimum for the 102 atom cluster and for the very recently discovered new putative optimum for the 98 atom cluster.     

A hybrid framework for optimizing beam angles in radiation therapy planning

The purpose of this paper is twofold: (1) to examine strengths and weaknesses of recently developed optimization methods for selecting radiation treatment beam angles and (2) to propose a simple and easy-to-use hybrid framework that overcomes some of the weaknesses observed with these methods. Six optimization methods—branch and bound (BB), simulated annealing (SA), genetic algorithms (GA), nested partitions (NP), branch and prune (BP), and local neighborhood search (LNS)—were evaluated. Our preliminary test results revealed that (1) one of the major drawbacks of the reported algorithms was the limited ability to find a good solution within a reasonable amount of time in a clinical setting, (2) all heuristic methods require selecting appropriate parameter values, which is a difficult chore, and (3) the LNS algorithm has the ability to identify good solutions only if provided with a good starting point. On the basis of these findings, we propose a unified beam angle selection framework that, through two sequential phases, consistently finds clinically relevant locally optimal solutions. Considering that different users may use different optimization approaches among those mentioned above, the first phase aims to quickly find a good feasible solution using SA, GA, NP, or BP. This solution is then used as a starting point for LNS to find a locally optimal solution. Experimental results using this unified method on five clinical cases show that it not only produces consistently good-quality treatment solutions but also alleviates the effort of selecting an initial set of appropriate parameter values that is required by all of the existing optimization methods.     

Order statistics and region-based evolutionary computation

Trust region algorithms are well known in the field of local continuous optimization. They proceed by maintaining a confidence region in which a simple, most often quadratic, model is substituted to the criterion to be minimized. The minimum of the model in the trust region becomes the next starting point of the algorithm and, depending on the amount of progress made during this step, the confidence region is expanded, contracted or kept unchanged. In the field of global optimization, interval programming may be thought as a kind of confidence region approach, with a binary confidence level: the region is guaranteed to contain the optimum or guaranteed to not contain it. A probabilistic version, known as branch and probability bound, is based on an approximate probability that a region of the search space contains the optimum, and has a confidence level in the interval [0,1]. The method introduced in this paper is an application of the trust region approach within the framework of evolutionary algorithms. Regions of the search space are endowed with a prospectiveness criterion obtained from random sampling possibly coupled with a local continuous algorithm. The regions are considered as individuals for an evolutionary algorithm with mutation and crossover operators based on a transformation group. The performance of the algorithm on some standard benchmark functions is presented.     

Global optimization based on local searches

In this paper we deal with the use of local searches within global optimization algorithms. We discuss different issues, such as the generation of new starting points, the strategies to decide whether to start a local search from a given point, and those to decide whether to keep the point or discard it from further consideration. We present how these topics have been faced in the existing literature and express our opinion on the relative merits of different choices.     

求解凸二次规划问题的一种加权路径跟踪内点算法

基于Darvay提出用加权路径跟踪内点算法解线性规划问题的相关工作,本文致力于将此算法推广于解凸二次规划问题,并证明此算法具有局部二次收敛速度和目前所知的最好的多项式时间算法复杂性.     

Lagrange optimality system for a class of nonsmooth convex optimization

In this paper, we revisit the augmented Lagrangian method for a class of nonsmooth convex optimization. We present the Lagrange optimality system of the augmented Lagrangian associated with the problems, and establish its connections with the standard optimality condition and the saddle point condition of the augmented Lagrangian, which provides a powerful tool for developing numerical algorithms: we derive a Lagrange–Newton algorithm for the nonsmooth convex optimization, and establish the nonsingularity of the Newton system and the local convergence of the algorithm.     

Global Optimization by Multilevel Coordinate Search

Inspired by a method by Jones et al. (1993), we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results.     

A New Superlinearly Convergent Strongly Subfeasible Sequential Quadratic Programming Algorithm for Inequality-Constrained Optimization

Combining the ideas of generalized projection and the strongly subfeasible sequential quadratic programming (SQP) method, we present a new strongly subfeasible SQP algorithm for nonlinearly inequality-constrained optimization problems. The algorithm, in which a new unified step-length search of Armijo type is introduced, starting from an arbitrary initial point, produces a feasible point after a finite number of iterations and from then on becomes a feasible descent SQP algorithm. At each iteration, only one quadratic program needs to be solved, and two correctional directions are obtained simply by explicit formulas that contain the same inverse matrix. Furthermore, the global and superlinear convergence results are proved under mild assumptions without strict complementarity conditions. Finally, some preliminary numerical results show that the proposed algorithm is stable and promising.     

A magnetic resonance device designed via global optimization techniques

In this paper we are concerned with the design of a small low-cost, low-field multipolar magnet for Magnetic Resonance Imaging with a high field uniformity. By introducing appropriate variables, the considered design problem is converted into a global optimization one. This latter problem is solved by means of a new derivative free global optimization method which is a distributed multi-start type algorithm controlled by means of a simulated annealing criterion. In particular, the proposed method employs, as local search engine, a derivative free procedure. Under reasonable assumptions, we prove that this local algorithm is attracted by global minimum points. Additionally, we show that the simulated annealing strategy is able to produce a suitable starting point in a finite number of steps with probability one.This work was supported by CNR/MIUR Research Program Metodi e sistemi di supporto alle decisioni, Rome, Italy.Mathematics Subject Classification (1991):65K05, 62K05, 90C56