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

decomposition algorithms for Some Deterministic and Two-Stage Stochastic Single-Leader Multi-Follower Games

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2021年第3期78卷 675-704页

作者： Borges, Pedro Sagastizabal, Claudia Solodov, Mikhail Inst Matematica Pura & Aplicada Rio De Janeiro RJ Brazil Univ Estadual Campinas IMECC Campinas SP Brazil

We consider a certain class of hierarchical decision problems that can be viewed as single-leader multi-follower games, and be represented by a virtual market coordinator trying to set a price system for traded goods, according to some criterion that balances supply and demand. The objective function of the market coordinator involves the decisions of many agents, which are taken independently by solving convex optimization problems that depend on the price configuration and on realizations of future states of the economy. One traditional way of solving this problem is via a mixed complementarity formulation. However, this approach can become impractical when the numbers of agents and/or scenarios become large. This work concerns agent-wise and scenario-wise decomposition algorithms to solve the equilibrium problems in question, assuming that the solutions of the agents' problems are unique, which is natural in many applications (when solutions are not unique, the approximating problems are still well-defined, but the convergence properties of the algorithm are not established). The algorithm is based on a previous work of the authors, where a suitable regularization of solution mappings of fully parameterized convex problems is developed. Here, we show one specific strategy to manage the regularization parameter, extend some theoretical results to the current setting, and prove that the smooth approximations of the market coordinator's problem converge epigraphically to the original problem. Numerical experiments and some comparisons with the complementarity solver PATH are shown for the two-stage stochastic Walrasian equilibrium problem.

关键词： Stochastic equilibrium decomposition algorithms Bilevel optimization Smoothing methods Interior penalty methods Tikhonov regularization

来源：评论

学校读者我要写书评

暂无评论

decomposition algorithms for Market Clearing With Large-Scale Demand Response

引用

IEEE TRANSACTIONS ON SMART GRID 2013年第4期4卷 1976-1987页

作者： Gatsis, Nikolaos Giannakis, Georgios B. Univ Minnesota Digital Technol Ctr Minneapolis MN 55455 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN USA

This paper is concerned with large-scale integration of demand response (DR) from small loads such as residential smart appliances into modern electricity systems. These appliances have intertemporal consumption constraints, while the satisfaction of the end-user from operating them is captured through utility functions. Incorporation of the appliance scheduling flexibility and user satisfaction in the system optimization points to maximizing the social welfare. In order to solve the resultant very large optimization problem with manageable complexity, dual decomposition is pursued. The problem decouples into separate subproblems for the market operator and each aggregator. Each aggregator addresses its local optimization aided by the end-users' smart meters. The subproblems are coordinated with carefully designed information exchanges between the market operator and the aggregators so that user privacy is preserved. Numerical tests illustrate the benefits of large-scale DR incorporation.

关键词： Aggregators decomposition algorithms demand response demand-side management pricing

来源：评论

学校读者我要写书评

暂无评论

decomposition algorithms FOR LOCATING MINIMAL CUTS IN A NETWORK

引用

MATHEMATICAL PROGRAMMING 1982年第3期22卷 316-331页

作者： JARVIS, JJ TUFEKCI, S SYRACUSE UNIV DEPT IND ENGN & OPERAT RESSYRACUSENY 13210

This paper provides decomposition algorithms for locating minimal cuts in a large directed network. The main theorem provides several cases for the algorithms. In the worst case, it is shown that the efficiency of one of the proposed algorithms is of the same order as a no-decomposition algorithm. As in linear programming, the obvious advantage of the proposed decomposition procedure is its ability to potentially handle larger problems than a no-decomposition algorithm.

关键词： decomposition algorithms Minimal Cut Flow Networks Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

decomposition algorithms and Parallel Computing for Chance-Constrained and Stochastic Integer Programs with Applications

Decomposition Algorithms and Parallel Computing for Chance-C...

引用

作者： Deng, Yan University of Michigan

学位级别：Ph.D.

The focus of this dissertation is to develop solution methods for stochastic programs with binary decisions and risk-averse features such as chance constraint or risk-minimizing objective. We approach these problems through scenario-based reformulations, which are often of intractable scale due to the use of a large number of scenarios to represent the uncertainty. Our goal is to develop specialized decomposition algorithms for solving the problem in reasonable time. We first study a surgery planning problem with uncertainty in surgery durations. A common practice is to first assign operating rooms to surgeries and then to develop schedules. We propose a chance-constrained model that integrates these two steps. A branch-and-cut algorithm is developed, which exploits valid inequalities derived from a bin packing problem and single-machine scheduling problems. We also discuss models and solutions given ambiguous distributional information. Computational results demonstrate the efficacy of the proposed algorithm and provide insights into enhancing performance by the proposed model. Next, we study general chance-constrained 0-1 programs, where decisions made before realization of uncertainty are binary. We develop dual decomposition algorithms that find solutions through bounds and cuts efficiently. We derive a proposition about computing the Lagrangian dual whose application substantially reduces the number of subproblems to solve, and deploy cut aggregation that accelerates the solution of subproblems. We also explore parallel schemes to implement our algorithms in a distributed system. All of them improve the efficacy effectively. We then study dual decomposition for risk-averse stochastic 0-1 programs, which minimize the risk of some random outcome measured by a coherent risk function. Using generic dual representations for coherent risk measures, we derive equivalent risk-neutral minimax reformulations, to which dual decomposition methods apply. We investigate how

关键词： Stochastic integer programming decomposition algorithms Chance-constrained programming Risk-averse stochastic programming Parallel computing Thesis

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time decomposition algorithms for support vector machines

引用

MACHINE LEARNING 2003年第1期51卷 51-71页

作者： Hush, D Scovel, C Los Alamos Natl Lab Los Alamos NM 87545 USA

This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple "rate certifying" condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies root1/2 less than or equal to Cless than or equal to mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC(2)m(4)/epsilon iterations to drive the criterion to within epsilon of its optimum.

关键词： support vector machines polynomial-time algorithms decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving constrained consumption-investment problems by decomposition algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第1期319卷 292-302页

作者： Pagnoncelli, Bernardo K. Homem-de-Mello, Tito Lagos, Guido Castaneda, Pablo Garcia, Javier Univ Cote Azur SKEMA Business Sch Ave Willy Brandt F-59777 Lille France Univ Adolfo Ibanez Sch Business Ave Diagonal Torres 2640 Santiago 7941169 Chile Univ Adolfo Ibanez Fac Engn & Sci Padre Hurtado 750 Vina Del Mar 2340000 Chile ACHS Fac Sci & Engn Ramon Carnicer 163 Santiago Chile

Consumption-investment problems with maximizing utility agents are usually considered from a theoretical viewpoint, aiming at closed-form solutions for the optimal policy. However, such an approach requires that the model be relatively simple: even the inclusion of nonnegativity constraints can prevent the derivation of explicit solutions. In such cases, it is necessary to solve the problem numerically, but standard dynamic programming algorithms can only solve small problems due to the curse of dimensionality. In this paper, we adapt the Stochastic Dual Dynamic Programming (SDDP) algorithm to solve dynamic constrained consumption-investment problems with stochastic labor income numerically. Unlike classical dynamic programming approaches, SDDP allows us to analyze problems with multiple assets, and an internal sampling procedure allows the problems to have a very large, or even infinite, number of scenarios. We start with a simpler problem for which a closed-form solution is known and compare it to the optimal policy obtained by SDDP. We then illustrate the flexibility of our approach by solving a defined contribution pension fund problem with multiple assets, for which no closed-form solution is available.

关键词： Finance Consumption-investment problems Multistage stochastic programming decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

General polynomial time decomposition algorithms

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2007年第2期8卷 303-321页

作者： List, Nikolas Simon, Hans Ulrich Ruhr Univ Bochum Fak Math D-44780 Bochum Germany

We present a general decomposition algorithm that is uniformly applicable to every (suitably normalized) instance of Convex Quadratic Optimization and efficiently approaches an optimal solution. The number of iterations required to be within e of optimality grows linearly with 1/epsilon and quadratically with the number m of variables. The working set selection can be performed in polynomial time. If we restrict our considerations to instances of Convex Quadratic Optimization with at most k(0) equality constraints for some fixed constant k(0) plus some so-called box-constraints (conditions that hold for most variants of SVM-optimization), the working set is found in linear time. Our analysis builds on a generalization of the concept of rate certifying pairs that was introduced by Hush and Scovel. In order to extend their results to arbitrary instances of Convex Quadratic Optimization, we introduce the general notion of a rate certifying q-set. We improve on the results by Hush and Scovel (2003) in several ways. First our result holds for Convex Quadratic Optimization whereas the results by Hush and Scovel are specialized to SVM-optimization. Second, we achieve a higher rate of convergence even for the special case of SVM-optimization (despite the generality of our approach). Third, our analysis is technically simpler. We prove furthermore that the strategy for working set selection which is based on rate certifying sets coincides with a strategy which is based on a so-called "sparse witness of sub-optimality". Viewed from this perspective, our main result improves on convergence results by List and Simon (2004) and Simon (2004) by providing convergence rates (and by holding under more general conditions).

关键词： convex quadratic optimization decomposition algorithms support vector machines

来源：评论

学校读者我要写书评

暂无评论

Feasible direction decomposition algorithms for training support vector machines

引用

MACHINE LEARNING 2002年第1-3期46卷 315-349页

作者： Laskov, P Univ Delaware Dept Comp & Informat Sci Newark DE 19718 USA

The article presents a general view of a class of decomposition algorithms for training Support Vector Machines (SVM) which are motivated by the method of feasible directions. The first such algorithm for the pattern recognition SVM has been proposed in Joachims, T. (1999, Scholkopf et al. (Eds.) Advances in kernel methods-Support vector learning (pp. 185-208). MIT Press). Its extension to the regression SVM-the maximal inconsistency algorithm-has been recently presented by the author (Laskov, 2000, Solla, Leen, & Muller (Eds.) Advances in neural information processing systems 12 (pp. 484-490). MIT Press). A detailed account of both algorithms is carried out, complemented by theoretical investigation of the relationship between the two algorithms. It is proved that the two algorithms are equivalent for the pattern recognition SVM, and the feasible direction interpretation of the maximal inconsistency algorithm is given for the regression SVM. The experimental results demonstrate an order of magnitude decrease of training time in comparison with training without decomposition, and, most importantly, provide experimental evidence of the linear convergence rate of the feasible direction decomposition algorithms.

关键词： support vector machines training decomposition algorithms methods of feasible directions working set selection

来源：评论

学校读者我要写书评

暂无评论

A local convergence analysis of bilevel decomposition algorithms

引用

OPTIMIZATION AND ENGINEERING 2006年第2期7卷 99-133页

作者： DeMiguel, V Murray, W London Business Sch London NW1 4SA England Stanford Univ Stanford CA 94305 USA

Multidisciplinary design optimization (MDO) problems are engineering design problems that require the consideration of the interaction between several design disciplines. Due to the organizational aspects of MDO problems, decomposition algorithms are often the only feasible solution approach. decomposition algorithms reformulate the MDO problem as a set of independent subproblems, one per discipline, and a coordinating master problem. A popular approach to MDO problems is bilevel decomposition algorithms. These algorithms use nonlinear optimization techniques to solve both the master problem and the subproblems. In this paper, we propose two new bilevel decomposition algorithms and analyze their properties. In particular, we show that the proposed problem formulations are mathematically equivalent to the original problem and that the proposed algorithms converge locally at a superlinear rate. Our computational experiments illustrate the numerical performance of the algorithms.

关键词： decomposition algorithms bilevel programming nonlinear programming multidisciplinary design optimization (MDO)

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL EXPERIENCE WITH ADVANCED IMPLEMENTATION OF decomposition algorithms FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1983年第3期27卷 283-290页

作者： HO, JK LOUTE, E FAC UNIV ST LOUIS SMASHB-1000 BRUSSELSBELGIUM CATHOLIC UNIV LOUVAIN COREB-1348 LOUVAIN LA NEUVEBELGIUM

This paper reports computational experience with the codesDecompsx andLift which are built on IBM's MPSX/370 LP software for large-scale structured *** is an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular LP'*** is an implementation of a nested decomposition algorithm for staircase and block-triangular LP's. A diverse collection of test problems drawn from real applications is used to test these codes, including multinational energy models and global economic models.

关键词： Large-Scale Systems decomposition algorithms Structured Linear Programs Optimization Software

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：