Quasi-Newton projection methods and the discrepancy principle in image restoration

In this work, the problem of the restoration of images corrupted by space invariant blur and noise is considered. This problem is ill-posed and regularization is required. The image restoration problem is formulated as a nonnegatively constrained minimization problem whose objective function depends on the statistical properties of the noise corrupting the observed image. The cases of Gaussian and Poisson noise are both considered. A Newton-like projection method with early stopping of the iterates is proposed as an iterative regularization method in order to determine a nonnegative approximation to the original image. A suitable approximation of the Hessian of the objective function is proposed for a fast solution of the Newton system. The results of the numerical experiments show the effectiveness of the method in computing a good solution in few iterations, when compared with some methods recently proposed as best performing.     

Gradient-type penalty method with inertial effects for solving constrained convex optimization problems with smooth data

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejér monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.     

Fixed point algorithm based on adapted metric method for convex minimization problem with application to image deblurring

Recently, optimization algorithms for solving a minimization problem whose objective function is a sum of two convex functions have been widely investigated in the field of image processing. In particular, the scenario when a non-differentiable convex function such as the total variation (TV) norm is included in the objective function has received considerable interests since many variational models encountered in image processing have this nature. In this paper, we propose a fast fixed point algorithm based on the adapted metric method, and apply it in the field of TV-based image deblurring. The novel method is derived from the idea of establishing a general fixed point algorithm framework based on an adequate quadratic approximation of one convex function in the objective function, in a way reminiscent of Quasi-Newton methods. Utilizing the non-expansion property of the proximity operator we further investigate the global convergence of the proposed algorithm. Numerical experiments on image deblurring problem demonstrate that the proposed algorithm is very competitive with the current state-of-the-art algorithms in terms of computational efficiency.     

Projected Subgradient Minimization Versus Superiorization

The projected subgradient method for constrained minimization repeatedly interlaces subgradient steps for the objective function with projections onto the feasible region, which is the intersection of closed and convex constraints sets, to regain feasibility. The latter poses a computational difficulty, and, therefore, the projected subgradient method is applicable only when the feasible region is “simple to project onto.” In contrast to this, in the superiorization methodology a feasibility-seeking algorithm leads the overall process, and objective function steps are interlaced into it. This makes a difference because the feasibility-seeking algorithm employs projections onto the individual constraints sets and not onto the entire feasible region. We present the two approaches side-by-side and demonstrate their performance on a problem of computerized tomography image reconstruction, posed as a constrained minimization problem aiming at finding a constraint-compatible solution that has a reduced value of the total variation of the reconstructed image.     

A variational approach for restoring images corrupted by noisy blur kernels and additive noise

In this paper, we study a deblurring algorithm for distorted images by random impulse response. We propose and develop a convex optimization model to recover the underlying image and the blurring function simultaneously. The objective function is composed of 3 terms: the data‐fitting term between the observed image and the product of the estimated blurring function and the estimated image, the squared difference between the estimated blurring function and its mean, and the total variation regularization term for the estimated image. We theoretically show that under some mild conditions, the resulting objective function can be convex in which the global minimum value is unique. The numerical results confirm that the peak‐to‐signal‐noise‐ratio and structural similarity of the restored images by the proposed algorithm are the best when the proposed objective function is convex. We also present a proximal alternating minimization scheme to solve the resulting minimization problem. Numerical examples are presented to demonstrate the effectiveness of the proposed model and the efficiency of the numerical scheme.     

非凸多目标优化中真有效解的一个非线性标量化性质

基于Pascoletti-Serafini标量化方法,利用罚函数思想提出了一类新的标量化函数,进而获得非凸多目标优化问题真有效解的充分条件和必要条件.该结果的建立不需要目标函数的像集有界这一条件,故文章是对Akbari等人[J.Optim.Theory Appl.,2018,178(2):560-590]建立的相应标量...     

A projected Newton-CG method for nonnegative astronomical image deblurring

Astronomical images are usually assumed to be corrupted by a space-invariant Point Spread Function and Poisson noise. In this paper we propose an original projected inexact Newton method for the solution of the constrained nonnegative minimization problem arising from image deblurring. The problem is ill-posed and the objective function must be regularized. The inner system is inexactly solved by few Conjugate Gradient iterations. The convergence of the method is proved and its efficiency is tested on simulated astronomical blurred images. The results show that the method produces good reconstructed images at low computational cost. Supported by the Italian MIUR Project Inverse Problems in Medicine and Astronomy 2006–2008.     

Non-negatively constrained image deblurring with an inexact interior point method

Nonlinear image deblurring procedures based on probabilistic considerations have been widely investigated in the literature. This approach leads to model the deblurring problem as a large scale optimization problem, with a nonlinear, convex objective function and non-negativity constraints on the sign of the variables. The interior point methods have shown in the last years to be very reliable in nonlinear programs. In this paper we propose an inexact Newton interior point (IP) algorithm designed for the solution of the deblurring problem. The numerical experience compares the IP method with another state-of-the-art method, the Lucy Richardson algorithm, and shows a significant improvement of the processing time.     

A nonlinear interval number programming method for uncertain optimization problems

In this paper, a method is suggested to solve the nonlinear interval number programming problem with uncertain coefficients both in nonlinear objective function and nonlinear constraints. Based on an order relation of interval number, the uncertain objective function is transformed into two deterministic objective functions, in which the robustness of design is considered. Through a modified possibility degree, the uncertain inequality and equality constraints are changed to deterministic inequality constraints. The two objective functions are converted into a single-objective problem through the linear combination method, and the deterministic inequality constraints are treated with the penalty function method. The intergeneration projection genetic algorithm is employed to solve the finally obtained deterministic and non-constraint optimization problem. Two numerical examples are investigated to demonstrate the effectiveness of the present method.     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

球面上$\ell_1$正则优化的随机临近梯度方法

本文研究球面上的$\ell_1$正则优化问题,其目标函数由一般光滑函数项和非光滑$\ell_1$正则项构成,且假设光滑函数的随机梯度可由随机一阶oracle估计.这类优化问题被广泛应用在机器学习,图像、信号处理和统计等领域.根据流形临近梯度法和随机梯度估计技术,提出一种球面随机临近梯度算法.基于非光滑函数的全局隐函数定理,分析了子问题解关于参数的Lipschtiz连续性,进而证明了算法的全局收敛性.在基于随机数据集和实际数据集的球面$\ell_1$正则二次规划问题、有限和SPCA问题和球面$\ell_1$正则逻辑回归问题上数值实验结果显示所提出的算法与流形临近梯度法、黎曼随机临近梯度法相比CPU时间上具有一定的优越性.     

A customized proximal point algorithm for convex minimization with linear constraints

This paper demonstrates a customized application of the classical proximal point algorithm (PPA) to the convex minimization problem with linear constraints. We show that if the proximal parameter in metric form is chosen appropriately, the application of PPA could be effective to exploit the simplicity of the objective function. The resulting subproblems could be easier than those of the augmented Lagrangian method (ALM), a benchmark method for the model under our consideration. The efficiency of the customized application of PPA is demonstrated by some image processing problems.     

Stability for Properly Quasiconvex Vector Optimization Problem

The aim of this paper is to study the stability aspects of various types of solution set of a vector optimization problem both in the given space and in its image space by perturbing the objective function and the feasible set. The Kuratowski?CPainlevé set-convergence of the sets of minimal, weak minimal and Henig proper minimal points of the perturbed problems to the corresponding minimal set of the original problem is established assuming the objective functions to be (strictly) properly quasi cone-convex.     

Inexact Alternating-Direction-Based Contraction Methods for Separable Linearly Constrained Convex Optimization

Alternating direction method of multipliers has been well studied in the context of linearly constrained convex optimization. In the last few years, we have witnessed a number of novel applications arising from image processing, compressive sensing and statistics, etc., where the approach is surprisingly efficient. In the early applications, the objective function of the linearly constrained convex optimization problem is separable into two parts. Recently, the alternating direction method of multipliers has been extended to the case where the number of the separable parts in the objective function is finite. However, in each iteration, the subproblems are required to be solved exactly. In this paper, by introducing some reasonable inexactness criteria, we propose two inexact alternating-direction-based contraction methods, which substantially broaden the applicable scope of the approach. The convergence and complexity results for both methods are derived in the framework of variational inequalities.     

Regularized Quadratic Penalty Methods for Shape from Shading

Shape from shading (SFS) denotes the problem of reconstructing a 3D surface, starting from a single shaded image which represents the surface itself. Minimization techniques are commonly used for solving the SFS problem, where the objective function is a weighted combination of the brightness error, plus one or more terms aiming to obtain a valid solution. We present a regularized quadratic penalty method where quadratic penalization is used to adaptively adjust the smoothing weights, and regularization improves the robustness and reliability of the procedure. A nonmonotone Barzilai–Borwein method is employed to efficiently solve the arising subproblems. Numerical results are provided showing the reliability of the proposed approach.     

On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems

In this paper, we analyse the convergence rate of the sequence of objective function values of a primal-dual proximal-point algorithm recently introduced in the literature for solving a primal convex optimization problem having as objective the sum of linearly composed infimal convolutions, nonsmooth and smooth convex functions and its Fenchel-type dual one. The theoretical part is illustrated by numerical experiments in image processing.     

Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties

We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms

Two-phase image segmentation is a fundamental task to partition an image into foreground and background. In this paper, two types of nonconvex and nonsmooth regularization models are proposed for basic two-phase segmentation. They extend the convex regularization on the characteristic function on the image domain to the nonconvex case, which are able to better obtain piecewise constant regions with neat boundaries. By analyzing the proposed non-Lipschitz model, we combine the proximal alternating minimization framework with support shrinkage and linearization strategies to design our algorithm. This leads to two alternating strongly convex subproblems which can be easily solved. Similarly, we present an algorithm without support shrinkage operation for the nonconvex Lipschitz case. Using the Kurdyka-Łojasiewicz property of the objective function, we prove that the limit point of the generated sequence is a critical point of the original nonconvex nonsmooth problem. Numerical experiments and comparisons illustrate the effectiveness of our method in two-phase image segmentation.     

A modified objective function method for solving nonlinear multiobjective fractional programming problems

A new method is used for solving nonlinear multiobjective fractional programming problems having V-invex objective and constraint functions with respect to the same function η. In this approach, an equivalent vector programming problem is constructed by a modification of the objective fractional function in the original nonlinear multiobjective fractional problem. Furthermore, a modified Lagrange function is introduced for a constructed vector optimization problem. By the help of the modified Lagrange function, saddle point results are presented for the original nonlinear fractional programming problem with several ratios. Finally, a Mond-Weir type dual is associated, and weak, strong and converse duality results are established by using the introduced method with a modified function. To obtain these duality results between the original multiobjective fractional programming problem and its original Mond-Weir duals, a modified Mond-Weir vector dual problem with a modified objective function is constructed.     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.