Polynomial Convergence of Primal-Dual Path-Following Algorithms for Symmetric Cone Programming Based on Wide Neighborhoods and a New Class of Directions

This paper presents a class of primal-dual path-following interior-point algorithms for symmetric cone programming(SCP)based on wide neighborhoods and new directions with a parameterθ.When the parameterθ=1,the direction is exactly the classical Newton direction.When the parameterθis independent of the rank of the associated Euclidean Jordan algebra,the algorithm terminates in at most O(κr logε−1)iterations,which coincides with the best known iteration bound for the classical wide neighborhood algorithms.When the parameterθ=√n/βτand Nesterov–Todd search direction is used,the algorithm has O(√r logε−1)iteration complexity,the best iteration complexity obtained so far by any interior-point method for solving SCP.To our knowledge,this is the first time that a class of interior-point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed over symmetric cone.

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 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.

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 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.

Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.

Approximation Algorithms for the Priority Facility Location Problem with Penalties

develop a mentation This paper considers the priority facility primal-dual 3-approximation algorithm for procedure, the authors further improve the location problem with penalties： The authors this problem. Combining with the greedy aug- previous ratio 3 to 1.8526.

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.

Path-following interior point algorithms for the Cartesian P_*(κ)-LCP over symmetric cones

In this paper, we establish a theoretical framework of path-following interior point al- gorithms for the linear complementarity problems over symmetric cones (SCLCP) with the Cartesian P*(κ)-property, a weaker condition than the monotonicity. Based on the Nesterov-Todd, xy and yx directions employed as commutative search directions for semidefinite programming, we extend the variants of the short-, semilong-, and long-step path-following algorithms for symmetric conic linear programming proposed by Schmieta and Alizadeh to the Cartesian P*(κ)-SCLCP, and particularly show the global convergence and the iteration complexities of the proposed algorithms.

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.

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.

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.

A variational formulation for physical noised image segmentation

Image segmentation is a hot topic in image science. In this paper we present a new variational segmentation model based on the theory of Mumford-Shah model. The aim of our model is to divide noised image, according to a certain criterion, into homogeneous and smooth regions that should correspond to structural units in the scene or objects of interest. The proposed region-based model uses total variation as a regularization term, and different fidelity term can be used for image segmentation in the cases of physical noise, such as Gaussian, Poisson and multiplicative speckle noise. Our model consists of five weighted terms, two of them are responsible for image denoising based on fidelity term and total variation term, the others assure that the three conditions of adherence to the data, smoothing, and discontinuity detection are met at once. We also develop a primal-dual hybrid gradient algorithm for our model. Numerical results on various synthetic and real images are provided to compare our method with others, these results show that our proposed model and algorithms are effective.

An Approximation Algorithm for P-prize-collecting Set Cover Problem

In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

Complexity Analysis of an Interior Point Algorithm for the Semidefinite Optimization Based on a Kernel Function with a Double Barrier Term

In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization（SDO） problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 〉 q2 〉 1, the algorithm has O（（q1 ＋ 1） nq1＋1/2（q1-q2）logn/ε）and O（（q1 ＋ 1）2（q1-q2）^3q1-2q2＋1√n logn/c） complexity results for large- and small-update methods, respectively.

An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties

In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→R_(+)is a submodular penalty function.The objective of the GPCSF-SP problem is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection S containing these Vi not connected by F is minimized.By using the primal-dual technique,we give a 3-approximation algorithm for this problem.

AN EXTENSION OF PREDICTOR-CORRECTOR ALGORITHM TO A CLASS OF CONVEX SEPARABLE PROGRAM

redictor-corrector algorithm for linear programming, proposed by Mizuno et al. [1], becomes the best-known in the interior point methods. In this paper it is modified and then extended to solving a class of convex separable programming problems.

A Two-Stage Color Image Segmentation Method Based on Saturation-Value Total Variation

Color image segmentation is crucial in image processing and computer vision.Most traditional segmentation methods simply regard an RGB color image as the direct combination of the three monochrome images and ignore the inherent color structures within channels,which contain some key feature information of the image.To better describe the relationship of color channels,we introduce a quaternion-based regularization that can reflect the image characteristics more intuitively.Our model combines the idea of the Mumford-Shah model-based two-stage segmentation method and the Saturation-Value Total Variation regularization for color image segmentation.The new strategy first extracts features from the color image and then subdivides the image in a new color feature space which achieves better performance than methods in RGB color space.Moreover,to accelerate the optimization process,we use a new primal-dual algorithm to solve our novel model.Numerical results demonstrate clearly that the performance of our proposed method is excellent.

Total Variation Based Parameter-Free Model for Impulse Noise Removal

We propose a new two-phase method for reconstruction of blurred im-ages corrupted by impulse noise.In the first phase,we use a noise detector to iden-tify the pixels that are contaminated by noise,and then,in the second phase,we reconstruct the noisy pixels by solving an equality constrained total variation mini-mization problem that preserves the exact values of the noise-free pixels.For images that are only corrupted by impulse noise(i.e.,not blurred)we apply the semismooth Newton’s method to a reduced problem,and if the images are also blurred,we solve the equality constrained reconstruction problem using a first-order primal-dual algo-rithm.The proposed model improves the computational efficiency(in the denoising case)and has the advantage of being regularization parameter-free.Our numerical results suggest that the method is competitive in terms of its restoration capabilities with respect to the other two-phase methods.