An approximate proximal-extragradient type method for monotone variational inequalities

Proximal point algorithms (PPA) are attractive methods for monotone variational inequalities. The approximate versions of PPA are more applicable in practice. A modified approximate proximal point algorithm (APPA) presented by Solodov and Svaiter [Math. Programming, Ser. B 88 (2000) 371–389] relaxes the inexactness criterion significantly. This paper presents an extended version of Solodov–Svaiter's APPA. Building the direction from current iterate to the new iterate obtained by Solodov–Svaiter's APPA, the proposed method improves the profit at each iteration by choosing the optimal step length along this direction. In addition, the inexactness restriction is relaxed further. Numerical example indicates the improvement of the proposed method.     

Global Solution of Optimization Problems with Parameter-Embedded Linear Dynamic Systems

This paper develops a theory for the global solution of nonconvex optimization problems with parameter-embedded linear dynamic systems. A quite general problem formulation is introduced and a solution is shown to exists. A convexity theory for integrals is then developed to construct convex relaxations for utilization in a branch-and-bound framework to calculate a global minimum. Interval analysis is employed to generate bounds on the state variables implied by the bounds on the embedded parameters. These bounds, along with basic integration theory, are used to prove convergence of the branch-and-bound algorithm to the global minimum of the optimization problem. The implementation of the algorithm is then considered and several numerical case studies are examined thoroughly     

Dynamic mechanical thermal analysis transitions of partially and fully substituted cellulose fatty esters

The main transitions of cellulose fatty esters with different degrees of substitution (DSs) were investigated with dynamic mechanical thermal analysis. Two distinct main relaxations were observed in partially substituted cellulose esters (PSCEs). They were attributed to the glass‐transition temperature and to the chain local motion of the aliphatic substituents. The temperatures of both transitions decreased when DS or the number of carbon atoms (n) of the acyl substituent increased. Conversely, all the transitions of fully substituted cellulose esters occurred within a narrow temperature range, and they did not vary significantly with n. This phenomenon was explained by the formation of a crystalline phase of the fatty substituents. The presence of few residual OH groups in PSCEs was responsible for a large increase in the storage bending modulus, and it eliminated the effect of n on damping. © 2002 Wiley Periodicals, Inc. J Polym Sci Part B: Polym Phys 41: 281–288, 2003     

Mathematical topographical correction of XPS images using multivariate statistical methods

For rough heterogeneous samples, the contrast observed in XPS images may result from both changes in elemental or chemical composition and sample topography. Background image acquisition and subtraction are frequently utilized to minimize topographical effects so that images represent concentration variations in the sample. This procedure may significantly increase the data acquisition time. Multivariate statistical methods can assist in resolving topographical and chemical information from multispectral XPS images. Principal component analysis (PCA) is one method for identification of the highest correlation/variation between the images. Topography, which is common to all of the images, will be resolved in the first most significant component. The score of this component contains spatial information about the topography of the surface, whereas the loading is a quantitative representation of the topography contribution to each elemental/chemical image. The simple‐to‐use self‐modelling mixture analysis (Simplisma) method is a pure variable method that searches for the source of most differences in the data and therefore has the potential to distinguish between chemical and topographical phases in images. The mathematical background correction scheme is developed and validated by comparing results to the experimental background correction for samples with differing degrees of topography. Copyright © 2004 John Wiley & Sons, Ltd.     

Compact directed acyclic word graphs for a sliding window

Suffix trees are a well-known and widely-studied data structure highly useful for string matching. The suffix tree of a string w can be constructed in O(n) time and space, where n denotes the length of w. Larsson achieved an efficient algorithm to maintain suffix trees for a sliding window. It contributes to prediction by partial matching (PPM) style statistical data compression scheme. Compact directed acyclic word graphs (CDAWGs) are a more space-economical data structure for indexing strings. In this paper we propose a linear-time algorithm to maintain CDAWGs for a sliding window.     

Parametric multiple sequence alignment and phylogeny construction

Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual formulations of these problems fall within the same integer parametric framework, implying that the number of distinct optima obtained as the parameters are varied across their ranges is polynomially bounded in the length and number of sequences.     

Lot-sizing with fixed charges on stocks: the convex hull

In this paper, we examine a variant of the uncapacitated lot-sizing model of Wagner–Whitin that includes fixed charges on the stocks. Such a model is natural in a production environment where stocking is a complex operation, and appears as a subproblem in more general network design problems.

Linear-programming formulations, a dynamic program, the convex hull of integer solutions and a separation algorithm are presented. All these turn out to be very natural extensions of the corresponding results of Barany et al. (Math. Programming Stud. 22 (1984) 32) for the uncapacitated lot-sizing problem. The convex hull proof is based on showing that an extended facility location formulation is tight and by projecting it onto the original space of variables.     

The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Towards the Exact Minimization of BDDs—An Elitism-Based Distributed Evolutionary Algorithm

Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.