Milnor numbers and Euler obstruction*

Using a geometric approach, we determine the relations between the local Euler obstruction Eu_f of a holomorphic function f and several generalizations of the Milnor number for functions on singular spaces. *This work was partially supported by CNRS-CONACYT (12409) Cooperation Program. The first and third named authors partially supported by CONACYT grant G36357-E and DGPA (UNAM) grant IN 101 401.     

Matrix Representations for Positive Noncommutative Polynomials

In real semialgebraic geometry it is common to represent a polynomial q which is positive on a region R as a weighted sum of squares. Serious obstructions arise when q is not strictly positive on the region R. Here we are concerned with noncommutative polynomials and obtaining a representation for them which is valid even when strict positivity fails. Specifically, we treat a ``symmetric' polynomial q(x, h) in noncommuting variables, {x<sub>1</sub>, . . . , } and {h<sub>1</sub>, . . . , } for which q(X,H) is positive semidefinite whenever are tuples of selfadjoint matrices with ||X<sub>j</sub>|| ≤ 1 but H<sub>j</sub> unconstrained. The representation we obtain is a Gram representation in the variables h where P<sub>q</sub> is a symmetric matrix whose entries are noncommutative polynomials only in x and V is a ``vector' whose entries are polynomials in both x and h. We show that one can choose P_q such that the matrix P_q(X) is positive semidefinite for all ||X_j|| ≤ 1. The representation covers sum of square results ([Am. Math. (to appear); Linear Algebra Appl. 326 (2001), 193–203; Non commutative Sums of Squares, preprint]) when g_x = 0. Also it allows for arbitrary degree in h, rather than degree two, in the main result of [Matrix Inequalities: A Symbolic Procedure to Determine Convexity Automatically to appear IOET July 2003] when restricted to x-domains of the type ||X_j|| ≤ 1. Partially supported by NSF, DARPA and Ford Motor Co. Partially supported by NSF grant DMS-0140112 Partially supported by NSF grant DMS-0100367     

A linear assignment approach for the least-squares protein morphing problem

This work addresses the computation of free-energy differences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morphing procedure, we employ permutations of atoms: we seek to find the permutation σ that minimizes the mean-square distance traveled by the atoms. Instead of performing this combinatorial search in the space of permutations, we show that the best permutation can be found by solving a linear assignment problem. We demonstrate that the use of such optimal permutations significantly improves the efficiency of the free-energy computation.     

Optimal control of systems with discontinuous differential equations

In this paper we discuss the problem of verifying and computing optimal controls of systems whose dynamics is governed by differential systems with a discontinuous right-hand side. In our work, we are motivated by optimal control of mechanical systems with Coulomb friction, which exhibit such a right-hand side. Notwithstanding the impressive development of nonsmooth and set-valued analysis, these systems have not been closely studied either computationally or analytically. We show that even when the solution crosses and does not stay on the discontinuity, differentiating the results of a simulation gives gradients that have errors of a size independent of the stepsize. This means that the strategy of “optimize the discretization” will usually fail for problems of this kind. We approximate the discontinuous right-hand side for the differential equations or inclusions by a smooth right-hand side. For these smoothed approximations, we show that the resulting gradients approach the true gradients provided that the start and end points of the trajectory do not lie on the discontinuity and that Euler’s method is used where the step size is “sufficiently small” in comparison with the smoothing parameter. Numerical results are presented for a crude model of car racing that involves Coulomb friction and slip showing that this approach is practical and can handle problems of moderate complexity.     

An existence result for a nonhomogeneous problem in R2 related to nonlinear Hencky-type materials

This paper investigates a nonlinear and non-homogeneous system of partial differential equations. The motivation comes from the fact that in a particular case the problem discussed here can be used in modeling the behavior of nonlinear Hencky-type materials. The main result of the paper establishes the existence of a nontrivial solution in an adequate functional space of Orlicz–Sobolev type by using Schauder’s fixed point theorem combined with adequate variational techniques.     

Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.     

ESR and XRD investigation of effects induced by gamma radiation on PVA-TiO2 membranes

The effects of gamma radiation on the local structure of PVA membranes containing TiO₂ were investigated by ESR and XRD methods. An intense ESR signal is observed after irradiation at 16 KGy dose. This signal appears only for irradiated samples and it is associated with the breaking of the polymeric chain, followed by local reorganization of the polymeric segments and the apparition of the unpaired electrons and free radicals. The intensity of the signal decreases with the concentration of TiO₂, indicating a shielding effect of the dopand. That the modification of local order of the polymeric chains has been modified after irradiation is confirmed by XRD method.     

Hierarchical approach for survivable network design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.