Consider the following code:

In[1]:= Minimize[{x^2 - y^2, 
      Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}]

Out[1]= Minimize[{x^2 - y^2, 
  Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}]

In[3]:= r = 
 Reduce[{Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}]

Out[3]= (-5 <= x < 1/3 (15 - 7 \[Pi]) && 
   1/3 (5 \[Pi] + 3 x) <= y <= 
    1/3 (7 \[Pi] + 3 x)) || (1/3 (15 - 7 \[Pi]) <= x < 
    1/3 (15 - 5 \[Pi]) && 
   1/3 (5 \[Pi] + 3 x) <= y <= 5) || (x == 1/3 (15 - 5 \[Pi]) && 
   y == 5) || (-5 <= x <= 1/3 (-15 + \[Pi]) && -5 <= y <= 
    1/3 (\[Pi] + 3 x)) || (1/3 (-15 + \[Pi]) < x < (15 - \[Pi])/3 && 
   1/3 (-\[Pi] + 3 x) <= y <= 1/3 (\[Pi] + 3 x)) || ((15 - \[Pi])/3 <=
     x <= 5 && 
   1/3 (-\[Pi] + 3 x) <= y <= 5) || (x == 1/3 (-15 + 5 \[Pi]) && 
   y == -5) || (1/3 (-15 + 5 \[Pi]) < x <= 
    1/3 (-15 + 7 \[Pi]) && -5 <= y <= 
    1/3 (-5 \[Pi] + 3 x)) || (1/3 (-15 + 7 \[Pi]) < x <= 5 && 
   1/3 (-7 \[Pi] + 3 x) <= y <= 1/3 (-5 \[Pi] + 3 x))

In[4]:= Minimize[{x^2 - y^2, r}, {x, y}]

Out[4]= {1/9 (-150 \[Pi] + 25 \[Pi]^2), {x -> 5 - (5 \[Pi])/3, 
  y -> 5}}