A Simply Constrained Optimization Reformulation of KKT Systems Arising from Variational Inequalities

The Karush—Kuhn—Tucker (KKT) conditions can be regarded as optimality conditions for both variational inequalities and constrained optimization problems. In order to overcome some drawbacks of recently proposed reformulations of KKT systems, we propose casting KKT systems as a minimization problem with nonnegativity constraints on some of the variables. We prove that, under fairly mild assumptions, every stationary point of this constrained minimization problem is a solution of the KKT conditions. Based on this reformulation, a new algorithm for the solution of the KKT conditions is suggested and shown to have some strong global and local convergence properties. Accepted 10 December 1997     

Image restoration with a high-order total variation minimization method

In this paper, we propose a fast and efficient way to restore blurred and noisy images with a high-order total variation minimization technique. The proposed method is based on an alternating technique for image deblurring and denoising. It starts by finding an approximate image using a Tikhonov regularization method. This corresponds to a deblurring process with possible artifacts and noise remaining. In the denoising step, a high-order total variation algorithm is used to remove noise in the deblurred image. We see that the edges in the restored image can be preserved quite well and the staircase effect is reduced effectively in the proposed algorithm. We also discuss the convergence of the proposed regularization method. Some numerical results show that the proposed method gives restored images of higher quality than some existing total variation restoration methods such as the fast TV method and the modified TV method with the lagged diffusivity fixed-point iteration.     

New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems

A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations.     

Modular solvers for image restoration problems using the discrepancy principle

Many problems in image restoration can be formulated as either an unconstrained non‐linear minimization problem, usually with a Tikhonov‐like regularization, where the regularization parameter has to be determined; or as a fully constrained problem, where an estimate of the noise level, either the variance or the signal‐to‐noise ratio, is available. The formulations are mathematically equivalent. However, in practice, it is much easier to develop algorithms for the unconstrained problem, and not always obvious how to adapt such methods to solve the corresponding constrained problem. In this paper, we present a new method which can make use of any existing convergent method for the unconstrained problem to solve the constrained one. The new method is based on a Newton iteration applied to an extended system of non‐linear equations, which couples the constraint and the regularized problem, but it does not require knowledge of the Jacobian of the irregularity functional. The existing solver is only used as a black box solver, which for a fixed regularization parameter returns an improved solution to the unconstrained minimization problem given an initial guess. The new modular solver enables us to easily solve the constrained image restoration problem; the solver automatically identifies the regularization parameter, during the iterative solution process. We present some numerical results. The results indicate that even in the worst case the constrained solver requires only about twice as much work as the unconstrained one, and in some instances the constrained solver can be even faster. Copyright © 2002 John Wiley & Sons, Ltd.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.     

战斗对策:有约束极小极大途径(Ⅱ)

本文提出几个用集合,测度和积分工具来的极小极大判别准则,用来解有约束极小极大问题．     

A mathematical model for the 3d location estimation of 2D echocardiography data

The recovery of 3D left ventricle(LV) shape using 2D echocardiography is very attractable topic in the field of ultrasound imaging. In this paper, we propose a mathematical model to determine the 3D position of LV contours extracted from multiple 2D echocardiography images. We formulate the proposed model as a non-convex constrained minimization problem. To solve it, we propose a proximal alternating minimization algorithm with a solver OPTI for quadratically constrained quadratic program. For validating the proposed model, numerical experiments are performed with real ultrasound data. The experimental results show that the proposed model is promising and available for real echocardiography data.     

Primal-dual algorithms for total variation based image restoration under Poisson noise Dedicated to Professor Lin Qun on the Occasion of his 80th Birthday

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.     

A primal-dual active-set algorithm for bilaterally constrained total variation deblurring and piecewise constant Mumford-Shah segmentation problems

In this paper, we propose a fast primal-dual algorithm for solving bilaterally constrained total variation minimization problems which subsume the bilaterally constrained total variation image deblurring model and the two-phase piecewise constant Mumford-Shah image segmentation model. The presence of the bilateral constraints makes the optimality conditions of the primal-dual problem semi-smooth which can be solved by a semi-smooth Newton’s method superlinearly. But the linear system to solve at each iteration is very large and difficult to precondition. Using a primal-dual active-set strategy, we reduce the linear system to a much smaller and better structured one so that it can be solved efficiently by conjugate gradient with an approximate inverse preconditioner. Locally superlinear convergence results are derived for the proposed algorithm. Numerical experiments are also provided for both deblurring and segmentation problems. In particular, for the deblurring problem, we show that the addition of the bilateral constraints to the total variation model improves the quality of the solutions.