Self-regular functions and new search directions for linear and semidefinite optimization

In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002     

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.     

Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

In this paper we give a new convergence analysis of a projective scaling algorithm. We consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed fraction λ≤2/3 of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, we will show (i) polynomiality of the algorithm with complexities of O(nL) and O(n ² L) iterations for λ<2/3 and λ=2/3, respectively; (ii) global covnergence of the algorithm when the optimal face is unbounded; (iii) convergence of the primal iterates to a relative interior point of the optimal face; (iv) convergence of the dual estimates to the analytic center of the dual optimal face; and (v) convergence of the reduction rate of the objective function value to 1−λ.     

A new full-Newton step <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) infeasible interior-point algorithm for semidefinite optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem, close to their central paths. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed pair, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close enough to the central path of the new perturbed pair. The starting point depends on a positive number ζ. The algorithm terminates either by finding an ε-solution or by detecting that the primal-dual problem pair has no optimal solution (X ^*,y ^*,S ^*) with vanishing duality gap such that the eigenvalues of X ^* and S ^* do not exceed ζ. The iteration bound coincides with the currently best iteration bound for semidefinite optimization problems.     

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/ε). This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098.     

Kernel-Based Interior-Point Methods for Monotone Linear Complementarity Problems over Symmetric Cones

We present an interior-point method for monotone linear complementarity problems over symmetric cones (SCLCP) that is based on barrier functions which are defined by a large class of univariate functions, called eligible kernel functions. This class is fairly general and includes the classical logarithmic function, the self-regular functions, as well as many non-self-regular functions as special cases. We provide a unified analysis of the method and give a general scheme on how to calculate the iteration bounds for the entire class. We also calculate the iteration bounds of both large-step and short-step versions of the method for ten frequently used eligible kernel functions. For some of them we match the best known iteration bound for large-step methods, while for short-step methods the best iteration bound is matched for all cases. The paper generalizes results of Lesaja and Roos (SIAM J. Optim. 20(6):3014–3039, 2010) from P _∗(κ)-LCP over the non-negative orthant to monotone LCPs over symmetric cones.     

Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming

We present an analysis of the full-Newton step infeasible interior-point algorithm for semidefinite optimization, which is an extension of the algorithm introduced by Roos [C. Roos, A full-Newton step 𝒪(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), pp. 1110–1136] for the linear optimization case. We use the proximity measure σ(V)?=?‖I???V ²‖ to overcome the difficulty of obtaining an upper bound of updated proximity after one full-Newton step, where I is an identity matrix and V is a symmetric positive definite matrix. It turns out that the complexity analysis of the algorithm is simplified and the iteration bound obtained is improved slightly.     

A minimum residual algorithm for solving linear systems

A minimum residual algorithm for solving a large linear system (I+S)x=b, with b∈ℂ ⁿ and S∈ℂ ^n×n being readily invertible, is proposed. For this purpose Krylov subspaces are generated by applying S and S ^-1 cyclically. The iteration can be executed with every linear system once the coefficient matrix has been split into the sum of two readily invertible matrices. In case S is a translation and a rotation of a Hermitian matrix, a five term recurrence is devised. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65F10     

Volumetric path following algorithms for linear programming

We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n ^1/4 m ^1/4 L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n ² m), as opposed to O(nm ²), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University of Iowa Center for Advanced Studies.     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.     

On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

Computation of Optimal Backward Perturbation Bounds for Large Sparse Linear Least Squares Problems

In this note we propose an algorithm based on the Lanczos bidiagonalization to approximate the backward perturbation bound for the large sparse linear squares problem. The algorithm requires ((m + n)l) operations where m and n are the size of the matrix under consideration and l <#60;<#60; min(m,n). The import of the proposed algorithm is illustrated by some examples coming from the Harwell-Boeing collection of test matrices.This revised version was published online in October 2005 with corrections to the Cover Date.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is O(lnN/n), where N is the dimension and n is the number of iterations. The bound looks promising because lnN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed. Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 6, pp. 734–737. Presented by Academician S.N. Vasil’ev February 9, 2009 The article was translated by the authors.     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Untangling Polygons and Graphs

Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C _n while keeping Ω(n ^2/3) vertices fixed. For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)^2/3) vertices are fixed in every untangling of δ.     

Resolution method for mixed integer bi-level linear problems based on decomposition technique

In this article, we propose a new algorithm for the resolution of mixed integer bi-level linear problem (MIBLP). The algorithm is based on the decomposition of the initial problem into the restricted master problem (RMP) and a series of problems named slave problems (SP). The proposed approach is based on Benders decomposition method where in each iteration a set of variables are fixed which are controlled by the upper level optimization problem. The RMP is a relaxation of the MIBLP and the SP represents a restriction of the MIBLP. The RMP interacts in each iteration with the current SP by the addition of cuts produced using Lagrangian information from the current SP. The lower and upper bound provided from the RMP and SP are updated in each iteration. The algorithm converges when the difference between the upper and lower bound is within a small difference ε. In the case of MIBLP Karush–Kuhn–Tucker (KKT) optimality conditions could not be used directly to the inner problem in order to transform the bi-level problem into a single level problem. The proposed decomposition technique, however, allows the use of KKT conditions and transforms the MIBLP into two single level problems. The algorithm, which is a new method for the resolution of MIBLP, is illustrated through a modified numerical example from the literature. Additional examples from the literature are presented to highlight the algorithm convergence properties.     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

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.