A note on alternating projections in Hilbert space

We provide a direct proof of a result regarding the asymptotic behavior of alternating nearest point projections onto two closed and convex sets in a Hilbert space. Our arguments are based on nonexpansive mapping theory.     

Solving semidefinite programming problems via alternating direction methods

In this paper, we consider an alternating direction algorithm for the solution of semidefinite programming problems (SDP). The main idea of our algorithm is that we reformulate the complementary conditions in the primal–dual optimality conditions as a projection equation. By using this reformulation, we only need to make one projection and solve a linear system of equation with reduced dimension in each iterate. We prove that the generated sequence converges to the solution of the SDP under weak conditions.     

A note on the implementation of the accelerated successive orthogonal projections method for solving large scale linear feasibility problems

In a recent paper we introduced an accelerated version of the Successive Orthogonal Projections method which seems to be useful for solving some classes of large scale linear feasibility problems. The main step of the method involves an orthogonal projection on a linear manifold Bx = b. In this note we consider the very frequent situation where the m X m identity matrix is a submatrix of B. We develop a procedure for computing the projection which only involves “small” matrix factorizations.     

A new L-curve for ill-posed problems

The truncated singular value decomposition is a popular method for the solution of linear ill-posed problems. The method requires the choice of a truncation index, which affects the quality of the computed approximate solution. This paper proposes that an L-curve, which is determined by how well the given data (right-hand side) can be approximated by a linear combination of the first (few) left singular vectors (or functions), be used as an aid for determining the truncation index.     

A mollification method for ill-posed problems

Summary. A mollification method for a class of ill-posed problems is suggested. The idea of the method is very simple and natural: if the data are given inexactly then we try to find a sequence of ``mollification operators" which map the improper data into well-posedness classes of the problem (mollify the improper data). Within these mollified data our problem becomes well-posed. And when these facts are in hand we try to obtain error estimates and optimal or ``quasi-optimal" mollification parameters. The method is working not only for problems in Hilbert spaces, but also for problems in Banach spaces. Applications of the method to concrete problems, like numerical differentiation, parabolic equations backwards in time, the Cauchy problem for the Laplace equation, one- and multidimensional non-characteristic Cauchy problems for parabolic equations (in infinite or finite domains),... give us very sharp stability estimates of H\"older continuous type. In these cases the method is optimal in the sense that it gives the same order of H\"older continuous dependence on the data as for the regularized problems. Furthermore, the method may be implemented numerically using fast Fourier transforms. For the first time a uniform stability estimate of H\"older continuous type of the solution of the heat equation backwards in time in the space for all could be established by our mollification method. A new simple sharp pointwise estimate of H\"older type for the weak solution of a non-characteristic Cauchy problem for parabolic equations in a finite domain is established. Received June 25, 1993 / Revised version received February 18, 1994     

A note on generic projections

Let X^N=²ⁿ_K be a subvariety of dimension n and P^N a generic point. If the tangent variety TanX is equal to ^N then for generic points x, y of X the projective tangent spaces t_xX and t_yX meet in one point P=P(x,y). The main result of this paper is that the rational map (x,y)P(x,y) is dominant. In other words, a generic point P is uniquely determined by the ramification locus R(_P) of the linear projection _P:X^N–1.This paper was supported by the DFG Schwerpunkt Global methods in complex analysis, MUR and the Research Group GNSAGA of INDAM. This investigation was also supported by the University of Bologna, funds for selected research topics     

A modified quasi-boundary value method for ill-posed problems

In this paper, we study a final value problem for first order abstract differential equation with positive self-adjoint unbounded operator coefficient. This problem is ill-posed. Perturbing the final condition we obtain an approximate nonlocal problem depending on a small parameter. We show that the approximate problems are well posed and that their solutions converge if and only if the original problem has a classical solution. We also obtain estimates of the solutions of the approximate problems and a convergence result of these solutions. Finally, we give explicit convergence rates.     

Multilevel algorithms for ill-posed problems

Summary In this paper new multilevel algorithms are proposed for the numerical solution of first kind operator equations. Convergence estimates are established for multilevel algorithms applied to Tikhonov type regularization methods. Our theory relates the convergence rate of these algorithms to the minimal eigenvalue of the discrete version of the operator and the regularization parameter. The algorithms and analysis are presented in an abstract setting that can be applied to first kind integral equations.Dedicated to Jim Bramble on the occasion of his sixtieth birthday     

An alternating extragradient method with non euclidean projections for saddle point problems

In this work we analyze a first order method especially tailored for smooth saddle point problems, based on an alternating extragradient scheme. The proposed method is based on three successive projection steps, which can be computed also with respect to non Euclidean metrics. The stepsize parameter can be adaptively computed, so that the method can be considered as a black-box algorithm for general smooth saddle point problems. We develop the global convergence analysis in the framework of non Euclidean proximal distance functions, under mild local Lipschitz conditions, proving also the \(\mathcal {O}(\frac{1}{k})\) rate of convergence on the primal–dual gap. Finally, we analyze the practical behavior of the method and its effectiveness on some applications arising from different fields.     

An alternating projections method for certain linear problems in a Hilbert space

Recent extensions of von Neumann's alternating projection methodpermit the computation of proximity projections onto certainconvex sets. This paper exploits this fact in constructing aglobally convergent method for minimizing linear functions overa convex set in a Hilbert space. In particular, we solve theeducational testing problem and an inverse eigenvalue problem,two difficult problems involving positive semidefiniteness constraints.     

A note on some analytic center cutting plane methods for convex feasibility and minimization problems

Recently Goffin, Luo and Ye have analyzed the complexity of an analytic center algorithm for convex feasibility problems defined by a separation oracle. The oracle is called at the (possibly approximate) analytic center of the set given by the linear inequalities which are the previous answers of the oracle. We discuss oracles for the problem of minimizing a convex (possibly nondifferentiable) function subject to box constraints, and give corresponding complexity estimates.The research of the first author is supported by the Polish Academy of Sciences; the research of the second author is supported by the State Committee for Scientific Research under Grant 8S50502206.     

A note on the existence of the Alizadeh-Haeberly-Overton direction for semidefinite programming

This note establishes a new sufficient condition for the existence and uniqueness of the Alizadeh-Haeberly-Overton direction for semidefinite programming. The work of these authors was based on research supported by the National Science Foundation under grants INT-9600343 and CCR-970048 and the Office of Naval Research under grant N00014-94-1-0340.     

A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs

We propose a modified alternating direction method for solving convex quadratically constrained quadratic semidefinite optimization problems. The method is a first-order method, therefore requires much less computational effort per iteration than the second-order approaches such as the interior point methods or the smoothing Newton methods. In fact, only a single inexact metric projection onto the positive semidefinite cone is required at each iteration. We prove global convergence and provide numerical evidence to show the effectiveness of this method.     

A spectral approach to ill-posed problems for wave equations

In this article, we consider the problem of finding a solution to ill-posed problems for abstract wave equations in a Hilbert space, of the form

A minimal error conjugate gradient method for ill-posed problems

For the ill-posed operator equationTx=y in Hilbert space, we introduce a modification of the usual conjugate gradient method which minimizes the error, not the residual, at each step. Moreover, the error is minimized over the same finite-dimensional subspace that is associated with the usual method.This work was completed while the author was on leave at the University of Tennessee, Knoxville, Tennessee. Travel support from the Taft Committee and from the University of Tennessee is gratefully acknowledged.     

Continuous dependence on modeling for nonlinear ill-posed problems

The nonlinear ill-posed Cauchy problem , where A is a positive self-adjoint operator on a Hilbert space H, χ∈H, and h:[0,T)×H→H is a uniformly Lipschitz function, is studied in order to establish continuous dependence results for solutions to approximate well-posed problems. The authors show here that solutions of the problem, if they exist, depend continuously on solutions to corresponding approximate well-posed problems, if certain stabilizing conditions are imposed. The approximate problem is given by , v(0)=χ, for suitable functions f. The main result is that , where C and M are computable constants independent of β and 0<β<1. This work extends to the nonlinear case earlier results by the authors and by Ames and Hughes.     

Cascadic multilevel methods for ill-posed problems

Multilevel methods are popular for the solution of well-posed problems, such as certain boundary value problems for partial differential equations and Fredholm integral equations of the second kind. However, little is known about the behavior of multilevel methods when applied to the solution of linear ill-posed problems, such as Fredholm integral equations of the first kind, with a right-hand side that is contaminated by error. This paper shows that cascadic multilevel methods with a conjugate gradient-type method as basic iterative scheme are regularization methods. The iterations are terminated by a stopping rule based on the discrepancy principle.     

A note on parallel and alternating time

A long standing open question in complexity theory over the reals is the relationship between parallel time and quantifier alternation. It is known that alternating digital quantifiers is weaker than parallel time, which in turn is weaker than alternating unrestricted (real) quantifiers. In this note we consider some complexity classes defined through alternation of mixed digital and unrestricted quantifiers in different patterns. We show that the class of sets decided in parallel polynomial time is sandwiched between two such classes for different patterns.     

Error estimates for large-scale ill-posed problems

The computation of an approximate solution of linear discrete ill-posed problems with contaminated data is delicate due to the possibility of severe error propagation. Tikhonov regularization seeks to reduce the sensitivity of the computed solution to errors in the data by replacing the given ill-posed problem by a nearby problem, whose solution is less sensitive to perturbation. This regularization method requires that a suitable value of the regularization parameter be chosen. Recently, Brezinski et al. (Numer Algorithms 49, 2008) described new approaches to estimate the error in approximate solutions of linear systems of equations and applied these estimates to determine a suitable value of the regularization parameter in Tikhonov regularization when the approximate solution is computed with the aid of the singular value decomposition. This paper discusses applications of these and related error estimates to the solution of large-scale ill-posed problems when approximate solutions are computed by Tikhonov regularization based on partial Lanczos bidiagonalization of the matrix. The connection between partial Lanczos bidiagonalization and Gauss quadrature is utilized to determine inexpensive bounds for a family of error estimates. In memory of Gene H. Golub. This work was supported by MIUR under the PRIN grant no. 2006017542-003 and by the University of Cagliari.