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

Active-set Methods for submodular minimization Problems

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 4809-4839页

作者： Kumar, K. S. Sesh Bach, Francis Imperial Coll London Dept Comp 180 Queens Gate London SW7 2AZ England INRIA Ecole Normale Super UMR CNRS ENS INRIA Dept Informat Sierra Project Team 2 Rue Simone Iff F-75012 Paris France

We consider the submodular function minimization (SFM) and the quadratic minimization problems regularized by the Lovasz extension of the submodular function. These optimization problems are intimately related;for example, min-cut problems and total variation denoising problems, where the cut function is submodular and its Lovasz extension is given by the associated total variation. When a quadratic loss is regularized by the total variation of a cut function, it thus becomes a total variation denoising problem and we use the same terminology in this paper for "general" submodular functions. We propose a new active-set algorithm for total variation denoising with the assumption of an oracle that solves the corresponding SFM problem. This can be seen as local descent algorithm over ordered partitions with explicit convergence guarantees. It is more flexible than the existing algorithms with the ability for warm-restarts using the solution of a closely related problem. Further, we also consider the case when a submodular function can be decomposed into the sum of two submodular functions F-1 and F-2 and assume SFM oracles for these two functions. We propose a new active-set algorithm for total variation denoising (and hence SFM by thresholding the solution at zero). This algorithm also performs local descent over ordered partitions and its ability to warm start considerably improves the performance of the algorithm. In the experiments, we compare the performance of the proposed algorithms with state-of-the-art algorithms, showing that it reduces the calls to SFM oracles.

关键词： discrete optimization submodular function minimization convex optimization cut functions total variation denoising

来源：评论

学校读者我要写书评

暂无评论

Joint Continuous and Discrete Model Selection via submodularity

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2022年第1期23卷 1-42页

作者： Bunton, Jonathan Tabuada, Paulo Univ Calif Los Angeles Dept Elect & Comp Engn 420 Westwood PlazaBox 951594 Los Angeles CA 90095 USA

In model selection problems for machine learning, the desire for a well-performing model with meaningful structure is typically expressed through a regularized optimization problem. In many scenarios, however, the meaningful structure is specified in some discrete space, leading to difficult nonconvex optimization problems. In this paper, we connect the model selection problem with structure-promoting regularizers to submodular function minimization with continuous and discrete arguments. In particular, we leverage the theory of submodular functions to identify a class of these problems that can be solved exactly and efficiently with an agnostic combination of discrete and continuous optimization routines. We show how simple continuous or discrete constraints can also be handled for certain problem classes, and extend these ideas to a robust optimization framework. We also show how some problems outside of this class can be embedded into the class, further extending the class of problems our framework can accommodate. Finally, we numerically validate our theoretical results with several pro of-of-concept examples with synthetic and real-world data, comparing against state-of-the-art algorithms.

关键词： submodularity submodular function minimization mixed continuous dis-crete optimization convex optimization sparsity

来源：评论

学校读者我要写书评

暂无评论

A heuristic search based on diversity for solving combinatorial problems

引用

JOURNAL OF HEURISTICS 2022年第3期28卷 287-328页

作者： Casas, Francisco Torres, Claudio E. Araya, Ignacio Univ Tecn Federico Santa Maria Dept Informat Valparaiso Chile Ctr Cient Tecnol Valparaiso CCTVal Valparaiso Chile Pontificia Univ Catolica Valparaiso Valparaiso Chile

In this paper we propose a novel heuristic search for solving combinatorial optimization problems which we call Diverse Search (DS). Like beam search, this constructive approach expands only a selected subset of the solutions in each level of the search tree. However, instead of selecting the solutions with the best values, we use an efficient method to select a diverse subset, after filtering out uninteresting solutions. DS also distinguishes solutions that do not produce better offspring, and applies a local search process to them. The intuition is that the combination of these strategies allows to reach more-and more diverse-local optima, increasing the chances of finding the global optima. We test DS on several instances of the Koerkel-Ghosh (KG) and K-median benchmarks for the Simple Plant Location Problem. We compare it with a state-of-the-art heuristic for the KG benchmark and the relatively old POPSTAR solver, which also relies on the idea of maintaining a diverse set of solutions and, surprisingly, reached a comparable performance. With the use of a Path Relinking post-optimization step, DS can achieve results of the same quality that the state-of-the-art in similar CPU times. Furthermore, DS proved to be slightly better on average for large scale problems with small solution sizes, proving to be an efficient algorithm that delivers a set of good and diverse solutions.

关键词： Facility location submodular function minimization Tree search Maximum diversity Selection operator

来源：评论

学校读者我要写书评

暂无评论

Minimizing symmetric submodular functions

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 3-12页

作者： Queyranne, M Univ British Columbia Fac Commerce & Business Adm Vancouver BC V6T 1Z2 Canada

We describe a purely combinatorial algorithm which, given a submodular set function f on a finite set V, finds a nontrivial subset A of V minimizing f[A] + f[V \ A].:This algorithm, an extension of the Nagamochi-Ibaraki minimum cut algorithm as simplified by Steer and Wagner [M. Steer, F. Wagner, A simple min cut algorithm, Proceedings of the European Symposium on Algorithms ESA '94, LNCS 855, Springer, Berlin, 1994, pp. 141-147] and by Frank [A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratoire Artemis, IMAG, Universite J. Fourier, Grenbole, 1994], minimizes any symmetric submodular function using O(/V/(3)) calls to a function value oracle. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： symmetric submodular function minimization submodular function minimization symmetric submodular functions submodular functions submodular systems

来源：评论

学校读者我要写书评

暂无评论

Discrete Newton methods for the evacuation problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 795卷 510-519页

作者： Kamiyama, Naoyuki Kyushu Univ Inst Math Ind Fukuoka Fukuoka Japan

A dynamic network is a directed graph in which arcs have capacities and transit times. In this paper, we consider the evacuation problem in dynamic networks. In this problem, we are given a dynamic network with a single sink vertex in which each vertex except the sink vertex has a supply. Then the goal of this problem is to find the minimum time limit T such that we can send all the supplies to the sink vertex by T. In this paper, we propose a discrete Newton method for the evacuation problem. First, we prove that the number of iterations of this method is at most the number of vertices of the input dynamic network. Then we propose theoretical and practical implementation of this method. The theoretical implementation is based on submodular function minimization, and the practical implementation is based on maximum flow computations in time-expanded networks. Finally, we compare the proposed practical implementation with an algorithm using a binary search in time-expanded networks in computational experiments. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Dynamic network flow Evacuation problem submodular function minimization

来源：评论

学校读者我要写书评

暂无评论

Earliest Arrival Transshipments in Networks with Multiple Sinks 20th

Earliest Arrival Transshipments in Networks with Multiple Si...

引用

20th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Schloter, Miriam Swiss Fed Inst Technol Inst Operat Res Zurich Switzerland

ISBN: (纸本)9783030179533;9783030179526

We study a classical flow over time problem that captures the essence of evacuation planning: given a network with capacities and transit times on the arcs and sources/sinks with supplies/demands, an earliest arrival transshipment (EAT) sends the supplies from the sources to the sinks such that the amount of flow which has reached the sinks is maximized for every point in time simultaneously. In networks with only a single sink earliest transshipments do exist for every choice of supplies and demands. This is why so far a lot of effort has been put into the development of efficient algorithms for computing EATs in this class of networks, whereas not much is known about EATs in networks with multiple sinks, aside from the fact that they don't exist in general. We make huge progress regarding EATs in networks with multiple sinks by formulating the first exact algorithm that decides whether a given tight EAT problem has solution and that computes the EAT in case of existence. Our algorithm only works on the originally given network without requiring any form of expansion and thus just requires polynomial space. Complementing this algorithm we show that in multiple sink networks it is, already for tight instances, NP-hard to decide whether an EAT does exist for a specific choice of supplies and demands.

关键词： Flows over time submodular function minimization Earliest arrival flows Earliest arrival transshipments Evacuation

来源：评论

学校读者我要写书评

暂无评论

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization 56

A Faster Cutting Plane Method and its Implications for Combi...

引用

56th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Lee, Yin Tat Sidford, Aaron Wong, Sam Chiu-wai MIT Dept Math Cambridge MA 02139 USA MIT Dept EECS Cambridge MA 02139 USA Univ Calif Berkeley Dept EECS Berkeley CA USA

ISBN: (纸本)9781467381918

In this paper we improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set K subset of R-n that is contained in a box of radius R we show how to either compute a point in K or prove that K does not contain a ball of radius epsilon using an expected O(n log(nR/epsilon)) evaluations of the oracle and additional time O(n(3) log(O(1))(nR/epsilon)). This matches the oracle complexity and improves upon the O(n(omega+1) log(nR/epsilon)) additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya [91] for the current value of the matrix multiplication constant omega < 2.373 [98], [36] when R/epsilon = O(poly(n)). Using a mix of standard reductions and new techniques we show how our algorithm can be used to improve the running time for solving classic problems in continuous and combinatorial optimization. In particular we provide the following running time improvements: submodular function minimization: n is the size of the ground set, M is the maximum absolute value of function values and EO is the time for function evaluation. Our weakly and strongly polynomial time algorithms have a running time of O(n(2) log *** + n(3) log(O(1)) nM) and O(n(3) log(2) *** + n(4) log(O(1)) n), improving upon the previous best of O((n(4) . EO + n(5)) log M) and O(n(5) . EO + n(6)) respectively. submodular Flow: n = vertical bar V vertical bar, m = vertical bar E vertical bar, C is the maximum edge cost in absolute value and U is maximum edge capacity in absolute value. We obtain a faster weakly polynomial running time of O(n(2) log nCU . EO + n(3) log(O(1)) nCU), improving upon the previous best of O(mn(5) log nU . EO) and O(n(4) h min {log C, log U}) from 15 years ago by a factor of <(O)over tilde> (n(4)). We also achieve faster strongly polynomial time algorithms as a consequence of our result on submodular minimization. Matroid Intersection: n is the size of the grou

关键词： Cutting Plane Method Ellipsoid Method submodular function minimization submodular Flow Matroid Intersection Semidefinite Programming

来源：评论

学校读者我要写书评

暂无评论

submodular minimization Under Congruency Constraints 29

Submodular Minimization Under Congruency Constraints

引用

29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

作者： Nagele, Martin Sudakov, Benny Zenklusen, Rico Swiss Fed Inst Technol Dept Math Zurich Switzerland

ISBN: (纸本)9781611975031

submodular function minimization (SFM) is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which SFM remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial SFM algorithms are known are parity constraints, i.e., optimizing only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants are bounded by two in absolute value. We show that efficient SFM is possible even for a significantly larger class than parity constraints, by introducing a new approach that combines techniques from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we can show that efficient SFM is possible over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. This covers generalizations of the odd-cut problem with open complexity status, and with relevance in the context of integer programming with higher subdeterminants. To obtain our results, we establish a connection between the correctness of a natural algorithm, and the inexistence of set systems with specific combinatorial properties. We introduce a general technique to disprove the existence of such set systems, which allows for obtaining extensions of our results beyond the above-mentioned setting. These extensions settle two open questions raised by Geelen and Kapadia [Combinatorica, 2017] in the context of computing the girth and cogirth of certain types of binary matroids.

关键词： submodular function minimization congruency constraints combinatorics

来源：评论

学校读者我要写书评

暂无评论

Generic Cuts: An Efficient Algorithm for Optimal Inference in Higher Order MRF-MAP

Generic Cuts: An Efficient Algorithm for Optimal Inference i...

引用

12th European Conference on Computer Vision (ECCV)

作者： Arora, Chetan Banerjee, Subhashis Kalra, Prem Maheshwari, S. N. Indian Inst Technol Delhi Delhi India

ISBN: (纸本)9783642337147

We propose a new algorithm called Generic Cuts for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials satisfying submodularity. The algorithm runs in time O(2(k)n(3)) in the worst case (k is clique order and n is the number of pixels). A special gadget is introduced to model flows in a high order clique and a technique for building a flow graph is specified. Based on the primal dual structure of the optimization problem the notions of capacity of an edge and cut are generalized to define a flow problem. We show that in this flow graph max flow is equal to min cut which also is the optimal solution to the problem when potentials are submodular. This is in contrast to all prevalent techniques of optimizing Boolean energy functions involving higher order potentials including those based on reductions to quadratic potential functions which provide only approximate solutions even for submodular functions. We show experimentally that our implementation of the Generic Cuts algorithm is more than an order of magnitude faster than all algorithms including reduction based whose outputs on submodular potentials are near optimal.

关键词： Higher Order MRF-MAP submodular function minimization Optimal Algorithm

来源：评论

学校读者我要写书评

暂无评论

An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems

引用

MATHEMATICS OF OPERATIONS RESEARCH 2023年第4期48卷 1934-1958页

作者： Dadush, Daniel Koh, Zhuan Khye Natura, Bento Vegh, Laszlo A. Ctr Wiskunde & Informat NL-1098 XG Amsterdam Netherlands London Sch Econ & Polit Sci Dept Math London WC2A 2AE England

We present an accelerated or "look-ahead" version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains. (i) For linear fractional combinatorial optimization, we show a convergence bound of O(m log m) iterations;the previous best bound was O(m2logm) by Wang, Yang, and Zhang from 2006. (ii) We obtain a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality (2VPI). For a 2VPI system with n variables and m constraints, our algorithm runs in O(mn) iterations. Every iteration takes O(mn) time for general 2VPI systems and O(m + n log n) time for the special case of deterministic Markov decision processes (DMDPs). This extends and strengthens a previous result by Madani from 2002 that showed a weakly polynomial bound for a variant of the Newton-Dinkelbach method for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result from 2017 by Goemans, Gupta, and Jaillet.

关键词： Newton-Dinkelbach method fractional optimization parametric optimization strongly polynomial algorithm two variables per inequality system Markov decision process submodular function minimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：