On the convergence of curvilinear search algorithms in unconstrained optimization

The purpose of this paper is to unify the conditions under which curvilinear algorithms for unconstrained optimization converge. Particularly, two gradient path approximation algorithms and a trust region curvilinear algorithm are examined in this context.     

On the complexity of optimization over the standard simplex

We review complexity results for minimizing polynomials over the standard simplex and unit hypercube. In addition, we derive new results on the computational complexity of approximating the minimum of some classes of functions (including Lipschitz continuous functions) on the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on the simplex combined with an earlier result by de Klerk et al. [A PTAS for the minimization of polynomials of fixed degree over the simplex, Theoretical Computer Science 361 (2–3) (2006) 210–225].     

On geometric convergence rate of Markov search towards the fat target

Let $f:A\to \mathbb{R}$ be a continuous function with the minimal value $f^{?}$, where $A$ is the compact metric space. Let ${\left\{X_t\right\}}_{t\in \mathbb{N}}$ be a Markov chain which represents the global optimization process on $A$. We present sufficient conditions for very strong, geometric convergence mode of the form $Ef\left(X_t\right)?f^1\le c^t?(Ef\left(X_0\right)?f^1)$, where $c\in (0,1)$ is some constant. This convergence mode is natural if the set of global minima is fat.     

On the rate of convergence of one inhomogeneous Markov algorithm of search for extremum

The paper is concerned with theoretical study of the rate of convergence of one inhomogeneous Markov random algorithm of search for extremum. Methods of random search have value in solving involved optimization problems. However, there are only few theoretical results concerning the rate of convergence of these algorithms.     

On the convergence rate of the Markov homogeneous monotone optimization method

An estimate of the convergence rate of some homogeneous Markov monotone random search optimization algorithms is obtained.     

A hybrid simplex search and particle swarm optimization for unconstrained optimization

This paper proposes the hybrid NM-PSO algorithm based on the Nelder–Mead (NM) simplex search method and particle swarm optimization (PSO) for unconstrained optimization. NM-PSO is very easy to implement in practice since it does not require gradient computation. The modification of both the Nelder–Mead simplex search method and particle swarm optimization intends to produce faster and more accurate convergence. The main purpose of the paper is to demonstrate how the standard particle swarm optimizers can be improved by incorporating a hybridization strategy. In a suite of 20 test function problems taken from the literature, computational results via a comprehensive experimental study, preceded by the investigation of parameter selection, show that the hybrid NM-PSO approach outperforms other three relevant search techniques (i.e., the original NM simplex search method, the original PSO and the guaranteed convergence particle swarm optimization (GCPSO)) in terms of solution quality and convergence rate. In a later part of the comparative experiment, the NM-PSO algorithm is compared to various most up-to-date cooperative PSO (CPSO) procedures appearing in the literature. The comparison report still largely favors the NM-PSO algorithm in the performance of accuracy, robustness and function evaluation. As evidenced by the overall assessment based on two kinds of computational experience, the new algorithm has demonstrated to be extremely effective and efficient at locating best-practice optimal solutions for unconstrained optimization.     

单纯型上Meyer-K(o)nig-Zeller算子逼近收敛阶的估计

利用分解技巧及一元的结论,讨论单纯型上Meyer-K(o)nig-Zeller算子逼近的收敛阶,得到逼近的正定理.     

On hermitian polynomial optimization

We compare three levels of algebraic certificates for evaluating the maximum modulus of a complex analytic polynomial, on a compact semi-algebraic set. They are obtained as translations of some recently discovered inequalities in operator theory. Although they can be stated in purely algebraic terms, the only known proofs for these decompositions have a transcendental character. Received: 27 June 2005     

On convergence rate of a rectangular partition based global optimization algorithm

The convergence rate of a rectangular partition based algorithm is considered. A hyper-rectangle for the subdivision is selected at each step according to a criterion rooted in the statistical models based theory of global optimization; only the objective function values are used to compute the criterion of selection. The convergence rate is analyzed assuming that the objective functions are twice- continuously differentiable and defined on the unit cube in d-dimensional Euclidean space. An asymptotic bound on the convergence rate is established. The results of numerical experiments are included.     

求解凸规划及鞍点问题定制的PPA 算法及其收敛速率

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式. 在变分不等式框架下求解这些问题, 选取适当的矩阵G, 采用G- 模下的PPA 算法, 会使迭代过程中的子问题求解变得相当容易. 本文证明这类定制的PPA 算法的误差界有1/k 的收敛速率.     

On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems

In this paper, we analyse the convergence rate of the sequence of objective function values of a primal-dual proximal-point algorithm recently introduced in the literature for solving a primal convex optimization problem having as objective the sum of linearly composed infimal convolutions, nonsmooth and smooth convex functions and its Fenchel-type dual one. The theoretical part is illustrated by numerical experiments in image processing.     

On the rate of strong convergence for convolutions

An estimate of the rate of strong convergence of convolutions of probability measures is given under the assumption that the components of each convolution converge weakly and in total variation, respectively. Reported at the XVI Seminar on Stability Problems for Stochastic Models, Eger, Hungary, 29 August–3 September 1994. Received by the Editorial Board 15 January, 1996. Proceedings of the XVII Seminar on Stability Problems for Stochastic Models, Kazan, Russia, 1995, Part II.     

On the convergence of the LJ search method

The convergence of the Luus-Jaakola search method for unconstrained optimization problems is established.Notation E _n Euclideann-space - f Gradient off(x) - ² f Hessian matrix - (·) ^T Transpose of (·) - I Index set {1, 2, ...,n} - [x _i1 ^*(j) ] Point around which search is made in the (j + 1)th iteration, i.e., [x _1l ^*(j) ,x _2l ^*(j) ,...,x _n1 ^*(j) ] - r _i ⁽ⁱ⁾ Range ofx _il ^*(i) in the (j + 1)th iteration - l ₁ min_i {r _i ⁽⁰⁾ } - l ₂ min_i {r _i ⁽⁰⁾ } - A _j Region of search in thejth iteration, i.e., {x E _n:x _il ^*(j-1) –0.5r _i ^(j-1) x _ix _il ^*(j-1) +0.5r _i ^(j-1) ,i I} - S _j Closed sphere with center origin and radius _j - Reduction factor in each iteration - 1– - (·) Gamma function Many discussions with Dr. S. N. Iyer, Professor of Electrical Engineering, College of Engineering, Trivandrum, India, are gratefully acknowledged. The author has great pleasure to thank Dr. K. Surendran, Professor, Department of Electrical Engineering, P.S.G. College of Technology, Coimbatore, India, for suggesting this work.     

On strongly polynomial dual simplex algorithms for the maximum flow problem

Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n ² m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.     

On the guaranteed convergence of new two-point root-finding methods for polynomial zeros

We presented new two-point methods for the simultaneous approximation of all n simple (real or complex) zeros of a polynomial of degree n. We proved that the R-order of convergence of the total-step version is three. Moreover, computationally verifiable initial conditions that guarantee the convergence of one of the proposed methods are stated. These conditions are stated in the spirit of Smale’s point estimation theory; they depend only on available data, the polynomial coefficients, polynomial degree n and initial approximations \(x_{1}^{(0)},\ldots ,x_{n}^{(0)}\) , which is of practical importance. Using the Gauss-Seidel approach we state the corresponding single-step version and consequently its prove that the lower bound of its R-order of convergence is at least 2 + y _n > 3, where y _n ∈ (1, 2) is the unique positive root of the equation y ⁿ ? y ? 2 = 0. Two numerical examples are given to demonstrate the convergence behavior of the considered methods, including global convergence.     

Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms.     

On the convergence of sequential number-theoretic method for optimization

1. IntroductionIn the papers [l] and [2] H. Niederreiter and K. McCurley gave a quasi-Monte Carlolnethod for the approxiInate computation of the extreme values of a mu1tivariab1e function.In l989 K.T. Fa11g and Y. Wang["'l proposed a sequential algorithm fOr optinlization bya number-theoretic method (abbr. SNTO), which is nlore effective than the Niederreiter'smethod in some cases, but it lacks a complete convergence result concerlling the a1gorithm.In the present note we will approach…     

On the uniform nonsingularity of matrices of search directions and the rate of convergence in minimization algorithms

A convergent minimization algorithm made up of repetitive line searches is considered in ⁿ . It is shown that the uniform nonsingularity of the matrices consisting ofn successive normalized search directions guarantees a speed of convergence which is at leastn-step Q-linear. Consequences are given for multistep methods, including Powell's 1964 procedure for function minimization without calculating derivatives as well as Zangwill's modifications of this procedure.The authors wish to thank the Namur Department of Mathematics, especially its optimization group, for many discussions and encouragement. They also thank the reviewers for many helpful suggestions.