Mathematical Programming: Series A and B

Given a linear program with a boundedp-dimensional feasible region let the objective vector range over ans-sphere, that is, ans-dimensional sphere centered at the origin wheres does not exceedpź1. If the feasible region and the sphere are in general ...

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within ...

The so called Modified Hung--Rom Algorithm, based upon theoretical considerations of Hirsch-paths, seems to be one of the most efficient algorithms for assignment problems. Since any two basic feasible solutions to a linear problem can always be ...

A knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more "knapsack" constraints (an inequality constraint with all non-negative coefficients). All knapsack sharing algorithms to date have assumed that the ...

This paper provides a modification to the Gauss--Newton method for nonlinear least squares problems. The new method is based on structured quasi-Newton methods which yield a good approximation to the second derivative matrix of the objective function. ...

This paper presents a globally convergent, locally quadratically convergent algorithm for solving general nonlinear programs, nonlinear complementarity and variational inequality problems. The algorithm is based on a unified formulation of these three ...

We prove the following theorem which gives a bound on the proximity of the real and the integer solutions to certain constrained optimization programs.

In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral ...

This paper presents extensions and further analytical properties of algorithms for linear programming based only on primal scaling and projected gradients of a potential function. The paper contains extensions and analysis of two polynomial-time ...

In this paper we analyze conjugate gradient-type algorithms for solving convex quadratic programs subject only to box constraints (i.e., lower and upper bounds on the variables). Programs of this type, which we denote by BQP, play an important role in ...

A new conical algorithm is developed for finding the global minimum of a concave function over a polytope. To ensure faster convergence and overcome some major drawbacks of previous conical algorithms, a normal (rather than exhaustive) subdivision ...

We simplify a result by Mangasarian on the existence of solutions to the linear complementarity problem. The simplified condition gives a new geometric interpretation of the result. When used to characterize the matrix classesQ andQ0, our condition ...

We prove a generalization of Brouwer's famous fixed point theorem to discontinuous maps. The main result shows that for discontinuous functions on a compact convex domainX one can always find a pointx źX such that źxźf(x)ź is less than a certain measure ...

For a given undirected graphG=(V, ź) withn vertices we define four norms on źn, namely[Figure not available: see fulltext.], where ź (resp.[Figure not available: see fulltext.]) stands for the family of all maximal cliques inG (resp. $$\tilde G$$ , the ...

It is shown that Lipschitzian functions are strictly convex if and only if their generalized gradients are disjoint at distinct interior points of a given bounded level set.

We analyze the method of sequential quadratic programming for equality constrained minimization problems in Hilbert spaces of functions, and for the discrete approximations of such problems in the context of an elliptic parameter identification problem. ...

A penalty method for convex functions which cannot necessarily be extended outside their effective domains by an everywhere finite convex function is proposed and combined with the proximal method. Proofs of convergence rely on variational convergence ...

This paper is concerned with the optimal value function arising in the primal decomposition of a quasidifferentiable programming problem. In particular, estimates for the upper Dini directional derivative of this function are derived. They involve ...

In Meanti et al. (1990) an almost sure asymptotic characterization has been derived for the optimal solution value as function of the knapsack capacities, when the profit and requirement coefficients of items to be selected from are random variables. In ...

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling ...

The Steiner arborescence (or Steiner directed tree) problem concerns the connection of a set of target vertices of a digraph to a given root vertex. This problem is known to be NP-hard. In the present paper we study the facial structure of two polyhedra ...