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

FINDING SPARSE SOLUTIONS FOR PACKING AND COVERING SEMIDEFINITE PROGRAMS

SIAM JOURNAL ON OPTIMIZATION 2022年第2期32卷 321-353页

作者： Elbassioni, Khaled Makino, Kazuhisa Najy, Waleed Khalifa Univ Sci & Technol Abu Dhabi U Arab Emirates Kyoto Univ Res Inst Math Sci RIMS Kyoto 6068502 Japan New York Univ Abu Dhabi Abu Dhabi U Arab Emirates

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081--1091] for packing/covering linear programs.

关键词： Key words semidefinite programs packing and covering logarithmic potential primal-dual algorithms approximate solutions robust packing and covering SDPs

来源：评论

学校读者我要写书评

暂无评论

ON THE CONVERGENCE OF STOCHASTIC primal-dual HYBRID GRADIENT

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第2期32卷 1288-1318页

作者： Alacaoglu, Ahmet Fercoq, Olivier Cevher, Volkan Univ Wisconsin Wisconsin Inst Discovery Madison WI 53703 USA Ecole Polytech Fed Lausanne Lab Informat & Inference Syst Lausanne Switzerland Inst Polytech Paris Telecom Paris Lab Traitement & Commun Informat F-91120 Palaiseau France Ecole Polytech Fed Lausanne Lab Informat & Inference Syst CH-1015 Lausanne Switzerland

In this paper, we analyze the recently proposed stochastic primal-dual hybrid gradient (SPDHG) algorithm and provide new theoretical results. In particular, we prove almost sure convergence of the iterates to a solution with convexity and linear convergence with further structure, using standard step sizes independent of strong convexity or other regularity constants. In the general convex case, we also prove the \scrO (1/k) convergence rate for the ergodic sequence, on expected primal-dual gap function. Our assumption for linear convergence is metric subregularity, which is satisfied for strongly convex-strongly concave problems in addition to many nonsmooth and/or nonstrongly convex problems, such as linear programs, Lasso, and support vector machines. We also provide numerical evidence showing that SPDHG with standard step sizes shows a competitive practical performance against its specialized strongly convex variant SPDHG-\mu and other state-of-the-art algorithms, including variance reduction methods.

关键词： convex optimization coordinate descent primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

A FIRST-ORDER primal-dual ALGORITHM WITH LINESEARCH

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第1期28卷 411-432页

作者： Malitsky, Yura Pock, Thomas Graz Univ Technol Inst Comp Graph & Vis A-8010 Graz Austria

The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires an update of only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under standard assumptions. We also show an ergodic O(1/N) rate of convergence for our method. In the case when one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle-point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.

关键词： saddle-point problems first-order algorithms primal-dual algorithms linesearch convergence rates backtracking

来源：评论

学校读者我要写书评

暂无评论

Controlling conservation laws I: Entropy-entropy flux

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2023年第1期480卷

作者： Li, Wuchen Liu, Siting Osher, Stanley Univ South Carolina Dept Math Columbia SC 29208 USA Univ Calif Los Angeles Dept Math Los Angeles CA USA

We study a class of variational problems for regularized conservation laws with Lax's entropy-entropy flux pairs. We first introduce a modified optimal transport space based on conservation laws with diffusion. Using this space, we demonstrate that conservation laws with diffusion are "flux-gradient flows". We next construct variational problems for these flows, for which we derive dual PDE systems for regularized conservation laws. Several examples, including traffic flow and Burgers' equation, are presented. Incorporating both primal-dual algorithms and monotone schemes, we successfully compute the control of conservation laws.(c) 2023 Elsevier Inc. All rights reserved.

关键词： Entropy-entropy flux pairs Optimal transport Mean-field games Monotone schemes primal-dual algorithms Hamiltonian flows

来源：评论

学校读者我要写书评

暂无评论

Adversarial Bandits with Knapsacks

引用

JOURNAL OF THE ACM 2022年第6期69卷 40-40页

作者： Immorlica, Nicole Sankararaman, Karthik Schapire, Robert Slivkins, Aleksandrs Microsoft Res New England One Mem Dr Cambridge MA 02142 USA Meta AI 1 Hacker Way Menlo Pk CA 94025 USA

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the "classic" adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon;we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version, and use it as a subroutine to solve the latter. Our algorithm is the first "black-box reduction" from bandits to BwK: it takes an arbitrary bandit algorithm and uses it as a subroutine. We use this reduction to derive several extensions.

关键词： Multi-armed bandits adversarial bandits bandits with knapsacks regret competitive ratio primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Contextual bandits with packing and covering constraints: a modular lagrangian approach via regression

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2024年第1期25卷 19264-19300页

作者： Aleksandrs Slivkins Xingyu Zhou Karthik Abinav Sankararaman Dylan J. Foster Microsoft Research NYC Wayne State University Detroit Meta

We consider contextual bandits with linear constraints (CBwLC), a variant of contextual bandits in which the algorithm consumes multiple resources subject to linear constraints on total consumption. This problem generalizes contextual bandits with knapsacks (CBwK), allowing for packing and covering constraints, as well as positive and negative resource consumption. We provide the first algorithm for CBwLC (or CBwK) that is based on regression oracles. The algorithm is simple, computationally efficient, and statistically optimal under mild assumptions. Further, we provide the first vanishing-regret guarantees for CBwLC (or CBwK) that extend beyond the stochastic environment. We side-step strong impossibility results from prior work by identifying a weaker (and, arguably, fairer) benchmark to compare against. Our algorithm builds on LagrangeBwK (Immorlica et al., 2019, 2022), a Lagrangianbased technique for CBwK, and SquareCB (Foster and Rakhlin, 2020), a regression-based technique for contextual bandits. Our analysis leverages the inherent modularity of both techniques.

关键词： multi-armed bandits contextual bandits bandits with knapsacks regression oracles primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

DATA-DRIVEN GRADIENT FLOWS

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2022年 57卷 193-215页

作者： Pietschmann, Jan-Frederik Schlottbom, Matthias Tech Univ Chemnitz Fak Math Reichenhainer Str 41 D-09126 Chemnitz Germany Univ Twente Dept Appl Math Postbus 217 NL-7500 AE Enschede Netherlands

We present a framework enabling variational data assimilation for gradient flows in general metric spaces, based on the minimizing movement (or Jordan-Kinderlehrer-Otto) approximation scheme. After discussing stability properties in the most general case, we specialize to the space of probability measures endowed with the Wasserstein distance. This setting covers many non-linear partial differential equations (PDEs), such as the porous-medium equation or general drift-diffusion-aggregation equations, which can be treated by our methods independently of their respective properties (such as finite speed of propagation or blow-up). We then focus on the numerical implementation using a primal-dual algorithm. The strength of our approach lies in the fact that, by simply changing the driving functional, a wide range of PDEs can be treated without the need to adopt the numerical scheme. We conclude by presenting several numerical examples.

关键词： gradient flows variational data assimilation primal-dual algorithms Wasserstein distance

来源：评论

学校读者我要写书评

暂无评论

Control Reconfiguration for Improved Performance via Reverse-engineering and Forward-engineering ⁎

引用

IFAC-PapersOnLine 2020年第2期53卷 4688-4694页

作者： Han Shu Xuan Zhang Na Li Antonis Papachristodoulou Tsinghua-Berkeley Shenzhen Institute Shenzhen Guangdong 518055 China School of Engineering and Applied Sciences Harvard University USA Department of Engineering Science University of Oxford UK

This paper presents a control redesign approach to improve the performance of a certain class of dynamical systems. Motivated by recent research on re-engineering cyber-physical systems, we propose a three-step control retrofit procedure. First, we reverse-engineer a dynamical system to dig out an optimization problem it actually solves. Second, we apply an augmented Lagrangian or a hat-x method to solve this optimization problem. Finally, by comparing the original and new dynamics, we obtain the implementation of the redesigned part (i.e., the extra dynamics). As a result, the convergence rate/speed or transient behavior of the given system can be improved while the system structure remains. To show the effectiveness of the proposed approach and its potential applications, we present two practical examples including Internet congestion control and distributed proportional-integral (PI) control.

关键词： Control redesign reverse-engineering optimization primal-dual algorithms augmented Lagrangian

来源：评论

学校读者我要写书评

暂无评论

A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming

引用

SIAM JOURNAL ON OPTIMIZATION 2003年第4期13卷 1054-1079页

作者： Monteiro, RDC Tsuchiya, T Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

In this paper we present a variant of Vavasis and Ye's layered-step path-following primal-dual interior-point algorithm for linear programming. Our algorithm is a predictor corrector-type algorithm which uses from time to time the layered least squares (LLS) direction in place of the a ne scaling (AS) direction. It has the same iteration-complexity bound of Vavasis and Ye's algorithm, namely O(n(3.5) log((χ) over bar (A)+n)), where n is the number of nonnegative variables and (χ) over bar (A) is a certain condition number associated with the constraint matrix A. Vavasis and Ye's algorithm requires explicit knowledge of (χ) over bar (A) (which is very hard to compute or even estimate) in order to compute the layers for the LLS direction. In contrast, our algorithm uses the AS direction at the current iterate to determine the layers for the LLS direction, and hence does not require the knowledge of (χ) over bar (A). A variant with similar properties and with the same complexity has been developed by Megiddo, Mizuno, and Tsuchiya [ Math. Programming, 82 ( 1998), pp. 339 355]. However, their algorithm needs to compute n LLS directions on every iteration, while ours computes at most one LLS direction on any given iteration.

关键词： interior-point algorithms primal-dual algorithms path-following central path layered steps condition number polynomial complexity predictor-corrector a ne scaling strongly polynomial linear programming

来源：评论

学校读者我要写书评

暂无评论

Stochastic primal-dual coordinate method for regularized empirical risk minimization

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2017年第1期18卷

作者： Yuchen Zhang Lin Xiao Department of Computer Science Stanford University Stanford CA Microsoft Research Redmond WA

We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variables. An extrapolation step on the primal variables is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.

关键词： computational complexity convex-concave saddle empirical risk minimization point problems primal-dual algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：