Covering symmetric supermodular functions by graphs

Received December 1996 / Revised version received January 1998 Published online March 16, 1999     

Increasing the rooted-connectivity of a digraph by one

In order to unify these approaches, here we describe a two-phase greedy algorithm working on a slight extension of lattice polyhedra. This framework includes the rooted node-connectivity augmentation problem, as well, and hence the resulting algorithm, when appropriately specialized, finds a minimum cost of new edges whose addition to a digraph increases its rooted connectivity by one. The only known algorithm for this problem used submodular flows. Actually, the specialized algorithm solves an extension of the rooted edge-connectivity and node-connectivity augmentation problem. Received December 1996 / Revised version received January 1998 Published online March 16, 1999     

Quadratic convergence of potential-reduction methods for degenerate problems

Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point algorithms that do not follow the central path. Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001     

Coverings and structure of crossing families

The second problem we consider is to find a compact representation of F. We prove that there exists a so-called hypercactus K of size O(|V|), consisting of cycles and (hyper)edges arranged in a tree-like manner, and a mapping from V to V(K) in such a way that there is a bijection between the minimum cuts of K and the members of F. If F corresponds to the minimum cuts of a k-edge-connected graph then K reduces to the well-known cactus representation of minimum cuts due to Dinitz et al. Received September 1995 / Revised version received March 1997 Published online March 16, 1999     

Stable outcomes of the roommate game with transferable utility

We consider the TU version of Gale and Shapley's roommate game. We find several results that are analogous to known results for the NTU game, such as a characterization of stable outcomes by forbidden minors, a characterization of the extreme points of the core, and a median property of stable outcomes. The TU roommate game is a special case of the TU partitioning game of Kaneko and Wooders. Bondareva and Shapley's balancedness condition for the core of such games is the starting point for our forbidden minors approach. Received: April 1999/Revised version: November 2000     

Successive edge-connectivity augmentation problems

0 ,G₁,G₂,... of supergraphs of G such that G_i is a subgraph of G_j for any i<j and G_i is an optimal (l+i)-edge-connected augmentation of G for any i≥0. In this paper we will show that the augmentation algorithm of A. Frank [3] can also be used to solve the corresponding Successive Edge-Augmentation Problem and implies (a stronger version of) the Successive Augmentation Property, even for some non-uniform demands. In addition we show the – previously unknown – Successive Augmentation Property for directed edge-connectivity (in the case of uniform demands). For several possible extensions and for the two vertex-connectivity versions counter-examples are given. Received March 1995 / Revised version received February 1997 Published online March 16, 1999     

Hypergraph connectivity augmentation

Received May 1995 / Revised version received May 1996 Published online March 16, 1999     

Constant curved minimal 2-spheres in G(2,4)

This paper gives a complete classification for minimal 2-spheres with constant Gaussian curvature immersed in the complex Grassmann manifold G(2,4). Received: 14 May 1998 / Revised version: 12 October 1998     

On two homogeneous self-dual approaches to linear programming and its extensions

We investigate the relation between interior-point algorithms applied to two homogeneous self-dual approaches to linear programming, one of which was proposed by Ye, Todd, and Mizuno and the other by Nesterov, Todd, and Ye. We obtain only a partial equivalence of path-following methods (the centering parameter for the first approach needs to be equal to zero or larger than one half), whereas complete equivalence of potential-reduction methods can be shown. The results extend to self-scaled conic programming and to semidefinite programming using the usual search directions. Received: July 1998 / Accepted: September 2000?Published online November 17, 2000     

Line search termination criteria for collinear scaling algorithms for minimizing a class of convex functions

Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence. Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important special case where the function being minimized belongs to a certain class of convex functions. Received February 1, 1997 / Revised version received September 8, 1997     

On the analyticity properties of infeasible-interior-point paths for monotone linear complementarity problems

Infeasible-interior-point paths , a positive vector, for a horizontal linear complementarity problem are defined as the solution of () If the path converges for , then it converges to a solution of . This paper deals with the analyticity properties of and its derivatives with respect to r near r = 0 for solvable monotone complementarity problems . It is shown for with a strictly complementary solution that the path , , has an extension to which is analytic also at . If has no strictly complementary solution, then , , has an extension to that is analytic at . Received May 24, 1996 / Revised version received February 25, 1998     

Scenario tree generation for multiperiod financial optimization by optimal discretization

Multiperiod financial optimization is usually based on a stochastic model for the possible market situations. There is a rich literature about modeling and estimation of continuous-state financial processes, but little attention has been paid how to approximate such a process by a discrete-state scenario process and how to measure the pertaining approximation error.?In this paper we show how a scenario tree may be constructed in an optimal manner on the basis of a simulation model of the underlying financial process by using a stochastic approximation technique. Consistency relations for the tree may also be taken into account. Received: December 15, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Parameter estimation in systems of nonlinear equations

Summary. A numerical method is presented to determine parameters in a system of non\-linear equations in the following sense: Proceeding from given experimental data, e.g., observation times and measurements, the minimum least-squares distance of the measured data from a fitting criterion depending on the solution of a system of nonlinear equations is to be computed. Specifically coupled mass equilibrium models are described in more detail that are used in pharmaceutical applications for receptor-ligand binding studies. They are used for instance for the radioimmunological determination of Fenoterol or related substances. Numerical results based on laboratory data are included to test the robustness of the algorithm implemented. Received May 24, 1993/Revised version received February 13, 1994     

A non–interior predictor–corrector path following algorithm for the monotone linear complementarity problem

We present a predictor–corrector non–interior path following algorithm for the monotone linear complementarity problem based on Chen–Harker–Kanzow–Smale smoothing techniques. Although the method is modeled on the interior point predictor–corrector strategies, it is the first instance of a non–interior point predictor–corrector algorithm. The algorithm is shown to be both globally linearly convergent and locally quadratically convergent under standard hypotheses. The approach to global linear convergence follows the authors’ previous work on this problem for the case of (P ₀+R ₀) LCPs. However, in this paper we use monotonicity to refine our notion of neighborhood of the central path. The refined neighborhood allows us to establish the uniform boundedness of certain slices of the neighborhood of the central path under the standard hypothesis that a strictly positive feasible point exists. Received September 1997 / Revised version received May 1999?Published online December 15, 1999     

Lifting valid inequalities for the precedence constrained knapsack problem

This paper considers the precedence constrained knapsack problem. More specifically, we are interested in classes of valid inequalities which are facet-defining for the precedence constrained knapsack polytope. We study the complexity of obtaining these facets using the standard sequential lifting procedure. Applying this procedure requires solving a combinatorial problem. For valid inequalities arising from minimal induced covers, we identify a class of lifting coefficients for which this problem can be solved in polynomial time, by using a supermodular function, and for which the values of the lifting coefficients have a combinatorial interpretation. For the remaining lifting coefficients it is shown that this optimization problem is strongly NP-hard. The same lifting procedure can be applied to (1,k)-configurations, although in this case, the same combinatorial interpretation no longer applies. We also consider K-covers, to which the same procedure need not apply in general. We show that facets of the polytope can still be generated using a similar lifting technique. For tree knapsack problems, we observe that all lifting coefficients can be obtained in polynomial time. Computational experiments indicate that these facets significantly strengthen the LP-relaxation. Received July 10, 1997 / Revised version received January 9, 1999? Published online May 12, 1999     

Lifted flow cover inequalities for mixed 0-1 integer programs

We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show the effectiveness of our lifting procedures. Received May 15, 1996 / Revised version received August 7, 1998 Published online June 28, 1999     

A 1-(S,T)-edge-connectivity augmentation algorithm

Received January 1995 / Revised version received April 1996 Published online March 16, 1999     

Solving a class of linear projection equations

Summary. Many interesting and important constrained optimization problems in mathematical programming can be translated into an equivalent linear projection equation Here, is the orthogonal projection on some convex set (e.g. ) and is a positive semidefinite matrix. This paper presents some new methods for solving a class of linear projection equations. The search directions of these methods are straighforward extensions of the directions in traditional methods for unconstrained optimization. Based on the idea of a projection and contraction method [7] we get a simple step length rule and are able to obtain global linear convergence. Received April 19, 1993 / Revised version received February 9, 1994