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

A primal-dual active-set algorithm for bilaterally constrained total variation deblurring and piecewise constant Mumford-Shah segmentation problems

引用

ADVANCES IN COMPUTATIONAL MATHEMATICS 2009年第1-3期31卷 237-266页

作者： Krishnan, D. Pham, Quang Vinh Yip, Andy M. Natl Univ Singapore Dept Math Singapore 117543 Singapore

In this paper, we propose a fast primal-dual algorithm for solving bilaterally constrained total variation minimization problems which subsume the bilaterally constrained total variation image deblurring model and the two-phase piecewise constant Mumford-Shah image segmentation model. The presence of the bilateral constraints makes the optimality conditions of the primal-dual problem semi-smooth which can be solved by a semi-smooth Newton's method superlinearly. But the linear system to solve at each iteration is very large and difficult to precondition. Using a primal-dual active-set strategy, we reduce the linear system to a much smaller and better structured one so that it can be solved efficiently by conjugate gradient with an approximate inverse preconditioner. Locally superlinear convergence results are derived for the proposed algorithm. Numerical experiments are also provided for both deblurring and segmentation problems. In particular, for the deblurring problem, we show that the addition of the bilateral constraints to the total variation model improves the quality of the solutions.

关键词： Bilateral constraints Total variation Image deblurring Image segmentation primal-dual algorithm Semi-smooth Newton's method

来源：评论

学校读者我要写书评

暂无评论

An efficient primal-dual interior point algorithm for convex quadratic semidefinite optimization

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2024年第3期70卷 2129-2148页

作者： Zaoui, Billel Benterki, Djamel Yassine, Adnan Univ Ferhat Abbas Setif 1 Fac Sci Dept Math Lab Fundamental & Numer Math Setif 19000 Algeria Normandie Univ UNIHAVRE LMAH ISCNFR CNRS 3335 F-76600 Le Havre France

We introduce a primal-dual interior point algorithm for convex quadratic semidefinite optimization. This algorithm is based on an extension of the technique presented in the work of Zhang et al. for linear optimization. The symmetrization of the search direction is based on the Nesterov-Todd scaling scheme. Our analysis demonstrates that this method solves efficiently the problem within polynomial time. Notably, the short-step algorithm achieves the best-known iteration bound, namely O(nlogn epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\sqrt{n}\log \frac{n}{\varepsilon })$$\end{document}-iterations. The numerical experiments conclude that the newly proposed algorithm is not only polynomial but requires a number of iterations clearly lower than that obtained theoretically.

关键词： Convex quadratic semidefinite optimization Interior point methods Descent direction primal-dual algorithm Nesterov-Todd scaling scheme

来源：评论

学校读者我要写书评

暂无评论

Linear convergence for distributed stochastic optimization with coupled inequality constraints

引用

JOURNAL OF THE FRANKLIN INSTITUTE 2025年第1期362卷

作者： Du, Kaixin Meng, Min Li, Xiuxian Tongji Univ Shanghai Res Inst Intelligent Autonomous Syst Shanghai 201210 Peoples R China Tongji Univ Coll Elect & Informat Engn Dept Control Sci & Engn Shanghai 201804 Peoples R China Natl Key Lab Autonomous Intelligent Unmanned Syst Shanghai Peoples R China Minist Educ Frontiers Sci Ctr Intelligent Autonomous Syst Shanghai Peoples R China

This paper considers the distributed stochastic optimization problem over time-varying networks, in which agents aim to cooperatively minimize the expected value of the sum of their cost functions subject to coupled affine inequalities. Considering various stochastic factors and constraints on decisions inherent in physical environments, this problem has wide applications such as in smart grids, resource allocation and distributed machine learning. To solve this problem, a novel distributed stochastic primal-dual algorithm is devised by applying variance reduction and distributed tracking techniques. A complete and rigorous analysis shows that the developed algorithm linearly converges to the optimal solution in the mean square sense, and an explicit upper bound on the required constant stepsize is presented. Finally, a numerical example is conducted to illustrate the theoretical findings.

关键词： Distributed stochastic optimization Coupled affine inequality constraints primal-dual algorithm Variance reduction Linear convergence

来源：评论

学校读者我要写书评

暂无评论

A Splitting algorithm for Coupled System of primal-dual Monotone Inclusions

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2015年第3期164卷 993-1025页

作者： Vu, Bang Cong Univ Paris 06 Lab Jacques Louis Lions UMR CNRS 7598 F-75005 Paris France

We propose a splitting algorithm for solving a coupled system of primal-dual monotone inclusions in real Hilbert spaces. The proposed algorithm has a structure identical to that of the forward-backward algorithm with variable metric. The operators involved in the problem formulation are used separately in the sense that single-valued operators are used individually and approximately in the forward steps and multi-valued operators are used individually via their generalization resolvent in the backward steps. The weak convergence of the algorithm proposed is proved. Applications to coupled system of monotone inclusions in duality and minimization problems, and multi-dictionary signal representation are demonstrated.

关键词： Coupled system Monotone inclusion Monotone operator Operator splitting Cocoercivity Forward-backward algorithm Composite operator duality primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

primal-dual algorithms for Discounted Markov Decision Processes

Primal-Dual Algorithms for Discounted Markov Decision Proces...

引用

European Control Conference (ECC)

作者： Cogill, Randy IBM Res Ireland Dublin Ireland

ISBN: (纸本)9783952426937

Several well-known algorithms in the field of combinatorial optimization can be interpreted in terms of the primal-dual method for solving linear programs. For example, Dijkstra's algorithm, the Ford-Fulkerson algorithm, and the Hungarian algorithm can all be viewed as the primal-dual method applied to the linear programming formulations of their respective optimization problems. Roughly speaking, successfully applying the primal-dual method to an optimization problem that can be posed as a linear program relies on the ability to find a simple characterization of the optimal solutions to a related linear program, called the 'dual of the restricted primal' (DRP). This paper is motivated by the following question: What is the algorithm we obtain if we apply the primal-dual method to a linear programming formulation of a discounted cost Markov decision process? We will first show that a widely-used variant of the value iteration algorithm for Markov decision processes can be interpreted in terms of the primal-dual method, where the value function is updated with suboptimal solutions to the DRP in each iteration. We then provide the optimal solution to the DRP in closed-form, and present the algorithm that results when using this solution to update the value function in each iteration. Unlike the algorithms obtained from suboptimal DRP updates, this algorithm is guaranteed to yield the optimal value function in a finite number of iterations. Finally, we show that the iterations of the primal-dual algorithm can be interpreted as repeated application of the policy iteration algorithm to a special class of Markov decision processes. When considered alongside recent results characterizing the computational complexity of the policy iteration algorithm, this observation could provide new insights into the computational complexity of solving discounted-cost Markov decision processes.

关键词： Markov processes combinatorial mathematics computational complexity iterative methods linear programming DRP Markov decision process combinatorial optimization dual of the restricted primal primal-dual algorithm value iteration algorithm Computational complexity Computational modeling Convergence Linear programming Optimization Polynomials

来源：评论

学校读者我要写书评

暂无评论

A primal-dual Backward Reflected Forward Splitting algorithm for Structured Monotone Inclusions

引用

ACTA MATHEMATICA VIETNAMICA 2024年第2期49卷 159-172页

作者： Bang, Vu Cong Papadimitriou, Dimitri Nham, Vu Xuan Huawei Belgium Res Ctr BeRC Gaston Geenslaan B-4000 Leuven Belgium Univ Transport Technol Hanoi 120415 Vietnam

We propose a primal-dual backward reflected forward splitting method for solving structured primal-dual monotone inclusions in real Hilbert spaces. The algorithm allows to use the inexact computations of Lipschitzian and cocoercive operators. The strong convergence of the generated iterative sequence is proved under the strong monotonicity condition, whilst the weak convergence is formally proved under several conditions used in the literature. An application to a structured minimization problem is provided.

关键词： Monotone inclusion primal-dual algorithm Monotone operator Operator splitting Cocoercive Backward-forward Forward-backward Lipschitz Composite operator duality

来源：评论

学校读者我要写书评

暂无评论

New primal-dual algorithms for Steiner tree problems

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第7期34卷 2147-2167页

作者： Melkonian, Vardges Ohio Univ Dept Math Athens OH 45701 USA

We present new primal-dual algorithms for several network design problems. The problems considered are the generalized Steiner tree problem (GST), the directed Steiner tree problem (DST), and the set cover problem (SC) which is a subcase of DST. All our problems are NP-hard;so we are interested in their approximation algorithms. First, we give an algorithm for DST which is based on the traditional approach of designing primal-dual approximation algorithms. We show that the approximation factor of the algorithm is k, where k is the number of terminals. in the case when the problem is restricted to quasi-bipartite graphs. We also give pathologically bad examples for the algorithm performance. To overcome the problems exposed by the bad examples, we design a new framework for primal-dual algorithms which can be applied to all of our problems. The main feature of the new approach is that, unlike the traditional primal-dual algorithms, it keeps the dual solution in the interior of the dual feasible region. The new approach allows us to avoid including too many arcs in the solution, and thus achieves a smaller-cost solution. Our computational results show that the interior-point version of the primal-dual most of the time performs better than the original primal-dual method. (c) 2005 Published by Elsevier Ltd.

关键词： Steiner tree integer programming approximation algorithm primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear Convergence of First- and Zeroth-Order primal-dual algorithms for Distributed Nonconvex Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第8期67卷 4194-4201页

作者： Yi, Xinlei Zhang, Shengjun Yang, Tao Chai, Tianyou Johansson, Karl H. KTH Royal Inst Technol Sch Elect Engn & Comp Sci Div Decis & Control Syst S-11428 Stockholm Sweden Digital Futures S-11428 Stockholm Sweden Univ North Texas Dept Elect Engn Denton TX 76203 USA Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China

This article considers the distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of local cost functions by using local information exchange. We first consider a distributed first-order primal-dual algorithm. We show that it converges sublinearly to a stationary point if each local cost function is smooth and linearly to a global optimum under an additional condition that the global cost function satisfies the Polyak-Lojasiewicz condition. This condition is weaker than strong convexity, which is a standard condition for proving linear convergence of distributed optimization algorithms, and the global minimizer is not necessarily unique. Motivated by the situations where the gradients are unavailable, we then propose a distributed zeroth-order algorithm, derived from the considered first-order algorithm by using a deterministic gradient estimator, and show that it has the same convergence properties as the considered first-order algorithm under the same conditions. The theoretical results are illustrated by numerical simulations.

关键词： Convergence Cost function Convex functions Costs Technological innovation Lyapunov methods Laplace equations Distributed nonconvex optimization first-order algorithm linear convergence primal-dual algorithm zeroth-order algorithm

来源：评论

学校读者我要写书评

暂无评论

NEW primal-dual algorithmS FOR A CLASS OF NONSMOOTH AND NONLINEAR CONVEX-CONCAVE MINIMAX PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第4期32卷 2580-2611页

作者： Zhu, Yuzixuan Liu, Deyi Tran-Dinh, Quoc Univ North Carolina Chapel Hill UNC Dept Stat & Operat Res Chapel Hill NC 27599 USA

In this paper, we develop new primal-dual algorithms to solve a class of nonsmooth and nonlinear convex-concave minimax problems, which covers many existing and brand-new models as special cases. Our approach relies on a combination of a generalized augmented Lagrangian function, Nesterov's accelerated scheme, and adaptive parameter updating strategies. Our algorithmic framework is single-loop and unifies two important settings: general convex-concave and convex-linear cases. Under mild assumptions, our algorithms achieve O(1/k) convergence rates through three different criteria: primal-dual gap, primal objective residual, and dual objective residual, where k is the iteration counter. Our rates are both ergodic (i.e., on a weighted averaging sequence) and nonergodic (i.e., on the last-iterate sequence). These convergence rates can be boosted up to O(1/k2) if only one objective term is strongly convex (or, equivalently, its conjugate is L-smooth). To the best of our knowledge, this is the first algorithm achieving optimal rates on the primal last-iterate sequence for convex-linear minimax problems. As a byproduct, we specify our algorithms to solve a general convex cone constrained program with both ergodic and nonergodic rate guarantees. We test our algorithms and compare them with two recent methods on two numerical examples.

关键词： convex-concave minimax problem primal-dual algorithm optimal convergence rate last-iterate convergence rate Nesterov's accelerated scheme convex cone constrained program

来源：评论

学校读者我要写书评

暂无评论

FedHybrid: A Hybrid Federated Optimization Method for Heterogeneous Clients

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 150-163页

作者： Niu, Xiaochun Wei, Ermin Northwestern Univ Dept Ind Engn & Management Sci Evanston IL 60208 USA Northwestern Univ Dept Elect & Comp Engn Dept Ind Engn & Management Sci Evanston IL 60208 USA

We consider a distributed consensus optimization problem over a server-client (federated) network, where all clients are connected to a central server. Current distributed algorithms fail to capture the heterogeneity in clients' local computation capacities. Motivated by the method of multipliers in centralized optimization, we derive a Newton-type primal-dual method with a distributed implementation utilizing the server-client topology. Then we propose FedHybrid as a hybrid primal-dual method that allows heterogeneous clients to perform different types of updates. Specifically, those clients with higher computational capabilities and/or cheaper costs to perform computation can implement Newton-type updates locally, while other clients can adopt much simpler gradient-type updates. Theoretically, we propose a novel merit function by combining the dual optimality gap and the primal tracking error. We prove that FedHybrid converges linearly to the exact optimal point for strongly convex functions, regardless of clients' choices of gradient-type or Newton-type updates. Finally, we show numerical studies to demonstrate the efficacy of our method in practice. To the best of our knowledge, this is the first hybrid method allowing heterogeneous local updates for distributed consensus optimization with provable convergence and rate guarantees.

关键词： Optimization Convergence Servers Topology Newton method Hardware Convex functions Server-client networks distributed optimization primal-dual algorithm heterogeneous systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：