A major drawback of orthogonal frequency division multiplexing (OFDM) is the high peak-to-average power ratio (PAPR) of the transmitted signal. Partial transmit sequence (PTS) technique can improve the PAPR statistics of OFDM signals. In the PTS technique, the data block to be transmitted is partitioned into disjoint subblocks and the subblocks are combined using phase factors to minimize PAPR. As ordinary PTS technique requires an exhaustive search over all combinations of allowed phase factors, the search complexity increases exponentially with the number of subblocks. In the proposed technique, a gradient descent search is performed to find the phase factors. It is shown that the proposed technique achieves significant reduction in search complexity with little performance degradation.