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.     

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.     

非线性约束条件下的SQP可行方法

本文对非线性规划问题给出了一个具有一步超线性收敛速度的可行方法。由于此算法每步迭代均在可行域内进行，并且每步迭代只需计算一个二次子规划和一个逆矩阵，因而算法具有较好的实用价值。本文还在较弱的条件下证明了算法的全局收敛和一步超线性收敛性。     

Algorithm for solving shifted skew-symmetric linear system

A new algorithm for solving a shifted skew-Hermitian linear system is presented and the corresponding convergence theorem is given. Some numerical examples are provided to demonstrate the algorithm.      

A NEW INEXACT SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM

This paper represents an inexact sequential quadratic programming (SQP) algorithm which can solve nonlinear programming (NLP) problems. An inexact solution of the quadratic programming subproblem is determined by a projection and contraction method such that only matrix-vector product is required. Some truncated criteria are chosen such that the algorithm is suitable to large scale NLP problem. The global convergence of the algorithm is proved.     

非匹配网格上Stokes-Darcy 问题非协调元离散的两水平和多水平方法

本文讨论了非匹配网格上Stokes-Darcy 问题的两种低阶非协调元方法, 给出了误差估计, 对耦合的非协调元离散问题, 通过粗网格求得的界面条件, 我们提出了一个解耦的两水平算法. 并且我们将两水平方法推广到多水平情形, 其只需在一个很粗的网格上解一耦合问题, 然后在逐步加细的网格上求解解耦的问题, 理论分析和数值试验都说明方法的高效性.     

一个新的单纯形类算法

提出了一个求解线性规划的新单纯形类算法。它不仅无须引入人工变量，而且在第一阶段中采用无比检验。因此新算法比Arsham最近提出的push-to—pull算法效率更高。此外，本算法的数值稳定性也优于push—to—pull算法。     

Reconstruction of the Linear Ordinary Differential System Based on Discrete Points

In this paper, we discuss an inverse problem, i.e., the reconstruction of a linear differential dynamic system from the given discrete data of the solution. We propose a model and a corresponding algorithm to recover the coefficient matrix of the differential system based on the normal vectors from the given discrete points, in order to avoid the problem of parameterization in curve fitting and approximation. We also give some theoretical analysis on our algorithm. When the data points are taken from the solution curve and the set composed of these data points is not degenerate, the coefficient matrix $A$ reconstructed by our algorithm is unique from the given discrete and noisefree data. We discuss the error bounds for the approximate coefficient matrix and the solution which are reconstructed by our algorithm. Numerical examples demonstrate the effectiveness of the algorithm.     

关于构造数学物理中非线性发展方程组孤波解的一种新算法

根据改进的sine-cosine法和吴文俊消元法,给出了一种构造非线性发展方程组孤波解的新算法。这种算法比已知的双曲函数法有更好的结论,并且在使用的过程中更简单。借助于MATH-EMATICA软件,这一算法能够在计算机上实现。     

The interior proximal extragradient method for solving equilibrium problems

In this article we present a new and efficient method for solving equilibrium problems on polyhedra. The method is based on an interior-quadratic proximal term which replaces the usual quadratic proximal term. This leads to an interior proximal type algorithm. Each iteration consists in a prediction step followed by a correction step as in the extragradient method. In a first algorithm each of these steps is obtained by solving an unconstrained minimization problem, while in a second algorithm the correction step is replaced by an Armijo-backtracking linesearch followed by an hyperplane projection step. We prove that our algorithms are convergent under mild assumptions: pseudomonotonicity for the two algorithms and a Lipschitz property for the first one. Finally we present some numerical experiments to illustrate the behavior of the proposed algorithms.     

FAST PARALLELIZABLE METHODS FOR COMPUTING INVARIANT SUBSPACES OF HERMITIAN MATRICES

We propose a quadratically convergent algorithm for computing the invariant subspaces of an Hermitian matrix. Each iteration of the algorithm consists of one matrix-matrix multiplication and one QR decomposition. We present an accurate convergence analysis of the algorithm without using the big O notation. We also propose a general framework based on implicit rational transformations which allows us to make connections with several existing algorithms and to derive classes of extensions to our basic algorithm with faster convergence rates. Several numerical examples are given which compare some aspects of the existing algorithms and the new algorithms.     

A theoretical analysis on efficiency of some Newton-PCG methods

In this paper, we study the efficiency issue of inexact Newton-type methods for smooth unconstrained optimization problems under standard assumptions from theoretical point of view by discussing a concrete Newton-PCG algorithm. In order to compare the algorithm with Newton's method, a ratio between the measures of their approximate efficiencies is investigated. Under mild conditions, it is shown that first, this ratio is larger than 1, which implies that the Newton-PCG algorithm is more efficient than Newton's method, and second, this ratio increases when the dimension n of the problem increases and tends to infinity at least at a rate In n/In 2 when n→∞, which implies that in theory the Newton-PCG algorithm is much more efficient for middle- and large-scale problems. These theoretical results are also supported by our preliminary numerical experiments.     

Efficient hybrid conjugate gradient techniques

Descent property and global convergence proofs are given for a new hybrid conjugate gradient algorithm. Computational results for this algorithm are also given and compared with those of the Fletcher-Reeves method and the Polak-Ribière method, showing a considerable improvement over the latter two methods. We also give new criteria for restarting conjugate gradient algorithms that prove to be computationally very efficient. These criteria provide a descent property and global convergence for any conjugate gradient algorithm using a nonnegative update .     

一个Newton-PCG型算法和它的效率分析

大量的数值实验表明Newton-PCG型算法很有效，但缺乏理论上的保证，最近在文[7]中，从理论上证明了该类算法比Newton法有效，本文取消了文[7]中的过程的假设条件，在标准假设下得到了一个更有效的算法。     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

A NEW FILLED FUNCTION METHOD FOR INTEGER PROGRAMMING

The Filled Function Method is a class of effective algorithms for continuous globaloptimization.In this paper,a new filled function method is introduced and used to solveinteger programming.Firstly,some basic definitions of discrete optimization are given.Then an algorithm and the implementation of this algorithm on several test problems areshowed.The computational results show the algorithm is effective.     

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.     

k-均值算法的初始化方法综述

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注, 是经典的NP-难问题之一. 给定N个d维实向量构成的观测集, 目标是把这N个观测点划分到k(\leq N)个集合中, 使得所有集合中的点到对应的聚类中心距离的平方和最小, 一个集合的聚类中心指的是该集合 中所有观测点的均值. k-均值算法作为解决k-均值问题的启发式算法,在实际应用中因其出色的收敛速度而倍受欢迎. k-均值算法可描述为: 给定问题的初始化分组, 交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解. 该算法通常被认为几乎是线性收敛的. 但缺点也很明显, 无法保证得到的是全局最优解, 并且算法结果好坏过于依赖初始解的选取. 于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量. 现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.     

Sturm's Method in Counting Roots of Random Polynomial Equations

The problem of finding the probability distribution of the number of zeros in some real interval of a random polynomial whose coefficients have a given continuous joint density function is considered. An algorithm which enables one to express this probability as a multiple integral is presented. Formulas for the number of zeros of random quadratic polynomials and random polynomials of higher order, some coefficients of which are non-random and equal to zero, are derived via use of the algorithm. Finally, the applicability of these formulas in numerical calculations is illustrated.     

AN EFFECTIVE SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS

In this paper,a new globally convergent algorithm for nonlinear optimization prablems with equality and inequality constraints is presented. The new algorithm is of SQP type which determines a search direction by solving a quadratic programming subproblem per itera-tion. Some revisions on the quadratic programming subproblem have been made in such a way that the associated constraint region is nonempty for each point x generated by the algorithm, i. e. , the subproblems always have optimal solutions. The new algorithm has two important properties. The computation of revision parameter for guaranteeing the consistency of quadratic sub-problem and the computation of the second order correction step for superlinear convergence use the same inverse of a matrix per iteration, so the computation amount of the new algorithm will not be increased much more than other SQP type algorithms; Another is that the new algorithm can give automatically a feasible point as a starting point for the quadratic subproblems pe