Search

In this article we propose a novel strategy for choosing the Lagrange multipliers in the Levenberg–Marquardt method for solving ill-posed problems modeled by nonlinear operators acting between Hilbert spaces. Convergence analysis results are established for the proposed method, including monotonicity of iteration error, geometrical decay of the residual, convergence for exact data, stability and semi-convergence for noisy data. Numerical experiments are presented for an elliptic parameter identification two-dimensional electrical impedance tomography problem. The performance of our strategy is compared with standard implementations of the Levenberg–Marquardt method (using a priori choice of the multipliers). [ABSTRACT FROM AUTHOR]

In this article we propose a novel nonstationary iterated Tikhonov (NIT)-type method for obtaining stable approximate solutions to ill-posed operator equations modeled by linear operators acting between Hilbert spaces. Geometrical properties of the problem are used to derive a new strategy for choosing the sequence of regularization parameters (Lagrange multipliers) for the NIT iteration. Convergence analysis for this new method is provided. Numerical experiments are presented for two distinct applications: (I) a two-dimensional elliptic parameter identification problem (inverse potential problem); and (II) an image-deblurring problem. The results obtained validate the efficiency of our method compared with standard implementations of the NIT method (where a geometrical choice is typically used for the sequence of Lagrange multipliers). [ABSTRACT FROM AUTHOR]

This paper studies the iteration complexity of new regularized hybrid proximal extragradient (HPE)-type methods for solving monotone inclusion problems (MIPs). The new (regularized HPE-type) methods essentially consist of instances of the standard HPE method applied to regularizations of the original MIP. It is shown that the pointwise iteration complexity of the proposed methods considerably improves upon that of the HPE method while approaching (up to a logarithmic factor) the ergodic iteration complexity of the latter method. [ABSTRACT FROM AUTHOR]

In this paper, we present a new mathematical rigorous technique for computing the average free energy of a disordered system with quenched randomness, using the replicas. The basic tool of this technique is a distributional zeta-function, a complex function whose derivative at the origin yields the average free energy of the system as the sum of two contributions: the first one is a series in which all the integer moments of the partition function of the model contribute; the second one, which cannot be written as a series of the integer moments, can be made as small as desired. This result supports the use of integer moments of the partition function, computed via replicas, for expressing the average free energy of the system. One advantage of the proposed formalism is that it does not require the understanding of the properties of the permutation group when the number of replicas goes to zero. Moreover, the symmetry is broken using the saddle-point equations of the model. As an application for the distributional zeta-function technique, we obtain the average free energy of the disordered model defined in a -dimensional Euclidean space. [ABSTRACT FROM AUTHOR]

This paper presents a hybrid proximal extragradient (HPE) self-concordant primal barrier method for solving a monotone variational inequality over a closed convex set endowed with a self-concordant barrier and with an underlying map that has Lipschitz continuous derivative. In contrast to the iteration of a previous method developed by the first and third authors that has to compute an approximate solution of a linearized variational inequality, the one of the present method solves a simpler Newton system of linear equations. The method performs two types of iterations, namely, those that follow ever changing interior paths and those that correspond to large-step HPE iterations. Due to its first-order nature, the present method is shown to have a better iterationcomplexity than its zeroth order counterparts such as Korpelevich's algorithm and Tseng's modified forward-backward splitting method, although its work per iteration is larger than the one for the latter methods. [ABSTRACT FROM AUTHOR]

The Riemann hypothesis states that all nontrivial zeros of the zeta function lie in the critical line (s) = 1/2. Hilbert and Pólya suggested that one possible way to prove the Riemann hypothesis is to interpret the nontrivial zeros in the light of spectral theory. Using the construction of the so-called super-zeta functions or secondary zeta functions built over the Riemann nontrivial zeros and the regularity property of one of this function at the origin, we show that it is possible to extend the Hilbert-Pólya conjecture to systems with countably infinite number of degrees of freedom. The sequence of the nontrivial zeros of the Riemann zeta function can be interpreted as the spectrum of a self-adjoint operator of some hypothetical system described by the functional approach to quantum field theory. However, if one considers the same situation with numerical sequences whose asymptotic distributions are not "far away" from the asymptotic distribution of prime numbers, the associated functional integral cannot be constructed. Finally, we discuss possible relations between the asymptotic behavior of a sequence and the analytic domain of the associated zeta function. [ABSTRACT FROM AUTHOR]

This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) framework. Iteration-complexity results are established for the A-HPE framework, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE framework are described in the context of a structured convex optimization problem whose objective function consists of the sum of a smooth convex function and an extended real-valued nonsmooth convex function. In the first implementation, a generalization of a variant of Nesterov's method is obtained for the case where the smooth component of the objective function has Lipschitz continuous gradient. In the second implementation, an accelerated Newton proximal extragradient (A-NPE) method is obtained for the case where the smooth component of the objective function has Lipschitz continuous Hessian. It is shown that the A-NPE method has a O(1/k7/2) convergence rate, which improves upon the O(1/k³) convergence rate bound for another accelerated Newton-type method presented by Nesterov. Finally, while Nesterov's method is based on exact solutions of subproblems with cubic regularization terms, the A-NPE method is based on inexact solutions of subproblems with quadratic regularization terms and hence is potentially more tractable from a computational point of view. [ABSTRACT FROM AUTHOR]

In this paper, we consider both a variant of Tseng's modified forward backward splitting method and all extension of Korpelevich's method for solving hemivariational inequalities with Lipschitz continuous operators. By showing that these methods are special cases of the hybrid proximal extra gradient method introduced by Solodov and Svaiter, we derive iteration-complexity bounds for them to obtain different types of approximate solutions. In the context of saddle-point problems, we also derive complexity bounds for these methods to obtain another type of an approximate solution, namely, that of an approximate saddle point. Finally, we illustrate the usefulness of the above results by applying them to a large class of linearly constrained convex programming problems, including, for example, cone programming and problems whose objective functions converge to infinity as the Boundaries of their effective domains are approached. [ABSTRACT FROM AUTHOR]

We introduce nonautonomous continuous dynamical systems which are linked to the Newton and Levenberg-Marquardt methods. They aim at solving inclusions governed by maximal monotone operators in Hilbert spaces. Relying on the Minty representation of maximal monotone operators as lipschitzian manifolds, we show that these dynamics can be formulated as first-order in time differential systems, which are relevant to the Cauchy-Lipschitz theorem. By using Lyapunov methods, we prove that their trajectories converge weakly to equilibria. Time discretization of these dynamics gives algorithms providing new insight into Newton's method for solving monotone inclusions. [ABSTRACT FROM AUTHOR]

We prove that the sequences generated by the Douglas-Rachford method converge weakly to zero of the sum of two maximal monotone operators using new tools introduced in recent works of Eckstein and the author. The assumption of maximal monotonicity of the sum is also removed, using a recent result of Bauschke. [ABSTRACT FROM AUTHOR]

We propose an extension of Newton's method for unconstrained multiobjective optimization (multicriteria optimization). This method does not use a priori chosen weighting factors or any other form of a priori ranking or ordering information for the different objective functions. Newton's direction at each iterate is obtained by minimizing the max-ordering scalarization of the variations on the quadratic approximations of the objective functions. The objective functions are assumed to be twice continuously differentiable and locally strongly convex. Under these hypotheses, the method, as in the classical case, is locally superlinear convergent to optimal points. Again as in the scalar case, if the second derivatives are Lipschitz continuous, the rate of convergence is quadratic. Our convergence analysis uses a Kantorovich-like technique. As a byproduct, existence of optima is obtained under semilocal assumptions. [ABSTRACT FROM AUTHOR]

We describe a general projective framework for finding a zero of the sum of n maximal monotone operators over a real Hilbert space. Unlike prior methods for this problem, we neither assume n = 2 nor first reduce the problem to the case n = 2. Our analysis defines a closed convex extended solution set for which we can construct a separating hyperplane by individually evaluating the resolvent of each operator. At the cost of a single, computationally simple projection step, this framework gives rise to a family of splitting methods of unprecedented flexibility: numerous parameters, including the proximal stepsize, may vary by iteration and by operator. The order of operator evaluation may vary by iteration and may be either serial or parallel. The analysis essentially generalizes our prior results for the case n = 2. We also include a relative error criterion for approximately evaluating resolvents, which was not present in our earlier work. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of a new necessary condition in variational inequality problems: approximated gradient projection (AGP). A feasible point satisfies such condition if it is the limit of a sequence of the approximated solutions of approximations of the variational problem. This condition comes from optimization where the error in the approximated solution is measured by the projected gradient onto the approximated feasible set, which is obtained from a linearization of the constraints with slack variables to make the current point feasible. We state the AGP condition for variational inequality problems and show that it is necessary for a point being a solution even without constraint qualifications (e.g., Abadie's). Moreover, the AGP condition is sufficient in convex variational inequalities. Sufficiency also holds for variational inequalities involving maximal monotone operators subject to the boundedness of the vectors in the image of the operator (playing the role of the gradients). Since AGP is a condition verified by a sequence, it is particularly interesting for iterative methods. [ABSTRACT FROM AUTHOR]

We study two outer approximation schemes, applied to the variational inequality problem in reflexive Banach spaces. First we propose a generic outer approximation scheme, and its convergence analysis unifies a wide class of outer approximation methods applied to the constrained optimization problem. As is standard in this setting, boundedness and optimality of weak limit points are proved to hold under two alternative conditions: (i) boundedness of the feasible set, or (ii) coerciveness of the operator. To develop a convergence analysis where (i) and (ii) do not hold, we consider a second scheme in which the approximated subproblems use a coercive approximation of the original operator. Under conditions alternative to both (i) and (ii), we obtain standard convergence results. Furthermore, when the space is uniformly convex, we establish full strong convergence of the second scheme to a solution. [ABSTRACT FROM AUTHOR]

This paper studies convergence properties of inexact variants of the proximal point, algorithm when applied to a certain class of nonmonotone mappings. The presented algorithms allow for constant relative errors, in the line of the recently proposed hybrid proximal-extragradient algorithm. The main convergence result extends a recent work of the second author, where exact solutions for the proximal subproblems were required. We also show thai the linear convergence property is preserved in the case when the inverse of the operator is locally Lipschitz continuous near the origin. As an application, we give a convergence analysis for an inexact, version of the proximal method of multipliers for a rather general family of problems which includes variational inequalities and constrained optimization problems. [ABSTRACT FROM AUTHOR]

We describe how Computational Group Theory provides tools for manipulating indexed objects (tensors, spinors, and so on) in explicit index notation. In particular, we present algorithms that put tensors with free and dummy indices obeying permutation symmetries into the canonical form. The method is based on algorithms for determining canonical double coset representatives of subgroups of the symmetric group. The complexity of the algorithms is polynomial on the number of indices in practical applications and allows one to address the simplification of tensor expressions with hundreds of indices, going beyond what is needed in practical applications. [ABSTRACT FROM AUTHOR]