非光滑参数规划的微分稳定性

稳定性理论是数学规划的重要理论问题之一.主要研究约束集合、扰动函数(最优值函数)、最优解集合与参数扰动之间的关系.稳定性问题的研究也有助于探讨算法收敛性和稳定性.稳定性问题的研究始于70年代.Rockafellar 等人,首先研究了凸规划的稳定性.近些年来才开始研究一般非凸规划的稳定性.Gauvin 等人对非凸规划研究了扰动函数的稳定性与微分稳定性问题,讨论了在一些特殊形式参数扰动的情况下,     

脉冲噪声下图像去模糊非光滑非凸最小化问题的近端线性化最小化算法

去除脉冲噪声是图像复原中的重要任务之一.我们提出一类非光滑非凸模型来恢复模糊和脉冲噪声污染的图像,该模型具有灵活的先验信息引入机制,如盒子约束或低秩等.为了求解所提非凸问题,我们采用近端线性化最小化算法.对于算法中的子问题,我们运用交替方向乘子法.在目标函数满足Kurdyka-Lojasiewicz性质的假设下,我们证明所提算法的全局收敛性.数值实验表明,在主观和客观质量评价方面,我们的方法优于$\ell_{1}$TV和非凸TV模型.     

闭凸集约束下线性矩阵方程求解的松弛交替投影算法

研究线性矩阵方程AXB=C在闭凸集合R约束下的数值迭代解法.所考虑的闭凸集合R为(1)有界矩阵集合,(2)Q-正定矩阵集合和(3)矩阵不等式解集合.构造松弛交替投影算法求解上述问题,并用算子理论证明了由该算法生成的序列具有弱收敛性.给出了矩阵方程AXB=C求对称非负解和对称半正定解的数值算例,大量数值实验验证了该算法的可行性和高效性,并说明该算法与交替投影算法和谱投影梯度算法比较在迭代效率上的明显优势.     

一类新的广义非凸集值变分不等式组

本文的主要目的是引入一类广义非凸集值变分不等式.首先,我们把这类广义非凸集值变分不等式等价的转化为不动,点问题,通过构造一种新的扰动投影算法,在一定条件下,我们证明了所给迭代算法是收敛的.     

Banach空间中φ-渐进非扩展映像不动点的迭代构造

在Mann的迭代算法基础上，运用Banach空间中的广义投影，使渐进非扩展映像每次迭代生成的序列都投影到一个闭凸的集合中．并证明了该算法的强收敛性．     

边界约束非凸二次规划问题的分枝定界方法

本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。     

非凸非精确线搜索时Broyden算法的收敛性

讨论在非凸非精确线搜索时,Broyden算法的的收敛性. 证明当Broyden算法得到的点列收敛时, 该点列一定趋向于稳定点.     

平均凸曲线缩短流的非坍塌性

本文主要研究了平面凸曲线缩短流的非坍塌性质.首先,我们给出了平面凸曲线非坍塌性的定义,并通过定义一个函数Z,我们证明了平面凸曲线非坍塌与函数Z的非负性是等价的.接着,我们利用极值原理证明平面凸曲线缩短流保持非坍塌性质.     

Hilbert空间中的非严格凸情况的Uzawa算法

无穷维空间中目标泛函为严格凸时的Uzawa算法已由Bensoussan等提出.一般说来,对于普通凸泛函,这种算法无效.这是因为在非严格凸情况时,对偶泛函一般是不可微的.本文提出Hilbert空间中的非严格凸情况的Uzawa算法.对于可分离问题,我们就得到了价格分解方法.考虑问题这里,     

凸距离空间内星形子集非扩张型映射不动点*

在本文中.我们给出包含一个集合的某种星形集的刻划及其性质.然后利用这些刻划和性质讨论凸距离空间的星形子集上非扩张型映射的不动点的存在问题,推广了丁协平、Beg和Azam的某些最近结果.最后还给出一个例子说明以上推广是本质上的推广.     

Polyak’s gradient method for split feasibility problem constrained by level sets

In this paper, we are concerned with the split feasibility problem (SFP) whenever the convex sets involved are composed of level sets. By applying Polyak’s gradient method, we get a new and simple algorithm for such a problem. Under standard assumptions, we prove that the whole sequence generated by the algorithm weakly converges to a solution. We also modify the proposed algorithm and state the strong convergence without regularity conditions on the sets involved. Numerical experiments are included to illustrate its applications in signal processing.     

Counting the number of independent sets in chordal graphs

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.     

Finding near-optimal independent sets at scale

The maximum independent set problem is NP-hard and particularly difficult to solve in sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In this paper, we present two new novel heuristic algorithms for computing large independent sets on huge sparse graphs, which are intractable in practice. First, we develop an advanced evolutionary algorithm that uses fast graph partitioning with local search algorithms to implement efficient combine operations that exchange whole blocks of given independent sets. Though the evolutionary algorithm itself is highly competitive with existing heuristic algorithms on large social networks, we further show that it can be effectively used as an oracle to guess vertices that are likely to be in large independent sets. We then show how to combine these guesses with kernelization techniques in a branch-and-reduce-like algorithm to compute high-quality independent sets quickly in huge complex networks. Our experiments against a recent (and fast) exact algorithm for large sparse graphs show that our technique always computes an optimal solution when the exact solution is known, and it further computes consistent results on even larger instances where the solution is unknown. Ultimately, we show that identifying and removing vertices likely to be in large independent sets opens up the reduction space—which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.     

New advances in permutation decoding of first-order Reed-Muller codes

In this paper we describe a variation of the classical permutation decoding algorithm that can be applied to any affine-invariant code with respect to certain type of information sets. In particular, we can apply it to the family of first-order Reed-Muller codes with respect to the information sets introduced in [2]. Using this algorithm we improve considerably the number of errors we can correct in comparison with the known results in this topic.     

On variable dimension algorithms and algorithms using primitive sets

We discuss the basic scheme and convergence conditions of variable dimension algorithms for computing fixed points and show the analogy of the recent algorithm of van der Laan and Talman with a restart) algorithm using primitive sets that was devel-oped earlier by Tuy-Thoai-Muu. Furthermore, we show that to each algorithm of the class developed by van der Laan and Talman one can associate an algorithm using primi-tive sets wnich proceeds according to the same scheme but with a different triangulation.     

An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing

Motivated by the method for the reconstruction of 3D objects from a set of parallel cross sections, based on the binary operation between 2D sets termed “metric average”, we developed an algorithm for the computation of the metric average between two intersecting convex polygons in 2D. For two 1D sets there is an algorithm for the computation of the metric average, with linear time in the number of intervals in the two 1D sets. The proposed algorithm has linear computation time in the number of vertices of the two polygons. As an application of this algorithm, a new technique for morphing between two convex polygons is developed. The new algorithm performs morphing in a non-intuitive way.     

An algorithm for addressing the real interval eigenvalue problem

In this paper we present an algorithm for approximating the range of the real eigenvalues of interval matrices. Such matrices could be used to model real-life problems, where data sets suffer from bounded variations such as uncertainties (e.g. tolerances on parameters, measurement errors), or to study problems for given states.The algorithm that we propose is a subdivision algorithm that exploits sophisticated techniques from interval analysis. The quality of the computed approximation and the running time of the algorithm depend on a given input accuracy. We also present an efficient C++ implementation and illustrate its efficiency on various data sets. In most of the cases we manage to compute efficiently the exact boundary points (limited by floating point representation).     

Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces

We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a half-space or onto the intersection of two half-spaces. Convergence of the algorithm is established and special choices of the half-spaces are proposed.The option to project onto half-spaces instead of general convex sets makes the algorithm more practical. The fact that the half-spaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms.The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super half-spaces, i.e., half-spaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super half-space from a family of such half-spaces. Since projecting a point onto a half-space is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super half-spaces themselves is not too difficult.     

Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon

In this article, we deal with some computational aspects of geodesic convex sets. Motzkin-type theorem, Radon-type theorem, and Helly-type theorem for geodesic convex sets are shown. In particular, given a finite collection of geodesic convex sets in a simple polygon and an “oracle,” which accepts as input three sets of the collection and which gives as its output an intersection point or reports its nonexistence; we present an algorithm for finding an intersection point of this collection.