We investigate the optimal vaccination and screening strategies to minimize human papillomavirus (HPV) associated morbidity and the interventions cost. We propose a two-sex compartmental model of HPV-infection with time-dependent controls (vaccination of adolescents, adults, and screening) which can act simultaneously. We formulate optimal control problems complementing our model with two different objective functionals. The first functional corresponds to the protection of the vulnerable group and the control problem consists of minimizing the cumulative level of infected females over a fixed time interval. The second functional aims to eliminate the infection, and, thus, the control problem consists of minimizing the total prevalence at the end of the time interval. We prove the existence of solutions for the control problems, characterize the optimal controls, and carry out numerical simulations using various initial conditions. The results and properties and drawbacks of the model are discussed.