Maximizing for the sum of ratios of two convex functions over a convex set

This paper presents an algorithm for globally maximizing a sum of convex–convex ratios problem with a convex feasible region, which does not require involving all the functions to be differentiable and requires that their sub-gradients can be calculated efficiently. To our knowledge, little progress has been made for globally solving this problem so far. The algorithm uses a branch and bound scheme in which the main computational effort involves solving a sequence of linear programming subproblems. Because of these properties, the algorithm offers a potentially attractive means for globally solving the sum of convex–convex ratios problem over a convex feasible region. It has been proved that the algorithm possesses global convergence. Finally, the numerical experiments are given to show the feasibility of the proposed algorithm.     

On completeness for NP via projection translations

In this paper we investigate the logics obtained by augmenting first-order logic (with successor) with operators corresponding to some decision problems complete forNP via logspace reductions. We show that our encodings of the Satisfiability Problem and the 3-Colourability Problem, namely SAT and 3COL, respectively (as sets of finite structures over specific vocabularies), are complete forNP via projection translations (very weak reductions between problems): the fact that an encoding of the Satisfiability Problem (resp. the 3-Satisfiability Problem) is (resp. not) complete forNP via interpretative reductions (again, very weak reductions) had been shown previously by Dahlhaus. It is unknown whether our encoding of the 3-Satisfiability Problem, namely 3SAT, is complete forNP via projection translations, although we show that it is for iterated projection translations. However, if we consider an encoding of the version of the 3-Satisfiability Problem where each instance has at most three literals in each clause (as opposed to exactly three literals), namely 3SAT, then we show that 3SAT is complete forNP via projection translations. It appears to matter as to how we encode a decision problem as a set of finite structures over some vocabulary when considering weak reductions such as ours. Our proof that SAT is complete forNP via projection translations differs extremely from the proof of Dahlhaus that SAT is complete forNP via interpretative reductions, as he relies on Fagin's well-known characterization ofNP whereas our results do not: indeed, they give Fagin's result as a corollary. We use the problem 3COL to show the difference between interpretative reductions and projection translations as we show that 3COL is complete forNP via the latter but not via the former. The logics mentioned above are shown to be similar in expressibility but are shown to be much more expressible than that formed by extending first-order logic with an operator corresponding to the Hamiltonian path problem for digraphs (assumingNP co-NP).     

3-D reconstruction of homogeneous objects from two poisson-distributed projections

It is computationally very convenient to view the problem of reconstructing a homogeneous 3-D object from two orthogonal projections as a flow problem in a capacitated network. This network flow approach is extended here to incorporate the Poisson nature of the projection data, as is the case in X-ray imaging.     

Perturbation‐resilient block‐iterative projection methods with application to image reconstruction from projections

A block‐iterative projection algorithm for solving the consistent convex feasibility problem in a finite‐dimensional Euclidean space that is resilient to bounded and summable perturbations (in the sense that convergence to a feasible point is retained even if such perturbations are introduced in each iterative step of the algorithm) is proposed. This resilience can be used to steer the iterative process towards a feasible point that is superior in the sense of some functional on the points in the Euclidean space having a small value. The potential usefulness of this is illustrated in image reconstruction from projections, using both total variation and negative entropy as the functional.     

2 guaranteed cost control for uncertain continuous-time linear systems

This paper proposes a solution to the ₂ guaranteed cost control problem for uncertain, continuous-time linear systems. It consists of the determination of a constant state feedback stabilizing matrix gain and a ₂-norm upper bound, valid for all feasible models. The uncertainties are only assumed to be convex-bounded, a concept which generalizes the important case of interval matrices uncertainties. The results follow from a new parameterization of all stabilizing gains over a convex set. As an additional property, the above mentioned ₂-norm upper bound reduces to the minimum ₂ cost in case of precisely known linear systems.     

高阶Hopfield神经网求解合取范式可满足性问题

本文提出用高阶Ｈｏｐｆｉｅｌｄ神经网络求解ＳＡＴ问题，给出了连续及离散高阶神经网络模型与相应的离散快速求解算法，证明了网络的稳定性，并用实验证明了该方法的可行性，且将该算法与Ｌｏｃａｌ Ｓｅａｒｃｈ算法进行了比较。     

基于SAT的多目标故障测试向量动态压缩方法

针对传统的自动测试图形向量生成采用逐个求解单一故障模型导致生成测试向量数据量巨大的缺点, 提出一种基于布尔满足性(boolean satisfiability, SAT)的多目标故障测试向量动态压缩方法, 同时论证多目标故障测试生成问题为布尔满足性问题。该方法将具有鲁棒性的SAT算法嵌入经典的动态压缩流程中, 首先利用经典动态压缩算法求解最小测试向量检测大部分失效故障, 然后采用SAT求解器对未测出的多故障电路进行同一求解和附加约束求解方式, 最终得到故障覆盖率高的测试向量和同一测试最大故障列表。实验数据表明, 在相同电路模型情况下, 此方法求得的测试向量相比经典动态压缩减少高达70%。     

基于混合投影的频繁模式挖掘算法

频繁模式挖掘是最基本的数据挖掘问题，由于内在复杂性，提高挖掘算法性能一直是个难题．耶是通过数据库混合投影来挖掘频繁模式完全集的全新算法．HP混合投影思想是：任意数据集都不能简单地归入某个单一特性类别，挖掘过程应根据局部数据子集的特性变化动态地调整频繁模式树构造策略、事务子集表示形式、投影方法．HP提出基于树表示的虚拟投影与基于数组表示的非过滤投影，较好地解决了提高时间效率与节省内存空间的矛盾．实验表明，HP时间效率比Apriori，FP—Growth和H-Mine高出1～3个数量级，并且空间可伸缩性也大大优于这些算法．     

Inexact dual averaging method for distributed multi-agent optimization

We consider a distributed convex optimization problem over a network where multiple agents collectively try to minimize a sum of local convex functions of the same variables, each of which is available to one specific agent only. For solving this optimization problem, we present an inexact version of the dual averaging method. This extends recent results of Duchi (2012), which cover the error-free case, to the case where an error is present in calculating the subgradient of the objective function or in computing the projection. We show that when the errors decrease at appropriate rates, our method achieves the same convergence rate as in the error-free case. In particular, the convergence of the method is also established for nonsummable errors. We also provide numerical results to validate the theoretic results.     

用于特征点配准的快速聚类凸集投影算法

提出一种用于特征点配准的快速聚类凸集投影算法. 该算法首先将模板点集和目标点集的配准问题通过聚类转化为相应类集合的配准问题，降低了算法的计算量；进而采用基于二次规划的凸集投影来求解类配准问题，避免了序贯凸集投影算法由于交替行列投影而引起的积累误差. 仿真表明，相对于现有的特征点配准算法，本文算法的配准精度和计算量均有所改善.     

基于演化算法的SAT问题求解

SAT问题即布尔可满足性问题是逻辑学的一个基本问题,也是计算机科学和人工智能研究的核心问题。寻找求解SAT问题的快速算法不仅在理论研究上而且在许多应用领域都具有极其重要的意义。本文讨论了基于演化算法的SAT问题求解方法。     

On the complexity of finding bounds for projection cardinalities in relational databases

We address the problem of deriving lower and upper bounds for the cardinality of the projections of a database relation, given a set of functional dependencies on the relation schema and measures of the cardinalities of the attributes in the schema. It is shown that deciding whether a given number is the least upper bound of a projection cardinality is an NP-complete problem, whereas determining whether the greatest lower bound and the least upper bound coincide can be easily solved in linear time.     

互联网信息组织和规划中的带拒绝装箱问题

讨论如下定义的带拒绝装箱问题：设有许多等长的一维箱子，给定一个物品集，每个物品有两个参数：长度和罚值．物品可以放入箱子也可被拒绝放入箱子．如果将物品放入箱子，则使该箱剩余长度减少．一旦需将某一物品放入某一箱中，而该箱的剩余长度不够时，则需启用新箱子．如果物品被拒绝放入任何箱中，则产生惩罚．问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题，来源于内部互联网的信息组织和规划．该文首先给出一个最优解值的下界估计，它可用于分枝定界法求最优解．由于该问题是强NP-难的，该文进一步研究它的离线和在线近似算法的设计与分析．文中给出一个离线算法，其绝对性能比为2；同时给出一个在线算法，其绝对性能比不超过3，渐近性能比为2，还对算法性能比的下界进行了讨论．     

Implementation of a subgradient projection algorithm

This paper discusses the implementation of an algorithm due to Sreedharan [8] for the minimization, subject to linear constraints, of an objective function composed of the sum of a piecewise-affine, convex function with a smooth, strictly convex function. Successful techniques for two subproblems arising in the algorithm, a projection problem and a line search problem, are described in detail. Computational experience with the algorithm on several test problems is presented.     

Mending broken vessels a fusion between color markings and anchor points on surface breaks

This paper presents a method to assist in the tedious process of reconstructing ceramic vessels from excavated fragments. The method exploits vessel surface marking information coupled with a series of generic models constructed by the archaeologists to produce a virtual reconstruction of what the original vessel may have looked like. Generic models are generated based on the experts’ historical knowledge of the period, provenance of the artifact, and site location. The generic models need not to be identical to the original vessel, but must be within a geometric transformation of it in most parts. By aligning the fragments against the generic models, the ceramic vessels are virtually reconstructed. The alignment is based on a novel set of weighted discrete moments computed from convex hulls of the markings on the surface of the fragments and the generic vessels. When the fragments have no markings on them, they are virtually mended to abutting fragments using intrinsic differential anchor points computed on the surface breaks and aligned using a set of absolute invariants. For axially symmetric objects, a global constraint induced by the surface of revolution is added to guarantee global mending consistency.     

Exact 3-satisfiability is decidable in time O(20.16254n)

Let F = C ₁ C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SAT O(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SAT O(2^0.16254n ).An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002).     

A gradient projection algorithm for relaxation methods

We consider a particular problem which arises when apply-ing the method of gradient projection for solving constrained optimiza-tion and finite dimensional variational inequalities on the convex set formed by the convex hull of the standard basis unit vectors. The method is especially important for relaxation labeling techniques applied to problems in artificial intelligence. Zoutendijk's method for finding feasible directions, which is relatively complicated in general situations, yields a very simple finite algorithm for this problem. We present an extremely simple algorithm for performing the gradient projection and an independent verification of its correctness.     

Reduction constraints for the global optimization of NLPs

Convergence of branch‐and‐bound algorithms for the solution of NLPs is obtained by finding ever‐nearer lower and upper bounds to the objective function. The lower bound is calculated by constructing a convex relaxation of the NLP. Reduction constraints are new linear problem constraints which are (a) linearly independent from the existing constraints; (b) redundant with reference to the original NLP formulation; (c) not redundant with reference to its convex relaxation. Thus, they can be successfully employed to reduce the feasible region of the convex relaxation without cutting the feasible region of the original NLP.     

A Parallelization Scheme Based on Work Stealing for a Class of SAT Solvers

Because of the inherent NP-completeness of SAT, many SAT problems currently cannot be solved in a reasonable time. Usually, in order to tackle a new class of SAT problems, new ad hoc algorithms must be designed. Another way to solve a new problem is to use a generic solver and employ parallelism to reduce the solve time. In this paper we propose a parallelization scheme for a class of SAT solvers based on the DPLL procedure. The scheme uses a dynamic load-balancing mechanism based on work-stealing techniques to deal with the irregularity of SAT problems. We parallelize Satz, one of the best generic SAT solvers, with our scheme to obtain a parallel solver called PSatz. The first experimental results on random 3-SAT problems and a set of well-known structured problems show the efficiency of PSatz. PSatz is freely available and runs on any networked workstations under Unix/Linux.     

Solving the signorini problem on the basis of domain decomposition techniques

The finite element discretization of the Signorini Problem leads to a large scale constrained minimization problem. To improve the convergence rate of the projection method preconditioning must be developed. To be effective, the relative condition number of the system matrix with respect to the preconditioning matrix has to be small and the applications of the preconditioner as well as the projection onto the set of feasible elements have to be fast computable. In this paper, we show how to construct and analyze such preconditioners on the basis of domain decomposition techniques. The numerical results obtained for the Signorini problem as well as for contact problems in plane elasticity confirm the theoretical analysis quite well.