How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the MOOP is also NP-Hard.
However, it's not clear to me how to define the worst-case complexity of the MOOP when all of their objective functions can be solved in polynomial-time, separately.
There is some different technique for proving that the MOOP is NP-Hard (or its decision version is NP-Complete), or I need to use the same techniques for demonstrating the worst-case complexity of single-objective optimization problems (show that it is in NP, then reduce a NP-Complete problem to my own, ...).
It's hard to find a good discussion regarding this theme on the Internet. Besides, I was unnable to find a good paper or book discussing this issue.