Linear aerospike engine is a rocket engine that is composed of arrays of small cell engines and a large spike nozzle whose one side is open to atmosphere. It is one of the promising propulsion systems for future space transportation since it can realize high performance for a wide range of ambient pressure conditions. Despite this advantage of the aerospike engine, previous design studies on aerospike nozzle shape are only devoted to maximizing the performance at a single design point. In order to explore the design of the aerospike engine considering performance at multiple operating altitudes, multi-objective design optimization is conducted in this paper. Design variables define cell engine parameters and the shape of the spike nozzle whose parameterization is carried out using monotonic cubic spline. An engineering-level performance analysis model of the engine is developed by combining 1) chemical equilibrium calculation for cell engines, 2) Riemann solver for spike wall flow, and 3) theoretical model for spike base flow. Five objective functions are considered for the maximization of specific impulse at three operating altitudes, the minimization of spike nozzle arc length, and the minimization of total engine height. The formulated many-objective problem is solved via MOEA/D with dynamic control of aggregate functions, and well-converged and widely-spread nondominated solutions are obtained. In these solutions, spike nozzle shapes that are different from shapes designed by previous methods are observed. After representative solutions are inspected in detail, the relations between objective functions and design variables in superior solutions are revealed using parallel coordinates plots.