Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation

Several promising approaches for hexahedral mesh generation work as follows: Given a prescribed quadrilateral surface mesh they first build the combinatorial dual of the hexahedral mesh. This dual mesh is converted into the primal hexahedral mesh, and finally embedded and smoothed into the given domain. Two such approaches, the modified whisker weaving algorithm by Folwell and Mitchell, as well as a method proposed by the author, rely on an iterative elimination of certain dual cycles in the surface mesh. An intuitive interpretation of the latter method is that cycle eliminations correspond to complete sheets of hexahedra in the volume mesh.

Although these methods can be shown to work in principle, the quality of the generated meshes heavily relies on the dual cycle structure of the given surface mesh. In particular, it seems that difficulties in the hexahedral meshing process and poor mesh qualities are often due to self-intersecting dual cycles. Unfortunately, all previous work on quadrilateral surface mesh generation has focused on quality issues of the surface mesh alone but has disregarded its suitability for a high-quality extension to a three-dimensional mesh.

In this paper, we develop a new method to generate quadrilateral surface meshes without self-intersecting dual cycles. This method reuses previous b-matching problem formulations of the quadrilateral mesh refinement problem. The key insight is that the b-matching solution can be decomposed into a collection of simple cycles and paths of multiplicity two, and that these cycles and paths can be consistently embedded into the dual surface mesh.

A second tool uses recursive splitting of components into simpler subcomponents by insertion of internal two-manifolds. We show that such a two-manifold can be meshed with quadrilaterals such that the induced dual cycle structure of each subcomponent is free of self-intersections if the original component satisfies this property. Experiments show that we can achieve hexahedral meshes with a good quality.     

The projective method for solving linear matrix inequalities

Numerous problems in control and systems theory can be formulated in terms of linear matrix inequalities (LMI). Since solving an LMI amounts to a convex optimization problem, such formulations are known to be numerically tractable. However, the interest in LMI-based design techniques has really surged with the introduction of efficient interior-point methods for solving LMIs with a polynomial-time complexity. This paper describes one particular method called the Projective Method. Simple geometrical arguments are used to clarify the strategy and convergence mechanism of the Projective algorithm. A complexity analysis is provided, and applications to two generic LMI problems (feasibility and linear objective minimization) are discussed.     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

Approximate Toeplitz Matrix Problem Using Semidefinite Programming

Given a data matrix, we find its nearest symmetric positive-semidefinite Toeplitz matrix. In this paper, we formulate the problem as an optimization problem with a quadratic objective function and semidefinite constraints. In particular, instead of solving the so-called normal equations, our algorithm eliminates the linear feasibility equations from the start to maintain exact primal and dual feasibility during the course of the algorithm. Subsequently, the search direction is found using an inexact Gauss-Newton method rather than a Newton method on a symmetrized system and is computed using a diagonal preconditioned conjugate-gradient-type method. Computational results illustrate the robustness of the algorithm.     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

An alternative approach for non-linear optimal control problems based on the method of moments

We propose an alternative method for computing effectively the solution of non-linear, fixed-terminal-time, optimal control problems when they are given in Lagrange, Bolza or Mayer forms. This method works well when the nonlinearities in the control variable can be expressed as polynomials. The essential of this proposal is the transformation of a non-linear, non-convex optimal control problem into an equivalent optimal control problem with linear and convex structure. The method is based on global optimization of polynomials by the method of moments. With this method we can determine either the existence or lacking of minimizers. In addition, we can calculate generalized solutions when the original problem lacks of minimizers. We also present the numerical schemes to solve several examples arising in science and technology.     

Semidefinite optimization models for limit and shakedown analysis problems involving matrix spreads

Limit and shakedown analysis problems of Computational Mechanics lead to convex optimization problems, characterized by linear objective functions, linear equality constraints and constraints expressing the restrictions imposed by the material strength. It is shown that two important strength criteria, the Mohr–Coulomb and the Tresca criterion, can be represented as systems of semidefinite constraints, leading this way to semidefinite programming problems.     

Solving large-scale semidefinite programs in parallel

We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in an implementation called LAMBDA, which delivers faster solution times than previously possible, and acceptable parallel scalability on sufficiently large problems. This work was supported in part by NSF grants DMS-0215373 and DMS-0238008.