The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of...The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of many machine learning techniques with data parallelism,such as deep learning and federated learning.We propose a distributed primal-dual stochastic gradient descent(SGD)algorithm,suitable for arbitrarily connected communication networks and any smooth(possibly nonconvex)cost functions.We show that the proposed algorithm achieves the linear speedup convergence rate O(1/(√nT))for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak-Lojasiewicz(P-L)condition,where T is the total number of iterations.We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum.We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms.展开更多
In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to...In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.展开更多
Neutron computed tomography(NCT)is widely used as a noninvasive measurement technique in nuclear engineering,thermal hydraulics,and cultural heritage.The neutron source intensity of NCT is usually low and the scan tim...Neutron computed tomography(NCT)is widely used as a noninvasive measurement technique in nuclear engineering,thermal hydraulics,and cultural heritage.The neutron source intensity of NCT is usually low and the scan time is long,resulting in a projection image containing severe noise.To reduce the scanning time and increase the image reconstruction quality,an effective reconstruction algorithm must be selected.In CT image reconstruction,the reconstruction algorithms can be divided into three categories:analytical algorithms,iterative algorithms,and deep learning.Because the analytical algorithm requires complete projection data,it is not suitable for reconstruction in harsh environments,such as strong radia-tion,high temperature,and high pressure.Deep learning requires large amounts of data and complex models,which cannot be easily deployed,as well as has a high computational complexity and poor interpretability.Therefore,this paper proposes the OS-SART-PDTV iterative algorithm,which uses the ordered subset simultaneous algebraic reconstruction technique(OS-SART)algorithm to reconstruct the image and the first-order primal–dual algorithm to solve the total variation(PDTV),for sparse-view NCT three-dimensional reconstruction.The novel algorithm was compared with other algorithms(FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV)by simulating the experimental data and actual neutron projection experiments.The reconstruction results demonstrate that the proposed algorithm outperforms the FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV algorithms in terms of preserving edge structure,denoising,and suppressing artifacts.展开更多
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 simpl...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.展开更多
In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local ...In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.展开更多
To preserve the edges and details of the image,a new variational model for wavelet domain inpainting was proposed which contained a non-convex regularizer. The non-convex regularizer can utilize the local information ...To preserve the edges and details of the image,a new variational model for wavelet domain inpainting was proposed which contained a non-convex regularizer. The non-convex regularizer can utilize the local information of image and perform better than those usual convex ones. In addition, to solve the non-convex minimization problem,an iterative reweighted method and a primaldual method were designed. The numerical experiments show that the new model not only gets better visual effects but also obtains higher signal to noise ratio than the recent method.展开更多
Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields ...Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.展开更多
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 c...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.展开更多
In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest problem.In this problem,we are given a connected graph G=(V,E)and a set of vertex sets V=...In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest problem.In 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 cost.For 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 subgraph.The 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 minimized.Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.展开更多
This paper investigates two distributed accelerated primal-dual neurodynamic approaches over undirected connected graphs for resource allocation problems(RAP)where the objective functions are generally convex.With the...This paper investigates two distributed accelerated primal-dual neurodynamic approaches over undirected connected graphs for resource allocation problems(RAP)where the objective functions are generally convex.With the help of projection operators,a primal-dual framework,and Nesterov's accelerated method,we first design a distributed accelerated primal-dual projection neurodynamic approach(DAPDP),and its convergence rate of the primal-dual gap is O(1/(t^(2)))by selecting appropriate parameters and initial values.Then,when the local closed convex sets are convex inequalities which have no closed-form solutions of their projection operators,we further propose a distributed accelerated penalty primal-dual neurodynamic approach(DAPPD)on the strength of the penalty method,primal-dual framework,and Nesterov's accelerated method.Based on the above analysis,we prove that DAPPD also has a convergence rate O(1/(t^(2)))of the primal-dual gap.Compared with the distributed dynamical approaches based on the classical primal-dual framework,our proposed distributed accelerated neurodynamic approaches have faster convergence rates.Numerical simulations demonstrate that our proposed neurodynamic approaches are feasible and effective.展开更多
This paper studies the distributed optimization problem when the objective functions might be nondifferentiable and subject to heterogeneous set constraints.Unlike existing subgradient methods,the authors focus on the...This paper studies the distributed optimization problem when the objective functions might be nondifferentiable and subject to heterogeneous set constraints.Unlike existing subgradient methods,the authors focus on the case when the exact subgradients of the local objective functions can not be accessed by the agents.To solve this problem,the authors propose a projected primaldual dynamics using only the objective function’s approximate subgradients.The authors first prove that the formulated optimization problem can generally be solved with an error depending upon the accuracy of the available subgradients.Then,the authors show the exact solvability of this distributed optimization problem when the accumulated approximation error of inexact subgradients is not too large.After that,the authors also give a novel componentwise normalized variant to improve the transient behavior of the convergent sequence.The effectiveness of the proposed algorithms is verified by a numerical example.展开更多
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 vert...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 penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The 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 function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When 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.展开更多
Nonlinear convex cone programming(NCCP)models have found many practical applications.In this paper,we introduce a flexible first-order primal-dual algorithm,called the variant auxiliary problem principle(VAPP),for sol...Nonlinear convex cone programming(NCCP)models have found many practical applications.In this paper,we introduce a flexible first-order primal-dual algorithm,called the variant auxiliary problem principle(VAPP),for solving NCCP problems when the objective function and constraints are convex but may be nonsmooth.At each iteration,VAPP generates a nonlinear approximation of the primal augmented Lagrangian model.The approximation incorporates both linearization and a distance-like proximal term,and then the iterations of VAPP are shown to possess a decomposition property for NCCP.Motivated by recent applications in big data analytics,there has been a growing interest in the convergence rate analysis of algorithms with parallel computing capabilities for large scale optimization problems.We establish O(1/t)convergence rate towards primal optimality,feasibility and dual optimality.By adaptively setting parameters at different iterations,we show an O(1/t2)rate for the strongly convex case.Finally,we discuss some issues in the implementation of VAPP.展开更多
We have proposed a primal-dual fixed point algorithm （PDFP） for solving minimiza- tion of the sum of three convex separable functions, which involves a smooth function with Lipschitz continuous gradient, a linear co...We have proposed a primal-dual fixed point algorithm （PDFP） for solving minimiza- tion of the sum of three convex separable functions, which involves a smooth function with Lipschitz continuous gradient, a linear composite nonsmooth function, and a nonsmooth function. Compared with similar works, the parameters in PDFP are easier to choose and are allowed in a relatively larger range. We will extend PDFP to solve two kinds of separable multi-block minimization problems, arising in signal processing and imaging science. This work shows the flexibility of applying PDFP algorithm to multi-block prob- lems and illustrates how practical and fully splitting schemes can be derived, especially for parallel implementation of large scale problems. The connections and comparisons to the alternating direction method of multiplier （ADMM） are also present. We demonstrate how different algorithms can be obtained by splitting the problems in different ways through the classic example of sparsity regularized least square model with constraint. In particular, for a class of linearly constrained problems, which are of great interest in the context of multi-block ADMM, can be also solved by PDFP with a guarantee of convergence. Finally, some experiments are provided to illustrate the performance of several schemes derived by the PDFP algorithm.展开更多
In this paper,we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP).This add a new type of functions to the class of eligible kernel functions....In this paper,we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP).This add a new type of functions to the class of eligible kernel functions.We prove that the interior-point algorithm based on the new kernel function meets O(n3/4 logε/n)iterations as the worst case complexity bound for the large-update method.This coincides with the complexity bound obtained by the first kernel function with a trigonometric barrier term proposed by El Ghami et al.in2012,and improves with a factor n(1/4)the obtained iteration bound based on the classic kernel function.We present some numerical simulations which show the effectiveness of the algorithm developed in this paper.展开更多
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 simultaneou...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.展开更多
In this paper,we consider an optimization problem of the grasping manipulation of multi-fingered hand-arm robots.We first formulate an optimization model for the problem,based on the dynamic equations of the object a...In this paper,we consider an optimization problem of the grasping manipulation of multi-fingered hand-arm robots.We first formulate an optimization model for the problem,based on the dynamic equations of the object and the friction constraints.Then,we reformulate the model as a convex quadratic programming over circular cones.Moreover,we propose a primal-dual interior-point algorithm based on the kernel function to solve this convex quadratic programming over circular cones.We derive both the convergence of the algorithm and the iteration bounds for largeand small-update methods,respectively.Finally,we carry out the numerical tests of 180◦and 90◦manipulations of the hand-arm robot to demonstrate the effectiveness of the proposed algorithm.展开更多
基金supported by the Knut and Alice Wallenberg Foundationthe Swedish Foundation for Strategic Research+1 种基金the Swedish Research Councilthe National Natural Science Foundation of China(62133003,61991403,61991404,61991400)。
文摘The distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of n local cost functions by using local information exchange is considered.This problem is an important component of many machine learning techniques with data parallelism,such as deep learning and federated learning.We propose a distributed primal-dual stochastic gradient descent(SGD)algorithm,suitable for arbitrarily connected communication networks and any smooth(possibly nonconvex)cost functions.We show that the proposed algorithm achieves the linear speedup convergence rate O(1/(√nT))for general nonconvex cost functions and the linear speedup convergence rate O(1/(nT)) when the global cost function satisfies the Polyak-Lojasiewicz(P-L)condition,where T is the total number of iterations.We also show that the output of the proposed algorithm with constant parameters linearly converges to a neighborhood of a global optimum.We demonstrate through numerical experiments the efficiency of our algorithm in comparison with the baseline centralized SGD and recently proposed distributed SGD algorithms.
文摘In the present paper we present a class of polynomial primal-dual interior-point algorithms for semidefmite optimization based on a kernel function. This kernel function is not a so-called self-regular function due to its growth term increasing linearly. Some new analysis tools were developed which can be used to deal with complexity ＂analysis of the algorithms which use analogous strategy in [5] to design the search directions for the Newton system. The complexity bounds for the algorithms with large- and small-update methodswere obtained, namely,O（qn^（p＋q/q（P＋1）log n/ε and O（q^2√n）log n/ε,respectlvely.
基金supported by the National Key Research and Development Program of China(No.2022YFB1902700)the Joint Fund of Ministry of Education for Equipment Pre-research(No.8091B042203)+5 种基金the National Natural Science Foundation of China(No.11875129)the Fund of the State Key Laboratory of Intense Pulsed Radiation Simulation and Effect(No.SKLIPR1810)the Fund of Innovation Center of Radiation Application(No.KFZC2020020402)the Fund of the State Key Laboratory of Nuclear Physics and Technology,Peking University(No.NPT2023KFY06)the Joint Innovation Fund of China National Uranium Co.,Ltd.,State Key Laboratory of Nuclear Resources and Environment,East China University of Technology(No.2022NRE-LH-02)the Fundamental Research Funds for the Central Universities(No.2023JG001).
文摘Neutron computed tomography(NCT)is widely used as a noninvasive measurement technique in nuclear engineering,thermal hydraulics,and cultural heritage.The neutron source intensity of NCT is usually low and the scan time is long,resulting in a projection image containing severe noise.To reduce the scanning time and increase the image reconstruction quality,an effective reconstruction algorithm must be selected.In CT image reconstruction,the reconstruction algorithms can be divided into three categories:analytical algorithms,iterative algorithms,and deep learning.Because the analytical algorithm requires complete projection data,it is not suitable for reconstruction in harsh environments,such as strong radia-tion,high temperature,and high pressure.Deep learning requires large amounts of data and complex models,which cannot be easily deployed,as well as has a high computational complexity and poor interpretability.Therefore,this paper proposes the OS-SART-PDTV iterative algorithm,which uses the ordered subset simultaneous algebraic reconstruction technique(OS-SART)algorithm to reconstruct the image and the first-order primal–dual algorithm to solve the total variation(PDTV),for sparse-view NCT three-dimensional reconstruction.The novel algorithm was compared with other algorithms(FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV)by simulating the experimental data and actual neutron projection experiments.The reconstruction results demonstrate that the proposed algorithm outperforms the FBP,OS-SART-TV,OS-SART-AwTV,and OS-SART-FGPTV algorithms in terms of preserving edge structure,denoising,and suppressing artifacts.
文摘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.
文摘In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.
基金National Natural Science Foundations of China(Nos.61301229,61101208)Doctoral Research Funds of Henan University of Science and Technology,China(Nos.09001708,09001751)
文摘To preserve the edges and details of the image,a new variational model for wavelet domain inpainting was proposed which contained a non-convex regularizer. The non-convex regularizer can utilize the local information of image and perform better than those usual convex ones. In addition, to solve the non-convex minimization problem,an iterative reweighted method and a primaldual method were designed. The numerical experiments show that the new model not only gets better visual effects but also obtains higher signal to noise ratio than the recent method.
基金Supported by National Natural Science Foundation of China (Grant Nos.10771133 and 70871082)Shanghai Leading Academic Discipline Project (Grant No.S30104)
文摘Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.
基金supported by National Natural Science Foundation of China(Grant Nos.1136103011271049 and 11271049)+5 种基金the Project Sponsored by the Scientific Research Foundation for the Returned Overseas Chinese ScholarsState Education Ministry(Grant Nos.CUHK400412HKBU502814211911and 12302714)Hong Kong Research Grants Council(Grant No.Ao E/M-05/12)FRGs of Hong Kong Baptist University
文摘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.
基金the National Natural Science Foundation of China(No.11371001)Collaborative Innovation Center on Beijing Society-Building and Social Governance.D.-L.Du is supported by the Natural Sciences and Engineering Research Council of Canada(No.06446).C.-C.Wu is supported by the National Natural Science Foundation of China(No.11501412).
文摘In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest problem.In 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 cost.For 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 subgraph.The 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 minimized.Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.
基金supported by the National Natural Science Foundation of China (Grant No.62176218)the Fundamental Research Funds for the Central Universities (Grant No.XDJK2020TY003)。
文摘This paper investigates two distributed accelerated primal-dual neurodynamic approaches over undirected connected graphs for resource allocation problems(RAP)where the objective functions are generally convex.With the help of projection operators,a primal-dual framework,and Nesterov's accelerated method,we first design a distributed accelerated primal-dual projection neurodynamic approach(DAPDP),and its convergence rate of the primal-dual gap is O(1/(t^(2)))by selecting appropriate parameters and initial values.Then,when the local closed convex sets are convex inequalities which have no closed-form solutions of their projection operators,we further propose a distributed accelerated penalty primal-dual neurodynamic approach(DAPPD)on the strength of the penalty method,primal-dual framework,and Nesterov's accelerated method.Based on the above analysis,we prove that DAPPD also has a convergence rate O(1/(t^(2)))of the primal-dual gap.Compared with the distributed dynamical approaches based on the classical primal-dual framework,our proposed distributed accelerated neurodynamic approaches have faster convergence rates.Numerical simulations demonstrate that our proposed neurodynamic approaches are feasible and effective.
基金supported by the National Natural Science Foundation of China under Grant No.61973043。
文摘This paper studies the distributed optimization problem when the objective functions might be nondifferentiable and subject to heterogeneous set constraints.Unlike existing subgradient methods,the authors focus on the case when the exact subgradients of the local objective functions can not be accessed by the agents.To solve this problem,the authors propose a projected primaldual dynamics using only the objective function’s approximate subgradients.The authors first prove that the formulated optimization problem can generally be solved with an error depending upon the accuracy of the available subgradients.Then,the authors show the exact solvability of this distributed optimization problem when the accumulated approximation error of inexact subgradients is not too large.After that,the authors also give a novel componentwise normalized variant to improve the transient behavior of the convergent sequence.The effectiveness of the proposed algorithms is verified by a numerical example.
基金The work was supported in part by the National Natural Science Foundation of China(Grant No.12071417)。
文摘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 penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The 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 function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When 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.
基金This research was supported by the National Natural Science Foundation of China(Nos.71471112 and 71871140).
文摘Nonlinear convex cone programming(NCCP)models have found many practical applications.In this paper,we introduce a flexible first-order primal-dual algorithm,called the variant auxiliary problem principle(VAPP),for solving NCCP problems when the objective function and constraints are convex but may be nonsmooth.At each iteration,VAPP generates a nonlinear approximation of the primal augmented Lagrangian model.The approximation incorporates both linearization and a distance-like proximal term,and then the iterations of VAPP are shown to possess a decomposition property for NCCP.Motivated by recent applications in big data analytics,there has been a growing interest in the convergence rate analysis of algorithms with parallel computing capabilities for large scale optimization problems.We establish O(1/t)convergence rate towards primal optimality,feasibility and dual optimality.By adaptively setting parameters at different iterations,we show an O(1/t2)rate for the strongly convex case.Finally,we discuss some issues in the implementation of VAPP.
文摘We have proposed a primal-dual fixed point algorithm （PDFP） for solving minimiza- tion of the sum of three convex separable functions, which involves a smooth function with Lipschitz continuous gradient, a linear composite nonsmooth function, and a nonsmooth function. Compared with similar works, the parameters in PDFP are easier to choose and are allowed in a relatively larger range. We will extend PDFP to solve two kinds of separable multi-block minimization problems, arising in signal processing and imaging science. This work shows the flexibility of applying PDFP algorithm to multi-block prob- lems and illustrates how practical and fully splitting schemes can be derived, especially for parallel implementation of large scale problems. The connections and comparisons to the alternating direction method of multiplier （ADMM） are also present. We demonstrate how different algorithms can be obtained by splitting the problems in different ways through the classic example of sparsity regularized least square model with constraint. In particular, for a class of linearly constrained problems, which are of great interest in the context of multi-block ADMM, can be also solved by PDFP with a guarantee of convergence. Finally, some experiments are provided to illustrate the performance of several schemes derived by the PDFP algorithm.
文摘In this paper,we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP).This add a new type of functions to the class of eligible kernel functions.We prove that the interior-point algorithm based on the new kernel function meets O(n3/4 logε/n)iterations as the worst case complexity bound for the large-update method.This coincides with the complexity bound obtained by the first kernel function with a trigonometric barrier term proposed by El Ghami et al.in2012,and improves with a factor n(1/4)the obtained iteration bound based on the classic kernel function.We present some numerical simulations which show the effectiveness of the algorithm developed in this paper.
基金supported by the National Natural Science Foundation of China (No. 60872069)the National Basic Research Program (973)of China (No. 2012CB316400)
文摘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.
基金the National Natural Science Foundation of China(No.11371242)。
文摘In this paper,we consider an optimization problem of the grasping manipulation of multi-fingered hand-arm robots.We first formulate an optimization model for the problem,based on the dynamic equations of the object and the friction constraints.Then,we reformulate the model as a convex quadratic programming over circular cones.Moreover,we propose a primal-dual interior-point algorithm based on the kernel function to solve this convex quadratic programming over circular cones.We derive both the convergence of the algorithm and the iteration bounds for largeand small-update methods,respectively.Finally,we carry out the numerical tests of 180◦and 90◦manipulations of the hand-arm robot to demonstrate the effectiveness of the proposed algorithm.
