检索结果-南通市图书馆

Science China Mathematics 2016年第1期59卷 141-160页

作者： WEN YouWei CHAN Raymond Honfu ZENG TieYong Faculty of Science Kunming University of Science and TechnologyKunming 650093China Department of Mathematics The Chinese University of Hong KongShatinHong KongChina Department of Mathematics Hong Kong Baptist UniversityKowloonHong KongChina

We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler(KL)-divergence term for the Poisson noise and a total variation(TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers(ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock's first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.

关键词： image restoration Poisson noise total variation (TV) alternating direction method of multipliers (ADMM) primal-dual minimax problem

维普期刊数据库

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

在线全文

学校读者我要写书评

暂无评论

Frontiers of Computer Science 2023年第3期17卷 125-132页

作者： Xiaofei LIU Weidong LI Jinhua YANG School of Information Science and Engineering Yunnan UniversityKunming 650500China School of Mathematics and Statistics Yunnan UniversityKunming 650500China Dianchi College of Yunnan University Kunming 650228China

In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular *** are given a cost graph and an *** problem determines a vertex set such that covers at least *** objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular *** design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the *** the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor *** the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.

关键词： vertex cover k-prize-collecting primal-dual approximation algorithm

维普期刊数据库

Convex relaxation for a 3D spatiotemporal segmentation model using the primal-dual method

在线全文

学校读者我要写书评

暂无评论

Journal of Zhejiang University-Science C(Computers and Electronics) 2012年第6期13卷 428-439页

作者： Shi-yan WANG Hui-min YU Department of Information Science&Electronic Engineering Zhejiang UniversityHangzhou 310027China

A method based on 3D videos is proposed for multi-target segmentation and tracking with a moving viewing system. A spatiotemporal energy functional is built up to perform motion segmentation and estimation simultaneously. To overcome the limitation of the local minimum problem with the level set method, a convex relaxation method is applied to the 3D spatiotemporal segmentation model. The relaxed convex model is independent of the initial condition. A primal-dual algorithm is used to improve computational efficiency. Several indoor experiments show the validity of the proposed method.

关键词： 3D spatiotemporal segmentation Motion estimation Total variation primal-dual

维普期刊数据库

A primal-dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

在线全文

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2017年第2期5卷 219-231页

作者： Lu Han Da-Chuan Xu Dong-Lei Du Chen-Chen Wu Department of Information and Operations Research Beijing University of TechnologyBeijing 100124China Faculty of Business Administration University of New BrunswickFrederictonNB E3B 5A3Canada College of Science Tianjin University of TechnologyTianjin 300384China

In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest *** this problem,we are given a connected graph G=(V,E)and a set of vertex sets V={V1,V2,…,Vl}.Every edge in E has a nonnegative cost,and every vertex set in V has a nonnegative penalty *** a given edge set F⊆E,vertex set Vi∈V is said to be connected by edge set F if Vi is in a connected component of the F-spanned *** objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is *** main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

关键词： Prize-collecting Steiner forest Approximation algorithm primal-dual

A primal-dual Hybrid Gradient Algorithm to Solve the LLT Model for Image Denoising

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Numerical Mathematics(Theory,Methods and Applications) 2012年第2期5卷 260-277页

作者： Chunxiao Liu Dexing Kong Shengfeng Zhu Department of Mathematics Hangzhou Normal UniversityHangzhou 310036China Department of Mathematics Zhejiang UniversityHangzhouChina

We propose an efficient gradient-type algorithm to solve the fourth-order LLT denoising model for both gray-scale and vector-valued *** on the primal-dual formulation of the original nondifferentiable model,the new algorithm updates the primal and dual variables alternately using the gradient descent/ascent *** examples are provided to demonstrate the superiority of our algorithm.

关键词： LLT model image denoising primal-dual

A primal-dual Simplex Algorithm for Solving Linear Programming Problems with Symmetric Trapezoidal Fuzzy Numbers

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Applied Mathematics 2011年第6期2卷 676-684页

作者： Ali Ebrahimnejad 不详

Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy primal simplex method proposed by Ganesan and Veeramani [1] and the fuzzy dual simplex method proposed by Ebrahimnejad and Nasseri [2]. The former method is not applicable when a primal basic feasible solution is not easily at hand and the later method needs to an initial dual basic feasible solution. In this paper, we develop a novel approach namely the primal-dual simplex algorithm to overcome mentioned shortcomings. A numerical example is given to illustrate the proposed approach.

关键词： Fuzzy Linear Programming Fuzzy Arithmetic Fuzzy Orders primal-dual Simplex Algorithm

Approximation Algorithms for the Priority Facility Location Problem with Penalties

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2015年第5期28卷 1102-1114页

作者： WANG Fengmin XU Dachuan WU Chenchen College of Applied Sciences Beijing University of Technology College of Science Tianjin University of Technology

This paper considers the priority facility location problem with penalties. The authors develop a primal-dual 3-approximation algorithm for this problem. Combining with the greedy augmentation procedure, the authors f... 详细信息

关键词： Approximation algorithm facility location problem greedy augmentation primal-dual

A ROBUST INTERIOR POINT METHOD FOR COMPUTING THE ANALYTIC CENTER OF AN ILL-CONDITIONED POLYTOPE WITH ERRORS

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Computational Mathematics 2019年第6期37卷 843-865页

作者： Zhouhong Wang Yuhong Dai Fengmin Xu School of Science Beijing Jiaotong UniversityBeijing 100044China LESC ICMSECAcademy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing 100190and School of Mathematical SciencesUniversity of Chinese Academy of Sciencest Beijing 100049China School of Economics and Finance Xi'an Jiaotong UniversityXi'an 710061China

In this paper we propose an efficient and robust method for computing the analytic center of the polyhedral set P={x€R^n|Ax=b,x>0},where the matrix A€ Rm×n is ill-conditioned,and there are errors in A and *** overcoming the difficulties caused by ill-cond计ioning of the matrix A and errors in A and b,our method can also detect the infeasibility and the unboundedness of the polyhedral set P automatically during the compu *** ailed mat hematical analyses for our method are presen ted and the worst case complexity of the algorithm is also *** some numerical results are presented to show the robustness and effectiveness of the new method.

关键词： Analytic center Ill-conditioning Unboundedness primal-dual interior point algorithm Convergence Polynomial complexity

A FIRST-ORDER SPLITTING METHOD FOR SOLVING A LARGE-SCALE COMPOSITE CONVEX OPTIMIZATION PROBLEM

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Computational Mathematics 2019年第5期37卷 666-688页

作者： Yuchao Tang Guorong Wu Chuanxi Zhu School of Management Nanchang UniversityNanchang 330031China Department of Mathematics Nanchang UniversityNanchang 330031China Department of Radiology and BRIC University of North Carolina at Chapel HillNC27599USA

In this paper, we construct several efficient first-order splitting algorithms for solving a multi-block composite convex optimization problem. The objective function includes a smooth function with a Lipschitz continuous gradient, a proximable convex function that may be nonsmooth, and a finite sum composed of a proximable function and a bounded linear operator. To solve such an optimization problem, we transform it into the sum of three convex functions by defining an appropriate inner product space. Based on the dual forward-backward splitting algorithm and the primal-dual forward-backward splitting algorithm, we develop several iterative algorithms that involve only computing the gradient of the differentiable function and proximity operators of related convex functions. These iterative algorithms are matrix-inversion-free and completely splitting algorithms. Finally, we employ the proposed iterative algorithms to solve a regularized general prior image constrained compressed sensing model that is derived from computed tomography image reconstruction. Numerical results show that the proposed iterative algorithms outperform the compared algorithms including the alternating direction method of multipliers, the splitting primal-dual proximity algorithm, and the preconditioned splitting primal-dual proximity algorithm.

关键词： Forward-backward splitting method primal-dual dual Proximity operator

An approximation algorithm for k-median with priorities

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2021年第5期64卷 45-46页

作者： Zhen ZHANG Qilong FENG Jinhui XU Jianxin WANG School of Computer Science and Engineering Central South University Department of Computer Science and Engineering State University of New York at Buffalo

Dear editor,Clustering is a fundamental problem in computer *** problem is to partition a given set of clients into several clusters such that clients in the same cluster are more similar to each other. In many clustering applications, the clients are different in the levels of services they require. Motivated by such applications, Ravi and Sinha [1] introduced the problem of clustering with priorities, wherein each client is associated with a priority and can only be assigned to a facility opened at the same or higher priorities.

关键词： Clustering k median approximation algorithm LP relaxtion primal-dual