On the convergence of two branch-and-bound algorithms for nonconvex programming problems

This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previously that, under certain conditions, whenever the algorithm generates an infinite sequence of points, at least one accumulation point of this sequence is a global minimum. We show here that, for each algorithm, in fact, under these conditions, every accumulation point of such a sequence is a global minimum.The author would like to thank Professor R. M. Soland for his helpful comments concerning this paper.     

Global convergence rates for descent algorithms: Improved results for strictly convex problems

Convergence to the minimal value is studied for the important type of descent algorithm which, at each interation, uses a search direction making an angle with the negative gradient which is smaller than a prespecified angle. Improvements on existing convergence rate results are obtained.Paper received on 4 October, 1977; in revised form, April 3, 1978     

The convergence of broyden algorithms for LC gradient function

1. IntroductionWe know that the variable metric algorithms, such as the Broyden algorithms, are veryefficient methods for solving the nonlinear programming problem:With exact line search, [11 proved that all the Broyden algorithms produce the same iterations for general functions. [21 proved that the rate of convergellce of these algorithms isone-step superlinear for the uniformly convex object function, and [3] proved that if thepoints given by these algorithms are convergent they are globall…     

A convergence for vector valued functions

We give a definition of gamma-convergence (epi-convergence) for the case of vector valued sequences of functions and prove some related properties analogous to the scalar case. We obtain one of the main variational theorems about convergence of ?-minimizers. In the convex case, we consider also variable domains and obtain stability of efficient points and minimal values.     

A generalization of Polyak's convergence result for subgradient optimization

This paper generalizes a practical convergence result first presented by Polyak. This new result presents a theoretical justification for the step size which has been successfully used in several specialized algorithms which incorporate the subgradient optimization approach.     

A convergence for infinite dimensional vector valued functions

By using the definition of Γ-convergence for vector valued functions given in Oppezzi and Rossi (Optimization, to appear), we obtain a property of infimum values of the Γ-limit. By generalizing Mosco convergence to vector valued functions, we also obtain, in the convex case, the extension of some stability results analogous to the ones in Oppezzi and Rossi (optimization, to appear), when domain and value space are infinite dimensional.      

Nested monotony for variational inequalities over product of spaces and convergence of iterative algorithms

The auxiliary problem principle has been proposed by the first author as a framework to describe and analyze iterative algorithms such as gradient as well as decomposition/coordination algorithms for optimization problems (Refs. 1–3) and variational inequalities (Ref. 4). The key assumption to prove the global and strong convergence of such algorithms, as well as of most of the other algorithms proposed in the literature, is the strong monotony of the operator involved in the variational inequalities. In this paper, we consider variational inequalities defined over a product of spaces and we introduce a new property of strong nested monotony, which is weaker than the ordinary overall strong monotony generally assumed. In some sense, this new concept seems to be a minimal requirement to insure convergence of the algorithms alluded to above. A convergence theorem based on this weaker assumption is given. Application of this result to the computation of Nash equilibria can be found in another paper (Ref. 5).This research has been supported by the Centre National de la Recherche Scientifique (ATP Complex Technological Systems) and by the Centre National d'Etudes des Télécommunications (Contract 83.5B.034.PAA).     

Measuring rates of convergence of numerical algorithms

We analyze the behavior of common indices used in numerical linear algebra, analysis, and optimization to measure rates of convergence of an algorithm. A simple consistent axiomatic structure is used to uniquely define convergence rate measures on the basic linear, superlinear, and sublinear scales in terms of standard comparison sequences. Agreement with previously utilized indices and related measures is discussed.This research was supported in part by grants from the Natural Sciences and Engineering Research Council of Canada.The authors are grateful to the referees for comments which improved an earlier draft.     

A feasible direction algorithm for convex optimization: Global convergence rates

At each iteration, the algorithm determines a feasible descent direction by minimizing a linear or quadratic approximation to the cost on the feasible set. The algorithm is easy to implement if the approximation is easy to minimize on the feasible set, which happens in some important cases. Convergence rate information is obtained, which is sufficient to enable deduction of the number of iterations needed to achieve a specified reduction in the distance from the optimum (measured in terms of the cost). Existing convergence rates for algorithms for solving such convex problems are either asymptotic (and so do not enable the required number of iterations to be deduced) or decrease as the number of constraints increases. The convergence rate information obtained here, however, is independent of the number of constraints. For the case where the quadratic approximation to the cost is not strictly convex (which includes the linear approximation case), the diameter is the only property of the feasible set which affects the convergence rate information. If the quadratic approximation is strictly convex, the convergence rate is independent of the size and geometry of the feasible set. An application to a control-constrained optimal control problem is outlined.     

Simplicial zero-point algorithms: A unifying description

In this paper, we consider the limiting paths of simplicial algorithms for finding a zero point. By rewriting the zero-point problem as a problem of finding a stationary point, the problem can be solved by generating a path of stationary points of the function restricted to an expanding convex, compact set. The limiting path of a simplicial algorithm to find a zero point is obtained by choosing this set in an appropriate way. Almost all simplicial algorithms fit in this framework. Using this framework, it can be shown very easily that Merrill's condition is sufficient for convergence of the algorithms.     

Global convergence in infeasible-interior-point algorithms

This paper presents a wide class of globally convergent interior-point algorithms for the nonlinear complementarity problem with a continuously differentiable monotone mapping in terms of a unified global convergence theory given by Polak in 1971 for general nonlinear programs. The class of algorithms is characterized as: Move in a Newton direction for approximating a point on the path of centers of the complementarity problem at each iteration. Starting from a strictly positive but infeasible initial point, each algorithm in the class either generates an approximate solution with a given accuracy or provides us with information that the complementarity problem has no solution in a given bounded set. We present three typical examples of our interior-point algorithms, a horn neighborhood model, a constrained potential reduction model with the use of the standard potential function, and a pure potential reduction model with the use of a new potential function.Research supported in part by Grant-in-Aids for Co-Operative Research (03832017) of the Japan Ministry of Education, Science and Culture.Corresponding author.     

A type of efficient feasible SQP algorithms for inequality constrained optimization

In this paper, motivated by Zhu et al. methods [Z.B. Zhu, K.C. Zhang, J.B. Jian, An improved SQP algorithm for inequality constrained optimization, Math. Meth. Oper. Res. 58 (2003) 271-282; Zhibin Zhu, Jinbao Jian, An efficient feasible SQP algorithm for inequality constrained optimization, Nonlinear Anal. Real World Appl. 10(2) (2009) 1220-1228], we propose a type of efficient feasible SQP algorithms to solve nonlinear inequality constrained optimization problems. By solving only one QP subproblem with a subset of the constraints estimated as active, a class of revised feasible descent directions are generated per single iteration. These methods are implementable and globally convergent. We also prove that the algorithms have superlinear convergence rate under some mild conditions.     

A class of nonmonotone trust region algorithms for unconstrained optimization problems

A class of nonmonotone trust region algorithms is presented for unconstrained optimizations. Under suitable conditions, the global and Q-quadratic convergences of the algorithm are proved. Several rules of choosing trial steps and trust region radii are also discussed. Project supported by the National Natural Science Foundation of China (Grant No. 19136012).     

Extending convergence theory for nonlinear stiff problems part I

Existing convergence concepts for the analysis of discretizations of nonlinear stiff problems suffer from considerable drawbacks. Our intention is to extend the convergence theory to a relevant class of nonlinear problems, where stiffness is axiomatically characterized in natural geometric terms.Our results will be presented in a series of papers. In the present paper (Part I) we motivate the need for such an extension of the existing theory, and our approach is illustrated by means of a convergence argument for the Implicit Euler scheme.     

Measure theory of statistical convergence

The question of establishing measure theory for statistical convergence has been moving closer to center stage, since a kind of reasonable theory is not only fundamental for unifying various kinds of statistical convergence, but also a bridge linking the studies of statistical convergence across measure theory, integration theory, probability and statistics. For this reason, this paper, in terms of subdifferential, first shows a representation theorem for all finitely additive probability measures defined on the σ-algebra of all subsets of N, and proves that every such measure can be uniquely decomposed into a convex combination of a countably additive probability measure and a statistical measure (i.e. a finitely additive probability measure μ with μ(k) = 0 for all singletons {k}). This paper also shows that classical statistical measures have many nice properties, such as: The set of all such measures endowed with the topology of point-wise convergence on forms a compact convex Hausdorff space; every classical statistical measure is of continuity type (hence, atomless), and every specific class of statistical measures fits a complementation minimax rule for every subset in N. Finally, this paper shows that every kind of statistical convergence can be unified in convergence of statistical measures. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10771175, 10471114)     

基于随机搜索的一个约束优化问题的全局收敛算法

讨论了具有一般约束的全局优化问题,给出该问题的一个随机搜索算法,证明了该算法依概率1收敛到问题的全局最优解．数值结果显示该方法是有效的．     

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.     

A unifying local-semilocal convergence analysis and applications for two-point Newton-like methods in Banach space

We provide a local as well as a semilocal convergence analysis for two-point Newton-like methods in a Banach space setting under very general Lipschitz type conditions. Our equation contains a Fréchet differentiable operator F and another operator G whose differentiability is not assumed. Using more precise majorizing sequences than before we provide sufficient convergence conditions for Newton-like methods to a locally unique solution of equation F(x)+G(x)=0. In the semilocal case we show under weaker conditions that our error estimates on the distances involved are finer and the information on the location of the solution at least as precise as in earlier results. In the local case a larger radius of convergence is obtained. Several numerical examples are provided to show that our results compare favorably with earlier ones. As a special case we show that the famous Newton-Kantorovich hypothesis is weakened under the same hypotheses as the ones contained in the Newton-Kantorovich theorem.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

On the convergence of the projected gradient method

We study the projected gradient algorithm for linearly constrained optimization. Wolfe (Ref. 1) has produced a counterexample to show that this algorithm can jam. However, his counterexample is only ¹( ⁿ ), and it is conjectured that the algorithm is convergent for ²-functions. We show that this conjecture is partly right. We also show that one needs more assumptions to prove convergence, since we present a family of counterexamples. We finally give a demonstration that no jamming can occur for quadratic objective functions.This work was supported by the Natural Sciences and Engineering Research Council of Canada