A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

A new LQP alternating direction method for solving variational inequality problems with separable structure

We presented a new logarithmic-quadratic proximal alternating direction scheme for the separable constrained convex programming problem. The predictor is obtained by solving series of related systems of non-linear equations in a parallel wise. The new iterate is obtained by searching the optimal step size along a new descent direction. The new direction is obtained by the linear combination of two descent directions. Global convergence of the proposed method is proved under certain assumptions. We show the O(1 / t) convergence rate for the parallel LQP alternating direction method.     

Two sided error bounds for discretisation methods in ordinary differential equations

A wide class of discretisation methods for ordinary differential equations is introduced and a new concept of consistency, called optimal consistency, is defined. This permits convergence of order exactlyp (that is, two sided error bounds) when the method is optimally consistent of orderp. This is then related to the minimal and optimal stability functionals introduced by Spijker and Albrecht, and a new algebraic criterion is given for a discretisation method consistent of orderp to be convergent of orderp + 1. Finally it is shown that the original motivation for the idea of optimal consistency arises from discretisation methods for Volterra integral equations.     

A new method for constructing infinite families of k-tight optimal double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. DLN has been widely used in the designing of local area networks and distributed systems. In this paper, a new method for constructing infinite families of k-tight optimal DLN is presented. For k = 0, 1, ..., 40, the infinite families of k-tight optimal DLN can be constructed by the new method, where the number n _k (t, a) of their nodes is a polynomial of degree 2 in t and contains a parameter a. And a conjecture is proposed.     

On the computation of the infimum in H∞‐optimization

In this paper, a new method for the computation of the infimum for a large class of continuous‐time H_∞ optimal control problem by state feedback is presented. The main ingredients of the new method include three generalized eigenvalue problems whose coefficient matrices are from a condensed form of the given system. This condensed form is computed using only orthogonal transformations which can be implemented via a numerically stable way. The superiority of the new method over the existing one given in Chen (H_∞ Control and its Applications, Chapter 5. Springer: Berlin, 1997) is verified by some numerical examples. Copyright © 2004 John Wiley & Sons, Ltd.     

An improved general extra-gradient method with refined step size for nonlinear monotone variational inequalities

Extra-gradient method and its modified versions are direct methods for variational inequalities VI(Ω, F) that only need to use the value of function F in the iterative processes. This property makes the type of extra-gradient methods very practical for some variational inequalities arising from the real-world, in which the function F usually does not have any explicit expression and only its value can be observed and/or evaluated for given variable. Generally, such observation and/or evaluation may be obtained via some costly experiments. Based on this view of point, reducing the times of observing the value of function F in those methods is meaningful in practice. In this paper, a new strategy for computing step size is proposed in general extra-gradient method. With the new step size strategy, the general extra-gradient method needs to cost a relatively minor amount of computation to obtain a new step size, and can achieve the purpose of saving the amount of computing the value of F in solving VI(Ω, F). Further, the convergence analysis of the new algorithm and the properties related to the step size strategy are also discussed in this paper. Numerical experiments are given and show that the amount of computing the value of function F in solving VI(Ω, F) can be saved about 12–25% by the new general extra-gradient method.     

On the Higher-Order Method for the Solution of a Nonlinear Scalar Equation

In this paper, a higher-order method for the solution of a nonlinear scalar equation is presented. It is proved that the new method is locally convergent with an order of (m+2), where m is the highest order derivative used in the iterative formula. Some numerical examples are used to demonstrate the new method.     

Fast Algorithm for Cross-Validation of the Best Linear Unbiased Predictor

This article proposes a new algorithm for cross-validation of the best linear unbiased predictor. The algorithm relies on a new technique for downdating the inverse of a Cholesky factor. Given n data points, the new algorithm has complexity O(n³), compared to O(n⁴), which is the order for the more traditional delete one and recalculate method.     

A New Gradient Method for Ill-Posed Problems

In this paper, we present a new gradient method for linear and nonlinear ill-posed problems F(x) = y. Combined with the discrepancy principle as stopping rule it is a regularization method that yields convergence to an exact solution if the operator F satisfies a tangential cone condition. If the exact solution satisfies smoothness conditions, then even convergence rates can be proven. Numerical results show that the new method in most cases needs less iteration steps than Landweber iteration, the steepest descent or minimal error method.     

Geometric heuristics for rural radio maps approximation

Given a terrain T and an antenna A located on it, we would like to approximate the Radio Map of A over T, namely, to associate a signal strength for each point p∈T as received from A. This work presents a new Radio Map approximation algorithm using an adaptive radial sweep-line technique. The suggested radar-like algorithm (RLA) uses a pipe-line method for computing the signal strength along points on a ray, and an adaptive method for interpolating the signal strength over regions between two consecutive rays. Whenever the difference between two consecutive rays is above a certain threshold, a middle ray is created. Thus, the density of the sampling rays is sensitive to the shape of the terrain. Finally, we report on an experiment which compares the new algorithm with other well-known methods. The main conclusion is that the new RLA is significantly faster than the others, i.e., its running time is 3–15 times faster for the same approximation accuracy.     

A new investigation of the extended Krylov subspace method for matrix function evaluations

For large square matrices A and functions f, the numerical approximation of the action of f(A) to a vector v has received considerable attention in the last two decades. In this paper we investigate theextended Krylov subspace method, a technique that was recently proposed to approximate f(A)v for A symmetric. We provide a new theoretical analysis of the method, which improves the original result for A symmetric, and gives a new estimate for A nonsymmetric. Numerical experiments confirm that the new error estimates correctly capture the linear asymptotic convergence rate of the approximation. By using recent algorithmic improvements, we also show that the method is computationally competitive with respect to other enhancement techniques. Copyright © 2009 John Wiley & Sons, Ltd.     

A method of estimating computational complexity based on input conditions for N-vehicle problem

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.     

A family of quasi-Newton methods for unconstrained optimization problems

ABSTRACT

In this paper, we present a class of approximating matrices as a function of a scalar parameter that includes the Davidon-Fletcher-Powell and Broyden-Fletcher-Goldfarb-Shanno methods as special cases. A powerful iterative descent method for finding a local minimum of a function of several variables is described. The new method maintains the positive definiteness of the approximating matrices. For a region in which the function depends quadratically on the variables, no more than n iterations are required, where n is the number of variables. A set of computational results that verifies the superiority of the new method are presented.     

A NEW TRUST REGION DOGLEG METHOD FOR UNCONSTRAINED OPTIMIZATION

Abstract. This paper presents a new trust region dogleg method for unconstrained optimization.The method can deal with the case when the Hessian B of quadratic models is indefinite. It isproved that the method is globally convergent and has a quadratic convergence rate if Under certain conditions, the solution obtained by the method is even a second order     

A conjugate directions method for subjective assessment of normal distributions

A procedure is developed that enables the encoding of a subjectiven-dimensional joint normal probability density function through the assessment of its marginal means and variances andn(n–1)/2 conditional means. The new method is based on the theory of conjugate directions for quadratic forms, and it exploits the fact that normal distributions have quadratic equal-likelihood surfaces. Unlike previous approaches, this new method enables easy detection and resolution of inconsistencies in the assessments that could lead to an indefinite estimate of the covariance matrix.     

A new bounding method for single facility location models

This paper develops a new lower bound for single facility location problems withl _p distances. We prove that the method produces superior results to other known procedures. The new bound is also computationally efficient. Numerical results are given for a range of examples with varying numbers of existing facilities andp values.     

A Method of Deducing L-Polyhedra for n-Lattices

We suggest a method for selecting an L-simplex in an L-polyhedron of an n-lattice in Euclidean space. By taking into account the specific form of the condition that a simplex in the lattice is an L-simplex and by considering a simplex selected from an L-polyhedron, we present a new method for describing all types of L-polyhedra in lattices of given dimension n. We apply the method to deduce all types of L-polyhedra in n-dimensional lattices for n=2,3,4, which are already known from previous results.     

Distribution of Nonlinear Congruential Pseudorandom Numbers Modulo Almost Squarefree Integers

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present a new bound on the s-dimensional discrepancy of nonlinear congruential pseudorandom numbers over the residue ring \Bbb Z_M{\Bbb Z}_M modulo M for an “almost squarefree” integer M. It is useful to recall that almost all integers are of this type. Moreover, if the generator is associated with a permutation polynomial over \Bbb Z_M{\Bbb Z}_M we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

A method for computing the Perron root for primitive matrices

Following the Perron theorem, the spectral radius of a primitive matrix is a simple eigenvalue. It is shown that for a primitive matrix A, there is a positive rank one matrix X such that B = A ° X , where ° denotes the Hadamard product of matrices, and such that the row (column) sums of matrix B are the same and equal to the Perron root. An iterative algorithm is presented to obtain matrix B without an explicit knowledge of X. The convergence rate of this algorithm is similar to that of the power method but it uses less computational load. A byproduct of the proposed algorithm is a new method for calculating the first eigenvector.