Linearly constrained minimax optimization

We present an algorithm for nonlinear minimax optimization subject to linear equality and inequality constraints which requires first order partial derivatives. The algorithm is based on successive linear approximations to the functions defining the problem. The resulting linear subproblems are solved in the minimax sense subject to the linear constraints. This ensures a feasible-point algorithm. Further, we introduce local bounds on the solutions of the linear subproblems, the bounds being adjusted automatically, depending on the quality of the linear approximations. It is proved that the algorithm will always converge to the set of stationary points of the problem, a stationary point being defined in terms of the generalized gradients of the minimax objective function. It is further proved that, under mild regularity conditions, the algorithm is identical to a quadratically convergent Newton iteration in its final stages. We demonstrate the performance of the algorithm by solving a number of numerical examples with up to 50 variables, 163 functions, and 25 constraints. We have also implemented a version of the algorithm which is particularly suited for the solution of restricted approximation problems.This work has been supported by the Danish Natural Science Research Council, Grant No. 511-6874.     

A finite algorithm for the least two-norm solution of a linear program 1

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overtaxation techniques). In this way large sparse linear programs can be handled.

In this paper we give a new computational criterion to check whether the solution of the perturbed quadratic program provides the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper.

We also describe an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iteration.s     

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.     

Towards auction algorithms for large dense assignment problems

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable. This research has been supported by IGA CTU under grant CTU0308013 and under research program MSMT 6840770014.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

一个新的线性规划Criss-cross算法

本文利用重新排列下标的技巧,提出了一个新的criss-cross算法.并证明了其有限性,理论分析及初步的计算实验表明,新算法比最小下标criss-cross算法效率更高.     

A primal conical linear programming algorithm

This paper completes the treatment of the conical approach to linear programming, introducing a conical primal algorithm of linear programming. After some recalls and improvements of a previous paper dealing with such an approach, the algorithm is defined. A first convergence result is then proved, which, along with a series of lemmata, allows to prove that the algorithm terminates in a finite number of steps     

Short-Time Linear Response with Reduced-Rank Tangent Map

The recently developed short-time linear response algorithm, which predicts the response of a nonlinear chaotic forced-dissipative system to small external perturbation, yields high precision of the response prediction. However, the computation of the short-time linear response formula with the full rank tangent map can be expensive. Here, a numerical method to potentially overcome the increasing numerical complexity for large scale models with many variables by using the reduced-rank tangent map in the computation is proposed. The conditions for which the short-time linear response approximation with the reduced-rank tangent map is valid are established, and two practical situations are examined, where the response to small external perturbations is predicted for nonlinear chaotic forced-dissipative systems with different dynamical properties.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

An LP-based algorithm for the correction of inconsistent linear equation and inequality systems

An algorithm based on linear programming is proposed, which finds for an inconsistent system minimal corrections of the matrix and RHS vector among those providing its consistency     

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

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

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

Global optimization for sum of geometric fractional functions

This paper presents an efficient branch and bound algorithm for globally solving sum of geometric fractional functions under geometric constraints, which arise in various practical problems. By using an equivalent transformation and a new linear relaxation technique, a linear relaxation programming problem of the equivalent problem is obtained. The proposed algorithm is convergent to the global optimal solution by means of the subsequent solutions of a series of linear programming problems. Numerical results are reported to show the feasibility of our algorithm.     

An incremental least squares algorithm for large scale linear classification

In this work we consider the problem of training a linear classifier by assuming that the number of data is huge (in particular, data may be larger than the memory capacity). We propose to adopt a linear least-squares formulation of the problem and an incremental recursive algorithm which requires to store a square matrix (whose dimension is equal to the number of features of the data). The algorithm (very simple to implement) converges to the solution using each training data once, so that it effectively handles possible memory issues and is a viable method for linear large scale classification and for real time applications, provided that the number of features of the data is not too large (say of the order of thousands). The extensive computational experiments show that the proposed algorithm is at least competitive with the state-of-the-art algorithms for large scale linear classification.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

A variation on Karmarkar’s algorithm for solving linear programming problems

The algorithm described here is a variation on Karmarkar’s algorithm for linear programming. It has several advantages over Karmarkar’s original algorithm. In the first place, it applies to the standard form of a linear programming problem and produces a monotone decreasing sequence of values of the objective function. The minimum value of the objective function does not have to be known in advance. Secondly, in the absence of degeneracy, the algorithm converges to an optimal basic feasible solution with the nonbasic variables converging monotonically to zero. This makes it possible to identify an optimal basis before the algorithm converges.     

A practicable branch-and-bound algorithm for globally solving linear multiplicative programming

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm.     

Two-variable linear programming in parallel

Two-variable linear programming is a fundamental problem in computational geometry. Sequentially, this problem was solved optimally in linear time by Megiddo and Dyer using the elegant prune-and-search technique. In parallel, the previously best known deterministic algorithm on the EREW PRAM for this problem takes O(lognloglogn) time and O(n) work. In this paper, we present a faster parallel deterministic two-variable linear programming algorithm, which takes O(lognlog^*n) time and O(n) work on the EREW PRAM. Our algorithm is based on an interesting parallel prune-and-search technique, and makes use of new geometric observations which can be viewed as generalizations of those used by Megiddo and Dyer's sequential algorithms. Our parallel prune-and-search technique also leads to efficient EREW PRAM algorithm for the weighted selection problem, and is likely to be useful in solving other problems.