多层线性规划问题的整体优化算法

本文研究了求解多层线性规划问题的整体优化算法,利用流动等值面技术,证明了算法的有限终止性,并给出实际例子验证了算法的有效性.     

修正的IPA算法的建立及在不等式约束凸优化问题中的应用

本文首先对IPA算法进行了修正，并证明了修正IPA算法的收敛性，然后将修正后的IPA应用到不等式约束凸优化问题中得到新的内点算法，并与传统的障碍函数法作了比较，从理论上体现了新算法的优势，并给出了其工程解求解法以及收敛性的证明．     

算法及其学习的意义

在新高中数学课程标准中，我们注意到算法作为必修部分进入了中学数学．标准中写到：“算法是一个全新的课题，已经成为计算机科学的核心，它在科学技术和社会发展中起着越来越重要的作用．算法的思想和初步知识，也正在成为普通公民的常识．在必修课程中将学习算法的基本思     

新的梯度算法求解单位球笛卡尔积约束优化问题北大核心CSCD

本文主要研究了单位球笛卡尔积作为约束的优化问题,给出了此类问题的最优性条件．同时将求解此问题的一些经典的梯度算法推广到了更加一般的形式,并证明了新算法的收敛性．随机二次规划问题和求解图像变分去噪模型的数值结果表明新算法并不弱于一些经典的算法,特别是在精度要求较高的情形下．     

分派问题的一个简单算法

本文给出了分派问题的一个新算法，这个算法是初等的，且便于使用和编程上机操作，尤其适合于较低阶分派问题．     

求解变分不等式问题的一个递推算法的一个注

本文改进了[3]中的一个基本不等式和原算法，从而提高了数值计算的效率,而且在新算法的收敛性分析中去掉了变分不等式问题的单调性条件．     

新课程视野下的算法试题透析

算法是计算机理论和技术的核心，是高中新课程新增内容之一，由于算法思想的朴实性，所以算法思想在数学本身的学习与研究中有着广泛的应用，算法与函数、方程、不等式、数列以及实际问题有着密切的联系．2007年新课标高考中初次将算法、流程图引入进来，考查了考生对构造性数学的意义的理解，检测了考生有条理思考与表达的能力，展示了新课标视野下高考命题的新视角，诠释了新高考的新理念．下面将新型的算法试题分类解析如下：     

二元整系数多项式因式分解的一种理论和算法

将二元多项式看成系数为一元多项式的一元多项式来进行分解，本文建立了二元整系数多项式因式分解的一种理论，提出了一个完整的分解二元整系数多项式的新算法．这个算法能自然地推广到多元整系数多项式的分解中去．     

线性约束优化问题的开关算法模型及其应用

本文利用开关函数．建立了解线性约束优化问题的一个组合型可行方向法─—开关算法模型，并给出了其收敛性质，从而统一、推广了包括起线性收敛的算法在内的常见的可行方向法．依此模型，具体构造了一类起线性收敛的新算法．     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

George Dantzig’s impact on the theory of computation

George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig’s work on linear programming and its application and extension to combinatorial optimization, and the investigations it has stimulated about the performance of the simplex algorithm and the intrinsic complexity of linear programming and combinatorial optimization.     

关于FLP问题一种新的单纯形算法的推广

指出FLP问题的一种新的单纯形算法[1]中主要结论成立的适用条件,并给出了该适用条件不成立时,一般条件下的推广.     

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.     

模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

Revised simplex algorithm for finite Markov decision processes

We introduce a revised simplex algorithm for solving a typical type of dynamic programming equation arising from a class of finite Markov decision processes. The algorithm also applies to several types of optimal control problems with diffusion models after discretization. It is based on the regular simplex algorithm, the duality concept in linear programming, and certain special features of the dynamic programming equation itself. Convergence is established for the new algorithm. The algorithm has favorable potential applicability when the number of actions is very large or even infinite.     

A simplex algorithm for piecewise-linear programming II: Finiteness,feasibility and degeneracy

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegeneracy of all such solutions. Part II now shows how these assumptions can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

A partitioning and bounded variable algorithm for linear programming

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one ‘less than or equal to’ constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.     

Modification of Karmarkar’s projective scaling algorithm

This paper presents a new conversion technique of the standard linear programming problem into a homogenous form desired for the Karmarkar’s algorithm, where we employed the primal–dual method. The new converted linear programming problem provides initial basic feasible solution, simplex structure, and homogenous matrix. Apart from the transformation, Hooker’s method of projected direction is employed in the Karmarkar’s algorithm and the modified algorithm is presented. The modified algorithm has a faster convergence with a suitable choice of step size.