An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

An exterior point simplex algorithm for (general) linear programming problems

We present an exterior point simplex type algorithm that possesses a new monotonic property. A dual feasible basic solution is required to start with. Intermediate solutions are neither primal nor dual feasible. Cycling-free pivoting rules and an exponentional example are presented.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Long steps in an O(n 3 L) algorithm for linear programming

We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n ³ L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous primal-only initialization actually reduces the complexity to less than O(m ^1.5 n ^1.5 L).     

An O(n 3 L) potential reduction algorithm for linear programming

We describe a primal-dual potential function for linear programming: $$\phi (x,s) = \rho \ln (x^T s) - \sum\limits_{j = 1}^n {\ln (x_j s_j )} $$ whereρ? n, x is the primal variable, ands is the dual-slack variable. As a result, we develop an interior point algorithm seeking reductions in the potential function with \(\rho = n + \sqrt n \) . Neither tracing the central path nor using the projective transformation, the algorithm converges to the optimal solution set in \(O(\sqrt n L)\) iterations and uses O(n ³ L) total arithmetic operations. We also suggest a practical approach to implementing the algorithm.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

An interior point algorithm for semi-infinite linear programming

We consider the generalization of a variant of Karmarkar's algorithm to semi-infinite programming. The extension of interior point methods to infinite-dimensional linear programming is discussed and an algorithm is derived. An implementation of the algorithm for a class of semi-infinite linear programs is described and the results of a number of test problems are given. We pay particular attention to the problem of Chebyshev approximation. Some further results are given for an implementation of the algorithm applied to a discretization of the semi-infinite linear program, and a convergence proof is given in this case.     

An O(n 3 L) primal interior point algorithm for convex quadratic programming

We present a primal interior point method for convex quadratic programming which is based upon a logarithmic barrier function approach. This approach generates a sequence of problems, each of which is approximately solved by taking a single Newton step. It is shown that the method requires iterations and O(n ^3.5 L) arithmetic operations. By using modified Newton steps the number of arithmetic operations required by the algorithm can be reduced to O(n ³ L).This research was supported in part by NSF Grant DMS-85-12277 and ONR Contract N-00014-87-K0214. It was presented at the Meeting on Mathematische Optimierung, Mathematisches Forschungsinstitut, Oberwolfach, West Germany, January 3–9, 1988.     

Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

To solve linear programming problems by interior point methods an approximately centered interior point has to be known. Such a point can be found by an algorithmic approach – a so-called phase 1 algorithm or centering algorithm. For random linear programming problems distributed according to the rotation symmetry model, especially with normal distribution, we present probabilistic results on the quality of the origin as starting point and the average number of steps of a centering algorithm.     

An extended branch and bound algorithm for linear bilevel programming

For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn–Tucker conditions. However, one principle challenge is that it could not well handle a linear bilevel programming problem when the constraint functions at the upper-level are of arbitrary linear form. This paper proposes an extended branch and bound algorithm to solve this problem. The results have demonstrated that the extended branch and bound algorithm can solve a wider class of linear bilevel problems can than current capabilities permit.     

An O(n) algorithm for quadratic knapsack problems

An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem.     

AnO(\sqrt n L) iteration bound primal-dual cone affine scaling algorithm for linear programmingiteration bound primal-dual cone affine scaling algorithm for linear programming

In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima et al., 1989). The new method requires main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions.     

An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex

We present an extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex. It is shown that in at most O(nL) steps, the algorithm produces a feasible point or proves that the problem has no solution. The complexity is O(n ² m ² L) arithmetic operations. The algorithm is endowed with two new powerful stopping criteria.     

An {O(\sqrt{n}L)} iteration primal-dual second-order corrector algorithm for linear programming

In this paper, we propose a primal-dual second-order corrector interior point algorithm for linear programming problems. At each iteration, the method computes a corrector direction in addition to the Ai–Zhang direction [Ai and Zhang in SIAM J Optim 16:400–417 (2005)], in an attempt to improve performance. The corrector is multiplied by the square of the step-size in the expression of the new iterate. We prove that the use of the corrector step does not cause any loss in the worst-case complexity of the algorithm. To our best knowledge, this is the first wide neighborhood second-order corrector algorithm enjoyed the low iteration bound of O(?nL){O(\sqrt{n}L)}, the same as the best known complexity results for interior point methods.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

An O(m log n) algorithm for the max + sum spanning tree problem

In a graph in which each edge has two weights, the max + sum spanning tree problem seeks a spanning tree that has the minimum value for the combined total of the maximum of one of the edge weights and the sum of the other weights among all the spanning trees in the graph. Exploiting an efficient data structure, an O(m log n) algorithm is presented for solving this problem. This improves the currently known bound of O(mn).