检索结果-内蒙古大学图书馆

ACCELERATION ON ADAPTIVE IMPORTANCE SAMPLING WITH sample average approximation

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2017年第4期39卷 A1586-A1615页

作者： Kawai, Reiichiro Univ Sydney Sch Math & Stat Sydney NSW 2006 Australia

We construct and analyze acceleration techniques for adaptive Monte Carlo simulations for general multivariate probability laws when the sample average approximation is employed for optimal parameter search. Our goal is to accelerate the adaptive Monte Carlo estimation by leading the parameter search line based on the sample average approximation to reach a nearly optimal realm at its small sample size stage. First, we introduce an auxiliary parameter into the parameter search line and update it wisely to aim for small-sample convergence. All three lines of the algorithm (the Monte Carlo averaging, the importance sampling parameter search, and the auxiliary parameter updating) run concurrently in a fully automated manner with a common set of random vectors without ad hoc tuning of the simulation system. We next propose and examine various criteria for the auxiliary parameter updating, all under which the asymptotic normality of the estimator of the desired mean and of the importance sampling parameter hold true. To illustrate the applicability and effectiveness of the proposed methods, we provide numerical results throughout the paper with particular attention toward the very early stages of the algorithm. In particular, direct use of the importance sampling parameter as the auxiliary parameter has the great potential to accelerate the parameter search line, and thus the Monte Carlo averaging as a consequence, by orders of magnitude without further restriction of the parameter domain or additional computing effort.

关键词： central limit theorem exponential family importance sampling small sample sizes sample average approximation variance reduction

来源：评论

学校读者我要写书评

暂无评论

Smoothing sample average approximation method for solving stochastic second-order-cone complementarity problems

引用

JOURNAL OF INEQUALITIES AND APPLICATIONS 2018年第1期2018卷 77-77页

作者： Luo, Meiju Zhang, Yan Liaoning Univ Sch Math Shenyang Liaoning Peoples R China

In this paper, we consider stochastic second-order-cone complementarity problems (SSOCCP). We first use the so-called second-order-cone complementarity function to present an expected residual minimization (ERM) model for giving reasonable solutions of SSOCCP. Then, we introduce a smoothing function, by which we obtain a smoothing approximate ERM model. We further show that the global solution sequence and weak stationary point sequence of this smoothing approximate ERM model converge to the global solution and the weak stationary point of the original ERM model as the smoothing parameter tends to zero respectively. Moreover, since the ERM formulation contains an expectation, we employ a sample average approximate method for solving the smoothing ERM model. As the convergence analysis, we first show that the global optimal solution of this smoothing sample average approximate problem converges to the global optimal solution of the ERM problem with probability one. Subsequently, we consider the weak stationary points' convergence results of this smoothing sample average approximate problem of ERM model. Finally, some numerical examples are given to explain that the proposed methods are feasible.

关键词： Second-order-cone Stochastic complementarity problems sample average approximation Smoothing function Convergence

来源：评论

学校读者我要写书评

暂无评论

An inexact sample average approximation approach for the stochastic connected facility location problem

引用

NETWORKS 2017年第1期70卷 19-33页

作者： Bardossy, M. Gisela Raghavan, S. Univ Baltimore Merrick Sch Business 1420 N Charles St Baltimore MD 21201 USA Univ Maryland Smith Sch Business College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA

The sample average approximation (SAA) approach is a widely used technique, based on Monte-Carlo simulation, often applied to large-scale stochastic optimization problems. In this approach, a set of sample average problems with multiple copies of sampled scenarios are generated and solved exactly. In other words, there is an implicit assumption that the sample average problems are solvable to optimality. In some instances, however, the sample average problems might be NP-hard problems, often difficult or impractical to solve to optimality. In this article, we broaden the scope of the SAA approach and show that even without solving the sample problems to optimality, by combining a heuristic and a lower bounding approach, high-quality solutions with tight confidence bounds on the optimal solution value can be obtained. We demonstrate this inexact SAA approach on two problems. First, we apply it to the Stochastic Connected Facility Location (SConFL) problem, the motivating application for this article, that arises in the design of telecommunications networks. As an additional application, we also use it for the Stochastic Uncapacitated Facility Location (SUFL) problem. Our computational results demonstrate the effectiveness of the inexact SAA approach. (c) 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 19-33 2017

关键词： heuristics network design network optimization stochastic optimization connected facility location problem uncapacitated facility location problem sample average approximation

来源：评论

学校读者我要写书评

暂无评论

Expected Value and sample average approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

引用

NUMERICAL FUNCTIONAL ANALYSIS AND OPTIMIZATION 2017年第7期38卷 911-925页

作者： Luo, Mei-Ju Zhang, Yan Li, Ya-Jie Liaoning Univ Sch Math Liaoning 110036 Peoples R China

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.

关键词： Convergence sample average approximation second-order cone smoothing function stochastic complementarity problems 90C33 65K05 90C15

来源：评论

学校读者我要写书评

暂无评论

Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables

引用

APPLIED MATHEMATICAL MODELLING 2017年 41卷 582-595页

作者： Bidhandi, Hadi Mohammadi Patrick, Jonathan Islamic Azad Univ South Tehran Branch Fac Ind Engn Tehran Iran Univ Ottawa Telfer Sch Management Ottawa ON K1N 6N5 Canada

This paper proposes an accelerated solution method to solve two-stage stochastic programming problems with binary variables in the first stage and continuous variables in the second stage. To develop the solution method, an accelerated sample average approximation approach is combined with an accelerated Benders' decomposition algorithm. The accelerated sample average approximation approach improves the main structure of the original technique through the reduction in the number of mixed integer programming problems that need to be solved. Furthermore, the recently accelerated Benders' decomposition approach is utilized to expedite the solution time of the mixed integer programming problems. In order to examine the performance of the proposed solution method, the computational experiments are performed on developed stochastic supply chain network design problems. The computational results show that the accelerated solution method solves these problems efficiently. The synergy of the two accelerated approaches improves the computational procedure by an average factor of over 42%, and over 12% in comparison with the original and the recently modified methods, respectively. Moreover, the betterment of the computational process increases substantially with the size of the problem. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Two-stage stochastic programming sample average approximation Mixed integer linear programming Benders' decomposition Supply chain network design

来源：评论

学校读者我要写书评

暂无评论

A capacitated bike sharing location-allocation problem under demand uncertainty using sample average approximation: A greedy genetic-particle swarm optimization algorithm

引用

SCIENTIA IRANICA 2017年第5期24卷 2567-2580页

作者： Ali-Askari, E. Bashiri, M. Tavakkoli-Moghaddam, R. Shahed Univ Dept Ind Engn Fac Engn Tehran Iran Univ Tehran Sch Ind Engn Coll Engn Tehran Iran

This paper considers a stochastic location-allocation problem for a capacitated bike sharing system (S-L&A-CBSS), in which bike demand is uncertain. To tackle this uncertainty, a sample average approximation (SAA) method is used. Because this problem is an NP-hard problem, a hybrid greedy/evolutionary algorithm based on Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), namely greedy GA-PSO, is embedded in the SAA method in order to solve the given large-sized problems. The performance of the proposed hybrid algorithm is tested by a number of numerical examples and used for empirical test based on Tehran business zone. Furthermore, the associated results show its efficiency in comparison to an exact solution method in solving small-sized problems. Finally, the conclusion is provided. (C) 2017 Sharif University of Technology. All rights reserved.

关键词： Bike sharing systems Stochastic programming Hybrid evolutionary algorithm sample average approximation

来源：评论

学校读者我要写书评

暂无评论

On sample average approximation algorithms for determining the optimal importance sampling parameters in pricing financial derivatives on Levy processes

引用

OPERATIONS RESEARCH LETTERS 2016年第1期44卷 44-49页

作者： Jiang, Guangxin Xu, Chenglong Fu, Michael C. City Univ Hong Kong Dept Econ & Finance Kowloon Hong Kong Peoples R China Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA Tongji Univ Dept Math Shanghai 200092 Peoples R China

We formulate the problem of determining the optimal importance sampling measure change for pricing financial derivatives under Levy processes as a parametric optimization problem, and propose a solution approach using sample average approximation (SAA) with Newton iteration to find the optimal parameters in the Esscher probability measure change. Theoretical results, such as convergence rate of the optimal solutions, are provided. A numerical example illustrates the effectiveness of the approach. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Importance sampling sample average approximation Newton iteration Infinitesimal perturbation analysis Levy processes

来源：评论

学校读者我要写书评

暂无评论

An enhanced sample average approximation method for stochastic optimization

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2016年 182卷 230-252页

作者： Emelogu, Adindu Chowdhury, Sudipta Marufuzzaman, Mohammad Bian, Linkan Eksioglu, Burak Mississippi State Univ Dept Ind & Syst Engn Starkville MS 39759 USA Clemson Univ Dept Ind Engn Clemson SC 29634 USA

Choosing the appropriate sample size in sample average approximation (SAA) method is very challenging. Inappropriate sample size can lead to the generation of low quality solutions with high computational burden. To overcome this challenge, our study proposes an enhanced SAA algorithm that utilizes clustering techniques to dynamically update the sample sizes and offers high quality solutions in a reasonable amount of time. We evaluate this proposed algorithm in the context of a facility location problem [FLP]. A number of numerical experiments (e.g., impact of different clustering techniques, fixed vs. dynamic clusters) are performed for various problem instances to illustrate the effectiveness of the proposed method. Results indicate that on average, enhanced SAA with fixed clustering size and dynamic clustering size solves [FLP] almost 631% and 699% faster than the basic SAA algorithm, respectively. Furthermore, it is observed that there is no single winner among the clustering techniques to solve all the problem instances of enhanced SAA algorithm and the performance is highly impacted by the size of the problems. (C) 2016 Elsevier B.V. All rights reserved.

关键词： sample average approximation K-means K-means plus K-meansll Fuzzy C-means Facility location problem Scenario clustering

来源：评论

学校读者我要写书评

暂无评论

Penalized sample average approximation methods for stochastic programs in economic and secure dispatch of a power system

引用

COMPUTATIONAL MANAGEMENT SCIENCE 2016年第3期13卷 393-422页

作者： Tong, X. J. Xu, H. Wu, F. F. Zhao, Z. Hunan First Normal Univ Dept Math Changsha 410205 Hunan Peoples R China Univ Southampton Sch Math Southampton SO17 1BJ Hants England Univ Hong Kong Dept Elect & Elect Engn Pok Fu Lam Hong Kong Peoples R China Hunan Prov Key Lab Smart Grids Operat Changsha 410114 Hunan Peoples R China

In this paper, we develop a stochastic programming model for economic dispatch of a power system with operational reliability and risk control constraints. By defining a severity-index function, we propose to use conditional value-at-risk (CVaR) for measuring the reliability and risk control of the system. The economic dispatch is subsequently formulated as a stochastic program with CVaR constraint. To solve the stochastic optimization model, we propose a penalized sample average approximation (SAA) scheme which incorporates specific features of smoothing technique and level function method. Under some moderate conditions, we demonstrate that with probability approaching to 1 at an exponential rate with the increase of sample size, the optimal solution of the smoothing SAA problem converges to its true counterpart. Numerical tests have been carried out for a standard IEEE-30 DC power system.

关键词： Stochastic programming Economic dispatch Conditional value-at-risk sample average approximation Level function method

来源：评论

学校读者我要写书评

暂无评论

sample average approximation under non-i.i.d. sampling for stochastic empty container repositioning problem

引用

OR SPECTRUM 2015年第2期37卷 389-405页

作者： Long, Yin Chew, Ek Peng Lee, Loo Hay Natl Univ Singapore Dept Ind & Syst Engn Singapore 117548 Singapore

The stochastic empty container repositioning (ECR) problem can be solved by the sample average approximation (SAA) method, in which a sample of random scenarios are generated and then deterministic optimization techniques can be applied to solve the problem based on this sample. Considering the scale of SAA problem with multiple scenarios and the large number of random parameters in the ECR problem, we propose a design which combines Latin hypercube design and supersaturated design, which is able to get a satisfying approximation by using only a few scenarios. The impact of several non-independent and identical distribution (i.i.d). sampling methods for the stochastic ECR problem has been computationally examined. It is shown that all these non-i.i.d. sampling methods in consideration could help to enhance the performance of the SAA method for the stochastic ECR problem. Moreover, by using the proposed sampling method, it is less probable to provide bad solutions and the bias of the expected objective value of the sampled problem could also be reduced.

关键词： Empty container repositioning sample average approximation Stochastic optimization Non-i.i.d. sampling Supersaturated design

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：