This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinitelinear program, and the dual ...
详细信息
This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinitelinear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinitelinear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinitelinear program and its dual.
In this paper, we analyze a logarithmic barrier decomposition method for solving a semi-infinite linear programming problem. This method is in some respects similar to the column generation methods using analytic cent...
详细信息
In this paper, we analyze a logarithmic barrier decomposition method for solving a semi-infinite linear programming problem. This method is in some respects similar to the column generation methods using analytic centers. Although the method was found to be very efficient in the recent computational studies, its theoretical convergence or complexity is still unknown except in the (finite) case of linearprogramming. In this paper we present a complexity analysis of this method in the general semi-infinite case. Our complexity estimate is given in terms of the problem dimension, the radius of the largest Euclidean ball contained in the feasible set, and the desired accuracy of the approximate solution. (C) 1999 Elsevier Science B.V. and IMACS. All rights reserved.
Abilities of fuzzy models in more adaptations with the real world phenomena causes that in this paper, we remodel semi-infinite linear programming problems as fuzzy problems which contained the crisp objective functio...
详细信息
Abilities of fuzzy models in more adaptations with the real world phenomena causes that in this paper, we remodel semi-infinite linear programming problems as fuzzy problems which contained the crisp objective function and the infinite number of fuzzy constraints. Then, we introduce a new hybrid solution method for these fuzzy semi-infinite linear programming problems. This solution technique is a kind of cutting plane algorithm in which its sub-problems were solved by using the Zimmermann-method. Convergence of the presented algorithm is proved, and some numerical test examples are given and also the obtained results are compared.
Finite-dimensional linear programs satisfy strong duality (SD) and have the "dual pricing" (DP) property. The DP property ensures that, given a sufficiently small perturbation of the right-hand-side vector, ...
详细信息
Finite-dimensional linear programs satisfy strong duality (SD) and have the "dual pricing" (DP) property. The DP property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correctly "prices" the perturbation by computing the exact change in the optimal objective function value. These properties may fail in semi-infinite linear programming where the constraint vector space is infinite dimensional. Unlike the finite-dimensional case, in semi-infinitelinear programs the constraint vector space is a modeling choice. We show that, for a sufficiently restricted vector space, both SD and DP always hold, at the cost of restricting the perturbations to that space. The main goal of the paper is to extend this restricted space to the largest possible constraint space where SD and DP hold. Once SD or DP fail for a given constraint space, then these conditions fail for all larger constraint spaces. We give sufficient conditions for when SD and DP hold in an extended constraint space. Our results require the use of linear functionals that are singular or purely finitely additive and thus not representable as finite support vectors. We use the extension of the Fourier-Motzkin elimination procedure to semi-infinitelinear systems to understand these linear functionals.
We introduce a new approach for the numerical pricing of American options. The main idea is to choose a finite number of suitable excessive functions (randomly) and to find the smallest majorant of the gain function i...
详细信息
We introduce a new approach for the numerical pricing of American options. The main idea is to choose a finite number of suitable excessive functions (randomly) and to find the smallest majorant of the gain function in the span of these functions. The resulting problem is a linearsemi-infiniteprogramming problem, that can be solved using standard algorithms. This leads to good upper bounds for the original problem. For our algorithms no discretization of space and time and no simulation is necessary. Furthermore it is applicable even for high-dimensional problems. The algorithm provides an approximation of the value not only for one starting point, but for the complete value function on the continuation set, so that the optimal exercise region and, for example, the Greeks can be calculated. We apply the algorithm to (one- and) multidimensional diffusions and show it to be fast and accurate.
This paper presents a globally convergent method for solving a general semi-infinite linear programming problem. Some important features of this method include: It can solve a semi-infinitelinear program having an un...
详细信息
This paper presents a globally convergent method for solving a general semi-infinite linear programming problem. Some important features of this method include: It can solve a semi-infinitelinear program having an unbounded feasible region. It requires an inexact solution to a nonlinear subproblem at each iteration. It allows unbounded index sets and nondifferentiable constraints. The amount of work at each iteration k does not increase with k.
We consider the generalization of a variant of Karmarkar's algorithm to semi-infiniteprogramming. The extension of interior point methods to infinite-dimensional linearprogramming is discussed and an algorithm i...
详细信息
We consider the generalization of a variant of Karmarkar's algorithm to semi-infiniteprogramming. The extension of interior point methods to infinite-dimensional linearprogramming is discussed and an algorithm is derived. An implementation of the algorithm for a class of semi-infinitelinear programs is described and the results of a number of test problems are given. We pay particular attention to the problem of Chebyshev approximation. Some further results are given for an implementation of the algorithm applied to a discretization of the semi-infinitelinear program, and a convergence proof is given in this case.
The aim of this work is to generalize strong duality theorems for inexact linearprogramming and to derive duality results for inexact semi-infiniteprogramming problems. We give a detailed proof of the general result...
详细信息
The aim of this work is to generalize strong duality theorems for inexact linearprogramming and to derive duality results for inexact semi-infiniteprogramming problems. We give a detailed proof of the general result, using the Dubovitskii-Milyutin approach. The last section contains applications to inexact problems and a few comments for further developments.
We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on t...
详细信息
We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find anε-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good anε-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding anε-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinearsemi-infiniteprogramming problems. Applications to convex programming are discussed.
This paper extends product mix/linearprogramming based problem with an infinite number of product types for decisions. The corresponding model becomes a class of semi-infinite linear programming model. With the probl...
详细信息
This paper extends product mix/linearprogramming based problem with an infinite number of product types for decisions. The corresponding model becomes a class of semi-infinite linear programming model. With the problem assumptions, the optimal solution can still be theoretically solved using the Simplex based method. To handle the infinite number of decision variables, a set of finite number of variables can be initially generated and then solved and improve sequentially using the classical column generation approach. The proposed procedure was programmed as a MATLAB code and was tested. The computational results are reported.
暂无评论