The phase-apodized-pupil Lyot coronagraph (PAPLC) is a pairing of the apodized-pupil Lyot coronagraph and the apodizing phase plate (APP) coronagraph. We describe a numerical optimization method to obtain globally optimal solutions for the phase apodizers for arbitrary telescope pupils, based on the linear map between complex-amplitude transmission of the apodizer and the electric field in the post-coronagraphic focal plane. PAPLCs with annular focal-plane masks and point-symmetric dark zones perform analogous to their corresponding APLCs. However, with a knife-edge focal-plane mask and one-sided dark zones, the PAPLC yields inner working angles as close as 1.4λ/D at contrasts of 10−10 and a maximum post-coronagraphic throughput of >75% for telescope apertures with central obscurations of up to 30%. We present knife-edge PAPLC designs optimized for the VLT/SPHERE instrument and the LUVOIR-A aperture. These designs show that the knife-edge PAPLC retains its performance, even for realistic telescope pupils with struts, segments, and non-circular outer edges.