A Newton Method for Linear Programming

A fast Newton method is proposed for solving linear programs with a very large (10⁶) number of constraints and a moderate (10²) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for finite values of the penalty parameter but not for the primal linear program. Solving the dual problem for a finite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to the dual problem can be used to generate an accurate primal solution if mn and the primal solution is unique. Utilizing these facts, a fast globally convergent finitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine.     

An Optimal Method for Adjusting the Centering Parameter in the Wide-Neighborhood Primal-Dual Interior-Point Algorithm for Linear Programming

In this paper we present a dynamic optimal method for adjusting the centering parameter in the wide-neighborhood primal-dual interior-point algorithms for linear programming, while the centering pararheter is generally a constant in the classical wideneighborhood primal-dual interior-point algorithms. The computational results show that the new method is more efficient.     

On the Log-exponential Trajectory of Linear Programming

Development in interior point methods has suggested various solution trajectories, also called central paths, for linear programming. In this paper we define a new central path through a log-exponential perturbation to the complementarity equation in the Karush-Kuhn-Tucker system. The behavior of this central path is investigated and an algorithm is proposed. The algorithm can compute an -optimal solution at a superlinear rate of convergence.     

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.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING＊

In this paper, we consider the solution of the standard linear programming [Lt＇）. A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan [19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan＇s face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.     

Linear Systems Associated with Numerical Methods for Constrained Optimization

Linear systems associated with numerical methods for constrained optimization are discussed in thia paper ,It is shown that the corresponding subproblems arise in most well-known methods,no matter line search methods or trust region methods for constrained optimization can be expressed as similar systems of linear equations.All these linear systems can be viewed as some kinds of approximation to the linear system derived by the Lagrange-Newton method .Some properties of these linear systems are analyzed.     

纵向数据下线性EV模型的变量选择

本文考虑了纵向数据线性EV模型的变量选择.基于二次推断函数方法和压缩方法的思想提出了一种新的偏差校正的变量选择方法.在选择适当的调整参数下,我们证明了所得到的估计量的相合性和渐近正态性.最后通过模拟研究验证了所提出的变量选择方法的有限样本性质.     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

线性约束凸规划内点法及其修正算法

凸规划的内点算法是目前较热门的课题之一，参考资料[2]；[3]等均给出了较深入的研究．本文在参考前人的工作前提下，提出了带线性约束凸规划的内点算法结论（定理2．8）及相应算法．另外，木文定义了偏移因子，偏移因子对的概念，对下降方向作出了修正，并给出了相关算法．     

关于存在多组最优解的整数线性规划问题的割平面法的研究

利用割平面法求解具有多组最优解情形的整数线性规划问题时,会出现不能求出全部最优解的现象,这是割平面法的一个缺陷.针对割平面法的这种缺陷,基于构造非线性标量化函数时引入凸锥的思想,提出了一种割平面一线性交叉搜索方法,这种割平面一线性交叉搜索方法可以解决利用割平面法求解整数线性规划问题时出现的缺陷.最后,通过数值例验证了割平面一线性交叉搜索方法的可行性与有效性.     

An Alternate Approach to Optimal L 2-Error Analysis of Semidiscrete Galerkin Methods for Linear Parabolic Problems with Nonsmooth Initial Data

In this article, we propose and analyze an alternate proof of a priori error estimates for semidiscrete Galerkin approximations to a general second order linear parabolic initial and boundary value problem with rough initial data. Our analysis is based on energy arguments without using parabolic duality. Further, it follows the spirit of the proof technique used for deriving optimal error estimates for finite element approximations to parabolic problems with smooth initial data and hence, it unifies both theories, that is, one for smooth initial data and other for nonsmooth data. Moreover, the proposed technique is also extended to a semidiscrete mixed method for linear parabolic problems. In both cases, optimal L ²-error estimates are derived, when the initial data is in L ². A superconvergence phenomenon is also observed, which is then used to prove L ^∞-estimates for linear parabolic problems defined on two-dimensional spatial domain again with rough initial data.     

Two Iteration Methods for Solving Linear Algebraic Systems with Low Order Matrix $A$ and High Order Matrix $B:Y=(A \otimes B)Y+\Phi$

This paper presents optimum a one-parameter iteration (OOPI) method and a multi-parameter iteration direct (MPID) method for efficiently solving linear algebraic systems with low order matrix $A$ and high order matrix $B: Y = (A \otimes B)Y+\Phi$. On parallel computers (also on serial computer) the former will be efficient, even very efficient under certain conditions, the latter will be universally very efficient.     

Harmonic and Refined Extraction Methods for the Singular Value Problem,with Applications in Least Squares Problems

For the accurate approximation of the minimal singular triple (singular value and left and right singular vector) of a large sparse matrix, we may use two separate search spaces, one for the left, and one for the right singular vector. In Lanczos bidiagonalization, for example, such search spaces are constructed. In SIAM J. Sci. Comput., 23(2) (2002), pp. 606–628, the author proposes a Jacobi–Davidson type method for the singular value problem, where solutions to certain correction equations are used to expand the search spaces. As noted in the mentioned paper, the standard Galerkin subspace extraction works well for the computation of large singular triples, but may lead to unsatisfactory approximations to small and interior triples. To overcome this problem for the smallest triples, we propose three harmonic and a refined approach. All methods are derived in a number of different ways. Some of these methods can also be applied when we are interested in the largest or interior singular triples. Theoretical results as well as numerical experiments indicate that the results of the alternative extraction processes are often better than the standard approach. We show that when Lanczos bidiagonalization is used for the subspace expansion, the standard, harmonic, and refined extraction methods are all essentially equivalent. This gives more insight in the success of Lanczos bidiagonalization to find the smallest singular triples. Finally, we show that the extraction processes for the smallest singular values may give an approximation to a least squares problem at low additional costs. The truncated SVD is also discussed in this context. AMS subject classification (2000) 65F15, 65F50, (65F35, 93E24).Submitted December 2002. Accepted October 2004. Communicated by Haesun Park.M. E. Hochstenbach: The research of this author was supported in part by NSF grant DMS-0405387. Part of this work was done when the author was at Utrecht University.