Local linear convergence analysis of Primal–Dual splitting methods

In this paper, we study the local linear convergence properties of a versatile class of Primal–Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework, we first show that (i) the sequences generated by Primal–Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal–Dual splitting can be specialized to cover existing ones on Forward–Backward splitting and Douglas–Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning. The demonstration not only verifies the local linear convergence behaviour of Primal–Dual splitting methods, but also the insights on how to accelerate them in practice.     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

Robust linear optimization under general norms

We explicitly characterize the robust counterpart of a linear programming problem with uncertainty set described by an arbitrary norm. Our approach encompasses several approaches from the literature and provides guarantees for constraint violation under probabilistic models that allow arbitrary dependencies in the distribution of the uncertain coefficients.     

Modules over Operator Algebras and Its Module Maps

ＭｏｄｕｌｅｓｏｖｅｒＯｐｅｒａｔｏｒＡｌｇｅｂｒａｓａｎｄＩｔｓＭｏｄｕｌｅＭａｐｓＸｕＴｉａｎｚｈｏｕ（许天周）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＵｎｉｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ，２１００９３）ＡｂｓｔｒａｃｔＬｅ...     

Dual Characterizations of Set Containments with Strict Convex Inequalities

Characterizations of the containment of a convex set either in an arbitrary convex set or in the complement of a finite union of convex sets (i.e., the set, described by reverse-convex inequalities) are given. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. The convex sets considered in this paper are the solution sets of an arbitrary number of convex inequalities, which can be either weak or strict inequalities. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems where they are used to describe the containments as inequality constraints in optimization problems. The idea of evenly convex set (intersection of open half spaces), which was introduced by W. Fenchel in 1952, is used to derive the dual conditions, characterizing the set containments.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

关于解椭圆型问题的多子域D-N交替算法

构造一个求解椭圆型边值问题的多子域D—N交替算法，导出对应的容度方程和等价的迭代法，证明算法的收敛性。     

A Degenerate Stefan Problem with Two Free Boundaries

ＡＤｅｇｅｎｅｒａｔｅＳｔｅｆａｎＰｒｏｂｌｅｍｗｉｔｈＴｗｏＦｒｅｅＢｏｕｎｄａｒｉｅｓ￥（李辉来）ＬｉＨｕｉｌａｉ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ，１３００２３）Ａｂｓｔｒａｃｔ...     

作业车间调度问题的改进混合遗传算法

作业车间调度是一类求解困难的组合优化问题,本文在考虑遗传算法早熟收敛问题和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法相结合,提出了一种基于遗传和禁忌搜索的混合算法,并用实例对该算法进行了仿真研究.结果表明,该算法有很好的收敛精度,是可行的,与传统的算法相比较,有明显的优越性.     

Dual frames in connected with generalized sampling in shift-invariant spaces

The aim of this article is to derive stable generalized sampling in a shift-invariant space by using some special dual frames in L²(0,1). These sampling formulas involve samples of filtered versions of the functions in the shift-invariant space. The involved samples are expressed as the frame coefficients of an appropriate function in L²(0,1) with respect to some particular frame in L²(0,1). Since any shift-invariant space with stable generator is the image of L²(0,1) by means of a bounded invertible operator, our generalized sampling is derived from some dual frame expansions in L²(0,1).