Analyzing the Performance of Generalized Hill Climbing Algorithms

Generalized hill climbing algorithms provide a framework to describe and analyze metaheuristics for addressing intractable discrete optimization problems. The performance of such algorithms can be assessed asymptotically, either through convergence results or by comparison to other algorithms. This paper presents necessary and sufficient convergence conditions for generalized hill climbing algorithms. These conditions are shown to be equivalent to necessary and sufficient convergence conditions for simulated annealing when the generalized hill climbing algorithm is restricted to simulated annealing. Performance measures are also introduced that permit generalized hill climbing algorithms to be compared using random restart local search. These results identify a solution landscape parameter based on the basins of attraction for local optima that determines whether simulated annealing or random restart local search is more effective in visiting a global optimum. The implications and limitations of these results are discussed.     

Tabu Guided Generalized Hill Climbing Algorithms

This paper formulates tabu search strategies that guide generalized hill climbing (GHC) algorithms for addressing NP-hard discrete optimization problems. The resulting framework, termed tabu guided generalized hill climbing (TG²HC) algorithms, uses a tabu release parameter that probabilistically accepts solutions currently on the tabu list. TG²HC algorithms are modeled as a set of stationary Markov chains, where the tabu list is fixed for each outer loop iteration. This framework provides practitioners with guidelines for developing tabu search strategies to use in conjunction with GHC algorithms that preserve some of the algorithms known performance properties. In particular, sufficient conditions are obtained that indicate how to design iterations of problem-specific tabu search strategies, where the stationary distributions associated with each of these iterations converge to the distribution with zero weight on all non-optimal solutions.     

Taylorian fields and subdivision algorithms

Some recents papers [3,8] provide a new approach for the concept of subdivision algorithms, widely used in CAGD: they develop the idea of interpolatory subdivision schemes for curves. In this paper, we show how the old results of H. Whitney [13,14] on Taylorian fields giving necessary and sufficient conditions for a function to be of classC ^k on a compact provide also necessary and sufficient conditions which can be used to construct interpolatory subdivision schemes, in order to obtain, at the limit, aC ¹ (orC ^k ,k>1 eventually) function. Moreover, we give general results for the approximation properties of these schemes, and error bounds for the approximation of a given function.     

Optimality conditions in preference-based spanning tree problems

Spanning tree problems defined in a preference-based environment are addressed. In this approach, optimality conditions for the minimum-weight spanning tree problem (MST) are generalized for use with other, more general preference orders. The main goal of this paper is to determine which properties of the preference relations are sufficient to assure that the set of ‘most-preferred’ trees is the set of spanning trees verifying the optimality conditions. Finally, algorithms for the construction of the set of spanning trees fulfilling the optimality conditions are designed, improving the methods in previous papers.     

Convergence of the parallel chaotic waveform relaxation method for stiff systems

In this paper, we establish several algorithms for parallel chaotic waveform relaxation methods for solving linear ordinary differential systems based on some given models. Under some different assumptions on the coefficient matrix A and its multisplittings we obtain corresponding sufficient conditions of convergence of the algorithms. Also a discussion on convergence speed comparison of synchronous and asynchronous algorithms is given.     

Local analysis of Newton-type methods for variational inequalities and nonlinear programming

This paper presents some new results in the theory of Newton-type methods for variational inequalities, and their application to nonlinear programming. A condition of semistability is shown to ensure the quadratic convergence of Newton's method and the superlinear convergence of some quasi-Newton algorithms, provided the sequence defined by the algorithm exists and converges. A partial extension of these results to nonsmooth functions is given. The second part of the paper considers some particular variational inequalities with unknowns (x, ), generalizing optimality systems. Here only the question of superlinear convergence of {x ^k } is considered. Some necessary or sufficient conditions are given. Applied to some quasi-Newton algorithms they allow us to obtain the superlinear convergence of {x ^k }. Application of the previous results to nonlinear programming allows us to strengthen the known results, the main point being a characterization of the superlinear convergence of {x ^k } assuming a weak second-order condition without strict complementarity.     

Regularity for some scalar variational problems under general growth conditions

We consider integrals of the calculus of variations over a set Ω of ? ⁿ , and the related regularity result: are the minimizers smooth functions, say for example of classC ^∞(Ω)? Classically, the so-called natural growth conditions on the integrand have been the main sufficient assumptions for regularity. In recent years, motivated also by application, the interest in the study of this problem has increased under more general growth assumptions. In this paper, we propose some general growth conditions that guarantee regularity for a class of scalar variational problems.     

Onl p solutions of discrete Volterra equations

Summary In the paper a discrete analog to the Volterra nonlinear integral equation is discussed. Weighted norms are used to find sufficient conditions that all solutions of such equations are elements of anl ^p space.Some generalizations ofl ^p spaces are also considered and the corresponding sufficient conditions are established.     

Ultimately periodic extension of partial endomorphisms of groups

Necessary and sufficient conditions for extending a partial endomorphism μ of a groupG to a total endomorphismμ ^* of a supergroup ofG are known. In this paper conditions, which are both necessary and sufficient, forμ ^* to be ultimately periodic are obtained.     

Global convergence of some differential equation algorithms for solving equations involving positive variables

This paper describes some sufficient conditions for global convergence in five differential equation algorithms for solving systems of non-linear algebraic equations involving positive variables. The algorithms are continuous time versions of a modified steepest descent method, Newton's method, a modified Newton's method and two algorithms using the transpose of the Jacobian in place of the inverse of the Jacobian in Newton's method. It is shown that under a set of mildly restrictive conditions the Jacobian transpose algorithm has qualitatively the same convergence as Newton's method.     

Perfect simulation for locally continuous chains of infinite order

We establish sufficient conditions for perfect simulation of chains of infinite order on a countable alphabet. The new assumption, localized continuity, is formalized with the help of the notion of context trees, and includes the traditional continuous case, probabilistic context trees and discontinuous kernels. Since our assumptions are more refined than uniform continuity, our algorithms perfectly simulate continuous chains faster than the existing algorithms of the literature. We provide several illustrative examples.     

The diffeomorphic types of the complements of arrangements in ℂℙ3 II

For any arrangement of hyperplanes in ??³, we introduce the soul of this arrangement. The soul, which is a pseudo-complex, is determined by the combinatorics of the arrangement of hyperplanes. In this paper, we give a sufficient combinatoric condition for two arrangements of hyperplanes to be diffeomorphic to each other. In particular we have found sufficient conditions on combinatorics for the arrangement of hyperplanes whose moduli space is connected. This generalizes our previous result on hyperplane point arrangements in ??³.     

Variable metric algorithms: Necessary and sufficient conditions for identical behavior of nonquadratic functions

Huang (Ref. 1) introduced a general family of variable metric updating formulas and showed that, for a convex quadratic function, all members of this family generate the same sequence of points and converge in at mostn steps. Huang and Levy (Ref. 2) published numerical data showing the behavior of this family for nonquadratic functions and concluded that this family could be divided into subsets that also generate sequences of identical points on more general functions. In this paper, the necessary and sufficient conditions for a group of algorithms to form part of one of these subsets are given.     

标准Jacobi矩阵的混合型特征反问题

0 引言 本文讨论如下标准形式的Jacobi矩阵 其中a_i>0(i=1,2,…,n),b_i>0(i=1,2,…,n-1)。 对于Jacobi矩阵(对称三对角矩阵)的特征反问题,已有的成果[1],基本上集中在由两组频谱或两个特征对(指特征值及相应的特征向量)构造Jacobi矩阵的元素这样两类问题上,习惯上称之为频谱型或特征向量型反问题。本文提出且求解了第三类型——混合型特征反问题。即由一组频谱数据和一个特征向量构造矩阵元素的问题: 问题Ⅰ 给定正数λ~(1),λ~(2),…,λ~(n)和实向量x=(x_1,x_2,…,x_n)~T,其中x_1=1。构造一个标准形式的Jacobi矩阵J,使其第k阶顺序主子阵恰以λ~(k)(k=1,2,…,n)为其特征值。且(λ~(n),x)为其特征对。 问题Ⅱ 给定正数0<λ_1~(n)<λ_1~(n-1)<…<λ_1~(1)和正向量x=(x_1,x_2,…,x_n),其中x_=,x_k>0(k=2,…,n),构造一个标准形式的Jacobi矩阵J,使其第K阶顺序主子阵恰以λ_1~(k)为其最小特征值,而(λ~(n),x)为J的特征对。 问题Ⅲ 给定n个实数0<λ_1)<λ_2<…<λ_n和m个实数λ~(1),λ~(2),…,λ~(m)及m维向量x=(x_1,…,x_m)~T。构造n阶标准形式的Jaeobi矩阵J,使其第K阶顺序主子阵恰以λ~(k)(k=1,2,…,m)为其特征值,而(λ~(m),x)为第m阶顺序主子阵的特征对,且λ_k(k=1,2,…,n)为J的特征值。这里系大于或等     

First-order conditions for isolated locally optimal solutions

There are well-known first-order sufficient conditions for a pointx ₀ to be a strict locally optimal solution of a nonlinear programming problem. In this paper, we show that these conditions also guarantee thatx ₀ is an isolated stationary point of the considered program provided a constraint qualification holds. This result has an interesting application to finite convergence of algorithms along the lines suggested by Al-Khayyal and Kyparisis.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

Optimal scaling of random-walk metropolis algorithms on general target distributions

One main limitation of the existing optimal scaling results for Metropolis–Hastings algorithms is that the assumptions on the target distribution are unrealistic. In this paper, we consider optimal scaling of random-walk Metropolis algorithms on general target distributions in high dimensions arising from practical MCMC models from Bayesian statistics. For optimal scaling by maximizing expected squared jumping distance (ESJD), we show the asymptotically optimal acceptance rate 0.234 can be obtained under general realistic sufficient conditions on the target distribution. The new sufficient conditions are easy to be verified and may hold for some general classes of MCMC models arising from Bayesian statistics applications, which substantially generalize the product i.i.d. condition required in most existing literature of optimal scaling. Furthermore, we show one-dimensional diffusion limits can be obtained under slightly stronger conditions, which still allow dependent coordinates of the target distribution. We also connect the new diffusion limit results to complexity bounds of Metropolis algorithms in high dimensions.     

Symmetric low‐rank corrections to quadratic models

In this paper, we study the quadratic model updating problems by using symmetric low‐rank correcting, which incorporates the measured model data into the analytical quadratic model to produce an adjusted model that matches the experimental model data, and minimizes the distance between the analytical and updated models. We give a necessary and sufficient condition on the existence of solutions to the symmetric low‐rank correcting problems under some mild conditions, and propose two algorithms for finding approximate solutions to the corresponding optimization problems. The good performance of the two algorithms is illustrated by numerical examples. Copyright © 2008 John Wiley & Sons, Ltd.     

Tractability results for the weighted star-discrepancy

The weighted star-discrepancy has been introduced by Sloan and Wo?niakowski to reflect the fact that in multidimensional integration problems some coordinates of a function may be more important than others. It provides upper bounds for the error of multidimensional numerical integration algorithms for functions belonging to weighted function spaces of Sobolev type. In the present paper, we prove several tractability results for the weighted star-discrepancy. In particular, we obtain rather sharp sufficient conditions under which the weighted star-discrepancy is strongly tractable. The proofs are probabilistic, and use empirical process theory.     

Reverse order laws in C-algebras

In this paper, we offer purely algebraic necessary and sufficient conditions for reverse order laws for generalized inverses in C^∗-algebras, extending rank conditions for matrices and range conditions for Hilbert space operators.     

Existence of the uniformly minimum risk equivariant estimators of parameters in a class of normal linear models

In this paper, we study the existence of the uniformly minimum risk equivariant (UMRE) estimators of parameters in a class of normal linear models, which include the normal variance components model, the growth curve model, the extended growth curve model, and the seemingly unrelated regression equations model, and so on. The necessary and sufficient conditions are given for the existence of UMRE estimators of the estimable linear functions of regression coefficients, the covariance matrixV and (trV)^α, where α > 0 is known, in the models under an affine group of transformations for quadratic losses and matrix losses, respectively. Under the (extended) growth curve model and the seemingly unrelated regression equations model, the conclusions given in literature for estimating regression coefficients can be derived by applying the general results in this paper, and the sufficient conditions for non-existence of UMRE estimators ofV and tr(V) are expanded to be necessary and sufficient conditions. In addition, the necessary and sufficient conditions that there exist UMRE estimators of parameters in the variance components model are obtained for the first time.