Modern mobile devices incorporate several transmit and receive antennas in highly constrained volumes. As miniaturized antennas impinge upon fundamental physical limits on efficiency, new design approaches are required to support ever-smaller devices with more varied and robust communication performance. We take an unconventional design approach in which an arbitrary metallic structure and its components can be modified to act as efficient radiators. Using eigenmode analysis and the theory of characteristic modes (TCM), we develop algorithms that allow for effective integration of antennas with mechanical structures and enable structure reuse, helping meet stringent space and weight constraints without sacrificing electromagnetic performance. We derive TCM-based objectives for effective exploration of the design space in the electromagnetic (EM) domain. The procedure includes a feed placement technique that identifies viable excitation points on the structure without running full EM analysis. In addition to computational advantages, this provides a point of comparison among a variety of antenna shapes. Empirical evaluation shows that the estimates of radiated power from TCM can effectively guide optimization toward structures with improved radiating properties. Automated feed placement increases the proportion of good-quality designs among the explored candidates by consistently selecting the most promising feed positions. The ability of the TCM-based algorithm to direct the search is further validated on two real-world applications: integration of a GPS antenna with the frame of a mobile phone and integration of an S-band antenna with the frame of a small spacecraft. To the best of our knowledge, this is the first work that applies TCM to automated optimization of antennas. We investigate how to leverage domain-specific methods and solution representations in the coupled optimization of antennas. We develop a novel multiobjective optimization framework based on local search in each domain. In this procedure, the local optima in each objective are obtained and modified to create a new population of candidate designs. On a number of benchmark problems, the proposed technique is competitive with leading multi-objective algorithms: while it finds a less uniform distribution along the Pareto front, it shows better performance in locating solutions at the boundaries of the tradeoff curve. The local search algorithm is successfully applied to topology optimization of an antenna for a CubeSat, a small low-cost satellite platform.