This paper presents an optimization methodology for a novel GaN-based online uninterruptible power supply (UPS). This UPS features a new multi-mode transformerless topology with a single dc bus with universal input/output voltage capability while using 650-V GaN transistors. A control strategy that combines variable on-time and fixed-frequency control within a single line cycle is applied to improve efficiency. The proposed optimization methodology generates multi-mode UPS designs within an expanded design space that includes the transition angle in the combined control between variable on-time and fixed-frequency control within a line cycle. The proposed approach yields more efficient and compact designs compared with approaches that assume only variable on-time control or only fixed-frequency control. A 1.2-kVA prototype of the UPS is designed and built. The power density of the main power stage is designed to be 46.3W/in3. The combined control is experimentally validated up to 800 W, achieving a peak efficiency of 98.2%, outperforming fixed-frequency control (96.5% efficiency) with a 1.7% efficiency improvement.