Primal-dual Fixed Point Algorithms For Convex Separable Minimization And Their Applications

In recent years, minimization of a sum of two convex functions has received consid-erable interests in variational image restoration model. In this thesis, we are intended topropose several general algorithmic frameworks from the point of view of primal-dual fixedpoint algorithms based on proximity operators for solving separable convex minimizationproblem, in which one function is a composition of a convex function with a linear trans-form, and the other is differentiable with a Lipschitz continuous gradient.Motivated from proximal forward-backward splitting (PFBS) and fixed point algorithmsbased on the proximity operator (FP~2O) for image denoising, we design a primal-dual fixedpoint algorithm based on proximity operator (PDFP~2O) and obtain a scheme with a closed-form for each iteration. We first propose PDFP~2O from our intuitions. Then we deducePDFP~2O again and express it as a fixed point iteration form based on the first optimal con-dition, the equivalent relationship between the proximity operator and the subdifferential ofa convex function, and the introduction of dual variable and two step extra inserting oper-ations. According to the fixed point form of the algorithm, we can easily get its extensionalgorithm PDFP~2Oκ. Using the firmly nonexpansive properties of the proximity operatorand with the help of a special norm over a product space, we achieve the convergence ofPDFP~2Oκ. Moreover, under some stronger assumptions, we can prove the global linear con-vergence of PDFP~2Oκ. We also give the equivalent forms of PDFP~2O and the connectionwith other existing first order methods for better understanding. Finally, we illustrate theefficiency of PDFP~2O through some numerical examples on image supperresolution, com-puterized tomographic reconstruction and parallel magnetic resonance imaging. Generallyspeaking, PDFP~2O is comparable with other state-of-the-art methods in numerical perfor-mance, while it has some advantages on parameters selection in real applications.In many real problems, the solutions may have constraints arising from their physicalrequirements. So we design efficient algorithms for solving the separable convex minimiza-tion with convex constraint based on PDFP~2O. The constraint can be enforced by addingan indicator function to the objective function, and the function are reformulated and canbe solved with PDFP~2O. Using the separability of the function with respect to its variables, we can get a primal-dual fixed point algorithm based on proximity operator on convex set(PDFP~2O_C). Since the algorithm PDFP~2O_Ccan be recast as the original PDFP~2O for uncon-strained problem, the convergence and convergence rate analysis can be obtained directly.Meanwhile, under the assumption that the solution lies in the interior of the constrained con-vex set，using the fact that the proximal operator of an indicator function is a projectionoperator, we propose a primal-dual fixed point algorithm based on proximity operator in thiscase, called PDFP~2O_C0, by fixed point iterations similar to PDFP~2O. Then we analyze theconvergence and convergence rate of the method by using the conclusion of PDFP~2O andthe fact the projection operator is also firmly nonexpansive. Generally speaking, PDFP~2O_Ccan be used in general cases, while PDFP~2O_C0requires that the solution lies in the interiorof the constrained convex set. However, PDFP~2O_C0is simpler in form and more intuitivethan PDFP~2O_C. Finally, we illustrate the efficiency of PDFP~2O_Cand PDFP~2O_C0by sev-eral numerical experiments including computerized tomographic reconstruction and parallelmagnetic resonance imaging.From the analysis of the convergence rate and the experiment results of CT reconstruc-tion, we can see that the convergence rate of PDFP~2O depends strongly on the conditionnumbers of the corresponding matrices, and the convergence rate of PDFP~2O will becomeworse when the condition numbers of the corresponding matrices become larger. So weconsider to accelerate PDFP~2O using preconditioning operators and propose a primal-dualfixed point algorithm based on proximity and precondition operators (PDFP~3O) by using thesimilar technique in PDFP~2O, in which we introduce two preconditioning operators. Similarto PDFP~2O, we can also analyze the convergence and the convergence rate of PDFP~3O byintroducing another special norm. We compare PDFP~3O with exact Uzawa, inexact Uzawaand non-linear inexact Uzawa, and also deduce these algorithms using the similar ideas forderiving PDFP~3O. In numerical experiments, we show that PDFP~3O is better than PDFP~2O,especially when the condition number of the problem is bad, through two problems fromthe second elliptic variational inequality problem. In simplified friction problem, we con-vert the degenerate case into the one suited for our theoretical analysis of convergence rateby using the first order optimal condition, and choose the preconditioning matrices via theintrinsic properties of the new problem. In the flow problem of a viscous plastic fluid ina pipe，we try to use conjugate gradient method to generate the effect of preconditioningmatrix in PDFP~3O.