The efficient optimization of actuated soft structures, particularly under complex nonlinear forces, remains a critical challenge in advancing robotics. Simulations of nonlinear structures, such as soft-bodied robots modeled using the finite element method (FEM), often demand substantial computational resources, especially during optimization. To address this challenge, we propose a novel optimization algorithm based on a tensorial parametric reduced order model (PROM). Our algorithm leverages dimensionality reduction and solution approximation techniques to facilitate efficient solving of nonlinear constrained optimization problems. The well-structured tensorial approach enables the use of analytical gradients within a specifically chosen reduced order basis (ROB), significantly enhancing computational efficiency. To showcase the performance of our method, we apply it to optimizing soft robotic swimmer shapes. These actuated soft robots experience hydrodynamic forces, subjecting them to both internal and external nonlinear forces, which are incorporated into our optimization process using a data-free ROB for fast and accurate computations. This approach not only reduces computational complexity but also unlocks new opportunities to optimize complex nonlinear systems in soft robotics, paving the way for more efficient design and control.