The optimization of kEP-SOPs: Computational complexity, approximability and experiments