The application of the Threshold Accepting (TA) algorithm in portfolio optimisation can reduce portfolio risk compared with a Trust-Region local search algorithm. In a benchmark comparison of several different objective functions combined with different optimisation routines, we show that the TA search algorithm applied to a Conditional Value at Risk (CVaR) objective function yields the lowest Basel III market risk capital requirements. Not only does the TA algorithm outmatch the Trust-Region algorithm in all risk and performance measures, but when combined with a CVaR or 1% VaR objective function, it also achieves the best portfolio risk profile.