Search

This paper presents an investigation of the effects of errors in the estimation of the gradient of the objective function on the FRANK-WOLFE nonlinear programming algorithm. The investigation was motivated by a desire to reconcile the use of interactive programming approaches to the solution of the multiple-criteria problem with utility models that allow for intransitive statements of indifference and preference. Results are provided regarding the ultimate convergence of the algorithm, and its initial convergence rate. [ABSTRACT FROM AUTHOR]

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

This paper examines, for undiscounted unichain Markov renewal programming, both the Hastings policy-value iteration algorithm and the case of multiple policy improvements between each policy evaluation. The modified policy improvement procedure proposed by Hastings either increases the gain rate or maintains it, and has a larger value improvement in some transient state than in all recurrent states. This prevents cycling and ensures convergence of the policy-value iteration algorithm. Multiple policy improvements, using either the unmodified or modified policy-improvement procedure, are shown to settle ultimately upon higher-gain policies, if any exist. The iterated policy improvements, each time using the improved values, also lead to upper and lower bounds on the maximal gain rate. [ABSTRACT FROM AUTHOR]

In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]

Conditions which are necessary and sufficient for convergence of a nonlinear programming algorithm are stated. It is also shown that the convergence conditions can be easily applied to most programming algorithms. As examples, algorithms by Arrow, Hurwicz and Uzawa; Cauchy; Frank and Wolfe; and Newton-Raphson are proven to converge by direct application of the convergence conditions. Also the Topkis-Veinott convergence conditions for feasible direction algorithms are shown to be a special case of the conditions stated in this paper. [ABSTRACT FROM AUTHOR]

This paper presents a method, called the convex simplex method, for minimizing a convex objective function subject to linear inequality constraints. The method is a true generalization of Dantzig's linear simplex method both in spirit and in the fact that the same tableau and variable selection techniques are used. With a linear objective function the convex simplex method reduces to the linear simplex method. Moreover, the convex simplex method actually behaves like the linear simplex method whenever it encounters a linear portion of a convex objective function. Many of the sophisticated techniques designed to enhance the efficiency of the linear simplex method are applicable to the convex simplex method. In particular, as an example, a network transportation problem with a convex objective function is solved by using the standard transportation tableau and by only slightly modifying the usual procedure for a linear objective function. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for optimal inventory policies for a class of multi-product dependent setup cost problems. The operational policy under consideration is to replenish jointly, at a reduced cost, all products of the dependent class which are to be ordered in a scheduling period. Demands are assumed to be random with known probability distributions. Convergence of the iterative algorithm to the optimal solution under suitable hypotheses is proven. Comparisons with the results of a simpler algorithm by Simmons demonstrate the cost advantages of our method. [ABSTRACT FROM AUTHOR]