Decompositions of powers of quadratic forms

We analyze the Waring decompositions of the powers of any quadratic form over the field of complex numbers. Our main objective is to provide detailed information about their rank and border rank. These forms are of significant importance because of the classical decomposition expressing the space of polynomials of a fixed degree as a direct sum of the spaces of harmonic polynomials multiplied by a power of the quadratic form. Using the fact that the spaces of harmonic polynomials are irreducible representations of the special orthogonal group over the field of complex numbers, we show that the apolar ideal of the s-th power of a non-degenerate quadratic form in n variables is generated by the set of harmonic polynomials of degree s+1. We also generalize and improve upon some of the results about real decompositions, provided by B. Reznick in his notes from 1992, focusing on possibly minimal decompositions and providing new ones, both real and complex. We investigate the rank of the second power of a non-degenerate quadratic form in n variables, which is equal to (n^2+n+2)/2 in most cases. We also study the border rank of any power of an arbitrary ternary non-degenerate quadratic form, which we determine explicitly using techniques of apolarity and a specific subscheme contained in its apolar ideal. Based on results about smoothability, we prove that the smoothable rank of the s-th power of such form corresponds exactly to its border rank and to the rank of its middle catalecticant matrix, which is equal to (s+1)(s+2)/2.

Topological analysis of singularity loci for serial and parallel manipulators

Singularities of robot manipulators have been intensely studied in the last decades by researchers of many fields. Serial singularities produce some local loss of dexterity of the manipulator, therefore it might be desirable to search for singularityfree trajectories in the jointspace. On the other hand, parallel singularities are very dangerous for parallel manipulators, for they may provoke the local loss of platform control, and jeopardize the structural integrity of links or actuators. It is therefore utterly important to avoid parallel singularities, while operating a parallel machine. Furthermore, there might be some configurations of a parallel manipulators that are allowed by the constraints, but nevertheless are unreachable by any feasible path. The present work proposes a numerical procedure based upon Morse theory, an important branch of differential topology. Such procedure counts and identify the singularity-free regions that are cut by the singularity locus out of the configuration space, and the disjoint regions composing the configuration space of a parallel manipulator. Moreover, given any two configurations of a manipulator, a feasible or a singularity-free path connecting them can always be found, or it can be proved that none exists. Examples of applications to 3R and 6R serial manipulators, to 3UPS and 3UPU parallel wrists, to 3UPU parallel translational manipulators, and to 3RRR planar manipulators are reported in the work.

Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.