共查询到20条相似文献,搜索用时 31 毫秒
1.
This paper considers several probability maximization models for multi-scenario portfolio selection problems in the case that
future returns in possible scenarios are multi-dimensional random variables. In order to consider occurrence probabilities
and decision makers’ predictions with respect to all scenarios, a portfolio selection problem setting a weight with flexibility
to each scenario is proposed. Furthermore, by introducing aspiration levels to occurrence probabilities or future target profit
and maximizing the minimum aspiration level, a robust portfolio selection problem is considered. Since these problems are
formulated as stochastic programming problems due to the inclusion of random variables, they are transformed into deterministic
equivalent problems introducing chance constraints based on the stochastic programming approach. Then, using a relation between
the variance and absolute deviation of random variables, our proposed models are transformed into linear programming problems
and efficient solution methods are developed to obtain the global optimal solution. Furthermore, a numerical example of a
portfolio selection problem is provided to compare our proposed models with the basic model. 相似文献
2.
Horand I. Gassmann 《Mathematical Programming》1990,47(1-3):407-423
This paper describes an efficient implementation of a nested decomposition algorithm for the multistage stochastic linear programming problem. Many of the computational tricks developed for deterministic staircase problems are adapted to the stochastic setting and their effect on computation times is investigated. The computer code supports an arbitrary number of time periods and various types of random structures for the input data. Numerical results compare the performance of the algorithm to MINOS 5.0. 相似文献
3.
Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in
mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these
individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong
decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between
the objective function value for the solution and the objective function value for the optimal solution for each scenario,
while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per
scenario plus coupling constraints.
Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition
and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational
results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation
and a parallel implementation on a network of three workstations. 相似文献
4.
We consider distributionally robust two-stage stochastic convex programming problems, in which the recourse problem is linear. Other than analyzing these new models case by case for different ambiguity sets, we adopt a unified form of ambiguity sets proposed by Wiesemann, Kuhn and Sim, and extend their analysis from a single stochastic constraint to the two-stage stochastic programming setting. It is shown that under a standard set of regularity conditions, this class of problems can be converted to a conic optimization problem. Numerical results are presented to show the efficiency of the distributionally robust approach. 相似文献
5.
Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time. 相似文献
6.
《European Journal of Operational Research》1997,101(2):317-327
The application of interior point methods (IPM) to solve the deterministic equivalent of two-stage stochastic linear programming problems is a known and natural idea. Experiments have proved that among the interior point methods, the augmented system approach gives the best performance on these problems. However, most of their implementations encounter numerical difficulties in certain cases, which can result in loss of efficiency. We present a new approach for the decomposition of the augmented system, which ‘automatically’ exploits the special behavior of the problems. We show that the suggested approach can be implemented in a fast and numerically robust way by solving a number of large-scale two-stage stochastic linear programming problems. The comparison of our solver with fo1aug, which is considered as a state-of-the-art augmented system implementation of interior point methods, is also given. 相似文献
7.
Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver. 相似文献
8.
We develop a new modeling and solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations for the studied stochastic problem, and we derive a set of strengthening valid inequalities. A crucial feature of the new integer formulations is that the number of integer variables does not depend on the number of scenarios used to represent uncertainty. The computational study, based on instances of the stochastic capital rationing problem, shows that the mixed-integer linear programming formulations are orders of magnitude faster to solve than the mixed-integer nonlinear programming formulation. The method integrating the valid inequalities in a branch-and-bound algorithm has the best performance. 相似文献
9.
A. Beck 《Journal of Optimization Theory and Applications》2009,142(1):1-29
We establish several convexity results which are concerned with nonconvex quadratic matrix (QM) functions: strong duality
of quadratic matrix programming problems, convexity of the image of mappings comprised of several QM functions and existence
of a corresponding S-lemma. As a consequence of our results, we prove that a class of quadratic problems involving several
functions with similar matrix terms has a zero duality gap. We present applications to robust optimization, to solution of
linear systems immune to implementation errors and to the problem of computing the Chebyshev center of an intersection of
balls.
This research was partially supported by the Israel Science Foundation under Grant ISF 489/06. 相似文献
10.
In this paper, we introduce a mixed integer stochastic programming approach to mean–variance post-tax portfolio management. This approach takes into account of risk in a multistage setting and allows general withdrawals from original capital. The uncertainty on asset returns is specified as a scenario tree. The risk across scenarios is addressed using the probabilistic approach of classical stochastic programming. The tax rules are used with stochastic linear and mixed integer quadratic programming models to compute an overall tax and return-risk efficient multistage portfolio. The incorporation of the risk term in the model provides robustness and leads to diversification over wrappers and assets within each wrapper. General withdrawals and risk aversion have an impact on the distribution of assets among wrappers. Computational results are presented using a study with different scenario trees in order to show the performance of these models. 相似文献
11.
The subject of this paper is to study a realistic planning environment in wafer fabrication for the control or dummy (C/D) wafers problem with uncertain demand. The demand of each product is assumed with a geometric Brownian motion and approximated by a finite discrete set of scenarios. A two‐stage stochastic programming model is developed based on scenarios and solved by a deterministic equivalent large linear programming model. The model explicitly considers the objective to minimize the total cost of C/D wafers. A real‐world example is given to illustrate the practicality of a stochastic approach. The results are better in comparison with deterministic linear programming by using expectation instead of stochastic demands. The model improved the performance of control and dummy wafers management and the flexibility of determining the downgrading policy. Copyright © 2008 John Wiley & Sons, Ltd. 相似文献
12.
Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally
cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the
uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting
the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an efficient method
to estimate the approximation error introduced by this rather drastic means of complexity reduction: we apply the linear decision
rule restriction not only to the primal but also to a dual version of the stochastic program. By employing techniques that
are commonly used in modern robust optimization, we show that both arising approximate problems are equivalent to tractable
linear or semidefinite programs of moderate sizes. The gap between their optimal values estimates the loss of optimality incurred
by the linear decision rule approximation. Our method remains applicable if the stochastic program has random recourse and
multiple decision stages. It also extends to cases involving ambiguous probability distributions. 相似文献
13.
We consider stochastic optimization problems involving stochastic dominance constraints. We develop portfolio optimization model involving stochastic dominance constrains using fuzzy decisions and we concentrate on fuzzy linear programming problems with only fuzzy technological coefficients and aplication/implementation of modified subgradient method to fuzy linear programming problems. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
14.
We discuss convex optimization problems in which some of the variables are constrained to be finite autocorrelation sequences.
Problems of this form arise in signal processing and communications, and we describe applications in filter design and system
identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding
power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities
via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization
problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback:
to represent an autocorrelation sequence of length $n$, it requires the introduction of a large number ($n(n+1)/2$) of auxiliary
variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present
a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear
inequalities.
Received: August 20, 2001 / Accepted: July 16, 2002 Published online: September 27, 2002
RID="★"
ID="★" This material is based upon work supported by the National Science Foundation under Grant No. ECS-9733450. 相似文献
15.
《European Journal of Operational Research》1986,26(1):65-82
In the field of investment planning within a time horizon, problems typically involve multiple objectives, and basic data are uncertain. In a large number of cases, these decision problems can be written as linear programming problems in which time dependent uncertainties affect the coefficients and the right hand side of constraints. Given the possibility of defining plausible scenarios on basic data, discrete sets of such coefficients are given, each with its subjective probability of occurrence. The corresponding structure is then characteristic for Multi-Objective Stochastic Linear Programming (MOSLP).In the paper, an interactive procedure is described to obtain a best compromise for such a MOSLP problem. This algorithm, called Strange, extends the Stem method to take the random aspects into account. It involves in particular, the concepts of stochastic programming with recourse. In its interactive steps, the efficiency projection techniques are used to provide the decision-maker with detailed graphical information on efficient solution families.As an illustration of the successive steps, a didactic example is solved in some detail, and the results of a case study in energy planning are given. 相似文献
16.
Emmanuel Fragnière Jacek Gondzio Jean-Philippe Vial 《Annals of Operations Research》2000,99(1-4):167-187
We present an integrated procedure to build and solve big stochastic programming models. The individual components of the system – the modeling language, the solver and the hardware – are easily accessible, or a least affordable to a large audience. The procedure is applied to a simple financial model, which can be expanded to arbitrarily large sizes by enlarging the number of scenarios. We generated a model with one million scenarios, whose deterministic equivalent linear program has 1,111,112 constraints and 2,555,556 variables. We have been able to solve it on the cluster of ten PCs in less than 3 hours. 相似文献
17.
Miles Lubin J. A. Julian Hall Cosmin G. Petra Mihai Anitescu 《Computational Optimization and Applications》2013,55(3):571-596
We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates. 相似文献
18.
Many practical large-scale optimization problems are not only sparse, but also display some form of block-structure such as
primal or dual block angular structure. Often these structures are nested: each block of the coarse top level structure is
block-structured itself. Problems with these characteristics appear frequently in stochastic programming but also in other
areas such as telecommunication network modelling.
We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver
for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested
block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing
to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation
of the linear algebra.
The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and
liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured
problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs.
A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies
its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation
of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over
2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves
nearly perfect speed-ups on a range of problems.
Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/R99683/01 相似文献
19.
A two-stage stochastic programming with recourse model for determining robust planting plans in horticulture 总被引:1,自引:0,他引:1
K Darby-Dowman S Barker E Audsley D Parsons 《The Journal of the Operational Research Society》2000,51(1):83-89
A two-stage stochastic programming with recourse model for the problem of determining optimal planting plans for a vegetable crop is presented in this paper. Uncertainty caused by factors such as weather on yields is a major influence on many systems arising in horticulture. Traditional linear programming models are generally unsatisfactory in dealing with the uncertainty and produce solutions that are considered to involve an unacceptable level of risk. The first stage of the model relates to finding a planting plan which is common to all scenarios and the second stage is concerned with deriving a harvesting schedule for each scenario. Solutions are obtained for a range of risk aversion factors that not only result in greater expected profit compared to the corresponding deterministic model, but also are more robust. 相似文献
20.
In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm. 相似文献