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

ASYMPTOTIC RESULTS OF STOCHASTIC decomposition FOR TWO-STAGE STOCHASTIC QUADRATIC PROGRAMMING

SIAM JOURNAL ON OPTIMIZATION 2020年第1期30卷 823-852页

作者： Liu, Junyi Sen, Suvrajeet Univ Southern Calif Dept Ind & Syst Engn Los Angeles CA 90089 USA

This paper presents the stochastic decomposition (SD) algorithms for two classes of stochastic programming problems: (1) two-stage stochastic quadratic-linear programming (SQLP) in which a quadratic program defines the objective function in the first stage and a linear program defines the value function in the second stage and (2) two-stage stochastic quadratic-quadratic programming (SQQP) which has quadratic programming problems in both stages. Similar to their stochastic linear programming (SLP) predecessor, these iterative schemes in SD approximate the objective function using piecewise affine/quadratic minorants and then apply a stochastic proximal mapping to obtain the next iterate. In this paper we show that under some assumptions, the proximal mapping applied in SD obeys a contraction mapping property even though the approximations are based on sequential random samples. Following that, we demonstrate that under those assumptions, SD can provide a sequence of solutions converging to the optimal solution with a sublinear convergence rate in both SQLP and SQQP problems. Finally, we present an "in-sample" stopping rule to assess the optimality gap by constructing consistent bootstrap estimators.

关键词： stochastic programming decomposition algorithms convergence rates

来源：评论

学校读者我要写书评

暂无评论

A decomposition framework for the scheduling of single- and multi-stage processes

引用

COMPUTERS & CHEMICAL ENGINEERING 2006年第3期30卷 407-420页

作者： Maravelias, CT Univ Wisconsin Dept Biol & Chem Engn Madison WI 53706 USA

A decomposition framework for the scheduling of single- and multi-stage batch chemical processes is presented. The problem is decomposed into an assignment and a sequencing subproblem. The assignment subproblem is solved using mixed-integer methods, while the sequencing subproblem is solved using efficient sequencing algorithms. The proposed method integrates mathematical programming with special-purpose sequencing algorithms. In addition to solving the sequencing subproblem more effectively, this also allows us to generate strong cuts for the assignment subproblem. A novel preprocessing algorithm that identifies infeasible assignments and generates tightening constraints for the assignment subproblem is also developed. This significantly reduces the number of sequencing subproblems needed to find the optimal solution and prove optimality. Computational results show that the proposed algorithm is considerably faster than state of the art methods. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： scheduling decomposition algorithms mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

decomposition by Successive Convex Approximation: A Unifying Approach for Linear Transceiver Design in Heterogeneous Networks

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2016年第2期15卷 1377-1392页

作者： Hong, Mingyi Li, Qiang Liu, Ya-Feng Iowa State Univ Dept Ind & Mfg Syst Engn Ames IA USA Univ Elect Sci & Technol China Sch Commun & Informat Engn Chengdu 610054 Peoples R China Chinese Acad Sci Acad Math & Syst Sci Inst Computat Math & Sci Engn Comp State Key Lab Sci & Engn Comp Beijing 100190 Peoples R China

We study the downlink linear precoder design problem in a multicell dense heterogeneous network (HetNet). The problem is formulated as a general sum-utility maximization (SUM) problem, which includes as special cases many practical precoder design problems such as multicell coordinated linear precoding, full and partial per-cell coordinated multipoint transmission, zero-forcing precoding, and joint BS clustering and beamforming/precoding. The SUM problem is difficult due to its nonconvexity and the tight coupling of the users' precoders. In this paper, we propose a novel convex approximation technique to approximate the original problem by a series of convex subproblems, each of which decomposes across all the cells. The convexity of the subproblems allows for efficient computation, while their decomposability leads to distributed implementation. Our approach hinges upon the identification of certain key convexity properties of the sum-utility objective, which allows us to transform the problem into a form that can be solved using a popular algorithmic framework called block successive upper-bound minimization (BSUM). Simulation experiments show that the proposed framework is effective for solving interference management problems in large HetNet.

关键词： BSUM decomposition algorithms HetNet Precoder Design SCA

来源：评论

学校读者我要写书评

暂无评论

New decomposition methods for solving variational inequality problems

引用

MATHEMATICAL AND COMPUTER MODELLING 2003年第3-4期37卷 405-418页

作者： Han, DR Sun, WY Nanjing Normal Univ Sch Math & Comp Sci Nanjing 210097 Peoples R China

For solving large-scale constrained separable variational inequality problems, the de-composition methods are attractive, since they solve the original problems via solving a series of small-scale problems, which may be much easier to solve than the original problems. In this paper, we-propose some new decomposition methods, which axe based on the Lagrange and the augmented Lagrange mappings of the problems, respectively. For the global convergence, the first method needs the partial cocoercivity of the underlying mapping, while the second one just requires monotonicity, a condition which is much weaker than partial cocoercivity. The cost for this weaker condition is to perform two additional projection steps on the dual variables and the primal-dual variables. We then extend the method to a more practical one, which just solves the subproblem approximately. We also report some computational results of the inexact method to show its promise. (C) 2003 Elsevier Science Ltd. All rights reserved.

关键词： variational inequality problems decomposition algorithms partial cocoercive mappings monotone mappings global convergence

来源：评论

学校读者我要写书评

暂无评论

Comparison of conventional and decomposition-enhanced spike triggered averaging techniques

引用

CLINICAL NEUROPHYSIOLOGY 2004年第3期115卷 564-568页

作者： Lawson, VH Bromberg, MB Stashuk, D Univ Utah Dept Neurol Salt Lake City UT 84132 USA Univ Waterloo Dept Biomed Med Engn Waterloo ON N2L 3G1 Canada

Objective: Spike triggered averaging (STA) is a technique to extract an estimate of a recurring motor unit potential from a complex electromyographic (EMG) signal. In conventional STA (C-STA), potentials related to the discharges of single intramuscular motor units are isolated and used to trigger an averager to obtain an individual surface-detected motor unit potential (S-MUP) from an EMG signal. In decomposition-enhanced STA (DE-STA), EMG signal decomposition algorithms determine discharges of a number of different motor units (4 to 10) that can be used to trigger an averager to obtain their corresponding S-MUPs. We tested the accuracy of extracting and averaging SMUPs using DE-STA compared to C-STA for the same EMG signals. Methods: We compared the intramuscular potentials used for triggering and the resultant averaged S-MUPs that were common in both techniques. Results: We found no statistically significant differences in the metrics used to describe the triggering potentials and S-MUPs. Conclusions: We conclude that DE-STA is an accurate and efficient method to obtain a large number of intramuscular motor unit potentials and their corresponding S-MUP in proximal and distal muscles. (C) 2004 International Federation of Clinical Neurophysiology. Published by Elsevier Ireland Ltd. All rights reserved.

关键词： spike triggered averaging decomposition algorithms motor unit number estimation

来源：评论

学校读者我要写书评

暂无评论

An Improved decomposition and Drawing Process for Optimal Topological Visualization of Directed Graphs 15

An Improved Decomposition and Drawing Process for Optimal To...

引用

31st Spring Conference on Computer Graphics

作者： Abuthawabeh, Ala Zeckzer, Dirk TU Kaiserslautern Kaiserslautern Germany Univ Leipzig D-04109 Leipzig Germany

ISBN: (纸本)9781450336932

Important information in application areas like Bio-Informatics, Biology, and Software Engineering is encoded in directed graphs. Typically, these graphs are represented using node-link diagrams. In these areas differentiating between cyclic and acyclic subgraphs shows important information about the structure and eases the analysis of these graphs. However, existing approaches are uniform and do not differentiate between different structures while computing the layout of the directed graph. We propose a topology-based approach that decomposes directed graphs into subgraphs for different topological structures, builds a two-level hierarchy of coarse grained graphs, and applies optimized area-aware layout algorithms to draw them. We applied our approach to one synthetic data set for illustration purposes and to one real data set showing usage dependencies in a software system. The results show that the different structural components of the directed graphs can be clearly identified.

关键词： topological visualization directed graphs graph drawing cyclic area-aware layout decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

QP algorithms with guaranteed accuracy and run time for support vector machines

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2006年第5期7卷 733-769页

作者： Hush, Don Kelly, Patrick Scovel, Clint Steinwart, Ingo Los Alamos Natl Lab Modeling Algorithms & Informat Grp Los Alamos NM 87545 USA

We describe polynomial-time algorithms that produce approximate solutions with guaranteed accuracy for a class of QP problems that are used in the design of support vector machine classifiers. These algorithms employ a two-stage process where the first stage produces an approximate solution to a dual QP problem and the second stage maps this approximate dual solution to an approximate primal solution. For the second stage we describe an O(n log n) algorithm that maps an approximate dual solution with accuracy (2 root 2K(n) + 8 root lambda)(-2) lambda epsilon(2)(p) to an approximate primal solution with accuracy epsilon(p) where n is the number of data samples, K-n is the maximum kernel value over the data and lambda > 0 is the SVM regularization parameter. For the first stage we present new results for decomposition algorithms and describe new decomposition algorithms with guaranteed accuracy and run time. In particular, for tau-rate certifying decomposition algorithms we establish the optimality of tau = 1/(n - 1). In addition we extend the recent tau = 1/(n - 1) algorithm of Simon ( 2004) to form two new composite algorithms that also achieve the t = 1/( n- 1) iteration bound of List and Simon ( 2005), but yield faster run times in practice. We also exploit the t - rate certifying property of these algorithms to produce new stopping rules that are computationally efficient and that guarantee a specified accuracy for the approximate dual solution. Furthermore, for the dual QP problem corresponding to the standard classification problem we describe operational conditions for which the Simon and composite algorithms possess an upper bound of O(n) on the number of iterations. For this same problem we also describe general conditions for which a matching lower bound exists for any decomposition algorithm that uses working sets of size 2. For the Simon and composite algorithms we also establish an O(n(2)) bound on the overall run time for the first stage. Combining the

关键词： quadratic programming decomposition algorithms approximation algorithms support vector machines

来源：评论

学校读者我要写书评

暂无评论

STRUCTURAL-PROPERTIES AND RECOGNITION OF RESTRICTED AND STRONGLY UNIMODULAR MATRICES

引用

MATHEMATICAL PROGRAMMING 1987年第1期38卷 17-27页

作者： CONFORTI, M RAO, MR 1.New York University 10003 New York NY USA

A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation.

关键词： Integer programming totally unimodular matrices decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

SDDP for multistage stochastic linear programs based on spectral risk measures

引用

OPERATIONS RESEARCH LETTERS 2012年第5期40卷 313-318页

作者： Guigues, Vincent Roemisch, Werner Univ Berlin Inst Math D-10099 Berlin Germany IMPA Rio De Janeiro Brazil Univ Fed Rio de Janeiro Escola Politecn Dept Engn Ind Ilha FundaoCT Rio de Janeiro Brazil

We consider risk-averse formulations of multistage stochastic linear programs. For these formulations, based on convex combinations of spectral risk measures, risk-averse dynamic programming equations can be written. As a result, the Stochastic Dual Dynamic Programming (SDDP) algorithm can be used to obtain approximations of the corresponding risk-averse recourse functions. This allows us to define a risk-averse nonanticipative feasible policy for the stochastic linear program. Formulas for the cuts that approximate the recourse functions are given. In particular, we show that some cut coefficients have analytic formulas. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Spectral risk measure Stochastic programming Risk-averse optimization decomposition algorithms Monte Carlo sampling

来源：评论

学校读者我要写书评

暂无评论

A CASCADE IMPLEMENTATION OF DIGITAL-SYSTEMS

MICROPROCESSING AND MICROPROGRAMMING

引用

MICROPROCESSING AND MICROPROGRAMMING 1990年第3期29卷 151-163页

作者： DVORAK, V TECH UNIV BRNO DEPT COMPCS-61266 BRNOCZECHOSLOVAKIA

This paper presents a new synthesis technique of multiple-output combinational networks based on iterative decomposition that results in implementation of digital systems in a form of a cascade of subsystems with regular interconnections. Some new theorems are proven and a figure of merit of cascade implementations is introduced in order to compare cost-effectiveness of different configurations. The technique is illustrated on several examples. Applications of cascade synthesis are found in multi-level partitioning of ROMs, in designing pipelined structures, and also in simulation of large multiple output Boolean function in software, which is several times faster than evaluation of Boolean expressions.

关键词： Cellular cascades decomposition algorithms Evaluation of logic functions Iterative decomposition Partial functions Pipelined processing ROM-based logic design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：