This paper deals with a novel application of the advanced optimal control techniques to a Counter-Terrorism optimal decision-making problem. The recently developed model of the Counter-Terrorism security policies (see [1]) naturally incorporates a competing interest group dynamics. The optimal dynamics can be found in this case by considering a specific Optimal Control Problem. In our work we propose an essential formal improvement of the above applied Optimal Control Problem and its numerical treatment. We formulate a suitable phase-constrained Optimal Control Problem for the initial Counter-Terrorism model and study a specific relaxation of this model. The proposed β-relaxation approach makes it possible to eliminate some model inconsistences and to design an optimal Counter-Terrorism strategy. We develop a new numeric algorithm for the improved dynamic optimization problem. We next study some analytic properties of this algorithm. The resulting computational technique involves a gradient based method in combination with the proposed relaxation scheme (see [2]). The obtained numerical approach is finally applied to an illustrative example.