Long-step primal-dual target-following algorithms for linear programming

In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.This work is completed with the support of a research grant from SHELL.The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.     

A new shrinking gradient-like projection method for equilibrium problems

The paper proposes a new shrinking gradient-like projection method for solving equilibrium problems. The algorithm combines the generalized gradient-like projection method with the monotone hybrid method. Only one optimization program is solved onto the feasible set at each iteration in our algorithm without any extra-step dealing with the feasible set. The absence of an optimization problem in the algorithm is explained by constructing slightly different cutting-halfspace in the monotone hybrid method. Theorem of strong convergence is established under standard assumptions imposed on equilibrium bifunctions. An application of the proposed algorithm to multivalued variational inequality problems (MVIP) is presented. Finally, another algorithm is introduced for MVIPs in which we only use a value of main operator at the current approximation to construct the next approximation. Some preliminary numerical experiments are implemented to illustrate the convergence and computational performance of our algorithms over others.     

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

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

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

Krylov subspace methods to solve a class of tensor equations via the Einstein product

This paper is concerned with some of the well‐known iterative methods in their tensor forms to solve a class of tensor equations via the Einstein product. More precisely, the tensor forms of the Arnoldi and Lanczos processes are derived and the tensor form of the global GMRES method is presented. Meanwhile, the tensor forms of the MINIRES and SYMMLQ methods are also established. The proposed methods use tensor computations with no matricizations involved. Numerical examples are provided to illustrate the efficiency of the proposed methods and testify the conclusions suggested in this paper.     

域外奇源分布法场点解的唯一性

应用奇源解的核函数沿距离递减的条件和积分不等式,可证这类奇源在凸域外分布只要满足以它产生的响应来表达的边界条件时,所引起相应的域内场点解是唯一的。文中给出这类奇源的部分例子,如Kelvin的点力,点圆力偶(PRC)等。并给出PRC分布解回转体扭转问题的场点解的唯一性证明作为应用例。     

A note on the biasing of Newton's direction

This note deals with the geometric interpretation of the Levenberg-Marquardt search direction when the augmented Hessian is not positive definite.     

Trefftz,collocation, and other boundary methods—A comparison

In this article we survey the Trefftz method (TM), the collocation method (CM), and the collocation Trefftz method (CTM). We also review the coupling techniques for the interzonal conditions, which include the indirect Trefftz method, the original Trefftz method, the penalty plus hybrid Trefftz method, and the direct Trefftz method. Other boundary methods are also briefly described. Key issues in these algorithms, including the error analysis, are addressed. New numerical results are reported. Comparisons among TMs and other numerical methods are made. It is concluded that the CTM is the simplest algorithm and provides the most accurate solution with the best numerical stability. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

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.

     

求解洛伦兹力系统的一个任意高阶的能量守恒格式

本文旨在提出一种求解带电粒子系统的任意高阶能量守恒格式.在使用能量不变二次化方法将原始哈密顿能量泛函转化为一个二次形式后,辛龙格-库塔方法被用来构造了一种新的能量守恒格式来求解洛伦兹力系统.新格式不仅能保持能量守恒,而且可以达到任意高阶.通过与经典的Boris方法和另一个二阶能量守恒方法对比,数值实验验证了所提算法的显著优越性.     

Interior proximal point algorithm for linear programs

An interior proximal point algorithm for finding a solution of a linear program is presented. The distinguishing feature of this algorithm is the addition of a quadratic proximal term to the linear objective function. This perturbation has allowed us to obtain solutions with better feasibility. Implementation of this algorithm shows that the algorithms. We also establish global convergence and local linear convergence of the algorithm.This research was supported by National Science Foundation Grants DCR-85-21228 and CCR-87-23091 and by Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-89-0410. It was conducted while the author was a Graduate Student at the Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

NONCONFORMING FINITE ELEMENT PENALTY METHOD FOR STOKES EQUATION

a special penalty method is presented to improve the accuracy of the standard penaltymethod (or solving Stokes equation with nonconforming finite element, It is shown that thismethod with a larger penalty parameter can achieve the same accuracy as the staodaxd methodwith a smaller penalty parameter. The convergence rate of the standard method is just hall order of this penalty method when using the same penalty parameter, while the extrapolationmethod proposed by Faik et al can not yield so high accuracy of convergence. At last, we alsoget the super-convergence estimates for total flux.     

Least squares methods for Volterra equations and generalizations

In this article least squares approximations to Volterra integral equations are considered, both with exact integration and with quadrature. Optimal error estimates are derived, and it is shown that the same order of convergence is obtained in both cases with only modest requirements on the quadrature rule used in the latter. The most important practical setting for least squares is the case of convolution kernels, and these are also studied in this article. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 679–693, 1998     

A parameterized Newton method and a quasi-Newton method for nonsmooth equations

This paper presents a parameterized Newton method using generalized Jacobians and a Broyden-like method for solving nonsmooth equations. The former ensures that the method is well-defined even when the generalized Jacobian is singular. The latter is constructed by using an approximation function which can be formed for nonsmooth equations arising from partial differential equations and nonlinear complementarity problems. The approximation function method generalizes the splitting function method for nonsmooth equations. Locally superlinear convergence results are proved for the two methods. Numerical examples are given to compare the two methods with some other methods.This work is supported by the Australian Research Council.     

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.     

Globally Convergent Algorithms for Unconstrained Optimization

A new globalization strategy for solving an unconstrained minimization problem is proposed based on the idea of combining Newton's direction and the steepest descent direction WITHIN each iteration. Global convergence is guaranteed with an arbitrary initial point. The search direction in each iteration is chosen to be as close to the Newton's direction as possible and could be the Newton's direction itself. Asymptotically the Newton step will be taken in each iteration and thus the local convergence is quadratic. Numerical experiments are also reported. Possible combination of a Quasi-Newton direction with the steepest descent direction is also considered in our numerical experiments. The differences between the proposed strategy and a few other strategies are also discussed.     

Interactive bicriterion solution method and its application to critical path method problems

An interactive solution method is developed for bicriterion mathematical programming (BCMP) problems. The new method, called the dichotomous bicriterion mathematical programming (DBCMP) method, combines Tchebycheff theory and the existing paired comparison method (PCM). The DBCMP method is then compared with the PCM method based on critical path method problems with two conflicting objectives: minimizing the total crashing cost and minimizing the total project completion time. The extension of the DBCMP method to BCMP problems with multiple decision makers is also discussed.     

大范围求解非线性方程组的指数同伦法

为了解决关于奇异的非线性方程组求根问题,提出了一种由同伦算法推出大范围收敛的连续型方法-指数同伦法,构造了一类指数同伦方程,克服了Jacobi矩阵的奇异,分析了指数同伦方