Classes and clusters in data analysis

We discuss the relation between classes and clusters in datasets with given classes. We examine the distribution of classes within obtained clusters, using different clustering methods which are based on different techniques. We also study the structure of the obtained clusters. One of the main conclusions, obtained in this research is that the notion purity cannot be always used for evaluation of accuracy of clustering techniques.     

Recursive constructions of secure codes and hash families using difference function families

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.     

在计算机模拟试验中不同试验设计的比较

计算机模拟试验的设计与建模有许多方法,本文选择了四种不同类型的真模型,用四种试验设计方法,考虑了大小不同的试验方案,并选用了四种建模方法进行比较,给出一些经验性结论,相信这些结论在计算机试验中是有参考价值的。     

Accurate solution of polynomial equations using Macaulay resultant matrices

We propose an algorithm for solving two polynomial equations in two variables. Our algorithm is based on the Macaulay resultant approach combined with new techniques, including randomization, to make the algorithm accurate in the presence of roundoff error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundoff of the method, showing that with high probability the roots are computed accurately, assuming that the input data (that is, the two polynomials) are well conditioned. Our analysis requires a novel combination of algebraic and numerical techniques.

     

Two acceleration mechanisms in verified global optimization

Acceleration devices are very important to speed up interval global optimization algorithms. We propose here two techniques which can be applied in addition to other known techniques. Firstly, we propose a test based on the one-dimensional Newton iteration to discard or split the current box. This test is usually cheap and it is likely to be successful when a good approximation of the minimum is known early. The other technique proposed deals with parallelization. We propose to share the task of the manager process among other non-idle processes in such a way that not only one process is responsible for the load balancing. Experimental results presented show that both techniques yield significant improvements in many cases.     

Approximations and Randomization to Boost CSP Techniques

In recent years we have seen an increasing interest in combining constraint satisfaction problem (CSP) formulations and linear programming (LP) based techniques for solving hard computational problems. While considerable progress has been made in the integration of these techniques for solving problems that exhibit a mixture of linear and combinatorial constraints, it has been surprisingly difficult to successfully integrate LP-based and CSP-based methods in a purely combinatorial setting. Our approach draws on recent results on approximation algorithms based on LP relaxations and randomized rounding techniques, with theoretical guarantees, as well on results that provide evidence that the runtime distributions of combinatorial search methods are often heavy-tailed. We propose a complete randomized backtrack search method for combinatorial problems that tightly couples CSP propagation techniques with randomized LP-based approximations. We present experimental results that show that our hybrid CSP/LP backtrack search method outperforms the pure CSP and pure LP strategies on instances of a hard combinatorial problem.     

On cautious probabilistic inference and default detachment

Conditional probabilities are one promising and widely used approach to model uncertainty in information systems. This paper discusses the DUCK-calculus, which is founded on the cautious approach to uncertain probabilistic inference. Based on a set of sound inference rules, derived probabilistic information is gained by local bounds propagation techniques. Precision being always a central point of criticism to such systems, we demonstrate that DUCK need not necessarily suffer from these problems. We can show that the popular Bayesian networks are subsumed by DUCK, implying that precise probabilities can be deduced by local propagation techniques, even in the multiply connected case. A comparative study with INFERNO and with inference techniques based on global operations-research techniques yields quite favorable results for our approach. Since conditional probabilities are also suited to model nonmonotonic situations by considering different contexts, we investigate the problems of maximal and relevant contexts, needed to draw default conclusions about individuals.     

Defect corrected averaging for parabolic PDEs

We consider parabolic partial differential equations with highly oscillatory source terms. The timescale of the problem is assumed to be much larger than the timescale of the oscillation. Resolution of the smallest timescale constitutes a strong restriction on the stepsize of time integration method. Averaging techniques like stroboscopic averaging have been developed to overcome this restriction. In case of parabolic equations these techniques are of limited advantage. We have developed defect corrected averaging techniques that allow timesteps taylored to the timescale of diffusion. They are based on Krylov subspace iterations for the abstract solution operator of the system. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

CMARS and GAM & CQP—Modern optimization methods applied to international credit default prediction

In this paper, we apply newly developed methods called GAM & CQP and CMARS for country defaults. These are techniques refined by us using Conic Quadratic Programming. Moreover, we compare these new methods with common and regularly used classification tools, applied on 33 emerging markets’ data in the period of 1980-2005. We conclude that GAM & CQP and CMARS provide an efficient alternative in predictions. The aim of this study is to develop a model for predicting the countries’ default possibilities with the help of modern techniques of continuous optimization, especially conic quadratic programming. We want to show that the continuous optimization techniques used in data mining are also very successful in financial theory and application. By this paper we contribute to further benefits from model-based methods of applied mathematics in the financial sector. Herewith, we aim to help build up our nations.     

A posteriori error estimation and adaptive mesh-refinement techniques

We analyse three different a posteriori error estimators for elliptic partial differential equations. They are based on the evaluation of local residuals with respect to the strong form of the differential equation, on the solution of local problems with Neumann boundary conditions, and on the solution of local problems with Dirichlet boundary conditions. We prove that all three are equivalent and yield global upper and local lower bounds for the true error. Thus adaptive mesh-refinement techniques based on these estimators are capable to detect local singularities of the solution and to appropriately refine the grid near these singularities. Some numerical examples prove the efficiency of the error estimators and the mesh-refinement techniques.     

Cuts for mixed 0-1 conic programming

In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

Robust variable selection for finite mixture regression models

Finite mixture regression (FMR) models are frequently used in statistical modeling, often with many covariates with low significance. Variable selection techniques can be employed to identify the covariates with little influence on the response. The problem of variable selection in FMR models is studied here. Penalized likelihood-based approaches are sensitive to data contamination, and their efficiency may be significantly reduced when the model is slightly misspecified. We propose a new robust variable selection procedure for FMR models. The proposed method is based on minimum-distance techniques, which seem to have some automatic robustness to model misspecification. We show that the proposed estimator has the variable selection consistency and oracle property. The finite-sample breakdown point of the estimator is established to demonstrate its robustness. We examine small-sample and robustness properties of the estimator using a Monte Carlo study. We also analyze a real data set.     

Comparison of time and spatial collocation methods for the heat equation

We combine a high-order compact finite difference scheme to approximate the spatial derivatives and collocation techniques for the time component to numerically solve the two-dimensional heat equation. We use two approaches to implement the time collocation methods. The first one is based on an explicit computation of the coefficients of polynomials and the second one relies on differential quadratures. We also implement a spatial collocation method where differential quadratures are utilized for spatial derivatives and an implicit scheme for marching in time. We compare all the three techniques by studying their merits and analyzing their numerical performance. Our experiments show that all of them achieve high-accurate approximate solution but the time collocation method with differential quadrature offers (with respect to the one with explicit polynomials) less computational complexity and a better efficiency. All our computations, based on parallel algorithms, are carried out on the CRAY SV1.     

Efficient decomposition and linearization methods for the stochastic transportation problem

The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. We compare several different methods based on decomposition techniques and linearization techniques for this problem, trying to find the most efficient method or combination of methods. We discuss and test a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross decomposition and the more well known Lagrangean relaxation with subgradient optimization, as well as combinations of these approaches. Computational tests are presented, indicating that some new combination methods are quite efficient for large scale problems.     

Combining expert judgment: On the performance of trimmed mean vote aggregation procedures in the presence of strategic voting

Analytic group decision techniques for selecting a subset of alternatives range between multicriteria decision analysis techniques such as multiattribute utility theory and the analytic hierarchy process to voting techniques where each member of the decision group submits a ranking of the alternatives, and these individual rankings are then aggregated into an overall ranking. The obvious advantage of voting is that it bypasses the rather intensive data generation requirements of multicriteria techniques. In this paper we compare the performance of trimmed mean rank-order aggregation procedures in the case where a subset of the individuals in the group charged with the decision vote strategically. We employ a Monte Carlo simulation experiment on a specific decision instance and find that trimmed mean aggregation compares favorably with other procedures.     

Comparison of iterative improvement techniques for schedule optimization

Due to complexity reasons of realistic scheduling applications, often iterative improvement techniques that perform a kind of local search to improve a given schedule are proposed instead of enumeration techniques that guarantee optimal solutions. In this paper we describe an experimental comparison of four iterative improvement techniques for schedule optimization that differ in the local search methodology. These techniques are iterative deepening, random search, tabu search and genetic algorithms. To compare the performance of these techniques, we use the same evaluation function, knowledge representation and data from one application. The evaluation function is defined on the gradual satisfaction of explicitly represented domain constraints and optimization functions. The satisfactions of individual constraints are weighted and aggregated for the whole schedule. We have applied these techniques on data of a steel making plant in Linz (Austria). In contrast to other applications of iterative improvement techniques reported in the literature, our application is constrained by a greater variety of antagonistic criteria that are partly contradictory.     

Towards a unified analysis of mixed methods for elasticity with weakly symmetric stress

We propose a framework for unified analysis of mixed methods for elasticity with weakly symmetric stress. Based on a commuting diagram in the weakly symmetric elasticity complex and extending a previous stability result, stable mixed methods are obtained by combining Stokes stable and elasticity stable finite elements. We show that the framework can be used to analyze most existing mixed methods for the linear elasticity problem with elementary techniques. We also show that some new stable mixed finite elements are obtained.     

Blow-up in nonlinear heat equations

We study the blow-up of solutions of nonlinear heat equations in dimension 1. We show that for an open set of even initial data which are characterized roughly by having maxima at the origin, the solutions blow up in finite time and at a single point. We find the universal blow-up profile and remainder estimates. Our results extend previous results in several directions and our techniques differ from the techniques previously used for this problem. In particular, they do not rely on maximum principle.     

Global integrability and degenerate quasilinear elliptic equations

We study an integrability phenomenon for elliptic equations in divergence form. We prove that solutions and supersolutions that are bounded from below are globally integrable to some power. This extends a result known for harmonic functions to a nonlinear situation. We use BMO techniques.