Search

The paper introduces and analyzes the convergence of a new iterative algorithm for approximating solutions of equilibrium problems involving strongly pseudomonotone and Lipschitz-type bifunctions in Hilbert spaces. The algorithm uses a stepsize sequence which is non-increasing, diminishing, and non-summable. This leads to the main advantage of the algorithm, namely that the construction of solution approximations and the proof of its convergence are done without the prior knowledge of the modulus of strong pseudomonotonicity and Lipschitz-type constants of bifunctions. The strongly convergent theorem is established under suitable assumptions. The paper also discusses the assumptions used in the formulation of the convergent theorem. Several numerical results are reported to illustrate the behavior of the algorithm with different sequences of stepsizes and also to compare it with others. [ABSTRACT FROM AUTHOR]

In this paper, we study a special instance of the split inverse problem (SIP), which is the split variational inclusion problem (SVIP). Three simple iterative methods for solving it are introduced and weak and strong convergence theorems are established under mild and standard assumptions. As an application, the problem of minimizing two proper, convex, and lower semi-continuous functions is considered. We compare and illustrate the efficiency and applicability of our schemes for several numerical experiments as well as an example in the field of compressed sensing. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to study some iterative algorithms for finding a common element of the set of solutions of systems of variational inequalities for inverse-strongly accretive mappings and the set of fixed points of an asymptotically nonexpansive mapping in uniformly convex and 2-uniformly smooth Banach space or uniformly convex and q-uniformly smooth Banach space. Strong convergence theorems are obtained under suitable conditions. We also give some numerical examples to support our main results. The results obtained in this paper improve and extend the recent ones announced by many others in the literature. [ABSTRACT FROM AUTHOR]

Since the beginning of the development of interior-point methods, there exists a puzzling gap between the results in theory and the observations in numerical experience, i.e., algorithms with good polynomial bounds are not computationally efficient and algorithms demonstrated efficiency in computation do not have a good or any polynomial bound. Todd raised a question in 2002: “Can we find a theoretically and practically efficient way to reoptimize?” This paper is an effort to close the gap. We propose two arc-search infeasible interior-point algorithms with infeasible central path neighborhood wider than all existing infeasible interior-point algorithms that are proved to be convergent. We show that the first algorithm is polynomial and its simplified version has a complexity bound equal to the best known complexity bound for all (feasible or infeasible) interior-point algorithms. We demonstrate the computational efficiency of the proposed algorithms by testing all Netlib linear programming problems in standard form and comparing the numerical results to those obtained by Mehrotra’s predictor-corrector algorithm and a recently developed more efficient arc-search algorithm (the convergence of these two algorithms is unknown). We conclude that the newly proposed algorithms are not only polynomial but also computationally competitive compared to both Mehrotra’s predictor-corrector algorithm and the efficient arc-search algorithm. [ABSTRACT FROM AUTHOR]

In this paper we consider the common fixed point problem for a finite family of quasi-nonexpansive mappings $U_{i}\colon \mathcal H\rightarrow \mathcal H$ , where i ∈ I := {1,..., M}, M≥1, and $\mathcal H$ is a real Hilbert space. This problem is defined as follows: find $x\in \bigcap _{i\in I}\text {Fix} U_{i}\neq \emptyset $ , where Fix $U_{i}:=\{z\in \mathcal H\mid z=U_{i}z\}$ . We propose the following iterative method: where for each k=0,1,2,..., the operator T is defined by a certain amalgamation procedure called modular string averaging. The main idea of this procedure is to combine repeatedly and recursively three primal operations: relaxation, convex combination and composition of the given operators U . The modular string averaging procedure, when combined with the above iterative method, provides a very flexible framework which covers and fills the gap between different algorithmic approaches such as string averaging and block iterative schemes. Moreover, our framework enables us to construct many algorithmic schemes, the convergence of which has not been investigated so far. The aim of this paper is to establish both weak and strong convergence results for the above iterative method. Moreover, in the case of firmly nonexpansive U 's, we show that convergence is preserved in the presence of inexact computations. In particular, this implies that the iterative scheme is resilient to bounded perturbations, which is important from the superiorization methodology point of view. [ABSTRACT FROM AUTHOR]

For the nonsymmetric saddle point problems with nonsymmetric positive definite (1,1) parts, the modified generalized shift-splitting (MGSS) preconditioner as well as the MGSS iteration method is derived in this paper, which generalize the modified shift-splitting (MSS) preconditioner and the MSS iteration method newly developed by Huang and Su (J. Comput. Appl. Math. 317:535-546, 2017), respectively. The convergent and semi-convergent analyses of the MGSS iteration method are presented, and we prove that this method is unconditionally convergent and semi-convergent. Meanwhile, some spectral properties of the preconditioned matrix are carefully analyzed. Numerical results demonstrate the robustness and effectiveness of the MGSS preconditioner and the MGSS iteration method and also illustrate that the MGSS iteration method outperforms the generalized shift-splitting (GSS) and the generalized modified shift-splitting (GMSS) iteration methods, and the MGSS preconditioner is superior to the shift-splitting (SS), GSS, modified SS (M-SS), GMSS and MSS preconditioners for the generalized minimal residual (GMRES) method for solving the nonsymmetric saddle point problems. [ABSTRACT FROM AUTHOR]

The multiple-sets split equality problem, a generalization and extension of the split feasibility problem, has a variety of specific applications in real world, such as medical care, image reconstruction, and signal processing. It can be a model for many inverse problems where constraints are imposed on the solutions in the domains of two linear operators as well as in the operators’ ranges simultaneously. Although, for the split equality problem, there exist many algorithms, there are but few algorithms for the multiple-sets split equality problem. Hence, in this paper, we present a relaxed two points projection method to solve the problem; under some suitable conditions, we show the weak convergence and give a remark for the strong convergence method in the Hilbert space. The interest of our algorithm is that we transfer the problem to an optimization problem, then, based on the model, we present a modified gradient projection algorithm by selecting two different initial points in different sets for the problem (we call the algorithm as two points algorithm). During the process of iteration, we employ subgradient projections, not use the orthogonal projection, which makes the method implementable. Numerical experiments manifest the algorithm is efficient. [ABSTRACT FROM AUTHOR]

We generalize and extend results of the series of papers by Greenbaum and Strakoš (IMA Vol Math Appl 60:95-118, ), Greenbaum et al. (SIAM J Matrix Anal Appl 17(3):465-469, ), Arioli et al. (BIT 38(4):636-643, ) and Duintjer Tebbens and Meurant (SIAM J Matrix Anal Appl 33(3):958-978, ). They show how to construct matrices with right-hand sides generating a prescribed GMRES residual norm convergence curve as well as prescribed Ritz values in all iterations, including the eigenvalues, and give parametrizations of the entire class of matrices and right-hand sides with these properties. These results assumed that the underlying Arnoldi orthogonalization processes are breakdown-free and hence considered non-derogatory matrices only. We extend the results with parametrizations of classes of general nonsingular matrices with right-hand sides allowing the early termination case and also give analogues for the early termination case of other results related to the theory developed in the papers mentioned above. [ABSTRACT FROM AUTHOR]

This paper presents a modified ODE-based algorithm for unconstrained optimization problems. It combines the idea of IMPBOT algorithm with nonmonotone and subspace techniques. The main feature of this method is that at each iteration, a lower dimensional system of linear equations is solved to obtain a trial step. Under some standard assumptions, the method is proven to be globally convergent. Numerical results show the efficiency of this proposed method in practical computation. [ABSTRACT FROM AUTHOR]

In this paper an interior-point algorithm for P( κ) horizontal linear complementarity problems is proposed that uses new search directions. The theoretical complexity of the new algorithm is calculated. It is investigated that the proposed algorithm has quadratically convergent with polynomial iteration complexity $O((1+\kappa)\sqrt{n}\log\frac{n}{\varepsilon})$, coincide with the best known iteration bound for P( κ) horizontal linear complementarity problems. [ABSTRACT FROM AUTHOR]

In this paper we propose a method for computing the roots of a monic matrix polynomial. To this end we compute the eigenvalues of the corresponding block companion matrix C. This is done by implementing the QR algorithm in such a way that it exploits the rank structure of the matrix. Because of this structure, we can represent the matrix in Givens-weight representation. A similar method as in Chandrasekaran et al. (Oper Theory Adv Appl 179:111-143, ), the bulge chasing, is used during the QR iteration. For practical usage, matrix C has to be brought in Hessenberg form before the QR iteration starts. During the QR iteration and the transformation to Hessenberg form, the property of the matrix being unitary plus low rank numerically deteriorates. A method to restore this property is used. [ABSTRACT FROM AUTHOR]

In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(\sqrt{n}\log(\frac{n}{\epsilon}))$ for small-update methods and $O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in the design and analysis of primal-dual interior-point algorithms. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the μ-center for the algorithms. In this paper we present a unified kernel function approach to primal-dual interior-point algorithms for convex quadratic semidefinite optimization based on the Nesterov and Todd symmetrization scheme. The iteration bounds for large- and small-update methods obtained are analogous to the linear optimization case. Moreover, this unifies the analysis for linear, convex quadratic and semidefinite optimizations. [ABSTRACT FROM AUTHOR]

We say that $X=[x_{ij}]_{i,j=1}^n$ is symmetric centrosymmetric if x ij = x ji and x n − j + 1, n − i + 1, 1 ≤ i, j ≤ n. In this paper we present an efficient algorithm for minimizing || AXA T − B|| where ||·|| is the Frobenius norm, A ∈ ℝ m× n, B ∈ ℝ m× m and X ∈ ℝ n× n is symmetric centrosymmetric with a specified central submatrix [ x ij] p ≤ i, j ≤ n − p. Our algorithm produces a suitable X such that AXA T = B in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim. [ABSTRACT FROM AUTHOR]

In this paper, the use of N-AGE and Newton-N-AGE iterative methods on a variable mesh for the solution of one dimensional parabolic initial boundary value problems is considered. Using three spatial grid points, a two level implicit formula based on Numerov type discretization is discussed. The local truncation error of the method is of $O({k^2h_l^{-1} +kh_l +h_l^3})$, where h l > 0 and k > 0 are the step lengths in space and time directions, respectively. We use a special technique to handle singular parabolic equations. The advantage of using these algorithms is highlighted computationally. [ABSTRACT FROM AUTHOR]

Abstract  A method for linearly constrained optimization which modifies and generalizes recent box-constraint optimization algorithms is introduced. The new algorithm is based on a relaxed form of Spectral Projected Gradient iterations. Intercalated with these projected steps, internal iterations restricted to faces of the polytope are performed, which enhance the efficiency of the algorithm. Convergence proofs are given and numerical experiments are included and commented. Software supporting this paper is available through the Tango Project web page: http://www.ime.usp.br/∼egbirgin/tango/. [ABSTRACT FROM AUTHOR]

Abstract  Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained. [ABSTRACT FROM AUTHOR]