Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

GUS-property for Lorentz cone linear complementarity problems on Hilbert spaces

Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator on H,ΩH is a Lorentz cone,and q ∈ H.We investigate some conditions for which the problem concerned has a unique solution for all q ∈ H(i.e.,T has the GUS-property).Several sufficient conditions and several necessary conditions are given.In particular,we provide two suficient and necessary cond...     

Tractability of quasilinear problems II: Second-order elliptic problems

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the Helmholtz equation in the -dimensional unit cube, in which depends linearly on , but nonlinearly on . Here, both and  are -variate functions from a reproducing kernel Hilbert space with finite-order weights of order . This means that, although  can be arbitrarily large, and  can be decomposed as sums of functions of at most  variables, with independent of .

In this paper, we apply our previous general results to the Helmholtz equation, subject to either Dirichlet or Neumann homogeneous boundary conditions. We study both the absolute and normalized error criteria. For all four possible combinations of boundary conditions and error criteria, we show that the problem is tractable. That is, the number of evaluations of and  needed to obtain an -approximation is polynomial in  and , with the degree of the polynomial depending linearly on . In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in  , independently of . We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in  and the integral of the univariate kernel is positive, then the Helmholtz equation is strongly tractable for three of the four possible combinations of boundary conditions and error criteria, the only exception being the Dirichlet boundary condition under the normalized error criterion.

     

A general iterative method for equilibrium problems and fixed point problems in Hilbert spaces

In this paper, we introduce two iterative schemes by the general iterative method for finding a common element of the set of an equilibrium problem and the set of fixed points of a nonexpansive mapping in a Hilbert space. Then, we prove two strong convergence theorems for nonexpansive mappings to solve a unique solution of the variational inequality which is the optimality condition for the minimization problem. These results extended and improved the corresponding results of Marino and Xu [G. Marino, H.K. Xu, A general iterative method for nonexpansive mapping in Hilbert spaces, J. Math. Anal. Appl. 318 (2006) 43-52], S. Takahashi and W. Takahashi [S. Takahashi, W. Takahashi, Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (1) (2007) 506-515], and many others.     

A finite steps algorithm for solving convex feasibility problems

This paper develops a new variant of the classical alternating projection method for solving convex feasibility problems where the constraints are given by the intersection of two convex cones in a Hilbert space. An extension to the feasibility problem for the intersection of two convex sets is presented as well. It is shown that one can solve such problems in a finite number of steps and an explicit upper bound for the required number of steps is obtained. As an application, we propose a new finite steps algorithm for linear programming with linear matrix inequality constraints. This solution is computed by solving a sequence of a matrix eigenvalue decompositions. Moreover, the proposed procedure takes advantage of the structure of the problem. In particular, it is well adapted for problems with several small size constraints.     

Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces

In this paper, we introduce an iterative scheme by the viscosity approximation method for finding a common element of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping in a Hilbert space. Then, we prove a strong convergence theorem which is connected with Combettes and Hirstoaga's result [P.L. Combettes, S.A. Hirstoaga, Equilibrium programming in Hilbert spaces, J. Nonlinear Convex Anal. 6 (2005) 117-136] and Wittmann's result [R. Wittmann, Approximation of fixed points of nonexpansive mappings, Arch. Math. 58 (1992) 486-491]. Using this result, we obtain two corollaries which improve and extend their results.     

On computer-assisted proofs for solutions of linear complementarity problems

In this paper we consider the linear complementarity problem where the components of the input data M and q are not exactly known but can be enclosed in intervals. We compare three tests to each other each of which can be used by a computer that supports interval arithmetic to give guaranteed bounds for a solution of the LCP defined by M and q.     

Constrained least-squares solutions of linear inclusions and singular control problems in Hilbert spaces

LetH ₁ andH ₂ be Hilbert spaces and letN be an algebraic subspace ofH ₁ . The least-squares problem for a linear relationLH ₁ H ₂ restricted to an algebraic cosetS:=g+N, g H ₁ , is considered. Various characterizations of a minimizer are derived in the form of inclusion relations that incorporate the constraints, and conditions under which a minimizer exists are developed. In particular, it is shown that generalized forms of the normal equations for constrained least-squares problems become normal inclusions that involve a multivalued adjoint. The setting includes large classes of constrained least-squares minimization problems and optimal control problems subject to generalized boundary conditions.An application of the abstract theory is given to a singular control problem involving ordinary differential equations with generalized boundary conditions, where the control may generate multiresponses. Characterizations of an optimal solution are developed in the form of inclusions that involve either an integrodifferential equation or a differential equation, and adjoint subspaces and/or solutions of certain linear equations.Research supported by the United States Army under Contract No. DAAG-29-83-K-0109.