Analytical properties of the central path at boundary point in linear programming

Received October 15, 1996 / Revised version received January 28, 1998 Published online October 21, 1998     

Benchmarking optimization software with performance profiles

We propose performance profiles — distribution functions for a performance metric — as a tool for benchmarking and comparing optimization software. We show that performance profiles combine the best features of other tools for performance evaluation. Received: February 2001 / Accepted: May 2001?Published online October 2, 2001     

Intersection theorems on polytopes

Received June 6, 1995 / Revised version received May 26, 1998 Published online October 9, 1998     

Stability in the presence of degeneracy and error estimation

Received February 10, 1997 / Revised version received June 6, 1998 Published online October 9, 1998     

A note on “On Pareto optima, the Fermat-Weber problem, and polyhedral gauges”

Received September 3, 1997 / Revised version received March 20, 1998 Published online October 9, 1998     

Sample-path solution of stochastic variational inequalities

Received July 30, 1997 / Revised version received June 4, 1998 Published online October 21, 1998     

Degeneracy in the multi-source Weber problem

Received June 10, 1996 / Revised version received May 20, 1997 Published online October 21, 1998     

The many facets of linear programming

We examine the history of linear programming from computational, geometric, and complexity points of view, looking at simplex, ellipsoid, interior-point, and other methods. Received: June 22, 2000 / Accepted: April 4, 2001?Published online October 2, 2001     

Chtoucas de Drinfeld et correspondance de Langlands

One proves Langlands’ correspondence for GL _r over function fields. This is a generalization of Drinfeld’s proof in the case of rank 2 : Langlands’ correspondence is realized in ℓ-adic cohomology spaces of the modular varieties classifying rank r Drinfeld shtukas. Oblatum 13-X-2000 & 7-VI-2001?Published online: 12 October 2001     

A branch-and-cut algorithm for the Undirected Rural Postman Problem

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported. Received: December 1, 1997 / Accepted: October 13, 1999?Published online January 27, 2000     

On the homotopy type of Poincaré spaces

We study the homotopy type of finite-oriented Poincaré spaces (and, in particular, of closed topological manifolds) in even dimension. Our results relate polarized homotopy types over a stage of the Postnikov tower with the concept of CW-tower of categories due to Baues. This fact allows us to obtain a new formula for the top-dimensional obstruction for extending maps to homotopy equivalences. Then we complete the paper with an algebraic characterization of high-dimensional handlebodies. Received: April 14, 1999?Published online: October 2, 2001     

Nonsmooth analysis of eigenvalues

Received October 28, 1996 / Revised version received January 28, 1998 Published online October 9, 1998     

Nonlinear programming algorithms using trust regions and augmented Lagrangians with nonmonotone penalty parameters

The strategy for obtaining global convergence is based on the trust region approach. The merit function is a type of augmented Lagrangian. A new updating scheme is introduced for the penalty parameter, by means of which monotone increase is not necessary. Global convergence results are proved and numerical experiments are presented. Received May 31, 1995 / Revised version received December 12, 1997 Published online October 21, 1998     

Metric regularity and quantitative stability in stochastic programs with probabilistic constraints

Received January 24, 1996 / Revised version received December 24, 1997 Published online October 21, 1998     

Approximating quadratic programming with bound and quadratic constraints

Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998     

A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation

We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio. Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000     

A characterization of ill-posed data instances for convex programming

Given a data instance of a convex program, we provide a collection of conic linear systems such that the data instance is ill-posed if and only if at least one of those systems is satisfied. This collection of conic linear systems is derived from a characterization of the boundary of the set of primal and dual feasible data instances associated with the given convex program. Received: September 1998 / Accepted: August 2000?Published online October 26, 2001     

A hybrid Newton method for solving the variational inequality problem via the D-gap function

The variational inequality problem (VIP) can be reformulated as an unconstrained minimization problem through the D-gap function. It is proved that the D-gap function has bounded level sets for the strongly monotone VIP. A hybrid Newton-type method is proposed for minimizing the D-gap function. Under some conditions, it is shown that the algorithm is globally convergent and locally quadratically convergent. Received May 6, 1997 / Revised version received October 30, 1998?Published online June 11, 1999     

Objective-derivative-free methods for constrained optimization

We propose feasible descent methods for constrained minimization that do not make explicit use of the derivative of the objective function. The methods iteratively sample the objective function value along a finite set of feasible search arcs and decrease the sampling stepsize if an improved objective function value is not sampled. The search arcs are obtained by projecting search direction rays onto the feasible set and the search directions are chosen such that a subset approximately generates the cone of first-order feasible variations at the current iterate. We show that these methods have desirable convergence properties under certain regularity assumptions on the constraints. In the case of linear constraints, the projections are redundant and the regularity assumptions hold automatically. Numerical experience with the methods in the linearly constrained case is reported. Received: November 12, 1999 / Accepted: April 6, 2001?Published online October 26, 2001     

Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints

We will propose a branch and bound algorithm for calculating a globally optimal solution of a portfolio construction/rebalancing problem under concave transaction costs and minimal transaction unit constraints. We will employ the absolute deviation of the rate of return of the portfolio as the measure of risk and solve linear programming subproblems by introducing (piecewise) linear underestimating function for concave transaction cost functions. It will be shown by a series of numerical experiments that the algorithm can solve the problem of practical size in an efficient manner. Received: July 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000