Gradient descent and stochastic gradient descent can be applied to any differentiable loss function irrespective of whether it is convex or non-convex. The "differentiable" requirement ensures that trainable parameters receive gradients that point in a direction that decreases the loss over time.
In the absence of a differentiable loss function, the true gradient must be approximated through other methods. For example, in classification problems, the 0-1 loss function is considered the "true" loss, but it is non-convex and difficult to optimize. Instead, surrogate loss functions act as tractable proxies for true loss functions. They are not necessarily worse; negative log-likelihood loss gives a softmax distribution over $k$ classes rather than just the classification boundary.
For your problem specifically, $f(x,a)=min(x,a)$ is not a differentiable loss function. It is not differentiable at $x=0.5$, but the gradient could be estimated through the subgradient. In practice, this works because neural networks often don't achieve the local/global minima of a loss function but instead asymptotically decreasing values that achieve good generalization error. Tensorflow and PyTorch use subgradients when fed non-differentiable loss functions. You could also use a smooth approximation of the $min$ function (see this thread) to get better gradients.