Lower semicontinuous functionals with uniform sublevel sets

In this paper, lower semicontinuous functionals with uniform sublevel sets are investigated, where the sublevel sets are linear shifts of a set in a fixed direction. The extended real-valued functionals are defined on a topological vector space. Conditions are given under which they are proper, finite-valued, continuous, convex, sublinear, strictly quasi-convex, strictly quasi-concave or monotone. We apply the functionals to the separation of not necessarily convex sets.     

Optimization for Inconsistent Split Feasibility Problems

The split feasibility problem deals with finding a point in a closed convex subset of the domain space of a linear operator such that the image of the point under the linear operator is in a prescribed closed convex subset of the image space. The split feasibility problem and its variants and generalizations have been widely investigated as a means for resolving practical inverse problems in various disciplines. Many iterative algorithms have been proposed for solving the problem. This article discusses a split feasibility problem which does not have a solution, referred to as an inconsistent split feasibility problem. When the closed convex set of the domain space is the absolute set and the closed convex set of the image space is the subsidiary set, it would be reasonable to formulate a compromise solution of the inconsistent split feasibility problem by using a point in the absolute set such that its image of the linear operator is closest to the subsidiary set in terms of the norm. We show that the problem of finding the compromise solution can be expressed as a convex minimization problem over the fixed point set of a nonexpansive mapping and propose an iterative algorithm, with three-term conjugate gradient directions, for solving the minimization problem.     

A relaxed self-adaptive CQ algorithm for the multiple-sets split feasibility problem

The multiple-sets split feasibility problem (MSFP) is to find a point belongs to the intersection of a family of closed convex sets in one space, such that its image under a linear transformation belongs to the intersection of another family of closed convex sets in the image space. Many iterative methods can be employed to solve the MSFP. Jinling Zhao et al. proposed a modification for the CQ algorithm and a relaxation scheme for this modification to solve the MSFP. The strong convergence of these algorithms are guaranteed in finite-dimensional Hilbert spaces. Recently López et al. proposed a relaxed CQ algorithm for solving split feasibility problem, this algorithm can be implemented easily since it computes projections onto half-spaces and has no need to know a priori the norm of the bounded linear operator. However, this algorithm has only weak convergence in the setting of infinite-dimensional Hilbert spaces. In this paper, we introduce a new relaxed self-adaptive CQ algorithm for solving the MSFP where closed convex sets are level sets of some convex functions such that the strong convergence is guaranteed in the framework of infinite-dimensional Hilbert spaces. Our result extends and improves the corresponding results.     

不同凸集条件下CQ算法的应用分析

针对CQ算法,通过定义不同条件的下非空闭凸集C和Q,并结合讨论稀疏角度的CT重建问题,在R^N空间中给出了5种不同的实现方案,每种实现方案相对于CT重建模型,具备不同的物理含义.给定相同的迭代步数,通过仿真试验,分别对不同方案的重建精度进行了分析,从而确定了在相同收敛条件下CQ算法在应用时的最佳方案,为分裂可行性问题及其扩展形式在工程领域的应用提供了新的思路.     

Proximity Function Minimization Using Multiple Bregman Projections, with Applications to Split Feasibility and Kullback–Leibler Distance Minimization

Problems in signal detection and image recovery can sometimes be formulated as a convex feasibility problem (CFP) of finding a vector in the intersection of a finite family of closed convex sets. Algorithms for this purpose typically employ orthogonal or generalized projections onto the individual convex sets. The simultaneous multiprojection algorithm of Censor and Elfving for solving the CFP, in which different generalized projections may be used at the same time, has been shown to converge for the case of nonempty intersection; still open is the question of its convergence when the intersection of the closed convex sets is empty.Motivated by the geometric alternating minimization approach of Csiszár and Tusnády and the product space formulation of Pierra, we derive a new simultaneous multiprojection algorithm that employs generalized projections of Bregman to solve the convex feasibility problem or, in the inconsistent case, to minimize a proximity function that measures the average distance from a point to all convex sets. We assume that the Bregman distances involved are jointly convex, so that the proximity function itself is convex. When the intersection of the convex sets is empty, but the closure of the proximity function has a unique global minimizer, the sequence of iterates converges to this unique minimizer. Special cases of this algorithm include the Expectation Maximization Maximum Likelihood (EMML) method in emission tomography and a new convergence result for an algorithm that solves the split feasibility problem.     

凸可行问题的一种强收敛算法

无限维Hilbert空间中,解凸可行问题的平行投影算法通常是弱收敛的.本文对一般的平行投影算法进行改进,设计了一种解凸可行问题的具有强收敛性的新算法.该算法主要是在原有算法基础上引入了一个参数序列,在参数序列满足一定的控制条件下保证了算法的强收敛性.为了简单证明算法的强收敛性,我们构建了一个新的积空间,然后把原空间的这种改进平行投影算法转换为积空间中的交替投影算法.这样,改进的平行投影算法的强收敛性就可以通过交替投影算法的收敛性证明得到.     

Abstract convergence theorem for quasi-convex optimization problems with applications

Abstract

Quasi-convex optimization is fundamental to the modelling of many practical problems in various fields such as economics, finance and industrial organization. Subgradient methods are practical iterative algorithms for solving large-scale quasi-convex optimization problems. In the present paper, focusing on quasi-convex optimization, we develop an abstract convergence theorem for a class of sequences, which satisfy a general basic inequality, under some suitable assumptions on parameters. The convergence properties in both function values and distances of iterates from the optimal solution set are discussed. The abstract convergence theorem covers relevant results of many types of subgradient methods studied in the literature, for either convex or quasi-convex optimization. Furthermore, we propose a new subgradient method, in which a perturbation of the successive direction is employed at each iteration. As an application of the abstract convergence theorem, we obtain the convergence results of the proposed subgradient method under the assumption of the Hölder condition of order p and by using the constant, diminishing or dynamic stepsize rules, respectively. A preliminary numerical study shows that the proposed method outperforms the standard, stochastic and primal-dual subgradient methods in solving the Cobb–Douglas production efficiency problem.     

Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in a suitable product space we are able to present a simultaneous subgradients projections algorithm that generates convergent sequences of iterates in the feasible case. We further derive and analyze a perturbed projection method for the multiple-sets split feasibility problem and, additionally, furnish alternative proofs to two known results.     

On the finite termination of the Douglas-Rachford method for the convex feasibility problem

In this paper we apply the Douglas–Rachford (DR) method to solve the problem of finding a point in the intersection of the interior of a closed convex cone and a closed convex set in an infinite-dimensional Hilbert space. For this purpose, we propose two variants of the DR method which can find a point in the intersection in a finite number of iterations. In order to analyse the finite termination of the methods, we use some properties of the metric projection and a result regarding the rate of convergence of fixed point iterations. As applications of the results, we propose the methods for solving the conic and semidefinite feasibility problems, which terminate at a solution in a finite number of iterations.     

Accelerated reflection projection algorithm and its application to the LMI problem

We discuss accelerated version of the alternating projection method which can be applied to solve the linear matrix inequality (LMI) problem. The alternating projection method is a well-known algorithm for the convex feasibility problem, and has many generalizations and extensions. Bauschke and Kruk proposed a reflection projection algorithm for computing a point in the intersection of an obtuse cone and a closed convex set. We carry on this research in two directions. First, we present an accelerated version of the reflection projection algorithm, and prove its weak convergence in a Hilbert space; second, we prove the finite termination of an algorithm which is based on the proposed algorithm and provide an explicit upper bound for the required number of iterations under certain assumptions. Numerical experiments for the LMI problem are provided to demonstrate the effectiveness and merits of the proposed algorithms.     

New algorithms for the split variational inclusion problems and application to split feasibility problems

ABSTRACT

In this paper, we suggest two new iterative methods for finding an element of the solution set of split variational inclusion problem in real Hilbert spaces. Under suitable conditions, we present weak and strong convergence theorems for these methods. We also apply the proposed algorithms to study the split feasibility problem. Finally, we give some numerical results which show that our proposed algorithms are efficient and implementable from the numerical point of view.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

A Successive Projection Algorithm for Solving the Multiple-Sets Split Feasibility Problem

The multiple-sets split feasibility problem (MSFP) arises in many areas and it can be unified as a model for many inverse problems where the constraints are required on the solutions in the domain of a linear operator as well as in the operator's range. Some existing algorithms, in order to get the suitable step size, need to compute the largest eigenvalue of the related matrix, estimate the Lipschitz constant, or use some step-size search scheme, which usually requires many inner iterations. In this article, we introduce a successive projection algorithm for solving the multiple-sets split feasibility problem. In each iteration of this algorithm, the step size is directly computed, which is not needed to compute the largest eigenvalue of the matrix or estimate the Lipschitz constant. It also does not need any step-size search scheme. Its theoretical convergence results are also given.     

Algorithms with new parameter conditions for split variational inclusion problems in Hilbert spaces with application to split feasibility problem

Split variational inclusion problem is an important problem, and it is a generalization of the split feasibility problem. In this paper, we present feasible algorithms for the split variational inclusion problems in Hilbert spaces, and provide convergence theorems for these algorithms. As application, we study the split feasibility problem in real Hilbert spaces. Final, numerical results are given for our main results.     

Extragradient and linesearch methods for solving split feasibility problems in Hilbert spaces

Utilizing the Tikhonov regularization method and extragradient and linesearch methods, some new extragradient and linesearch algorithms have been introduced in the framework of Hilbert spaces. In the presented algorithms, the convexity of optimization subproblems is assumed, which is weaker than the strong convexity assumption that is usually supposed in the literature, and also, the auxiliary equilibrium problem is not used. Some strong convergence theorems for the sequences generated by these algorithms have been proven. It has been shown that the limit point of the generated sequences is a common element of the solution set of an equilibrium problem and the solution set of a split feasibility problem in Hilbert spaces. To illustrate the usability of our results, some numerical examples are given. Optimization subproblems in these examples have been solved by FMINCON toolbox in MATLAB.     

Convergence Theorem for Variational Inequality in Hilbert Spaces with Applications

In this paper, we study variational inequality over the set of the common fixed points of a countable family of quasi-nonexpansive mappings. To tackle this problem, we propose an algorithm and use it to prove a strong convergence theorem under suitable conditions. As applications, we study variational inequality over the solution set of different nonlinear or linear problems, like minimization problems, split feasibility problems, convexly pseudoinverse problems, convex linear inverse problems, etc.     

Convergence in norm of modified Krasnoselski-Mann iterations for fixed points of demicontractive mappings

This paper deals with fixed points methods related to the general class of demicontractive mappings (including the well-known classes of nonexpansive and quasi-nonexpansive mappings) in Hilbert spaces. Specifically, we point out some historical aspects concerning the concept of demicontactivity and we investigate a regularized variant of the Krasnoselski-Mann iteration that can be alternatively regarded as a simplified form of the inertial iteration (P-E. Maingé, J. Math. Anal. Appl. 344 (2008) 876-887) with non-constant relaxation factors. These two methods ensure the strong convergence of the generated sequence towards the least norm element of the set of fixed-points of demicontractive mappings. However, for convergence, our method does not require anymore the knowledge of some constant related to the involved demicontractive operator. A new and simpler proof is also proposed for its convergence even when involving non-constant relaxation factors. We point out the simplicity of this algorithm (at least from computational point of view) in comparison with other existing methods. We also present some numerical experiments concerning a convex feasibility problem, experiments that emphasize the characteristics of the considered algorithm comparing with a classical cyclic projection-type iteration.     

凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.     

多重集非凸分裂可行问题的非精确均值投影算法

在本文中,我们引入了非精确均值投影算法来求解多重集非凸分裂可行问题,其中这些非凸集合为半代数邻近正则集合.通过借助著名的Kurdyka-Lojasiewicz不等式理论,我们建立了算法的收敛性.     

Inexact subgradient methods for quasi-convex optimization problems

In this paper, we consider a generic inexact subgradient algorithm to solve a nondifferentiable quasi-convex constrained optimization problem. The inexactness stems from computation errors and noise, which come from practical considerations and applications. Assuming that the computational errors and noise are deterministic and bounded, we study the effect of the inexactness on the subgradient method when the constraint set is compact or the objective function has a set of generalized weak sharp minima. In both cases, using the constant and diminishing stepsize rules, we describe convergence results in both objective values and iterates, and finite convergence to approximate optimality. We also investigate efficiency estimates of iterates and apply the inexact subgradient algorithm to solve the Cobb–Douglas production efficiency problem. The numerical results verify our theoretical analysis and show the high efficiency of our proposed algorithm, especially for the large-scale problems.