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

Random Minibatch subgradient algorithms for Convex Problems with Functional Constraints

APPLIED MATHEMATICS AND OPTIMIZATION 2019年第3期80卷 801-833页

作者： Nedic, Angelia Necoara, Ion Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ USA Univ Politehn Bucuresti Dept Automat Control & Syst Engn Bucharest 060042 Romania

In this paper we consider non-smooth convex optimization problems with (possibly) infinite intersection of constraints. In contrast to the classical approach, where the constraints are usually represented as intersection of simple sets, which are easy to project onto, in this paper we consider that each constraint set is given as the level set of a convex but not necessarily differentiable function. For these settings we propose subgradient iterative algorithms with random minibatch feasibility updates. At each iteration, our algorithms take a subgradient step aimed at only minimizing the objective function and then a subsequent subgradient step minimizing the feasibility violation of the observed minibatch of constraints. The feasibility updates are performed based on either parallel or sequential random observations of several constraint components. We analyze the convergence behavior of the proposed algorithms for the case when the objective function is strongly convex and with bounded subgradients, while the functional constraints are endowed with a bounded first-order black-box oracle. For a diminishing stepsize, we prove sublinear convergence rates for the expected distances of the weighted averages of the iterates from the constraint set, as well as for the expected suboptimality of the function values along the weighted averages. Our convergence rates are known to be optimal for subgradient methods on this class of problems. Moreover, the rates depend explicitly on the minibatch size and show when minibatching helps a subgradient scheme with random feasibility updates.

关键词： Convex minimization Functional constraints subgradient algorithms Random minibatch projection algorithms Convergence rates

来源：评论

学校读者我要写书评

暂无评论

subgradient method with entropic projections for convex nondifferentiable minimization

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第1期96卷 159-173页

作者： Kiwiel, KC Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

We replace orthogonal projections in the Polyak subgradient method for nonnegatively constrained minimization with entropic projections, thus obtaining an interior-point subgradient method. Inexact entropic projection... 详细信息

关键词： convex programming nondifferentiable optimization subgradient algorithms entropic projections

来源：评论

学校读者我要写书评

暂无评论

Interior gradient and epsilon-subgradient descent methods for constrained convex minimization

引用

MATHEMATICS OF OPERATIONS RESEARCH 2004年第1期29卷 1-26页

作者： Auslender, A Teboulle, M Univ Lyon 1 Dept Math F-69365 Lyon France Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel

We extend epsilon-subgradient descent methods for unconstrained nonsmooth convex minimization to constrained problems over polyhedral sets, in particular over R-+(p). This is done by replacing the usual squared quadratic regularization term used in subgradient schemes by the logarithmic-quadratic distancelike function recently introduced by the authors. We then obtain interior epsilon-subgradient descent methods, which allow us to provide a natural extension of bundle methods and Polyak's subgradient projection methods for nonsmooth convex minimization. Furthermore, similar extensions are considered for smooth constrained minimization to produce interior gradient descent methods. Global convergence as well as an improved global efficiency estimate are established for these methods within a unifying principle and minimal assumptions on the problem's data.

关键词： nondifferentiable convex optimization subgradient algorithms bundle methods logarithmic-quadratic proximal methods projected gradient methods convex programming

来源：评论

学校读者我要写书评

暂无评论

Constrained Consensus and Optimization in Multi-Agent Networks

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2010年第4期55卷 922-938页

作者： Nedic, Angelia Ozdaglar, Asuman Parrilo, Pablo A. Univ Illinois Ind & Enterprise Syst Engn Dept Urbana IL 61801 USA MIT Lab Informat & Decis Syst Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets. To highlight the effects of constraints, we first consider a constrained consensus problem and present a distributed "projected consensus algorithm" in which agents combine their local averaging operation with projection on their individual constraint sets. This algorithm can be viewed as a version of an alternating projection method with weights that are varying over time and across agents. We establish convergence and convergence rate results for the projected consensus algorithm. We next study a constrained optimization problem for optimizing the sum of local objective functions of the agents subject to the intersection of their local constraint sets. We present a distributed "projected subgradient algorithm" which involves each agent performing a local averaging operation, taking a subgradient step to minimize its own objective function, and projecting on its constraint set. We show that, with an appropriately selected stepsize rule, the agent estimates generated by this algorithm converge to the same optimal solution for the cases when the weights are constant and equal, and when the weights are time-varying but all agents have the same constraint set.

关键词： Consensus constraints distributed optimization subgradient algorithms

来源：评论

学校读者我要写书评

暂无评论

Generalized Bregman projections in convex feasibility problems

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第1期96卷 139-157页

作者： Kiwiel, KC Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

We present a method for finding common points of finitely many closed convex sets in Euclidean space. The Bregman extension of the classical method of cyclic orthogonal projections employs nonorthogonal projections induced by a convex Bregman function, whereas the Bauschke and Borvein method uses Bregman/Legendre functions. Our method works with generalized Bregman functions (B-functions) and inexact projections, which are easier to compute than the exact ones employed in other methods. We also discuss subgradient algorithms with Bregman projections.

关键词： convex feasibility problems successive projections Bregman functions B-functions subgradient algorithms nondifferentiable optimization

来源：评论

学校读者我要写书评

暂无评论

A Lagrangian-based heuristic for large-scale set covering problems

引用

MATHEMATICAL PROGRAMMING 1998年第2期81卷 215-228页

作者： Ceria, S Nobili, P Sassano, A Columbia Univ Grad Sch Business New York NY 10027 USA CNR Ist Anal Sistemi & Informat I-00185 Rome Italy Univ La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy

We present a new Lagrangian-based heuristic for solving large-scale set-covering problems arising from crew-scheduling at the Italian Railways (Ferrovie dello Stato). Our heuristic obtained impressive results when compared to state-of-the-art codes on a test-bed provided by the company, which includes instances with sizes ranging from 50,000 variables and 500 constraints to 1,000,000 variables and 5000 constraints. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： set covering crew scheduling primal-dual Lagrangian subgradient algorithms 0-1 programming approximate solutions railways

来源：评论

学校读者我要写书评

暂无评论

Random algorithms for convex minimization problems

引用

MATHEMATICAL PROGRAMMING 2011年第2期129卷 225-253页

作者： Nedic, Angelia Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA

This paper deals with iterative gradient and subgradient methods with random feasibility steps for solving constrained convex minimization problems, where the constraint set is specified as the intersection of possibly infinitely many constraint sets. Each constraint set is assumed to be given as a level set of a convex but not necessarily differentiable function. The proposed algorithms are applicable to the situation where the whole constraint set of the problem is not known in advance, but it is rather learned in time through observations. Also, the algorithms are of interest for constrained optimization problems where the constraints are known but the number of constraints is either large or not finite. We analyze the proposed algorithm for the case when the objective function is differentiable with Lipschitz gradients and the case when the objective function is not necessarily differentiable. The behavior of the algorithm is investigated both for diminishing and non-diminishing stepsize values. The almost sure convergence to an optimal solution is established for diminishing stepsize. For non-diminishing stepsize, the error bounds are established for the expected distances of the weighted averages of the iterates from the constraint set, as well as for the expected sub-optimality of the function values along the weighted averages.

关键词： Convex minimization Gradient algorithms subgradient algorithms Random algorithms Error bounds

来源：评论

学校读者我要写书评

暂无评论

MINMAX COMBINATORIAL OPTIMIZATION

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1995年第3期81卷 634-643页

作者： PUNNEN, AP ANEJA, YP UNIV WINDSOR FAC BUSINESS ADMWINDSORON N9B 3P4CANADA

Let E be a finite set, and F be a family of subsets of E. For each element e is-an-element-of E, p weights c(i), e, i = 1, 2, ..., p are prescribed. Then the minmax combinatorial optimization problem is to Minimize S is-an-element-of F(Maximum) 1 less-than-or-equal-to i less-than-or-equal-to p(SIGMA(e) is-an-element-of S{c(i)e-. Several special cases of this general problem, viz. 3-partition, makespan minimization problem, bandwidth minimization in matrices and graphs, categorized assignment problem, etc., have been studied in literature. In this paper we propose exact and heuristic methods to solve the general problem. Our algorithms also give some new insights into the application of subgradient optimization in solving the Lagrangean dual of combinatorial problems when the Lagrange multipliers are required to satisfy additional constraints. Encouraging computational results are also reported.

关键词： MINMAX OPTIMIZATION LAGRANGEAN RELAXATION subgradient algorithms COMBINATORIAL OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

Finding maxmin allocations in cooperative and competitive fair division

引用

ANNALS OF OPERATIONS RESEARCH 2014年第1期223卷 121-136页

作者： Dall'Aglio, Marco Di Luca, Camilla LUISS Univ Rome Italy

We define a subgradient algorithm to compute the maxmin value of a completely divisible good in both competitive and cooperative strategic contexts. The algorithm relies on the construction of upper and lower bounds for the optimal value which are based on the convexity properties of the range of utility vectors associated to all possible divisions of the good. The upper bound always converges to the optimal value. Moreover, if two additional hypotheses hold: that the preferences of the players are mutually absolutely continuous, and that there always exists relative disagreement among the players, then also the lower bound converges, and the algorithm finds an approximately optimal allocation.

关键词： Fair division theory Cooperative game theory Convex optimization subgradient algorithms

来源：评论

学校读者我要写书评

暂无评论

Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2012年第3期57卷 592-606页

作者： Duchi, John C. Agarwal, Alekh Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent coordination, estimation in sensor networks, and large-scale machine learning. We develop and analyze distributed algorithms based on dual subgradient averaging, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our analysis allows us to clearly separate the convergence of the optimization algorithm itself and the effects of communication dependent on the network structure. We show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network, and confirm this prediction's sharpness both by theoretical lower bounds and simulations for various networks. Our approach includes the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

关键词： Convex optimization distributed control distributed multi-agent system distributed optimization subgradient algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：