Interior path following primal-dual algorithms. part II: Convex quadratic programming

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n ³ L).     

An extension of Karmarkar's projective algorithm for convex quadratic programming

We present an extension of Karmarkar's linear programming algorithm for solving a more general group of optimization problems: convex quadratic programs. This extension is based on the iterated application of the objective augmentation and the projective transformation, followed by optimization over an inscribing ellipsoid centered at the current solution. It creates a sequence of interior feasible points that converge to the optimal feasible solution in O(Ln) iterations; each iteration can be computed in O(Ln ³) arithmetic operations, wheren is the number of variables andL is the number of bits in the input. In this paper, we emphasize its convergence property, practical efficiency, and relation to the ellipsoid method.     

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.     

Polar Varieties,Real Equation Solving,and Data Structures: The Hypersurface Case

In this paper we apply for the first time a new method for multivariate equation solving which was developed for complex root determination to therealcase. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem-adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in nonuniform sequential time that ispolynomialin the length of the input (given in straight-line program representation) and an adequately definedgeometric degree of the equation system.Replacing the notion of geometric degree of the given polynomial equation system by a suitably definedreal (or complex) degreeof certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.     

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms.     

A flow-mode,self-steering,cellular multiplier-summation processor

Flow-mode or stream-processing digital systems have been proposed in which code, control and data are constantly moving so that multiple instructions are processed concurrently. We show the design of a flow-mode cellular array processor which can perform a number of two's complement fixed-point arithmetic operations. These operations are: three operand addition and/or subtraction, two operand multiplication and vector inner-product. Operand sizes are: 2N bit for addition and subtraction operands, andN bit for multiplication operands. Results are 2N bit. The network can simultaneously operate on 4N+2 datasets with any mix of the above operations being handled. The processor is based on the use of asynchronous cellular arrays. Given a continued flow of input datasets, the effective computation time is worst-case propagation time within one cell. A typical cell contains a 1-bit position 3-input full adder with associated input data storage. Thus the effective computation time is independent of the operand bit length.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

AVLSI partition algorithm

A VLSI sorter of sizeO(n) can sortn elements in linear time when the input and output time are taken into account. If the input contains more thann elements, some prepocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner isO(logk) for a data file of sizekn wheren is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must goO(k) times through the partitioner like in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

Self-intersections and smoothness of general offset surfaces

A convex body N moves such that it touches a closed surface M. While doing this, it is undergoing a purely translational motion. A fixed point of N traces out the general offset surface during this motion. We study the connection between singularities and self-intersections of and the possible collisions of M with N during this motion and obtain some global results. Received 27 January 1999.     

Domains of Holomorphy with Edges and Lower Dimensional Boundary Singularities

It is shown that a domain in C ^N with piecewise smooth boundary (and also of some more general shape) is a domain of holomorphy, provided the Levi form at every regular point is positively semidefinite and the tangent cone is convex at every point outside a boundary subset of zero Hausdorff (2N-2)-dimensional measure.     

Steiner minimal trees for three points with one convex polygonal obstacle

The problem of constructing Steiner minimal trees in the Euclidean plane is NP-hard. When in addition obstacles are present, difficulties of constructing obstacle-avoiding Steiner minimal trees are compounded. This problem, which has many obvious practical applications when designing complex transportation and distribution systems, has received very little attention in the literature. The construction of Steiner minimal trees for three terminal points in the Euclidean plane (without obstacles) has been completely solved (among others by Fermat, Torricelli, Cavallieri, Simpson, Heinen) during the span of the last three centuries. This construction is a cornerstone for both exact algorithms and heuristics for the Euclidean Steiner tree problem with arbitrarily many terminal points. An algorithm for three terminal points in the presence of one polygonal convex obstacle is given. It is shown that this algorithm has the worst-case time complexityO(n), wheren is the number of extreme points on the obstacle. As an extension to the underlying algorithm, if the obstacle is appropriately preprocessed inO(n) time, we can solve any problem instance with three arbitrary terminal points and the preprocessed convex polygonal obstacle inO(logn) time. We believe that the three terminal points algorithm will play a critical role in the development of heuristics for problem instances with arbitrarily many terminal points and obstacles.     

A stochastic gradient type algorithm for closed-loop problems

We focus on the numerical solution of closed-loop stochastic problems, and propose a perturbed gradient algorithm to achieve this goal. The main hurdle in such problems is the fact that the control variables are infinite-dimensional, due to, e.g., the information constraints. Alternatively said, control variables are feedbacks, i.e., functions. Such controls have hence to be represented in a finite way in order to solve the problem numerically. In the same way, the gradient of the criterion is itself an infinite-dimensional object. Our algorithm replaces this exact (and unknown) gradient by a perturbed one, which consists of the product of the true gradient evaluated at a random point and a kernel function which extends this gradient to the neighbourhood of the random point. Proceeding this way, we explore the whole space iteration after iteration through random points. Since each kernel function is perfectly known by a small number of parameters, say N, the control at iteration k is perfectly known as an infinite-dimensional object by at most N × k parameters. The main strength of this method is that it avoids any discretization of the underlying space, provided that we can sample as many points as needed in this space. Moreover, our algorithm can take into account the possible measurability constraints of the problem in a new way. Finally, the randomized strategy implemented by the algorithm causes the most probable parts of the space to be the most explored ones, which is a priori an interesting feature. In this paper, we first prove two convergence results of this algorithm in the strongly convex and convex cases, and then give some numerical examples showing the interest of this method for practical stochastic optimization problems. In Memoriam: Jean-Sébastien Roy passed away July 04, 2007. He was 33 years old.     

On a proposed divide-and-conquer minimal spanning tree algorithm

In a recent paper published in this journal, R. Chang and R. Lee purport to devise anO(N logN) time minimal spanning tree algorithm forN points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound ofO(N ² logN). Since it is known that alternate, trulyO(N logN) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable.This author's research is supported in part by the Washington State Technology Center and by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

A general approach to the analysis of controlled perturbation algorithms

Controlled Perturbation (CP, for short) is an approach to obtaining efficient and robust implementations of a large class of geometric algorithms using the computational speed of multiple precision floating point arithmetic (compared to exact arithmetic), while bypassing the precision problems by perturbation. It also allows algorithms to be written without consideration of degenerate cases. CP replaces the input objects by a set of randomly perturbed (moved, scaled, stretched, etc.) objects and protects the evaluation of geometric predicates by guards. The execution is aborted if a guard indicates that the evaluation of a predicate with floating point arithmetic may return an incorrect result. If the execution is aborted, the algorithm is rerun on a new perturbation and maybe with a higher precision of the floating point arithmetic. If the algorithm runs to completion, it returns the correct output for the perturbed input.The analysis of CP algorithms relates various parameters: the perturbation amount, the arithmetic precision, the range of input values, and the number of input objects. We present a general methodology for analyzing CP algorithms. It is powerful enough to analyze all geometric predicates that are formulated as signs of polynomials.     

On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

Derivatives with respect to metrics and applications: subgradient marching algorithm

This paper introduces a subgradient descent algorithm to compute a Riemannian metric that minimizes an energy involving geodesic distances. The heart of the method is the Subgradient Marching Algorithm to compute the derivative of the geodesic distance with respect to the metric. The geodesic distance being a concave function of the metric, this algorithm computes an element of the subgradient in O(N ² log(N)) operations on a discrete grid of N points. It performs a front propagation that computes a subgradient of a discrete geodesic distance. We show applications to landscape modeling and to traffic congestion. Both applications require the maximization of geodesic distances under convex constraints, and are solved by subgradient descent computed with our Subgradient Marching. We also show application to the inversion of travel time tomography, where the recovered metric is the local minimum of a non-convex variational problem involving geodesic distances.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

Constrained stabilization: an enlargement technique of positively invariant sets

This paper presents a new technique of enlargement of positivelyinvariant sets for linear systems with input saturation. Thistechnique is based on the use of the convex hull of the unionof N preconstructed positively invariant sets. It is shown thatthe obtained region is a stability region where the controlis always admissible.     

A Class of Infeasible Interior Point Algorithms for Convex Quadratic Programming

This article proposes a class of infeasible interior point algorithms for convex quadratic programming, and analyzes its complexity. It is shown that this algorithm has the polynomial complexity. Its best complexity is O(nL).