Let
\(F=\max_{i\in I}\{f_{i}+ \sum_{\substack{j\ne i \\ j\in I}}g_{j}\}\) and
\(G=\sum_{i\in I}g_{i}\). We can see the problem (P) is converted to the following equivalent problem (P″) from (
8):
$$\begin{aligned}& \mbox{minimize } f_{0}(x)-g_{0}(x) \\& \mbox{subject to } f_{i}(x)-g_{i}(x)\le 0, \quad \forall i \notin I ,\hspace{183pt}\mbox{(P$''$)} \\& F(x)-G(x)\le 0. \end{aligned}$$
From (
1),
$$D=\bigcup_{x\in S} \biggl( \prod _{i\notin I}\partial g _{i}(x)\times \sum _{i\in I}\partial g_{i}(x) \biggr) = \bigcup _{x\in S} \biggl( \prod_{i\notin I}\partial g_{i}(x) \times \partial \sum_{i\in I}g_{i}(x) \biggr) . $$
For each
\(((y_{i})_{i\notin I},\hat{y})\in D\cap (\prod_{i\notin I} \operatorname{dom} g^{*}_{i}\times \operatorname{dom} G^{*})\), there exists
\(\hat{x}\in S\) such that
\(y_{i}\in \partial g_{i}(\hat{x})\) for each
\(i\notin I\) and
\(\hat{y}\in \partial \sum_{i\in I}g_{i}(\hat{x})\), that is,
$$g_{i}(\hat{x})+g^{*}_{i}(y_{i})= \langle \hat{x},y_{i} \rangle \quad (i\notin I), \qquad \biggl(\sum _{i\in I}g_{i} \biggr) (\hat{x})+ \biggl(\sum _{i\in I}g_{i} \biggr)^{*}(\hat{y})= \langle \hat{x}, \hat{y} \rangle . $$
From (
3), there exists
\(y_{i}\) (
\(i\in I\)) such that
\((\sum_{i\in I}g_{i})^{*}(\hat{y})=\sum_{i\in I}g^{*}_{i}(y _{i})\) and
\(\sum_{i\in I}y_{i}=\hat{y}\). Then
$$\sum_{i\in I} \bigl(g_{i}( \hat{x})+g^{*}_{i}(y_{i}) \bigr)=\sum _{i\in I} \langle \hat{x},y _{i} \rangle , $$
and since
\(g_{i}(\hat{x})+g^{*}_{i}(y_{i})\ge \langle \hat{x},y _{i} \rangle \) for each
\(i\in I\), we have
$$g_{i}(\hat{x})+g^{*}_{i}(y_{i})= \langle \hat{x},y_{i} \rangle, \quad \mbox{that is}, y_{i} \in \partial g_{i}(\hat{x}) $$
for each
\(i\in I\). Therefore
$$ (y_{i})_{i=1}^{m}\in \prod ^{m}_{i=1}\partial g_{i}(\hat{x})\subseteq \bigcup_{x\in S}\prod^{m}_{i=1} \partial g_{i}(x). $$
(13)
From
\(\hat{y}\in \partial \sum_{i\in I}g_{i}(\hat{x})\) and
\(\hat{x} \in S\),
$$\begin{aligned} F(x)- \langle \hat{x},\hat{y} \rangle +G^{*}( \hat{y}) =& \max_{i\in I} \biggl\{ f_{i}(\hat{x})+\sum _{\substack{j\ne i\\j\in I}}g_{j}( \hat{x}) \biggr\} - \langle \hat{x}, \hat{y} \rangle + \biggl(\sum_{i\in I}g _{i} \biggr)^{*}(\hat{y}) \\ =&\max_{i\in I} \biggl\{ f_{i}(\hat{x})+\sum _{\substack{j\ne i\\j\in I}}g _{j}(\hat{x}) \biggr\} -\sum _{i\in I}g_{i}(\hat{x}) \\ =&\max_{i\in I} \bigl\{ f_{i}(\hat{x})-g_{i}( \hat{x}) \bigr\} \le 0. \end{aligned}$$
From
\(y_{i}\in \partial g_{i}(\hat{x})\) for each
\(i\notin I\) and
\(\hat{x}\in S\),
\(f_{i}(\hat{x})- \langle \hat{x},y_{i} \rangle +g ^{*}_{i}(y_{i})=f_{i}(\hat{x})-g_{i}(\hat{x})\le 0\). Therefore
x̂ is an element of
\(\{x\in \mathbb{R}^{n}\mid f_{i}(x)- \langle x,y _{i} \rangle +g^{*}_{i}(y_{i})\le 0, \forall i\notin I, F(x)- \langle x,\hat{y} \rangle +G^{*}(\hat{y})\le 0\}\) and this set is non-empty. For each
\(i\in I\), let
\(F_{i}=f_{i}+ \sum_{\substack{j\ne i \\ j\in I}}g_{j}\). Now we have
$$\begin{aligned} \operatorname {epi}F^{*} =&\operatorname {co}\bigcup_{i\in I} \operatorname {epi}F^{*}_{i}\quad \bigl( \because \mbox{ from (5)} \bigr) \\ =& \bigcup_{ \substack{\lambda_{i}\ge 0\\\sum _{i\in I}\lambda_{i}=1}} \sum_{i\in I} \lambda_{i} \operatorname {epi}F^{*}_{i} \quad (\because \mbox{ by using Lemma 1}) \\ =& \bigcup_{ \substack{\lambda_{i}\ge 0\\\sum _{i\in I}\lambda_{i}=1}} \sum_{i\in I} \lambda_{i} \biggl(\operatorname {epi}f^{*}_{i}+\sum _{\substack{j\ne i\\j\in I}}\operatorname {epi}g^{*}_{j} \biggr) \quad \bigl( \because \mbox{ from (4)}\bigr) \\ =& \bigcup_{ \substack{\lambda_{i}\ge 0\\\sum ^{m}_{i=1}\lambda_{i}=1}} \sum_{i\in I} \bigl(\lambda_{i}\operatorname {epi}f^{*}_{i}+(1- \lambda_{i})\operatorname {epi}g^{*} _{i} \bigr) \\ =&\operatorname {co}\bigcup_{ \substack{\lambda_{i}\ge 0\\\sum ^{m}_{i=1}\lambda_{i}=1}} \sum _{i\in I} \bigl(\lambda_{i}\operatorname {epi}f^{*}_{i}+(1- \lambda_{i})\operatorname {epi}g^{*} _{i} \bigr) \\ =&\operatorname {co}\bigcup_{i\in I} \biggl(\operatorname {epi}f^{*}_{i}+ \sum_{\substack{j\ne i\\j\in I}}\operatorname {epi}g^{*}_{i} \biggr)\quad (\because \mbox{from Lemma 2}). \end{aligned}$$
Therefore
$$\operatorname {epi}F^{*}- \bigl(\hat{y},G^{*}(\hat{y}) \bigr)= \operatorname {co}\biggl( \bigcup_{i\in I} \biggl(\operatorname {epi}f^{*}_{i}+ \sum_{\substack{j\in I \\ j\ne i}}\operatorname {epi}g^{*}_{j} \biggr)- \sum_{i\in I} \bigl(y_{i},g^{*}_{i}(y_{i}) \bigr) \biggr), $$
and hence
$$\begin{aligned}& \operatorname {cone}\operatorname {co}\biggl(\bigcup_{i\notin I} \bigl( \operatorname {epi}f^{*}_{i}- \bigl(y_{i},g^{*} _{i}(y_{i}) \bigr) \bigr)\cup \bigl(\operatorname {epi}F^{*}- \bigl(\hat{y},G^{*}(\hat{y}) \bigr) \bigr) \biggr)+\{0 \}\times [0,+ \infty ) \\& \quad =\operatorname {cone}\operatorname {co}\biggl(\bigcup_{i\notin I} \bigl(\operatorname {epi}f^{*}_{i}- \bigl(y_{i},g ^{*}_{i}(y_{i}) \bigr) \bigr)\cup \biggl(\bigcup_{i\in I} \biggl(\operatorname {epi}f^{*}_{i}+ \sum_{\substack{j\in I\\j\ne i}}\operatorname {epi}g^{*}_{j} \biggr)-\sum_{i\in I} \bigl(y_{i},g ^{*}_{i}(y_{i}) \bigr) \biggr) \biggr) \\& \qquad {} +\{0\}\times [0,+\infty ), \end{aligned}$$
because
\(\operatorname {co}(A\cup \operatorname {co}B)=\operatorname {co}(A\cup B)\) for any
\(A, B\subseteq \mathbb{R}^{n}\). From (
10), this set is closed. By using Theorem
2,
$$\begin{aligned} \operatorname{Val}(\mathrm{P}) = &\inf_{(y_{0},((y_{i})_{i\notin I},\hat{y}))\in D_{0}\times D} \max_{\hat{\lambda }, \lambda_{i}\ge 0}\inf _{x\in \mathbb{R}^{n}}\Biggl\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})\vphantom{\sum_{i\notin I}} \\ &{}+\sum_{i\notin I}\lambda_{i} \bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i})\bigr) +\hat{\lambda }\bigl(F(x)- \langle x,\hat{y} \rangle +G^{*}( \hat{y})\bigr) \Biggr\} \end{aligned}$$
holds. For any
\((y_{0},((y_{i})_{i\notin I},\hat{y}))\in D_{0}\times D\),
$$\begin{aligned}& \max_{\substack{\lambda_{i}\ge 0(i\notin I)\\\hat{\lambda } \ge 0}}\inf_{x\in \mathbb{R}^{n}} \Biggl\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0}) + \sum_{i\notin I}\lambda_{i} \bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i})\bigr) \\& \qquad {}+\hat{\lambda }\bigl(F(x)- \langle x,\hat{y} \rangle +G^{*}( \hat{y})\bigr)\vphantom{\sum_{i\notin I}} \Biggr\} \\& \quad =\max_{\substack{\lambda_{i}\ge 0(i\notin I)\\\hat{\lambda } \ge 0}}\inf_{x\in \mathbb{R}^{n}}\Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+ \sum_{i\notin I}\lambda_{i}\bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\hat{\lambda } \biggl(\max_{i\in I} \biggl\{ f_{i}(x)+\sum_{j\ne i, j\in I}g_{j}(x) \biggr\} - \langle x,\hat{y} \rangle +\biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y}) \biggr) \Bigg\} \\& \quad =\max_{\substack{\lambda_{i}\ge 0(i\notin I)\\\hat{\lambda } \ge 0}} \inf_{x\in \mathbb{R}^{n}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+ \sum_{i\notin I}\lambda_{i} \bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\hat{\lambda } \biggl(\max_{ \substack{\lambda_{i}\ge 0(i\in I)\\\sum_{i\in I}\lambda_{i}=1}} \sum _{i\in I}\lambda_{i}\biggl(f_{i}(x)+ \sum_{j\ne i, j\in I}g_{j}(x)\biggr)- \langle x, \hat{y} \rangle +\biggl(\sum_{j\in I}g_{j} \biggr)^{*}( \hat{y}) \biggr) \Bigg\} \\& \quad =\max_{\substack{\lambda_{i}\ge 0(i\notin I)\\\hat{\lambda } \ge 0}}\inf_{x\in \mathbb{R}^{n}}\max _{ \substack{\lambda_{i}\ge 0(i\in I)\\\sum_{i\in I}\lambda_{i}=1}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+\sum _{i\notin I}\lambda_{i}\bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\hat{\lambda }\biggl(\sum_{i\in I} \lambda_{i}\biggl(f_{i}(x)+\sum _{j\ne i, j\in I}g_{j}(x)\biggr)- \langle x,\hat{y} \rangle + \biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y})\biggr) \Bigg\} \\& \quad =\max_{\substack{\lambda_{i}\ge 0(i\notin I)\\\hat{\lambda } \ge 0}}\max_{\substack{\lambda_{i}\ge 0(i\in I)\\\sum _{i\in I} \lambda_{i}=1}}\inf _{x\in \mathbb{R}^{n}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+\sum _{i\notin I}\lambda_{i}\bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\hat{\lambda }\biggl(\sum_{i\in I} \lambda_{i}\biggl(f_{i}(x)+\sum _{j\ne i, j\in I}g_{j}(x)\biggr)- \langle x,\hat{y} \rangle + \biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y})\biggr)\Bigg\} \\& \quad =\max_{\substack{\hat{\lambda }, \lambda_{i}\ge 0\\\sum _{i \in I}\lambda_{i}=1}}\inf_{x\in \mathbb{R}^{n}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+ \sum_{i\notin I}\lambda_{i}\bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\hat{\lambda }\biggl(\sum_{i\in I} \lambda_{i}\biggl(f_{i}(x)-g_{i}(x)+\sum _{j\in I}g_{j}(x)\biggr)- \langle x,\hat{y} \rangle + \biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y})\biggr) \Bigg\} \\& \quad =\max_{\substack{\hat{\lambda }, \lambda_{i}\ge 0\\\sum _{i \in I}\lambda_{i}=1}}\inf_{x\in \mathbb{R}^{n}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+ \sum_{i\notin I}\lambda_{i}\bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\hat{\lambda }\sum_{i\in I} \lambda_{i}\bigl(f_{i}(x)-g_{i}(x)\bigr)+ \hat{ \lambda }\biggl(\sum_{j\in I}g_{j}(x)- \langle x,\hat{y} \rangle +\biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y})\biggr) \Bigg\} \\& \quad =\max_{\substack{\hat{\lambda }, \lambda_{i}\ge 0\\\sum _{i \in I}\lambda_{i}=\hat{\lambda }}}\inf_{x\in \mathbb{R}^{n}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})+ \sum_{i\notin I}\lambda_{i}\bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i}) \bigr)\\& \qquad {}+\sum_{i\in I}\lambda_{i} \bigl(f_{i}(x)-g_{i}(x)\bigr) +\hat{\lambda }\biggl(\sum _{j\in I}g_{j}(x)- \langle x,\hat{y} \rangle + \biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y})\biggr) \Bigg\} . \end{aligned}$$
The fourth equality of the previous equalities follows from Theorem
1. Hence we have
$$\begin{aligned} \operatorname{Val}(\mathrm{P}) = &\inf_{(y_{0},((y_{i})_{i\notin I},\hat{y}))\in D_{0}\times D} \max_{\substack{\hat{\lambda }, \lambda_{i}\ge 0\\\sum _{i \in I}\lambda_{i}=\hat{\lambda }}}\inf _{x\in \mathbb{R}^{n}} \Bigg\{ f_{0}(x)- \langle x,y_{0} \rangle +g^{*}_{0}(y_{0})\vphantom{\sum_{i\notin I}} \\ &{}+\sum_{i\notin I}\lambda_{i} \bigl(f_{i}(x)- \langle x,y_{i} \rangle +g ^{*}_{i}(y_{i})\bigr) +\sum _{i\in I}\lambda_{i}\bigl(f_{i}(x)-g_{i}(x) \bigr)\\ &{}+\hat{\lambda }\biggl( \sum_{j\in I}g_{j}(x)- \langle x,\hat{y} \rangle +\biggl( \sum_{j\in I}g_{j} \biggr)^{*}(\hat{y})\biggr) \Bigg\} . \end{aligned}$$
This completes the proof. □