We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower...
详细信息
We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.
In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve O(square-root n L) step complexity, opposed to the O(nL) step complexity originally demonstrated for the a...
详细信息
In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve O(square-root n L) step complexity, opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.
The primal projective algorithm for linear programs with unknown optimal objective function value is extended to the case where one uses a weighted Karmarkar potential function. This potential is defined with respect ...
详细信息
The primal projective algorithm for linear programs with unknown optimal objective function value is extended to the case where one uses a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimum. The minimization of this potential when the lower bound is kept fixed, yields a primal and a dual feasible solution. The dual solution is the weighted analytic center of a certain dual polytope. Finally one exhibits a pair of homothetic dual ellipsoids that extends results obtained by Sonnevend, Todd, Ye, Freund and Anstreicher.
Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better sear...
详细信息
Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.
We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasib...
详细信息
We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasible) standard form linear program, without the addition of any “bigM“ terms or conversion to a primal-dual problem.
A path-following, or short-step, version of Karmarkar's algorithm is proposed. When the first term of Karmarkar's potential function is given the weight (n + n(delta)), with delta greater than or equal to 0, t...
详细信息
A path-following, or short-step, version of Karmarkar's algorithm is proposed. When the first term of Karmarkar's potential function is given the weight (n + n(delta)), with delta greater than or equal to 0, the algorithm converges in O(n(max{delta/2,1-delta/2})L) iterations. The best convergence result O(root nL) is achieved for delta = 1. Two proofs of convergence are given: one based on duality gap reductions and the other on potential reductions. The weighted version of the standard projective algorithm is also analyzed. It is interpreted as a max-step algorithm. It is known to converge in at most O((n + n(delta))L) iterations. The reduction of the duality gap when an updating of the lower bound is performed is studied. It is shown to be of a multiplicative factor at most equal to 1 - n(delta)/(n + n(delta))(1 - theta), where 0 < theta < 1 is a fixed parameter in the algorithm. It is deduced from it that the total number of updates of the lower bound in the weighted projective algorithm is at most O(n(1-delta))L) for 0 less than or equal to delta less than or equal to 1.
This paper deals with an application of a variant of Karmarkar's projective algorithm for linear programming to the solution of a generic nondifferentiable minimization problem. This problem is closely related to ...
详细信息
This paper deals with an application of a variant of Karmarkar's projective algorithm for linear programming to the solution of a generic nondifferentiable minimization problem. This problem is closely related to the Dantzig-Wolfe decomposition technique used in large-scale convex programming. The proposed method is based on a column generation technique defining a sequence of primal linear programming maximization problems. Associated with each problem one defines a weighted potential function which is minimized using a variant of the projective algorithm. When a point close to the minimum of the potential function is reached, a corresponding point in the dual space is constructed, which is close to the analytic center of a polytope containing the solution set of the nondifferentiable optimization problem. An admissible cut of the polytope, corresponding to a new supporting hyperplane of the epigraph of the function of minimize, is then generated at this approximate analytic center. In the primal space this new cut translates into a new column for the associated linear programming problem. The algorithm has performed well on a set of convex nondifferentiable programming problems.
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 sequenc...
详细信息
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 polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.
Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. T...
详细信息
Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. This paper examines several search directions in a common framework that does not need any problem transformation. These directions prove to be combinations of two problem-dependent vectors, and can all be improved by a bidirectional search procedure. We conclude that there are essentially two polynomial algorithms: Karmarkar's method and the algorithm that follows a central trajectory, and they differ only in a choice of parameters (respectively lower bound and penalty multiplier).
We propose a path-following version of the Todd-Burrell procedure to solve linear programming problems with an unknown optimal value. The path-following scheme is not restricted to Karmarkar's primal step;it can a...
详细信息
We propose a path-following version of the Todd-Burrell procedure to solve linear programming problems with an unknown optimal value. The path-following scheme is not restricted to Karmarkar's primal step;it can also be implemented with a dual Newton step or with a primal-dual step.
暂无评论