  This two-part paper is concerned with the problem of minimizing a linear
objective function subject to a bilinear matrix inequality (BMI) constraint. In
this part, we first consider a family of convex relaxations which transform BMI
optimization problems into polynomial-time solvable surrogates. As an
alternative to the state-of-the-art semidefinite programming (SDP) and
second-order cone programming (SOCP) relaxations, a computationally efficient
parabolic relaxation is developed, which relies on convex quadratic constraints
only. Next, we developed a family of penalty functions, which can be
incorporated into the objective of SDP, SOCP, and parabolic relaxations to
facilitate the recovery of feasible points for the original non-convex BMI
optimization. Penalty terms can be constructed using any arbitrary initial
point. We prove that if the initial point is sufficiently close to the feasible
set, then the penalized relaxations are guaranteed to produce feasible points
for the original BMI. In Part II of the paper, the efficacy of the proposed
penalized convex relaxations is demonstrated on benchmark instances of H2 and
Hinf optimal control synthesis problems.
