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

ON THE IMPLEMENTATION OF INTERIOR POINT DECOMPOSITION ALGORITHMS FOR TWO-STAGE STOCHASTIC conic PROGRAMS

SIAM JOURNAL ON OPTIMIZATION 2009年第4期19卷 1846-1880页

作者： Mehrotra, Sanjay Ozevin, M. Gokhan Northwestern Univ Dept Ind Engn & Management Sci Evanston IL 60208 USA ZS Associates Evanston IL 60201 USA

In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in [S. Mehrotra and M. G. Ozevin, "Decomposition based interior point methods for two-stage stochastic convex quadratic programs with recourse," to appear in Oper. Res.;S. Mehrotra;and M. G. Ozevin, SIAM J. Optim., 18 (2007), pp. 206-222] and [G. Zhao, Math. Program., 90 (2001), pp. 507-536], however, their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs the log-barrier terms in the second stage problems differently from the theoretical algorithms analyzed in [S. Mehrotra and M. G. Ozevin, Oper. Res., to appear], [S. Mehrotra and M. G. Ozevin, SIAM J. Optim., 18 (2007), pp. 206-222], and [G. Zhao, Math. Program., 90 (2001), pp. 507-536]. We give a method for generating a suitable starting point;a method for selecting a good starting barrier parameter;a heuristic for first stage step-length calculation without performing line searches;and a method for adaptive addition of new scenarios over the course of the algorithm. The decomposition algorithm is implemented to solve two-stage stochastic conic programs with recourse whose underlying cones are Cartesian products of linear, second order, and semidefinite cones. The performance of primal decomposition method is studied on a set of randomly generated test problems as well as a two-stage stochastic programming extension of the Markowitz portfolio selection model. The computational results show that an efficient and stable implementation of the primal decomposition method is possible. These results also show that in problems with a large number of scenarios, the adaptive addition of scenarios can yield computational savings of up to 80%.

关键词： stochastic programming conic programming semidefinite programming Benders decomposition interior point methods primal-dual methods

来源：评论

学校读者我要写书评

暂无评论

Robust sample average approximation

引用

MATHEMATICAL programming 2018年第1-2期171卷 217-282页

作者： Bertsimas, Dimitris Gupta, Vishal Kallus, Nathan MIT Sloan Sch Management Cambridge MA 02139 USA Univ Southern Calif Marshall Sch Business Los Angeles CA 90029 USA Cornell Univ Sch Operat Res & Informat Engn New York NY 10011 USA Cornell Univ Cornell Tech New York NY 10011 USA

Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to our method is linking SAA, distributionally robust optimization, and hypothesis testing of goodness-of-fit. Beyond Robust SAA, this connection provides a unified perspective enabling us to characterize the finite sample and asymptotic guarantees of various other data-driven procedures that are based upon distributionally robust optimization. This analysis provides insight into the practical performance of these various methods in real applications. We present examples from inventory management and portfolio allocation, and demonstrate numerically that our approach outperforms other data-driven approaches in these applications.

关键词： Sample average approximation of stochastic optimization Data-driven optimization Goodness-of-fit testing Distributionally robust optimization conic programming Inventory management Portfolio allocation

来源：评论

学校读者我要写书评

暂无评论

Exact approaches for competitive facility location with discrete attractiveness

引用

OPTIMIZATION LETTERS 2021年第2期15卷 377-389页

作者： Lin, Yun Hui Tian, Qingyun Natl Univ Singapore Dept Ind Syst Engn & Management Singapore Singapore Nanyang Technol Univ Sch Civil & Environm Engn Singapore Singapore

We study a variant of the competitive facility location problem, in which a company is to locate new facilities in a market where competitor's facilities already exist. We consider the scenario where only a limited number of possible attractiveness levels is available, and the company has to select exactly one level for each open facility. The goal is to decide the facilities' locations and attractiveness levels that maximize the profit. We apply the gravity-based rule to model the behavior of the customers and formulate a multi-ratio linear fractional 0-1 program. Our main contributions are the exact solution approaches for the problem. These approaches allow for easy implementations without the need for designing complicated algorithms and are "friendly" to the users without a solid mathematical background. We conduct computational experiments on the randomly generated datasets to assess their computational performance. The results suggest that the mixed-integer quadratic conic approach outperforms the others in terms of computational time. Besides that, it is also the most straightforward one that only requires the users to be familiar with the general form of a conic quadratic inequality. Therefore, we recommend it as the primary choice for such a problem.

关键词： Competitive facility location Gravity model conic programming Outer approximation Mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A DATA-INDEPENDENT DISTANCE TO INFEASIBILITY FOR LINEAR conic SYSTEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第2期30卷 1049-1066页

作者： Pena, Javier Roshchina, Vera Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Univ South Wales Sch Math & Stat Sydney NSW 2052 Australia

We offer a unified treatment of distinct measures of well-posedness for homogeneous conic systems. To that end, we introduce a distance to infeasibility based entirely on geometric considerations of the elements defining the conic system. Our approach sheds new light on and connects several well-known condition measures for conic systems, including Renegar's distance to infeasibility, the Grassmannian condition measure, a measure of the most interior solution, and other geometric measures of symmetry and of depth of the conic system.

关键词： condition number conic programming distance to infeasibility convex duality

来源：评论

学校读者我要写书评

暂无评论

Constrained multi-location assortment optimization under the multinomial logit model

引用

NAVAL RESEARCH LOGISTICS 2023年第7期70卷 653-674页

作者： Bebitoglu, Basak Sen, Alper Kaminsky, Philip London Business Sch Dept Management Sci & Operat London England Bilkent Univ Bilkent Dept Ind Engn Ankara Turkiye Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA USA Amazon Santa Clara CA USA Bilkent Univ Bilkent Dept Ind Engn TR-06800 Ankara Turkiye

We study the assortment optimization problem in an online setting where a retailer uses multiple distribution centers (DC) to fulfill orders from multiple regions. Customer choice in each region follows a multinomial logit model. Each DC can carry up to a pre-specified number of products. Outbound shipping cost to a region depends on the DC that ships the order. The problem is to determine which products to carry in each DC and which products to offer for sale in each region to maximize the expected profit. We first show that the problem is NP-complete. We develop a conic quadratic mixed integer programming formulation and suggest a family of valid inequalities. We also show that a special case with identical choice models can be solved as a linear program. This LP solution approach can be used to develop heuristics for the general case. Numerical experiments show that our conic approach outperforms the mixed integer linear programming formulation and enables us to solve moderately sized instances optimally. The experiments also show that not allowing cross-shipments or not considering them in assortment decisions may lead to substantial losses and LP-based heuristics can be effective in practice.

关键词： conic programming multi-location assortment optimization multinomial logit online retailing

来源：评论

学校读者我要写书评

暂无评论

SAA method based on modified Newton method for stochastic variational inequality with second-order cone constraints and application in portfolio optimization

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2016年第1期84卷 129-154页

作者： Chen, Shuang Pang, Li-Ping Ma, Xue-Fei Li, Dan Dalian Univ Informat & Engn Coll Dalian Peoples R China Dalian Univ Technol Sch Math Sci Dalian Peoples R China Syracuse Univ Dept Math Syracuse NY 13244 USA

In this paper we apply modified Newton method based on sample average approximation (SAA) to solve stochastic variational inequality with stochastic second-order cone constraints (SSOCCVI). Under some moderate conditions, the SAA solution converges to its true counterpart with probability approaching one at exponential rate as sample size increases. We apply the theoretical results for solving a class of stochastic second order cone complementarity problems and stochastic programming problems with stochastic second order cone constraints. Some illustrative examples are given to show how the globally convergent method works and the comparison results between our method and other methods. Furthermore, we apply this method to portfolio optimization with loss risk constraints problems.

关键词： Stochastic variational inequality problem Stochastic programming conic programming Portfolio optimization

来源：评论

学校读者我要写书评

暂无评论

On distributional robust probability functions and their computations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第1期233卷 23-33页

作者： Wong, Man Hong Zhang, Shuzhong Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Univ Minnesota Dept Ind & Syst Engn Minneapolis MN 55455 USA

Consider a random vector, and assume that a set of its moments information is known. Among all possible distributions obeying the given moments constraints, the envelope of the probability distribution functions is introduced in this paper as distributional robust probability function. We show that such a function is computable in the bi-variate case under some conditions. Connections to the existing results in the literature and its applications in risk management are discussed as well. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Risk management Distributional robust Moment bounds Semidefinite programming (SDP) conic programming

来源：评论

学校读者我要写书评

暂无评论

Cutting plane algorithms for robust conic convex optimization problems

引用

OPTIMIZATION METHODS & SOFTWARE 2006年第5期21卷 779-803页

作者： Gomez, J. A. Gomez, W. Univ Concepcion Dept Ingn Matemat Concepcion Chile Univ La Frontera Dept Ingn Matemat Temuco Chile

In this paper, we study some well-known cases of nonlinear programming problems, presenting them as instances of inexact or semi-infinite linear programming. The class of problems considered contains, in particular, semi-definite programming, second-order cone programming and special cases of inexact semi-definite programming. Strong duality results for the nonlinear problems studied are obtained via the Lagrangian duality. Using these results, we propose some dual algorithms for the studied classes of problems. The proposed algorithms can be interpreted as cutting plane or discretization algorithms. Finally, some comments on the convergence of the proposed algorithms and on preliminary numerical tests are given.

关键词： semi-infinite linear programming cutting plane algorithms conic programming

来源：评论

学校读者我要写书评

暂无评论

Solution refinement at regular points of conic problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2019年第3期74卷 627-643页

作者： Busseti, Enzo Moursi, Walaa M. Boyd, Stephen Stanford Univ Dept Elect Engn 350 Serra Mall Stanford CA 94305 USA Mansoura Univ Dept Math Fac Sci Mansoura 35516 Egypt

Many numerical methods for conic problems use the homogenous primal-dual embedding, which yields a primal-dual solution or a certificate establishing primal or dual infeasibility. Following Themelis and Patrinos (IEEE Trans Autom Control, 2019), we express the embedding as the problem of finding a zero of a mapping containing a skew-symmetric linear function and projections onto cones and their duals. We focus on the special case when this mapping is regular, i.e., differentiable with nonsingular derivative matrix, at a solution point. While this is not always the case, it is a very common occurrence in practice. In this paper we do not aim for new theorerical results. We rather propose a simple method that uses LSQR, a variant of conjugate gradients for least squares problems, and the derivative of the residual mapping to refine an approximate solution, i.e., to increase its accuracy. LSQR is a matrix-free method, i.e., requires only the evaluation of the derivative mapping and its adjoint, and so avoids forming or storing large matrices, which makes it efficient even for cone problems in which the data matrices are given and dense, and also allows the method to extend to cone programs in which the data are given as abstract linear operators. Numerical examples show that the method improves an approximate solution of a conic program, and often dramatically, at a computational cost that is typically small compared to the cost of obtaining the original approximate solution. For completeness we describe methods for computing the derivative of the projection onto the cones commonly used in practice: nonnegative, second-order, semidefinite, and exponential cones. The paper is accompanied by an open source implementation.

关键词： conic programming Homogenous self-dual embedding Projection operator Residual map

来源：评论

学校读者我要写书评

暂无评论

Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第1期229卷 21-28页

作者： Deng, Zhibin Fang, Shu-Cherng Jin, Qingwei Xing, Wenxun N Carolina State Univ Edward P Fitts Dept Ind & Syst Engn Raleigh NC 27695 USA Zhejiang Univ Dept Management Sci & Engn Hangzhou 310058 Zhejiang Peoples R China Tsinghua Univ Dept Math Sci Beijing 100084 Peoples R China

It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix. (C) 2013 Elsevier B.V. All rights reserved.

关键词： conic programming Copositive Cone of nonnegative quadratic functions Adaptive approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：