Tail risk measures such as Value at Risk (VaR) and Conditional Value at Risk (CVaR) are popularly accepted criteria for financial risk management, but are usually difficult to optimize. Especially for VaR, it generally leads to a non-convex NP-hard problem which is computationally challenging. In this paper we propose the use of model-based annealing random search (MARS) method in tail risk optimization problems. For illustration purposes we discuss a weather index insurance design problem with VaR and CVaR objective functions, but the gradient-free MARS approach can be flexibly applicable to other financial and insurance applications under mild mathematical conditions. We conduct an empirical analysis in which we use a set of weather variables to hedge against corn production losses in Illinois. Numerical results show that the proposed optimization scheme effectively helps corn producers to manage their tail risk.