Duality-based regularization in a linear convex mathematical programming problem

For a linear convex mathematical programming (MP) problem with equality and inequality constraints in a Hilbert space, a dual-type algorithm is constructed that is stable with respect to input data errors. In the algorithm, the dual of the original optimization problem is solved directly on the basis of Tikhonov regularization. It is shown that the necessary optimality conditions in the original MP problem are derived in a natural manner by using dual regularization in conjunction with the constructive generation of a minimizing sequence. An iterative regularization of the dual algorithm is considered. A stopping rule for the iteration process is presented in the case of a finite fixed error in the input data.     

Stable sequential Lagrange principles in the inverse final observation problem for the system of Maxwell equations in the quasistationary magnetic approximation

We justify the possibility of using stable, with respect to errors in the input data, algorithms of dual regularization and iterative dual regularization for solving the inverse final observation problem for the system of Maxwell equations in the quasistationary magnetic approximation under general conditions on the coefficients, which is treated as an optimal control problem for the differential equation describing the magnetic field intensity with an operator equality constraint. We state a classical parametric Lagrange principle and stable Lagrange principles in sequential form for the posed problem. We present a stopping rule for the iterative process for the stable sequential Lagrange principle in iterative form in the case of finite fixed error in the input data.     

An iterative regularization method for the 2-constrained pseudoinversion of an operator equation

An iterative regularization algorithm is proposed for solving a special optimization problem, the so-called 2-constrained operator pseudoinversion. The convergence of the algorithm is examined in the case of perturbed input data. An error estimate is derived, and an a priori choice of the regularization parameters is described. The algorithm is applied to an optimal control problem with minimal costs.     

An iterative algorithm for large size least-squares constrained regularization problems

In this paper we propose an iterative algorithm to solve large size linear inverse ill posed problems. The regularization problem is formulated as a constrained optimization problem. The dual Lagrangian problem is iteratively solved to compute an approximate solution. Before starting the iterations, the algorithm computes the necessary smoothing parameters and the error tolerances from the data.The numerical experiments performed on test problems show that the algorithm gives good results both in terms of precision and computational efficiency.     

Dual regularization and Pontryagin’s maximum principle in a problem of optimal boundary control for a parabolic equation with nondifferentiable functionals

A problem of optimal boundary control is considered for a divergent linear parabolic equation. Equality constraints of the problem are given by nondifferentiable functionals. A dual regularization algorithm stable to errors in initial data is constructed for solving the problem. Pontryagin’s maximum principle plays the key role in this algorithm.     

Primal and dual alternating direction algorithms for ℓ 1-ℓ 1-norm minimization problems in compressive sensing

In this paper, we propose, analyze and test primal and dual versions of the alternating direction algorithm for the sparse signal reconstruction from its major noise contained observation data. The algorithm minimizes a convex non-smooth function consisting of the sum of ? ₁-norm regularization term and ? ₁-norm data fidelity term. We minimize the corresponding augmented Lagrangian function alternatively from either primal or dual forms. Both of the resulting subproblems admit explicit solutions either by using a one-dimensional shrinkage or by an efficient Euclidean projection. The algorithm is easily implementable and it requires only two matrix-vector multiplications per-iteration. The global convergence of the proposed algorithm is established under some technical conditions. The extensions to the non-negative signal recovery problem and the weighted regularization minimization problem are also discussed and tested. Numerical results illustrate that the proposed algorithm performs better than the state-of-the-art algorithm YALL1.     

SOURCE TERM IDENTIFICATION WITH DISCONTINUOUS DUAL RECIPROCITY APPROXIMATION AND QUASI-NEWTON METHOD FROM BOUNDARY OBSERVATIONS

This paper deals with discontinuous dual reciprocity boundary element method for solving an inverse source problem.The aim of this work is to determine the source term in elliptic equations for nonhomogenous anisotropic media,where some additional boundary measurements are required.An equivalent formulation to the primary inverse problem is established based on the minimization of a functional cost,where a regularization term is employed to eliminate the oscillations of the noisy data.Moreover,an efficient algorithm is presented and tested for some numerical examples.     

On an algorithm for dynamic reconstruction of the input

We consider the problem of dynamic reconstruction of the input in a system described by a vector differential equation and nonlinear in the state variable. We indicate an algorithm that is stable under information noises and computational errors and is aimed at infinite system operation time. The algorithm is based on the dynamic regularization method.     

Combined ℓ<Subscript>2</Subscript> data and gradient fitting in conjunction with ℓ<Subscript>1</Subscript> regularization

We are interested in minimizing functionals with ℓ₂ data and gradient fitting term and ℓ₁ regularization term with higher order derivatives in a discrete setting. We examine the structure of the solution in 1D by reformulating the original problem into a contact problem which can be solved by dual optimization techniques. The solution turns out to be a ’smooth’ discrete polynomial spline whose knots coincide with the contact points while its counterpart in the contact problem is a discrete version of a spline with higher defect and contact points as knots. In 2D we modify Chambolle’s algorithm to solve the minimization problem with the ℓ₁ norm of interacting second order partial derivatives as regularization term. We show that the algorithm can be implemented efficiently by applying the fast cosine transform. We demonstrate by numerical denoising examples that the ℓ₂ gradient fitting term can be used to avoid both edge blurring and staircasing effects.      

A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems

The aim of this paper is to develop an efficient algorithm for solving a class of unconstrained nondifferentiable convex optimization problems in finite dimensional spaces. To this end we formulate first its Fenchel dual problem and regularize it in two steps into a differentiable strongly convex one with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method with the aim of accelerating the resulting convergence scheme. The theoretical results are finally applied to an l ₁ regularization problem arising in image processing.     

A primal–dual regularized interior-point method for convex quadratic programs

Interior-point methods in augmented form for linear and convex quadratic programming require the solution of a sequence of symmetric indefinite linear systems which are used to derive search directions. Safeguards are typically required in order to handle free variables or rank-deficient Jacobians. We propose a consistent framework and accompanying theoretical justification for regularizing these linear systems. Our approach can be interpreted as a simultaneous proximal-point regularization of the primal and dual problems. The regularization is termedexact to emphasize that, although the problems are regularized, the algorithm recovers a solution of the original problem, for appropriate values of the regularization parameters.     

A stabilization method for solution of a parametric multicriteria equilibrium programming problem

A multicriteria equilibrium programming problem comprising a mathematical programming problem as a particular case, a multicriteria Pareto-point search problem, a minimization problem with equilibrium selection of the feasible set, etc., is considered. It is assumed that the initial data are known only approximately. In view of the fact that the considered problem is generally unstable with respect to the input data, a regularization method, which is a generalization of the Tikhonov stabilization method, is proposed. Conditions for matching the method parameters to the error in the input data are presented. The convergence of this method is analyzed.     

Employing different loss functions for the classification of images via supervised learning

Supervised learning methods are powerful techniques to learn a function from a given set of labeled data, the so-called training data. In this paper the support vector machines approach is applied to an image classification task. Starting with the corresponding Tikhonov regularization problem, reformulated as a convex optimization problem, we introduce a conjugate dual problem to it and prove that, whenever strong duality holds, the function to be learned can be expressed via the dual optimal solutions. Corresponding dual problems are then derived for different loss functions. The theoretical results are applied by numerically solving a classification task using high dimensional real-world data in order to obtain optimal classifiers. The results demonstrate the excellent performance of support vector classification for this particular problem.     

Lagrange multipliers, (exact) regularization and error bounds for monotone variational inequalities

We examine two central regularization strategies for monotone variational inequalities, the first a direct regularization of the operative monotone mapping, and the second via regularization of the associated dual gap function. A key link in the relationship between the solution sets to these various regularized problems is the idea of exact regularization, which, in turn, is fundamentally associated with the existence of Lagrange multipliers for the regularized variational inequality. A regularization is said to be exact if a solution to the regularized problem is a solution to the unregularized problem for all parameters beyond a certain value. The Lagrange multipliers corresponding to a particular regularization of a variational inequality, on the other hand, are defined via the dual gap function. Our analysis suggests various conceptual, iteratively regularized numerical schemes, for which we provide error bounds, and hence stopping criteria, under the additional assumption that the solution set to the unregularized problem is what we call weakly sharp of order greater than one.     

Parametric dual regularization for an optimal control problem with pointwise state constraints

The perturbation method is used in the dual regularization theory for a linear convex optimal control problem with a strongly convex objective functional and pointwise state constraints understood as ones in L ₂. Primary attention is given to the qualitative properties of the dual regularization method, depending on the differential properties of the value function (S-function) in the optimization problem. It is shown that the convergence of the method is closely related to the Lagrange principle and the Pontryagin maximum principle. The dual regularization scheme is shown to provide a new method for proving the maximum principle in the problem with pointwise state constraints understood in L ₂ or C. The regularized Lagrange principle in nondifferential form and the regularized Pontryagin maximum principle are discussed. Illustrative examples are presented.     

数据缺损矩阵低秩分解的正则化方法

数据缺损下矩阵低秩逼近问题出现在许多数据处理分析与应用领域. 由于极高的元素缺损率,数据缺损下的矩阵低秩逼近呈现很大的不适定性, 因而寻求有效的数值算法是一个具有挑战性的课题. 本文系统完整地综述了作者近期在这方面的一些研究进展, 给出了基本模型问题的不适定性理论分析, 提出了两种新颖的正则化方法: 元素约束正则化和引导正则化, 分别适用于中等程度的数据缺损和高度元素缺损的矩阵低秩逼近. 本文同时也介绍了相应快速有效的数值算法. 在一些实际的大规模数值例子中, 这些新的正则化算法均表现出比现有其他方法都好的数值特性.     

A “Nonconvex+Nonconvex” approach for image restoration with impulse noise removal

In this paper, we propose a new method for image restoration problems, which are degraded by impulsive noise, with nonconvex data fitting term and nonconvex regularizer.The proposed method possesses the advantages of nonconvex data fitting and nonconvex regularizer simultaneously, namely, robustness for impulsive noise and efficiency for restoring neat edge images.Further, we propose an efficient algorithm to solve the “Nonconvex+Nonconvex” structure problem via using the alternating direction minimization, and prove that the algorithm is globally convergent when the regularization parameter is known. However, the regularization parameter is unavailable in general. Thereby, we combine the algorithm with the continuation technique and modified Morozov’s discrepancy principle to get an improved algorithm in which a suitable regularization parameter can be chosen automatically. The experiments reveal the superior performances of the proposed algorithm in comparison with some existing methods.     

On the acceleration of the double smoothing technique for unconstrained convex optimization problems

In this article, we investigate the possibilities of accelerating the double smoothing (DS) technique when solving unconstrained nondifferentiable convex optimization problems. This approach relies on the regularization in two steps of the Fenchel dual problem associated with the problem to be solved into an optimization problem having a differentiable strongly convex objective function with Lipschitz continuous gradient. The doubly regularized dual problem is then solved via a fast gradient method. The aim of this article is to show how the properties of the functions in the objective of the primal problem influence the implementation of the DS approach and its rate of convergence. The theoretical results are applied to linear inverse problems by making use of different regularization functionals.     

Reconstructing unknown nonlinear boundary conditions in a time‐fractional inverse reaction–diffusion–convection problem

This paper has focused on unknown functions identification in nonlinear boundary conditions of an inverse problem of a time‐fractional reaction–diffusion–convection equation. This inverse problem is generally ill‐posed in the sense of stability, that is, the solution of problem does not depend continuously on the input data. Thus, a combination of the mollification regularization method with Gauss kernel and a finite difference marching scheme will be introduced to solve this problem. The generalized cross‐validation choice rule is applied to find a suitable regularization parameter. The stability and convergence of the numerical method are investigated. Finally, two numerical examples are provided to test the effectiveness and validity of the proposed approach.     

Sequential stable Kuhn-Tucker theorem in nonlinear programming

A general parametric nonlinear mathematical programming problem with an operator equality constraint and a finite number of functional inequality constraints is considered in a Hilbert space. Elements of a minimizing sequence for this problem are formally constructed from elements of minimizing sequences for its augmented Lagrangian with values of dual variables chosen by applying the Tikhonov stabilization method in the course of solving the corresponding modified dual problem. A sequential Kuhn-Tucker theorem in nondifferential form is proved in terms of minimizing sequences and augmented Lagrangians. The theorem is stable with respect to errors in the initial data and provides a necessary and sufficient condition on the elements of a minimizing sequence. It is shown that the structure of the augmented Lagrangian is a direct consequence of the generalized differentiability properties of the value function in the problem. The proof is based on a “nonlinear” version of the dual regularization method, which is substantiated in this paper. An example is given illustrating that the formal construction of a minimizing sequence is unstable without regularizing the solution of the modified dual problem.