Energy storage systems (ESSs) are increasingly used in power system optimization. Different ESS mathematical models are developed that consider nonlinear functions for power losses. However, these models require non-convex constraints to represent the ESS losses, resulting in challenging optimization problems. To reduce the complexity, convex relaxation models are often derived but generate infeasible solutions when the relaxation exactness is violated. To deal with this issue, this work develops two successive convexification algorithms that generate fast and high-quality feasible solutions when the derived solution is not exact. The first algorithm handles general loss functions, while the second algorithm enhances performance when piecewise-linear loss functions are used. Specifically, the algorithms reduce the feasible region of the relaxed ESS models using a tightening box trust region around the current solution in successive iterations. The proposed algorithms are applied to the Unit Commitment and Peak Shaving and Energy Arbitrage problems to investigate their performance considering piecewise-linear and quadratic ESS loss functions. Simulation results demonstrate the impact of the ESSs relaxation violation on the actual system operation and validate the algorithms efficacy to generate high-quality feasible and even optimal solutions with significantly lower execution times compared to problems utilizing exact ESS models.