On the Equivalence of the Simplex Methods and a Multiplier-Alike Method for Linear Programming

In linear programming, the simplex method has been viewed for a long time as an efficient tool. Interior methods have attracted a lot of attention since they were proposed recently. It seems plausible intuitively that there is no reason why a good linear programming algorithm should not be allowed to cross the boundary of the feasible region when necessary. However, such an algorithm is seldom studied. In this paper, we will develop first a framework of a multiplier-alike algorithm for linear programming which allows its trajectory to move across the boundary of the feasible region. Second, we illustrate that such a framework has the potential to perform as well as the simplex method by showing that these methods are equivalent in a well-defined sense, even though they look so different.     

On the Convergence of Descent Algorithms

It is proved that any cluster point of a sequence defined by a steepest descent algorithm in a general normed vector space is a critical point. The function is just assumed to be continuously differentiable. The class of algorithms we consider encompasses several choices such as the Cauchy steplength and the Curry steplength.     

A comparison between the variational iteration method and the successive approximations method

In this paper we investigate and compare the variational iteration method and the successive approximations method for solving a class of nonlinear differential equations. We prove that these two methods are equivalent for solving these types of equations.     

A fast collocation method for the radiosity equation,based on the hierarchical algorithm of Hanrahan and Salzman: the 1d case

In this paper we study a collocation method with piecewise constant trial functions for the solution of the planar radiosity equation. The matrix of the collocation method is approximated by a method which was developed by Hanrahan et al. [9,10]. We prove that the modified collocation method results in a reduction of work while the order of convergence stays the same. Numerical examples demonstrate the theoretical results. AMS subject classification 45B05, 65R20, 65Y20     

Local convergence of the diagonalized method of multipliers

In this study, we consider a modification of the method of multipliers of Hestenes and Powell in which the iteration is diagonalized, that is, only a fixed finite number of iterations of Newton's method are taken in the primal minimization stage. Conditions are obtained for quadratic convergence of the standard method, and it is shown that a diagonalization where two Newton steps are taken preserves the quadratic convergence for all multipler update formulas satisfying these conditions.This work constitutes part of the author's doctoral dissertation in the Department of Mathematical Sciences, Rice University, under the direction of Professor R. A. Tapia and was supported in part by ERDA Contract No. E-(40-1)-5046.The author would like to thank Professor Richard Tapia for his comments, suggestions, and discussions on this material.     

Comparison of the finite difference and Galerkin methods as applied to the solution of the hydrodynamic equations

The three-dimensional nonlinear hydrodynamic equations which describe wind induced flow in a homogeneous sea are transformed from Cartesian coordinates into sigma coordinates. The solution of these equations in the horizontal is accomplished using a standard finite difference grid and established finite difference methods.The accuracy and computational efficiency, in terms of both computer time and main memory requirements, of using either the Galerkin method or a finite difference grid through the vertical is considered. Calculations, using the same number of functions in the Galerkin method as grid bases through the vertical shows that the Galerkin method has superior accuracy over the grid box method. Hence, for a given accuracy a smaller number of functions than grid boxes may be used, with associated saving in computational resources.For the case in which the vertical variation of eddy viscosity is fixed, an eigenvalue problem can be solved to yield a set of eigenfunctions. Using these eigenfunctions as a basis set with the Galerkin approach, a Galerkin-eigenfunction method is developed. Calculations show that the Galerkin-eigenfunction technique is accurate and in a linear model is clearly computationally more economic than the use of grid boxes through the vertical.     

Analysis of the Fictitious Domain Method with an L 2-Penalty for Elliptic Problems

The L ²-penalty fictitious domain method is based on a reformulation of the original problem in a larger simple-shaped domain by introducing a discontinuous reaction term with a penalty parameter ε > 0. We first derive regularity results and some a priori estimates and then prove several error estimates. We also give several error estimates for discretization problems by the finite element and finite volume methods.     

Comparison between the convergence rates of the Chebyshev method and the related (2,2)‐step methods

An optimal Chebyshev method for solving A x = b , where all the eigenvalues of the real and non‐symmetric matrix A are located in the open right half plane, is dependent on an optimal ellips∂Ω^* such that the spectrum of A is contrained in Ω^*, the closed interior of the ellipse. The relationship between the convergence rates of the Chebyshev method and the closely related (2,2)‐step iterative methods are studied. (2,2)‐step iterative methods are faster than an optimal Chebyshev method under certain conditions. A numerical example illustrates such an improvement of a (2,2)‐step iterative method. Copyright © 2000 John Wiley & Sons, Ltd.     

Newton-like method with modification of the right-hand-side vector

This paper proposes a new Newton-like method which defines new iterates using a linear system with the same coefficient matrix in each iterate, while the correction is performed on the right-hand-side vector of the Newton system. In this way a method is obtained which is less costly than the Newton method and faster than the fixed Newton method. Local convergence is proved for nonsingular systems. The influence of the relaxation parameter is analyzed and explicit formulae for the selection of an optimal parameter are presented. Relevant numerical examples are used to demonstrate the advantages of the proposed method.

     

Complexity of the Gravitational Method for Linear Programming

In the gravitational method for linear programming, a particle is dropped from an interior point of the polyhedron and is allowed to move under the influence of a gravitational field parallel to the objective function direction. Once the particle falls onto the boundary of the polyhedron, its subsequent motion is constrained to be on the surface of the polyhedron with the particle moving along the steepest-descent feasible direction at any instant. Since an optimal vertex minimizes the gravitational potential, computing the trajectory of the particle yields an optimal solution to the linear program.Since the particle is not constrained to move along the edges of the polyhedron, as the simplex method does, the gravitational method seemed to have the promise of being theoretically more efficient than the simplex method. In this paper, we first show that, if the particle has zero diameter, then the worst-case time complexity of the gravitational method is exponential in the size of the input linear program. As a simple corollary of the preceding result, it follows that, even when the particle has a fixed nonzero diameter, the gravitational method has exponential time complexity. The complexity of the version of the gravitational method in which the particle diameter decreases as the algorithm progresses remains an open question.     

Convergence study of the Chorin-Marsden formula

Using the fundamental solution of the heat equation, we give an expression of the solutions to two-dimensional initial-boundary value problems of the Navier-Stokes equations, where the vorticity is expressed in terms of a Poisson integral, a Newtonian potential, and a single layer potential. The density of the single layer potential is the solution to an integral equation of Volterra type along the boundary. We prove there is a unique solution to the integral equation. One fractional time step approximation is given, based on this expression. Error estimates are obtained for linear and nonlinear problems. The order of convergence is for the Navier-Stokes equations. The result is in the direction of justifying the Chorin-Marsden formula for vortex methods. It is shown that the density of the vortex sheet is twice the tangential velocity for the half plane, while in general the density differs from it by one additional term.

     

Looking Ahead with the Pilot Method

The pilot method as a meta-heuristic is a tempered greedy method aimed at obtaining better solutions while avoiding the greedy trap by looking ahead for each possible choice. Repeatedly a master solution is modified; each time in a minimal fashion to account for best choices, where choices are judged by means of a separate heuristic result, the pilot solution. The pilot method may be seen as a meta-heuristic enhancing the quality of (any) heuristic in a system for heuristic repetition. Experiments show that the pilot method as well as similar methods can behave quite competitively in comparison with well-known and accepted meta-heuristics. In this paper we review some less known results. As a higher time complexity is usually associated with repetition, we investigate a simple short-cut policy to reduce the running times, while retaining an enhanced solution quality. Furthermore, we report successful experiments that incorporate a distinguishing feature of the pilot method, which is the extension of neighborhoods into “local” search, creating tabu search hybrids.     

A projection technique for incompressible flow in the meshless finite volume particle method

The finite volume particle method is a meshless discretization technique, which generalizes the classical finite volume method by using smooth, overlapping and moving test functions applied in the weak formulation of the conservation law. The method was originally developed for hyperbolic conservation laws so that the compressible Euler equations particularly apply. In the present work we analyze the discretization error and enforce consistency by a new set of geometrical quantities. Furthermore, we introduce a discrete Laplace operator for the scheme in order to extend the method to second order partial differential equations. Finally, we transfer Chorins projection technique to the finite volume particle method in order to obtain a meshless scheme for incompressible flow. AMS subject classification 65M99, 68U20, 76B99, 76M12, 76M25, 76M28     

A multicolour SOR method for the finite-element method

In this paper we present several algorithms to reorder unknowns in a finite-element mesh so that we can use the multicolour SOR method to solve the corresponding linear system on a pipelined computer or on a parallel computer. We also discuss the assembling process by reordering elements with our algorithms. Numerical tests on a pipelined computer indicate the efficiency of the multicolour SOR method.     

Run time estimation of the spectral radius of Jacobians

It is useful for ordinary differential equation (ODE) solvers to include an estimator of the spectral radius of the Jacobian matrix of the system of ODE's, since this determines the numerical stability of the method. Hence a knowledge of spectral radius enables the run time selection of a more efficient integrator. Some techniques for estimating spectral radius are described and compared. They include methods suitable for use with any ODE solvers, but which require additional computation. Other methods are described which are suitable with Runge-Kutta or Rosenbrock methods, and which require little extra computation.     

Stabilization of the trial method for the Bernoulli problem in case of prescribed Dirichlet data

We apply the trial method for the solution of Bernoulli's free boundary problem when the Dirichlet boundary condition is imposed for the solution of the underlying Laplace equation, and the free boundary is updated according to the Neumann boundary condition. The Dirichlet boundary value problem for the Laplacian is solved by an exponentially convergent boundary element method. The update rule for the free boundary is derived from the linearization of the Neumann data around the actual free boundary. With the help of shape sensitivity analysis and Banach's fixed‐point theorem, we shed light on the convergence of the respective trial method. Especially, we derive a stabilized version of this trial method. Numerical examples validate the theoretical findings.Copyright © 2014 John Wiley & Sons, Ltd.     

对非线性方程近似解的认识和思考

二分法和牛顿法求非线性方程根的近似值已列入中学课程.但它背后的哲学原理(相对真理)/(绝对真理)=0.9,只在林群的新书中说到2^(1/2)时提出来.根据教学需要,通过(不足近似值)/(过剩近似值)=0.9等数值化的公式,来刻画根的近似过程.可以清楚地看到,随着小数点后9的个数的增加,近似解和真实解的误差在不断减小.因此0.9数值化系列公式也可以看做是误差估计的另一种表型形式.     

Solving the sum-of-ratios problem by a stochastic search algorithm

In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.     

Technical Note: A note on the selection of the penalty parameter for discontinuous Galerkin finite element schemes

We obtain a computable lower bound on the value of the interior penalty parameters sufficient for the existence of a unique discontinuous Galerkin finite element approximation of a second order elliptic problem. The bound obtained is valid for meshes containing an arbitrary number of hanging nodes and elements of arbitrary nonuniform polynomial order. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming

We introduce a framework in which updating rules for the barrier parameter in primal-dual interior-point methods become dynamic. The original primal-dual system is augmented to incorporate explicitly an updating function. A Newton step for the augmented system gives a primal-dual Newton step and also a step in the barrier parameter. Based on local information and a line search, the decrease of the barrier parameter is automatically adjusted. We analyze local convergence properties, report numerical experiments on a standard collection of nonlinear problems and compare our results to a state-of-the-art interior-point implementation. In many instances, the adaptive algorithm reduces the number of iterations and of function evaluations. Its design guarantees a better fit between the magnitudes of the primal-dual residual and of the barrier parameter along the iterations.