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 new primal-dual interior-point algorithm for convex quadratic optimization

In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization （CQO） based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method （IPM） to O（√n log nlog n/e）, which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.

Primal-Dual Interior-Point Algorithms with Dynamic Step-Size Based on Kernel Functions for Linear Programming

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.

A new primal-dual path-following interior-point algorithm for linearly constrained convex optimization

In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization(LCCO) is presented.The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path.At each iteration, only full-Newton steps are used.Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O(√n log n /ε).

A NEW FRAMEWORK OF PRIMAL-DUAL INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING

On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.

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.

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.

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.

A New Infeasible Interior-point Method for Linear Complementarity Problem Based on Full Newton Step

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last,we prove that the algorithm has O(nlog n/ε) polynomial complexity,which coincides with the best known one for the infeasible interior-point algorithm at present.

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interiorpoint method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.

A CORRECTOR-PREDICTOR ARC SEARCH INTERIOR-POINT ALGORITHM FOR SYMMETRIC OPTIMIZATION

In this paper, a corrector-predictor interior-point algorithm is proposed for sym- metric optimization. The algorithm approximates the central path by an ellipse, follows the ellipsoidal approximation of the central-path step by step and generates a sequence of iter- ates in a wide neighborhood of the central-path. Using the machinery of Euclidean Jordan algebra and the commutative class of search directions, the convergence analysis of the algo- rithm is shown and it is proved that the algorithm has the complexity bound O （√τL） for the well-known Nesterov-Todd search direction and O （τL） for the xs and sx search directions.

A Modified Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

This paper proposes a new full Nesterov-Todd(NT) step infeasible interior-point algorithm for semidefinite programming. Our algorithm uses a specific kernel function, which is adopted by Liu and Sun, to deduce the feasibility step. By using the step, it is remarkable that in each iteration of the algorithm it needs only one full-NT step, and can obtain an iterate approximate to the central path. Moreover, it is proved that the iterative bound corresponds with the known optimal one for semidefinite optimization problems.

A POSITIVE INTERIOR-POINT ALGORITHM FOR NONLINEAR COMPLEMENTARITY PROBLEMS

A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theorems of the algorithm is established.In addition,some numerical results are reported.

Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function

The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.

A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

In this paper, we propose a new infeasible interior-point algorithm with full NesterovTodd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. We used a specific kernel function to induce the feasibility step. The analysis is more simplified. The iteration bound coincides with the currently best known bound for infeasible interior-point methods.

Interior-point algorithm based on general kernel function for monotone linear complementarity problem

A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.