  This article deals with the following simpler version of an open problem in
system realization theory which has several important engineering applications:
Given a collection of masses and a set of linear springs with a specified cost
and stiffness, a resource constraint in terms of a budget on the total cost,
the problem is to determine an optimal connection of masses and springs so that
the resulting structure is as stiff as possible, i.e., the structure is
connected and its smallest non-zero natural frequency is as large as possible.
In this article, algebraic connectivity, or its mechanical analog - the
smallest non-zero natural frequency of a connected structure was chosen as a
performance objective. Algebraic connectivity determines the convergence rate
of consensus protocols and error attenuation in Unmanned Aerial Vehicle (UAV)
formations and is chosen to be a performance objective as it can be viewed as a
measure of robustness in UAV communication networks to random node failures.
Underlying the mechanical and UAV network synthesis problems is a Mixed Integer
Semi-Definite Program (MISDP), an NP-hard problem. The novel contributions of
this article lies in developing efficient algorithms to solve the MISDPs based
on iterative primal-dual algorithm, cutting-plane methods for polyhedral
outer-approximation, capturing the feasible set of MISDPs using Fiedler vectors
or Laplacian with equivalency guarantees, and efficient
neighborhood-search-based heuristic algorithms.
