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     

The volume algorithm: producing primal solutions with a subgradient method

We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location. Received: June 15, 1998 / Accepted: November 15, 1999?Published online March 15, 2000     

A primal—dual infeasible-interior-point algorithm for linear programming

As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.Part of this research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contract N00014-91-C-0026 is acknowledged.Supported by Grant-in-Aids for Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Encouragement of Young Scientist (03740125) and Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.     

A primal dual modified subgradient algorithm with sharp Lagrangian

We apply a modified subgradient algorithm (MSG) for solving the dual of a nonlinear and nonconvex optimization problem. The dual scheme we consider uses the sharp augmented Lagrangian. A desirable feature of this method is primal convergence, which means that every accumulation point of a primal sequence (which is automatically generated during the process), is a primal solution. This feature is not true in general for available variants of MSG. We propose here two new variants of MSG which enjoy both primal and dual convergence, as long as the dual optimal set is nonempty. These variants have a very simple choice for the stepsizes. Moreover, we also establish primal convergence when the dual optimal set is empty. Finally, our second variant of MSG converges in a finite number of steps.     

A primal—dual affine-scaling potential-reduction algorithm for linear programming

We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

A partial complement method for approximating solutions of a primal dual fixed-point problem

We study the convergence of the Mann Iteration applied to the partial complement of a firmly nonexpansive operator with respect to a linear subspace of a Hilbert space. A new concept considered here. A regularized version is also proposed. Furthermore, to motivate this concept, some applications to robust regression procedures and location problems are proposed.     

A new shift of the QL algorithm for irreducible symmetric tridiagonal matrices

A new shift in the QL algorithm for symmetric tridiagonal matrices is described. The shift is a combination of the Rayleigh quotient shift and Wilkinson's shift. It is shown that QL is globally convergent with this shift and that the asymptotic rate is always cubic.     

A note on primal network flow algorithms

Klein [1967] andDomschke [1973] have developed primal algorithms for network flow problems. An alternative derivation shows that these algorithms implicitly take advantage of duality and end up with an optimal dual solution.

---

Zusammenfassung Ausgangspunkt dieser Arbeit sind die Algorithmen vonKlein [1967] undDomschke [1973] zur Bestimmung kostenminimaler Flüsse in Netzwerken. Es werden allgemein interessierende Zusammenhänge zwischen primalen und primal-dualen Algorithmen aufgezeigt.

     

A comparison of pivot selection rules for primal simplex based network codes

This note reports a comparative study of several approaches for selecting the incoming arc in primal simplex specializations for network problems. Our tests establish that a recent method improves on two established choice rules found effective in earlier studies.     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

A finiteness theorem for primal extensions

A set W⊆V(G) is called homogeneous in a graph G if 2?|W|?|V(G)|-1, and N(x)?W=N(y)?W for each x,y∈W. A graph without homogeneous sets is called prime. A graph H is called a (primal) extension of a graph G if G is an induced subgraph of H, and H is a prime graph. An extension H of G is minimal if there are no extensions of G in the set ISub(H)?{H}. We denote by Ext(G) the set of all minimal extensions of a graph G.We investigate the following problem: find conditions under which Ext(G) is a finite set. The main result of Giakoumakis (Discrete Math. 177 (1997) 83-97) is the following sufficient condition.

Theorem. If every homogeneous set of G has exactly two vertices thenExt(G)is a finite set.     

Limiting Lagrangians: A primal approach

In this paper, we consider a convex program with either a finite or an infinite number of constraints and its formal Lagrangian dual. We show that either the primal program satisfies a general condition which implies there is no duality gap or that there is a nonzero vectord with the following properties: First, wheneverd is added to the objective function, where is a positive number not greater than one, the resulting program satisfies the general sufficient condition cited above for no duality gap. Second, the optimal value of this perturbed program is attained and tends to the optimal value of the original program as tends to zero. Third, the optimal solutions of the perturbed programs form a minimizing sequence of the original program. As a consequence of the above, we derive the limiting Lagrangian theory of Borwein, Duffin, and Jeroslow.The authors are indebted to an unknown referee who suggested the very short and elegant proofs of Lemma 2.3 and Theorem 2.3.This work was completed while the first author was a member of the College of Management, Georgia Institute of Technology, Atlanta, Georgia.     

A comparison between a primal and a dual cutting plane algorithm for posynomial geometric programming problems

In this paper, primal and dual cutting plane algorithms for the solution of posynomial geometric programming problems are presented. It is shown that these cuts are deepest, in the sense that they cut off as much of the infeasible set as possible. Problems of nondifferentiability in the dual cutting plane are circumvented by the use of a subgradient. Although the resulting dual problem seems easier to solve, the computational experience seems to show that the primal cutting plane outperforms the dual.     

Solving large-scale minimax problems with the primal—dual steepest descent algorithm

This paper shows that the primal-dual steepest descent algorithm developed by Zhu and Rockafellar for large-scale extended linear—quadratic programming can be used in solving constrained minimax problems related to a generalC ² saddle function. It is proved that the algorithm converges linearly from the very beginning of the iteration if the related saddle function is strongly convex—concave uniformly and the cross elements between the convex part and the concave part of the variables in its Hessian are bounded on the feasible region. Better bounds for the asymptotic rates of convergence are also obtained. The minimax problems where the saddle function has linear cross terms between the convex part and the concave part of the variables are discussed specifically as a generalization of the extended linear—quadratic programming. Some fundamental features of these problems are laid out and analyzed.This work was supported by Eliezer Naddor Postdoctoral Fellowship in Mathematical Sciences at the Department of Mathematical Sciences, the Johns Hopkins University during the year 1991–92.     

A class of primal affine scaling algorithms

We obtain a class of primal affine scaling algorithms which generalize some known algorithms. This class, depending on a r-parameter, is constructed through a family of metrics generated by −r power, r ? 1, of the diagonal iterate vector matrix. We prove the so-called weak convergence of the primal class for nondegenerate linearly constrained convex programming. We observe the computational performance of the class of primal affine scaling algorithms, accomplishing tests with linear programs from the NETLIB library and with some quadratic programming problems described in the Maros and Mészáros repository.