有界变量线性规划的一种简易解法

本文在[1]的基础上，较系统地叙述了有界变量线性规划一种简易解法的基本思路、方法步骤、理论分析和应用举例。指出，因变量有界所引起的种种麻烦在这里通过单纯形表的小小变动便加以解决了。     

Lemke-Howson方法的一个反例

参考文献[1]中对Lemke-Howson算法给出了相似于线性规划中的单纯形解法。本文用例指出了该解法中出现循环的情况,导致有解求不出。     

线性规划分解筛选法的一个注记

[1][2]提出了求解线性规划问题的一种方法－分解筛选法,[3]证明了[2]的命题A是错误的,本进一步证明,用分解筛选法筛选出变量不一定是最优基变量。     

求解凸二次规划问题的势下降内点算法

1　引　言二次规划问题的求解是数学规划和工业应用等领域的一个重要课题 ,同时也是解一般非线性规划问题的序列二次规划算法的关键 .求解二次规划问题的早期技术是利用线性规划问题的单纯形方法求解二次规划问题的 KKT最优性必要条件[1 ] .这类算法比较直观 ,但在处理不等式约束时 ,松弛变量的引进很容易导致求解过程的明显减慢 .有效集策略是求解二次规划问题的另一类主要技术 .这类方法一般都是稳定的 ,但随着问题中大量不等式约束的出现 ,其收敛速度将越来越低[2 ] .简约空间技术将所求问题的 Hessian阵投影到自由变量所在的子空间中 …     

有界变量亏基单纯形算法

为克服单纯形算法中退化现象带来的困扰,本文在文[1]的基础上进一步提出亏基有界变量单纯形算法,并证明了算法的收敛性.     

相似于线规划中单纯形解法的Lemke-Howson 方法的改进

参考文献中对Lemke—Howson算法给出了相似于线性规划中的单纯形解法．我们在参考文献中给出一个反例．本文对文献中给出的相似于线性规划中的单纯形解法的Lemke—Howson算法作出改进，     

Lemke-Howson方法的一个反例

参考文献[I]中对Lemke—Howson算法给出了相似于线性规划中的单纯形解法．本文用例指出了该解法中出现循环的情况,导致有解求不出。     

一类有报酬的馬尔可夫决策过程最优化問題的线性規划模型

§1.引言 Ronald A.Howard在[1]中解决了一类有报酬的马尔可夫决策过程的最优化问题,这类问题在生产实际中是常见到的,例如,关于设备的维修与更新的某些问题便属于这种类型。实质上,这种问题是一个组合问题,本文得出了它与一个线性规划问题之间的对应关系,并因此指出了Howard方法与单纯形方法的联系。此外,将此问题所对应的线性     

互补基解性质的应用研究

对线性规划互补基解性质进行了研究,得到了由线性规划问题最优基对应的单纯形表直接获得对偶线性规划问题最优基对应的单纯形表的一个有效方法,给出了应用实例.     

避免引入人工变量求线性规划可行基的一个新方法

讨论了线性规划的单纯形解法,给出了不须加人工变量就可得到一个可行基的算法.通过大量的算例表明此法比传统的单纯形方法具有算法结构简单,计算量小的优点.     

Finding all Solutions of Systems of Nonlinear Equations Using the Dual Simplex Method

An efficient algorithm is proposed for finding all solutions of nonlinear equations using linear programming (LP). This algorithm is based on a simple test (termed the LP test) for nonexistence of a solution to a system of nonlinear equations in a given region. In the conventional LP test, the system of nonlinear equations is transformed into an LP problem, to which the simplex method is applied. However, although the LP test is very powerful, it requires many pivotings for each region. In this paper, we use the dual simplex method in the LP test, which makes the average number of pivotings per region much smaller (less than one, for example) and makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm can find all solutions of systems of 200 nonlinear equations in practical computation time.     

Optimal Prioritized Infeasibility Handling in Model Predictive Control: Parametric Preemptive Multiobjective Linear Programming Approach

All practical implementations of model-based predictive control (MPC) require a means to recover from infeasibility. We propose a strategy designed for linear state-space MPC with prioritized constraints. It relaxes optimally an infeasible MPC optimization problem into a feasible one by solving a single-objective linear program (LP) online in addition to the standard online MPC optimization problem at each sample. By optimal, it is meant that the violation of a lower prioritized constraint cannot be made less without increasing the violation of a higher prioritized constraint. The problem of computing optimal constraint violations is naturally formulated as a parametric preemptive multiobjective LP. By extending well-known results from parametric LP, the preemptive multiobjective LP is reformulated into an equivalent standard single-objective LP. An efficient algorithm for offline design of this LP is given, and the algorithm is illustrated on an example.     

LP narrowing: A new strategy for finding all solutions of nonlinear equations

An efficient algorithm is proposed for finding all solutions of systems of n nonlinear equations. This algorithm is based on interval analysis and a new strategy called LP narrowing. In the LP narrowing strategy, boxes (n-dimensional rectangles in the solution domain) containing no solution are excluded, and boxes containing solutions are narrowed so that no solution is lost by using linear programming techniques. Since the LP narrowing is very powerful, all solutions can be found very efficiently. By numerical examples, it is shown that the proposed algorithm could find all solutions of systems of 5000-50,000 nonlinear equations in practical computation time.     

Fast gradient descent method for Mean-CVaR optimization

We propose an iterative gradient descent algorithm for solving scenario-based Mean-CVaR portfolio selection problem. The algorithm is fast and does not require any LP solver. It also has efficiency advantage over the LP approach for large scenario size.     

Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation

We present two linearization-based algorithms for mixed-integer nonlinear programs (MINLPs) having a convex continuous relaxation. The key feature of these algorithms is that, in contrast to most existing linearization-based algorithms for convex MINLPs, they do not require the continuous relaxation to be defined by convex nonlinear functions. For example, these algorithms can solve to global optimality MINLPs with constraints defined by quasiconvex functions. The first algorithm is a slightly modified version of the LP/NLP-based branch-and-bouund \((\text{ LP/NLP-BB })\) algorithm of Quesada and Grossmann, and is closely related to an algorithm recently proposed by Bonami et al. (Math Program 119:331–352, 2009). The second algorithm is a hybrid between this algorithm and nonlinear programming based branch-and-bound. Computational experiments indicate that the modified LP/NLP-BB method has comparable performance to LP/NLP-BB on instances defined by convex functions. Thus, this algorithm has the potential to solve a wider class of MINLP instances without sacrificing performance.     

一类线性规划逆问题及解法

本文讨论了逆ＬＰ问题的更一般的情况,这里称它为广义逆ＬＰ问题,即在知道了一部分变量和价值系数的条件下,求余下的未知的变量和价值系数,将它们合起来组成给定的ＬＰ问题的最优解。显然若知道全部价值系数就成为ＬＰ问题;若知道全部变量就成为逆ＬＰ问题,它是在根据研制应用软件时提出的。文中给出了解广义逆ＬＰ问题的算法,并成功地用于“宏观经济调控系统”等应用软件的研制中,对要解决的实际问题,给出了强多项式算法。     

An improved approximation algorithm for the partial Latin square extension problem

Previous work on the partial Latin square extension (PLSE) problem resulted in a 2-approximation algorithm based on the LP relaxation of a three-dimensional assignment IP formulation. We present an e/(e−1)-approximation algorithm that is based on the LP relaxation of a packing IP formulation of the PLSE problem.     

A BRANCH-AND-PRICE ALGORITHM FOR SOLVING THE CUTTING STRIPS PROBLEM

After giving a suitable model for the cutting strips problem, we present a branch-and-price algorithm for it by combining the column generation technique and the branch-and-hound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computarional experience is reported.     

Dijkstra’s algorithm and L-concave function maximization

Dijkstra’s algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra’s algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the steepest ascent algorithm for L-concave function maximization, when applied to the LP dual of the shortest path problem and implemented with some auxiliary variables, coincides exactly with Dijkstra’s algorithm.     

Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.