Context-specific independence in graphical log-linear models

Log-linear models are the popular workhorses of analyzing contingency tables. A log-linear parameterization of an interaction model can be more expressive than a direct parameterization based on probabilities, leading to a powerful way of defining restrictions derived from marginal, conditional and context-specific independence. However, parameter estimation is often simpler under a direct parameterization, provided that the model enjoys certain decomposability properties. Here we introduce a cyclical projection algorithm for obtaining maximum likelihood estimates of log-linear parameters under an arbitrary context-specific graphical log-linear model, which needs not satisfy criteria of decomposability. We illustrate that lifting the restriction of decomposability makes the models more expressive, such that additional context-specific independencies embedded in real data can be identified. It is also shown how a context-specific graphical model can correspond to a non-hierarchical log-linear parameterization with a concise interpretation. This observation can pave way to further development of non-hierarchical log-linear models, which have been largely neglected due to their believed lack of interpretability.     

Interactive texture mapping for polygonal models

Polygonal models have been widely applied in the community of CAD and computer graphics. Since a polygonal surface usually has no intrinsic parameterization, it is very difficult to map textures onto it with low distortion. In this paper, we present an efficient texture mapping algorithm for polygonal models. For each region to be mapped, the algorithm first constructs a B-spline patch with similar shape to surround the model. The mapped region is then projected onto the constructed B-spline patch to achieve a parameterization. By interactively controlling the B-spline patch, the user can conveniently decorate the surface of the model to meet his requirements. Both local and global texture mapping are discussed. The experimental results demonstrate that the algorithm has a great of potential applications in computer animation and virtual reality systems.     

Mixed-volume computation by dynamic lifting applied to polynomial system solving

The aim of this paper is to present a flexible approach for the efficient computation of the mixed volume of a tuple of polytopes. In order to compute the mixed volume, a mixed subdivision of the tuple of polytopes is needed, which can be obtained by embedding the polytopes in a higher-dimensional space, i.e., by lifting them. Dynamic lifting is opposed to the static approach. This means that one considers one point at a time and only fixes the value of the lifting function when the point really influences the mixed volume. Conservative lifting functions have been developed for this purpose. This provides us with a deterministic manipulation of the lifting for computing mixed volumes, which rules out randomness conditions. Cost estimates for the algorithm are given. The implications of dynamic lifting on polyhedral homotopy methods for the solution of polynomial systems are investigated and applications are presented.     

A linear formulation for disk conformal parameterization of simply-connected open surfaces

Surface parameterization is widely used in computer graphics and geometry processing. It simplifies challenging tasks such as surface registrations, morphing, remeshing and texture mapping. In this paper, we present an efficient algorithm for computing the disk conformal parameterization of simply-connected open surfaces. A double covering technique is used to turn a simply-connected open surface into a genus-0 closed surface, and then a fast algorithm for parameterization of genus-0 closed surfaces can be applied. The symmetry of the double covered surface preserves the efficiency of the computation. A planar parameterization can then be obtained with the aid of a Möbius transformation and the stereographic projection. After that, a normalization step is applied to guarantee the circular boundary. Finally, we achieve a bijective disk conformal parameterization by a composition of quasi-conformal mappings. Experimental results demonstrate a significant improvement in the computational time by over 60%. At the same time, our proposed method retains comparable accuracy, bijectivity and robustness when compared with the state-of-the-art approaches. Applications to texture mapping are presented for illustrating the effectiveness of our proposed algorithm.     

Proof of Convergence for a Global Optimization Algorithm for Problems with Ordinary Differential Equations

A deterministic spatial branch and bound global optimization algorithm for problems with ordinary differential equations in the constraints has been developed by Papamichail and Adjiman [A rigorous global optimization algorithm for problems with ordinary differential equations. J. Glob. Optim. 24, 1–33]. In this work, it is shown that the algorithm is guaranteed to converge to the global solution. The proof is based on showing that the selection operation is bound improving and that the bounding operation is consistent. In particular, it is shown that the convex relaxation techniques used in the algorithm for the treatment of the dynamic information ensure bound improvement and consistency are achieved.     

RETRACTED ARTICLE: Discrete optimization method based on grassmannian parameterization in multidimensional dichotomic data structuring

A solution of the large computational time problem arising in multidimensional data structuring is addressed by employing algebraic properties of finite geometries. A vector parameterization of the Grassmannian Gr₂(k, n) is proposed which makes it possible to minimize the amount of memory and reduce the number of operations required to solve the problem. An algorithm based on this parameterization and the Gray codes is constructed; the algorithm is suitable for parallel computation, which further reduces computation time.     

A simulated annealing approach to mine production scheduling

Increasing global competition, quality standards, environmental awareness and decreasing ore prices impose new challenges to mineral industries. Therefore, the extraction of mineral resources requires careful design and scheduling. In this research, simulated annealing (SA) is recommended to solve a mine production scheduling problem. First of all, in situ mineral characteristics of a deposit are simulated by sequential Gaussian simulation, and averaging the simulated characteristics within specified block volumes creates a three-dimensional block model. This model is used to determine optimal pit limits. A linear programming (LP) scheme is used to identify all blocks that can be included in the blend without violating the content requirements. The Lerchs–Grosmann algorithm using the blocks identified by the LP program determines optimal pit limits. All blocks that lie outside of the optimal pit limit are removed from the system and the blocks within the optimal pit are submitted to the production scheduling algorithm. Production scheduling optimization is carried out in two stages: Lagrangean parameterization, resulting in an initial sub-optimal solution, and multi-objective SA, improving the sub-optimal schedule further. The approach is demonstrated on a Western Australian iron ore body.     

A global optimization procedure for the location of a median line in the three-dimensional space

A global optimization procedure is proposed to find a line in the Euclidean three-dimensional space which minimizes the sum of distances to a given finite set of three-dimensional data points.Although we are using similar techniques as for location problems in two dimensions, it is shown that the problem becomes much harder to solve. However, a problem parameterization as well as lower bounds are suggested whereby we succeeded in solving medium-size instances in a reasonable amount of computing time.     

Bayesian estimation of stochastic volatility models based on OU processes with marginal Gamma law

This paper discusses practical Bayesian estimation of stochastic volatility models based on OU processes with marginal Gamma laws. Estimation is based on a parameterization which is derived from the Rosiński representation, and has the advantage of being a non-centered parameterization. The parameterization is based on a marked point process, living on the positive real line, with uniformly distributed marks. We define a Markov chain Monte Carlo (MCMC) scheme which enables multiple updates of the latent point process, and generalizes single updating algorithm used earlier. At each MCMC draw more than one point is added or deleted from the latent point process. This is particularly useful for high intensity processes. Furthermore, the article deals with superposition models, where it discuss how the identifiability problem inherent in the superposition model may be avoided by the use of a Markov prior. Finally, applications to simulated data as well as exchange rate data are discussed.     

Nondecomposable solutions to group equations and an application to polyhedral combinatorics

This paper is based on the study of the set of nondecomposable integer solutions in a Gomory corner polyhedron, which was recently used in a reformulation method for integer linear programs. In this paper, we present an algorithm for efficiently computing this set. We precompute a database of nondecomposable solutions for cyclic groups up to order 52. As a second application of this database, we introduce an algorithm for computing nontrivial simultaneous lifting coefficients. The lifting coefficients are exact for a discrete relaxation of the integer program that consists of a group relaxation plus bound constraints. Received: November 2004 / Revised version: June 2005 AMS classification: 90C10, 90C57     

基于非均匀参数化的自由终端时间最优控制问题求解

针对自由终端时间最优控制问题,提出了一种基于非均匀控制向量参数化的数值解法.将控制时域离散化为不同长度的时间段,各时间段长度作为新的控制变量.通过引入标准化的时间变量,原问题转化为均匀参数化的固定终端时间最优控制问题.建立目标和约束函数的Hamilton函数,通过求解伴随方程获得目标和约束函数的梯度,采用序列二次规划(SQP)获得数值解.针对两个经典的化工过程自由终端时间最优控制问题进行仿真研究,验证了所提出算法的可行性和有效性.     

Towards a classification of global integral constructions and functorial liftings using the small representations method

This is a survey article in which we discuss some recent approach toward the classification of global factorizable integrals, and constructions of Langlands functorial lifting using small representations. To do that we use the language of unipotent orbits and their relation to Fourier coefficients. We also introduce the dimension equation, and set our goal to classify all global integrals of a certain form which satisfies this equation.     

Non-uniform data distribution for communication-efficient parallel clustering

Global communication requirements and load imbalance of some parallel data mining algorithms are the major obstacles to exploit the computational power of large-scale systems. This work investigates how non-uniform data distributions can be exploited to remove the global communication requirement and to reduce the communication cost in parallel data mining algorithms and, in particular, in the k-means algorithm for cluster analysis. In the straightforward parallel formulation of the k-means algorithm, data and computation loads are uniformly distributed over the processing nodes. This approach has excellent load balancing characteristics that may suggest it could scale up to large and extreme-scale parallel computing systems. However, at each iteration step the algorithm requires a global reduction operation which hinders the scalability of the approach. This work studies a different parallel formulation of the algorithm where the requirement of global communication is removed, while maintaining the same deterministic nature of the centralised algorithm. The proposed approach exploits a non-uniform data distribution which can be either found in real-world distributed applications or can be induced by means of multi-dimensional binary search trees. The approach can also be extended to accommodate an approximation error which allows a further reduction of the communication costs. The effectiveness of the exact and approximate methods has been tested in a parallel computing system with 64 processors and in simulations with 1024 processing elements.     

An improved particle swarm optimizer for parametric optimization of flexible satellite controller

Parametric optimization of flexible satellite controller is an essential for almost all modern satellites. Particle swarm algorithm is a global optimization algorithm but it suffers from two major shortcomings, that of, premature convergence and low searching accuracy. To solve these problems, this paper proposes an improved particle swarm optimization (IPSO) which substitute “poorly-fitted-particles” with a cross operation. Based on decision possibility, the cross operation can interchange local optima between three particles. Thereafter the swarm is split in two halves, and random number (s) get generated by crossing the dimension of particle from both halves. This produces a new swarm. Now the new swarm and old swarm are mixed, and based on relative fitness a half of the particles are selected for the next generation. As a result of the cross operation, IPSO can easily jump out of local optima, has improved searching accuracy and accelerates the convergence speed. Some test functions with different dimensions are used to analyze the performance of IPSO algorithm. Simulation results show that the IPSO has more advantages than standard PSO and Genetic Algorithm PSO (GAPSO). In that it has a more stable performance and lower level of complexity. Thus the IPSO is applied for parametric optimization of flexible satellite control, for a satellite having solar wings and antennae. Simulation results shows that the IPSO can effectively get the best controller parameters vis-a-vis the other optimization methods.     

A discrete optimization method based on a parameterization of a Grassmannian in multidimensional dichotomous data structuring

An approach to reducing large computational time in the problem of multidimensional dichotomous data structuring based on algebraic properties of finite geometries is proposed. A vector parameterization of the Grassmannian Gr₂(k, n) reducing memory expenditures and the number of operations required to solve this problem is introduced. A parallelization algorithm based on this parameterization and Gray coding which further reduces computational time is constructed.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

有限维逼近无限维总极值的积分型方法

本文用有限维逼近无限维的方法来讨论函数空间中的总体最优化问题．我们给出了新的最优性条件和用变测度方法求得的有限维解逼近总体最优解的算法．对于有约柬问题，我们用不连续罚函数法把有约束问题化为无约束问题来求解．最后，我们通过一个具有非凸状态约束的最优控制问可题的实例来说明算法的有效性．     

Hensel lifting and bivariate polynomial factorisation over finite fields

This paper presents an average time analysis of a Hensel lifting based factorisation algorithm for bivariate polynomials over finite fields. It is shown that the average running time is almost linear in the input size. This explains why the Hensel lifting technique is fast in practice for most polynomials.