Line-start permanent-magnet synchronous motors (LSPMSMs) have poorer starting performance than induction motors. Optimization focusing only on transient performance improvement of the LSPMSM may degrade steady-state performance, and vice versa. In fact, an optimization focusing on maximizing starting torque may reduce efficiency by up to approximately 7% and optimizing efficiency may cause degradation in starting torque by 5%. Hence, simultaneous steady-state and transient performance optimization of a 4-kW LSPMSM under a multi-objective function is examined in this study. Efficiency maximization and starting torque maximization are nominated as objective functions. Two different optimization approaches, a gradient-based algorithm and gradient-free algorithm, are employed to optimize the LSPMSM. Sequential nonlinear programming is used as the gradient-based algorithm in this study, and the gradient-free algorithm used is the genetic algorithm (GA). A comparative study of the algorithms’ performance is presented. To provide an inclusive comparison of both algorithms’ performance, a similar optimization study is implemented for a baseline induction motor. The results demonstrate that the multi-objective optimization improves steady-state and start-up performance of both motors. Results indicate that both algorithms converge reliably to almost the same optimum (objective) value. Depending on the nature of the optimization problem, number of design variables, and degree of convergence, the genetic algorithm requires many more evaluations than the gradient-based algorithm. Accordingly, optimization time required by the GA is more than the gradient-based algorithm under similar conditions.