0

Suppose I have two independent problems of the form $\max L(f)$ and $\max L'(g)$ for two objective function $L$ and $L'$. We can assume that the space over which we try to find solutions $f,g$ are well defined and the two solutions exist. How can we prove that this is the same as $$\max_{f,g} L(f) + L'(g)$$

That $\max_{f,g} L(f) + L'(g)\le \max_f L(f) +\max_gL'(g)$ is clear. But how to conclude the other direction if there is no cross dependencies between $L$ and $L'$?

swissy
  • 91
  • 1
  • 11
  • This is true because if $A$ and $B$ are any non-empty subsets of the extended real number system $\bar{\mathbb{R}},$ then $\sup A + \sup B = \sup{a + b : a \in A, \ b \in B}.$ This can be proved by two applications of the more basic proposition that if $(E_i){i\in I}$ is any non-empty family of non-empty subsets of $\bar{\mathbb{R}},$ then $\sup\bigcup{i \in I}E_i = \sup{\sup E_i : i \in I}.$ The proof is similar to this answer. (I mentioned $\bar{\mathbb{R}}$ this time only so as not to have to keep postulating that upper bounds exist.) – Calum Gilhooley Nov 25 '22 at 21:36

1 Answers1

1

You can prove the remaining direction by contradiction. Suppose the inequality is strict, and then use the resulting optimal $f$ and $g$ from the RHS to obtain a better than optimal solution for the LHS.

RobPratt
  • 45,619