First-order primal-dual algorithm for sparse-view neutron computed tomography-based three-dimensional image reconstruction

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.

A class of polynomial primal-dual interior-point algorithms for semidefinite optimization

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.

A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization

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.

A Primal-Dual Simplex Algorithm for Solving Linear Programming Problems with Symmetric Trapezoidal Fuzzy Numbers

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.

Weighted Variational Minimization Model for Wavelet Domain Inpainting with Primal-Dual Method

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.

A Primal-dual Interior Point Method for Nonlinear Programming

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.

A Primal-Dual Infeasible-Interior-Point Algorithm for Multiple Objective Linear Programming Problems

A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.

Distributed accelerated primal-dual neurodynamic approaches for resource allocation problem

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.

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

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.

Primal-Dual ε-Subgradient Method for Distributed Optimization

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.

A New Kernel Function Yielding the Best Known Iteration Bounds for Primal-Dual Interior-Point Algorithms

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.

A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

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.

A PRIMAL-DUAL FIXED POINT ALGORITHM FOR MULTI-BLOCK CONVEX MINIMIZATION

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.

Adaptive Parallel Primal-Dual Method for Saddle Point Problems

The primal-dual hybrid gradient method is a classic way to tackle saddle-point problems.However,its convergence is not guaranteed in general.Some restric-tions on the step size parameters,e.g.,τσ≤1/||A^(T)A||,are imposed to guarantee the convergence.In this paper,a new convergent method with no restriction on parame-ters is proposed.Hence the expensive calculation of ||A^(T)A|| is avoided.This method produces a predictor like other primal-dual methods but in a parallel fashion,which has the potential to speed up the method.This new iterate is then updated by a sim-ple correction to guarantee the convergence.Moreover,the parameters are adjusted dynamically to enhance the efficiency as well as the robustness of the method.The generated sequence monotonically converges to the solution set.A worst-case O(1/t)convergence rate in ergodic sense is also established under mild assumptions.The nu-merical efficiency of the proposed method is verified by applications in LASSO problem and Steiner tree problem.

Several Variants of the Primal-Dual Hybrid Gradient Algorithm with Applications

By reviewing the primal-dual hybrid gradient algorithm(PDHG)pro-posed by He,You and Yuan(SIAM J.Image Sci.,7(4)(2014),pp.2526–2537),in this paper we introduce four improved schemes for solving a class of saddle-point problems.Convergence properties of the proposed algorithms are ensured based on weak assumptions,where none of the objective functions are assumed to be strongly convex but the step-sizes in the primal-dual updates are more flexible than the pre-vious.By making use of variational analysis,the global convergence and sublinear convergence rate in the ergodic/nonergodic sense are established,and the numer-ical efficiency of our algorithms is verified by testing an image deblurring problem compared with several existing algorithms.

Novel Kernel Function With a Hyperbolic Barrier Term to Primal-dual Interior Point Algorithm for SDP Problems

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 Primal-Dual Interior-Point Method for Optimal Grasping Manipulation of Multi-fingered Hand-Arm Robots

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.

On Iteration Complexity of a First-Order Primal-Dual Method for Nonlinear Convex Cone Programming

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.

A Primal-Dual Hybrid Gradient Algorithm to Solve the LLT Model for Image Denoising

We propose an efficient gradient-type algorithm to solve the fourth-order LLT denoising model for both gray-scale and vector-valued images.Based 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 flows.Numerical examples are provided to demonstrate the superiority of our algorithm.