We present a new optimization strategy to compute numerical approximations of minimizers for optimal control problems governed by scalar conservation laws in the presence of shocks. We focus on the 1-d inviscid Burgers equation. We first prove the existence of minimizers and, by a Gamma-convergence argument, the convergence of discrete minima obtained by means of numerical approximation schemes satisfying the so called one-sided Lipschitz condition (OSLC). Then we address the problem of developing efficient descent algorithms. We first consider and compare the existing two possible approaches. The first one, the so-called discrete approach, based on a direct computation of gradients in the discrete problem and the so-called continuous one, where the discrete descent direction is obtained as a discrete copy of the continuous one. When optimal solutions have shock discontinuities, both approaches produce highly oscillating minimizing sequences and the effective descent rate is very weak. As a remedy we propose a new method that uses the recent developments of generalized tangent vectors and the linearization around discontinuous solutions. We develop a new descent stratagey, that we shall call "alternating descent method", distinguishing descent directions that move the shock and those that perturb the profile of the solution away of it. As we shall see, a suitable alternating combination of these two classes of descent directions allows building very efficient and fast descent algorithms.