On the partial synchronization of iterative methods

The rapidly growing field of parallel computing systems promotes the study of parallel algorithms, with the Monte Carlo method and asynchronous iterations being among the most valuable types. These algorithms have a number of advantages. There is no need for a global time in a parallel system (no need for synchronization), and all computational resources are efficiently loaded (the minimum processor idle time). The method of partial synchronization of iterations for systems of equations was proposed by the authors earlier. In this article, this method is generalized to include the case of nonlinear equations of the form x = F(x), where x is an unknown column vector of length n, and F is an operator from ?ⁿ into ?ⁿ. We consider operators that do not satisfy conditions that are sufficient for the convergence of asynchronous iterations, with simple iterations still converging. In this case, one can specify such an incidence of the operator and such properties of the parallel system that asynchronous iterations fail to converge. Partial synchronization is one of the effective ways to solve this problem. An algorithm is proposed that guarantees the convergence of asynchronous iterations and the Monte Carlo method for the above class of operators. The rate of convergence of the algorithm is estimated. The results can prove useful for solving high-dimensional problems on multiprocessor computational systems.     

Local search for multiprocessor scheduling: how many moves does it take to a local optimum?

We analyze two local search algorithms for multiprocessor scheduling. The first algorithm is a job interchange algorithm for identical parallel machines due to Finn and Horowitz (Bit 19 (1979) 312). We construct instances for which this algorithm takes a quadratic number of iterations. This contradicts the original analysis of Finn and Horowitz who claimed a linear number of iterations.The second algorithm adds an additional rule to the Finn and Horowitz algorithm. Even for n jobs on m uniformly related machines, this modified algorithm takes only O(nm) iterations.     

Curvature integrals and iteration complexities in SDP and symmetric cone programs

In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. Integrating curvature along the central path, we obtain a precise estimate of the number of iterations to solve the problem. It has been shown for LP that the number of iterations is asymptotically precisely estimated with the integral divided by $\sqrt{\beta}$ , where β is the opening parameter of the neighborhood of the central path in MTY-PC algorithms. Furthermore, this estimate agrees quite well with the observed number of iterations of the algorithm even when β is close to one and when applied to solve large LP instances from NETLIB. The purpose of this paper is to develop direct extensions of these two results to SDP and symmetric cone programs. More specifically, we give concrete formulas for curvature integrals in SDP and symmetric cone programs and give asymptotic estimates for iteration complexities. Through numerical experiments with large SDP instances from SDPLIB, we demonstrate that the number of iterations is explained quite well with the integral even for a large step size which is enough to solve practical large problems.     

Computing the matrix sign and absolute value functions

We present two algorithms for the computation of the matrix sign and absolute value functions. Both algorithms avoid a complete diagonalisation of the matrix, but they however require some informations regarding the eigenvalues location. The first algorithm consists in a sequence of polynomial iterations based on appropriate estimates of the eigenvalues, and converging to the matrix sign if all the eigenvalues are real. Convergence is obtained within a finite number of steps when the eigenvalues are exactly known. Nevertheless, we present a second approach for the computation of the matrix sign and absolute value functions, when the eigenvalues are exactly known. This approach is based on the resolution of an interpolation problem, can handle the case of complex eigenvalues and appears to be faster than the iterative approach. To cite this article: M. Ndjinga, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Average number of iterations of some polynomial interior-point ——Algorithms for linear programming

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above byO(n ^1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.     

Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems

Discretization algorithms for semiinfinite minimax problems replace the original problem, containing an infinite number of functions, by an approximation involving a finite number, and then solve the resulting approximate problem. The approximation gives rise to a discretization error, and suboptimal solution of the approximate problem gives rise to an optimization error. Accounting for both discretization and optimization errors, we determine the rate of convergence of discretization algorithms, as a computing budget tends to infinity. We find that the rate of convergence depends on the class of optimization algorithms used to solve the approximate problem as well as the policy for selecting discretization level and number of optimization iterations. We construct optimal policies that achieve the best possible rate of convergence and find that, under certain circumstances, the better rate is obtained by inexpensive gradient methods.     

On a stopping rule for iterative orthogonalization of symmetric matrices

In this paper we consider three versions of Kovarik's iterative orthogonalization algorithms, for approximating the minimal norm solution of symmetric least squares problems. Although the convergence of these algorithms is linear, in practical applications we observed that a too big number of iterations can dramatically deteriorate the already obtained approximation. In this respect we analyse the above mentioned Kovarik–like methods according to the modifications they make on the “machine zero” eigenvalues of the problem (symmetric) matrix. We establish a theoretical almost optimal formula for the number of iterations necessary to obtain an enough accurate approximation, as well as to avoid the above mentioned troubles. Experiments on collocation discretization of a Fredholm first kind integral equation ilustrate the efficiency of our considerations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Performance Analysis of Cyclical Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Measures for assessing the finite-time performance of GHC algorithms have been developed using this framework, including the expected number of iterations to visit a predetermined objective function value level. This paper analyzes how the expected number of iterations to visit a predetermined objective function value level can be estimated for cyclical simulated annealing. Cyclical simulated annealing uses a cooling schedule that cycles through a set of temperature values. Computational results with traveling salesman problem instances taken from TSPLIB show how the expected number of iterations to visit solutions with predetermined objective function levels can be estimated for cyclical simulated annealing.AMS 2000 Subject Classification 90-08 Computational Methods: Local Search, 90C59 Heuristics: Simulated Annealing     

Adaptive constraint reduction for convex quadratic programming

We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. Numerical experiments on random problems, on a data-fitting problem, and on a problem in array pattern synthesis show the effectiveness of the constraint reduction in decreasing the time per iteration without significantly affecting the number of iterations. We note that a similar constraint-reduction approach can be applied to algorithms of Mehrotra’s predictor-corrector type, although no convergence theory is supplied.     

General alternative regularization method for solving split equality common fixed point problem for quasi-pseudocontractive mappings in Hilbert spaces

We propose a general alternative regularization algorithm for solving the split equality fixed point problem for the class of quasi-pseudocontractive mappings in Hilbert spaces. We also illustrate the performance of our algorithm with numerical example and compare the result with some other algorithms in the literature in this direction. We found out that our algorithm requires a lesser number of iterations and CPU time for its convergence than some of the existing algorithms. Our results extend and generalize some existing results in the literature in this direction.     

The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

This paper is concerned with the minimum cost flow problem. It is shown that the class of dual algorithms which solve this problem consists of different variants of a common general algorithm. We develop a new variant which is, in fact, a new form of the ‘primal-dual algorithm’ and which has several interesting properties. It uses, explicitly only dual variables. The slope of the change in the (dual) objective is monotone. The bound on the maximum number of iterations to solve a problem with integral bounds on the flow is better than bounds for other algorithms. This paper is part of the author's doctoral dissertation submitted at Yale University.     

A parareal approach of semi‐linear parabolic equations based on general waveform relaxation

We present a parareal approach of semi‐linear parabolic equations based on general waveform relaxation (WR) at the partial differential equation (PDE) level. An algorithm for initial‐boundary value problem and two algorithms for time‐periodic boundary value problem are constructed. The convergence analysis of three algorithms are provided. The results show that the algorithm for initial‐boundary value problem is superlinearly convergent while both algorithms for the time‐periodic boundary value problem linearly converge to the exact solutions at most. Numerical experiments show that the parareal algorithms based on general WR at the PDE level, compared with the parareal algorithm based on the classical WR at the ordinary differential equations (ODEs) level (the PDEs is discretized into ODEs), require much fewer number of iterations to converge.     

A new algorithm for the intersection of a line with the independent set polytope of a matroid

We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n⁵). Finally, numerical tests reveal that it should only require O(n²) iterations in practice.     

An application of Lemke's method to a class of Markov decision problems

This paper presents an application of Lemke's method to a class of Markov decision problems, appearing in the optimal stopping problems, and other well-known optimization problems. We consider a special case of the Markov decision problems with finitely many states, where the agent can choose one of the alternatives; getting a fixed reward immediately or paying the penalty for one term. We show that the problem can be reduced to a linear complementarity problem that can be solved by Lemke's method with the number of iterations less than the number of states. The reduced linear complementarity problem does not necessarily satisfy the copositive-plus condition. Nevertheless we show that the Lemke's method succeeds in solving the problem by proving that the problem satisfies a necessary and sufficient condition for the extended Lemke's method to compute a solution in the piecewise linear complementarity problem.     

Subdivision of simplices relative to a cutting plane and finite concave minimization

In this article, our primary concern is the classical problem of minimizing globally a concave function over a compact polyhedron (Problem (P)). We present a new simplicial branch and bound approach, which combines triangulations of intersections of simplices with halfspaces and ideas from outer approximation in such a way, that a class of finite algorithms for solving (P) results. For arbitrary compact convex feasible sets one obtains a not necessarily finite but convergent algorithm. Theoretical investigations include determination of the number of simplices in each applied triangulation step and bounds on the number of iterations in the resulting algorithms. Preliminary numerical results are given, and additional applications are sketched.     

Q-learning and policy iteration algorithms for stochastic shortest path problems

We consider the stochastic shortest path problem, a classical finite-state Markovian decision problem with a termination state, and we propose new convergent Q-learning algorithms that combine elements of policy iteration and classical Q-learning/value iteration. These algorithms are related to the ones introduced by the authors for discounted problems in Bertsekas and Yu (Math. Oper. Res. 37(1):66-94, 2012). The main difference from the standard policy iteration approach is in the policy evaluation phase: instead of solving a linear system of equations, our algorithm solves an optimal stopping problem inexactly with a finite number of value iterations. The main advantage over the standard Q-learning approach is lower overhead: most iterations do not require a minimization over all controls, in the spirit of modified policy iteration. We prove the convergence of asynchronous deterministic and stochastic lookup table implementations of our method for undiscounted, total cost stochastic shortest path problems. These implementations overcome some of the traditional convergence difficulties of asynchronous modified policy iteration, and provide policy iteration-like alternative Q-learning schemes with as reliable convergence as classical Q-learning. We also discuss methods that use basis function approximations of Q-factors and we give an associated error bound.     

Analyzing the performance of simultaneous generalized hill climbing algorithms

Simultaneous generalized hill climbing (SGHC) algorithms provide a framework for using heuristics to simultaneously address sets of intractable discrete optimization problems where information is shared between the problems during the algorithm execution. Many well-known heuristics can be embedded within the SGHC algorithm framework. This paper shows that the solutions generated by an SGHC algorithm are a stochastic process that satisfies the Markov property. This allows problem probability mass functions to be formulated for particular sets of problems based on the long-term behavior of the algorithm. Such results can be used to determine the proportion of iterations that an SGHC algorithm will spend optimizing over each discrete optimization problem. Sufficient conditions that guarantee that the algorithm spends an equal number of iterations in each discrete optimization problem are provided. SGHC algorithms can also be formulated such that the overall performance of the algorithm is independent of the initial discrete optimization problem chosen. Sufficient conditions are obtained guaranteeing that an SGHC algorithm will visit the globally optimal solution for each discrete optimization problem. Lastly, rates of convergence for SGHC algorithms are reported that show that given a rate of convergence for the embedded GHC algorithm, the SGHC algorithm can be designed to preserve this rate.     

A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja–Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.     

Numerical experiments on dual matrix algorithms for function minimization

In Ref. 2, four algorithms of dual matrices for function minimization were introduced. These algorithms are characterized by the simultaneous use of two matrices and by the property that the one-dimensional search for the optimal stepsize is not needed for convergence. For a quadratic function, these algorithms lead to the solution in at mostn+1 iterations, wheren is the number of variables in the function. Since the one-dimensional search is not needed, the total number of gradient evaluations for convergence is at mostn+2. In this paper, the above-mentioned algorithms are tested numerically by using five nonquadratic functions. In order to investigate the effects of the stepsize on the performances of these algorithms, four schemes for the stepsize factor are employed, two corresponding to small-step processes and two corresponding to large-step processes. The numerical results show that, in spite of the wide range employed in the choice of the stepsize factor, all algorithms exhibit satisfactory convergence properties and compare favorably with the corresponding quadratically convergent algorithms using one-dimensional searches for optimal stepsizes.     

Accelerated reflection projection algorithm and its application to the LMI problem

We discuss accelerated version of the alternating projection method which can be applied to solve the linear matrix inequality (LMI) problem. The alternating projection method is a well-known algorithm for the convex feasibility problem, and has many generalizations and extensions. Bauschke and Kruk proposed a reflection projection algorithm for computing a point in the intersection of an obtuse cone and a closed convex set. We carry on this research in two directions. First, we present an accelerated version of the reflection projection algorithm, and prove its weak convergence in a Hilbert space; second, we prove the finite termination of an algorithm which is based on the proposed algorithm and provide an explicit upper bound for the required number of iterations under certain assumptions. Numerical experiments for the LMI problem are provided to demonstrate the effectiveness and merits of the proposed algorithms.