Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield va...
详细信息
Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield valuable insight into the behavior of the underlying linear programming algorithm when the number of constraints or the number of variables is very large. In this paper, we study the behavior of the affine-scaling algorithm on a particular semi-infinite linear programming problem. We show that the continuous trajectories converge to the optimal solution but that, for any strictly positive step, there are starting points for which the discrete algorithm converges to nonoptimal boundary points.
This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by s...
详细信息
This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.
Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dua...
详细信息
Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dual problems as long as the step size is no more than two-thirds of the distance to the nearest face of the polytope. An important feature of this result is that it does not require any nondegeneracy assumptions. In this paper we show that Tsuchiya and Muramatsu's result is sharp by providing a simple linear programming problem for which the sequence of dual variables fails to converge for every step size greater than two-thirds.
暂无评论