A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial t...
详细信息
ISBN:
(纸本)9781581136746
A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time construction that guarantee's Racke's bounds, and more generally gives the true optimal ratio for any network.
We describe a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set C subset of R(n). At each step the algorithm has a system of linear inequality cons...
详细信息
We describe a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set C subset of R(n). At each step the algorithm has a system of linear inequality constraints which defines a polyhedron P superset of C, and an interior point x is an element of P. The algorithm then either drops one constraint, or calls an oracle to check if x is an element of C, and, if not, obtain a new constraint that separates x from C. Following the addition or deletion of a constraint, the algorithm takes a small number of Newton steps for the volumetric barrier V(.). Progress of the algorithm is measured in terms of changes in V(.). The algorithm is terminated when either it is discovered that x is an element of C, or V(.) becomes large enough to demonstrate that the volume of C must be below some prescribed amount. The complexity of the algorithm compares favorably with that of the ellipsoid method, especially in terms of the number of calls to the separation oracle. Compared to Vaidya's original analysis, we decrease the total number of Newton steps required for termination by a factor of about 1.3 million, white at the same time decreasing the maximum number of constraints used to define P from 10(7)n to 200n.
In this paper, a class of min-max continuous location problems is discussed. After giving a complete characterization of the stationary points, we propose a simple central and deep-cut ellipsoid algorithm to solve the...
详细信息
In this paper, a class of min-max continuous location problems is discussed. After giving a complete characterization of the stationary points, we propose a simple central and deep-cut ellipsoid algorithm to solve these problems for the quasiconvex case. Moreover, an elementary convergence proof of this algorithm and some computational results are presented.
A variant of the ellipsoid method for nonlinear programming is introduced to enhance the speed of convergence. This variant is based on a new simple scheme to reduce the ellipsoid volume by using two center cuts gener...
详细信息
A variant of the ellipsoid method for nonlinear programming is introduced to enhance the speed of convergence. This variant is based on a new simple scheme to reduce the ellipsoid volume by using two center cuts generated in two consecutive iterations of the ellipsoid method. Computational tests show a significant improvement in computational efficiency. The tests show that the improvement is more significant for larger-size problems.
In this paper fuzzy programming technique is used to solve a multi-objective geometric programming problem as a vector minimum problem. A fuzzy membership function is defined for the multi-objective geometric programm...
详细信息
In this paper fuzzy programming technique is used to solve a multi-objective geometric programming problem as a vector minimum problem. A fuzzy membership function is defined for the multi-objective geometric programming problem. Two numerical examples are presented to illustrate the method.
This paper presents a bundle method of descent for minimizing a convex (possibly nonsmooth) function f of several variables. At each iteration the algorithm finds a trial point by minimizing a polyhedral model of f su...
详细信息
This paper presents a bundle method of descent for minimizing a convex (possibly nonsmooth) function f of several variables. At each iteration the algorithm finds a trial point by minimizing a polyhedral model of f subject to an ellipsoid trust region constraint. The quadratic matrix of the constraint, which is updated as in the ellipsoid method, is intended to serve as a generalized “Hessian” to account for “second-order” effects, thus enabling faster convergence. The interpretation of generalized Hessians is largely heuristic, since so far this notion has been made precise by J. L. Goffin only in the solution of linear inequalities. Global convergence of the method is established and numerical results are given.
An ellipsoid algorithm for convex, quadratical programming is given, based on the use of the objective function itself for ellipsoidal iterations. An implemented version is presented and numerical results are discusse...
详细信息
A computational comparison of several general purpose nonlinear programming algorithms is presented. This study was motivated by the preliminary results in [12] which show that the recently developed ellipsoid algorit...
详细信息
A computational comparison of several general purpose nonlinear programming algorithms is presented. This study was motivated by the preliminary results in [12] which show that the recently developed ellipsoid algorithm is competitive with a widely used augmented Lagrangian algorithm. To provide a better perspective on the value of ellipsoid algorithms in nonlinear programming, the present study includes some of the most highly regarded nonlinear programming algorithms and is a much more comprehensive study than [12]. The algorithms considered here are chosen from four distinct classes and 50 well-known test problems are used. The algorithms used represent augmented Lagrangian, ellipsoid, generalized reduced gradient, and iterative quadratic programming methods. Results regarding robustness and relative efficiency are presented.
We present a method for implementing the ellipsoid algorithm, whose basic iterative step is a linear row manipulation on the matrix of inequalities. This step is somewhat similar to a simplex iteration, and may give a...
详细信息
We present a method for implementing the ellipsoid algorithm, whose basic iterative step is a linear row manipulation on the matrix of inequalities. This step is somewhat similar to a simplex iteration, and may give a clue to the relation between the two algorithms. Geometrically, the step amounts to performing affine transformations which map the ellipsoids onto a fixed sphere. The method was tried successfully on linear programs with up to 50 variables, some of which required more than 24 000 iterations. Geometrical properties of the iteration suggest that the ellipsoid algorithm is numerically robust, which is supported by our computational experience.
We investigate an ellipsoid algorithm for nonlinear programming. After describing the basic steps of the algorithm, we discuss its computer implementation and present a method for measuring computational efficiency. T...
详细信息
We investigate an ellipsoid algorithm for nonlinear programming. After describing the basic steps of the algorithm, we discuss its computer implementation and present a method for measuring computational efficiency. The computational results obtained from experimenting with the algorithm are discussed and the algorithm's performance is compared with that of a widely used commercial code.
暂无评论