<p>Yes, <a href="https://link.springer.com/article/10.1007/s43036-020-00125-y" rel="nofollow noreferrer">Bachir et al. (2021)</a> extend the Karush-Kuhn-Tucker theorem under mild hypotheses, for an infinite number of variables (their Corollary 4.1).</p>
<p>I give hereafter a weaker version of the generalization of Karush-Kuh-Tucker for sequence spaces:</p>
<blockquote>
<p>Let <span class="math-container">$X\subset\mathbb{R}^{\mathbb{N}}$</span> be a nonempty convex subset of
<span class="math-container">$\mathbb{R}^{\mathbb{N}}$</span> and let <span class="math-container">$x^{*}\in Int\left(X\right)$</span>. Let
<span class="math-container">$f,g_{1},g_{2},...,g_{m}:X\rightarrow\mathbb{R}$</span> be convex functions
continuous at <span class="math-container">$x^{*}$</span> and term-to-term differentiable at <span class="math-container">$x^{*}$</span>, i.e.
such that the functions
<span class="math-container">$f_{n,x^{*}}\left(x_{n}\right):=f\left((x_1^{*},...,x_{n-1}^*,x_n,x_{n+1}^*,...)\right)$</span> and
<span class="math-container">$g_{j,n,x^{*}}\left(x_{n}\right):=g_{j}\left((x_1^{*},...,x_{n-1}^*,x_n,x_{n+1}^*,...)\right)$</span> are
differentiable at <span class="math-container">$x_{n}$</span> for all <span class="math-container">$n\in\mathbb{N}$</span> and
<span class="math-container">$j\in\left\{ 1,2,...,m\right\}$</span>.</p>
<p>(Qualification condition) Suppose that for all <span class="math-container">$k\in\mathbb{N}^{*}$</span>
and for all <span class="math-container">$x\in X$</span>,
<span class="math-container">$$x^{*}+P^{k}\left(x-x^{*}\right)=\left(x_{1},...,x_{k},x_{k+1}^{*},x_{k+2}^{*},...\right)\in X$$</span>
If there exist
<span class="math-container">$\left(\lambda_{j}^{*}\right)_{j}\in\left(\mathbb{R}_{+}\right)^{\mathbb{N}}$</span>
such that</p>
<p><span class="math-container">$$\lambda_{j}^{*}g_{j}\left(x^{*}\right)  =0,\:\forall j\in\left\{
1,2,...,m\right\} \quad \quad \quad \quad \quad (1)$$</span>
<span class="math-container">$$f_{n,x^{*}}^{\prime}\left(x_{n}^{*}\right)+\sum_{j=1}^{m}   \lambda_{j}^{*}g_{j,n,x^{*}}^{\prime}\left(x_{n}^{*}\right)=0,\:\forall
n\in\mathbb{N} \quad \quad (2)$$</span></p>
<p>(Sufficiency) Then <span class="math-container">$x^{*}$</span> is an optimal solution on <span class="math-container">$\Gamma:=\left\{
\left(x_{i}\right)_{i}\in
X\,:\,g_{1}\left(x\right)\leq0,...,g_{m}\left(x\right)\leq0\right\} :$</span></p>
<p><span class="math-container">$$f\left(x^{*}\right)=\underset{x\in\Gamma}{\inf}f\left(x\right)$$</span></p>
<p>(Necessity) Besides, if <span class="math-container">$x^{*}$</span> is an optimal solution on <span class="math-container">$\Gamma$</span> and
if the Slater condition <span class="math-container">$Int\left(\Gamma\right)\neq\emptyset$</span> is
verified, then there exist unique
<span class="math-container">$\left(\lambda_{j}^{*}\right)_{j}\in\left(\mathbb{R}_{+}\right)^{\mathbb{N}}$</span>
which verify the (Karush-Kuhn-Tucker) conditions (1) and (2).</p>
</blockquote>
<p>The number of constraints has to be finite, but simple constraints like non-negativity constraints can be replaced by an equivalent restriction on the domain of the variables. For example, instead of the constraints <span class="math-container">$\forall n \in \mathbb{N},\;x_n \geq 0$</span> on the domain <span class="math-container">$\mathbb{R}^{\mathbb{N}}$</span>, one can take <span class="math-container">$X=(\mathbb{R}_+)^{\mathbb{N}}$</span>, and the theorem applies.</p>
<p>Note that the (sufficiency) result is easy to prove when one further assumes that the convex Lagrangian <span class="math-container">$\mathcal L(x, \lambda)=f(x)+\sum_{j=1}^m\lambda_j g_j(x)$</span> is Gateaux differentiable, with a Gateaux derivative equal to 0 at <span class="math-container">$u=(x^*, \lambda^*)$</span>.</p>
<p>Indeed, a function <span class="math-container">$h: V \rightarrow \mathbb{R} $</span> convex and Gateaux differentiable on <span class="math-container">$V$</span> verifies <span class="math-container">$h(v)-h(u) \geq h^\prime(u; v-u), \forall u,v \in V$</span>, where <span class="math-container">$h^\prime(u; v)$</span> is the directional derivative of <span class="math-container">$h$</span> at <span class="math-container">$u$</span> in the direction <span class="math-container">$v$</span>. (One can see that from the definition of convexity: <span class="math-container">$h(u)+\theta \left( h(v) -h(u) \right) \geq h\left(u+\theta (v-u)\right)$</span>; subtracting <span class="math-container">$h(u)$</span>, dividing by <span class="math-container">$\theta$</span>, and taking the limit when <span class="math-container">$\theta \rightarrow 0^+$</span>; see <a href="https://math.unice.fr/%7Eauroux/EPU/Optim2.pdf" rel="nofollow noreferrer">this</a> for more details). Applying that inequality to the Lagrangian at <span class="math-container">$u$</span> proves that the Lagrangian admits a minimum at <span class="math-container">$u$</span>, which solves the minimization program: <span class="math-container">$ f(x^*) =L(x^*, \lambda^*) \leq f(x)+\sum_{j=1}^m\lambda_j g_j(x) \leq f(x), \; \forall x\in \Gamma$</span>.</p>
<p>However, in general, it is not easy to prove that the Gateaux derivative of a convex series (such as an infinite Lagragian) (exists and) equals 0 at some point <span class="math-container">$u$</span>, unless one uses the result (Theorem 3.14 in <a href="https://link.springer.com/article/10.1007/s43036-020-00125-y" rel="nofollow noreferrer">Bachir et al. (2021)</a>) that the Gateaux derivative is thus equal to the sum of derivatives of each term in the series.</p>

CC BY-SA 4.0
2018-09-24T21:57:21.777Z
2021-11-21T10:51:05.683Z
2021-11-21T10:51:05.683Z
bixiou
<p>Does the Karush-Kuhn-Tucker theorem on sufficient conditions for optimality of a convex program apply in countable dimension?</p>

<p>For precisions, see Definition 4.1.1 and Theorem 4.1.4 of <a href="https://ljk.imag.fr/membres/Anatoli.Iouditski/cours/convex/chapitre_4.pdf" rel="noreferrer">this course</a>. Does the theorem extend to an infinite (but discrete) number of variables and associated constraints? If so, do you have a reference?</p>

CC BY-SA 4.0
2021-03-08T18:42:01.703Z
I don't think "countable dimension" is that useful. Any infinite-dimensional Banach space has uncountable dimension. Actually, the dimension must be at least the cardinality of the continuum.
Michael Greinecker
CC BY-SA 4.0
2021-03-18T10:31:11.290Z
What do you mean? Maybe there exists similar results in uncountable dimension (i.e. for functions instead of series) but that's not the question here, and I am not sure the link between the two is straightforward. The paper presented below works in countable dimension.
bixiou
CC BY-SA 4.0
2021-03-18T10:37:36.100Z
No infinite-dimensional Banach space has countable dimension, that includes spaces of sequences and series. You can see the standard argument [here](https://math.stackexchange.com/questions/217516/let-x-be-an-infinite-dimensional-banach-space-prove-that-every-hamel-basis-of).
Michael Greinecker
CC BY-SA 4.0
2021-03-18T12:24:26.040Z
No. What this shows is that no infinite-dimensional Banach space has a countable (Hamel) basis. But there can be a countable Schauder basis. In Bachir et al. (2021), Schauder bases are used on a Banach space of countable dimension.
bixiou
CC BY-SA 4.0
2021-03-18T13:39:30.183Z
"Dimension" refers to the size of a Hamel basis.
Michael Greinecker
CC BY-SA 4.0
2021-03-25T20:07:07.960Z
Ah ok. How should I say then?
bixiou
CC BY-SA 4.0
2021-03-25T20:08:09.523Z
Maybe a KKT-theorem for sequence spaces.
Michael Greinecker
CC BY-SA 4.0
2021-11-21T10:53:13.770Z
Thank you. I have changed the title from "Karush-Kuhn-Tucker in infinite dimension" to "KKT for series".
bixiou
<mathematical-economics><optimization>
Karush-Kuhn-Tucker for series
bixiou
# Karush-Kuhn-Tucker for series

(Asked by: username_0 on 2018-01-17)

Does the Karush-Kuhn-Tucker theorem on sufficient conditions for optimality of a convex program apply in countable dimension?

For precisions, see Definition 4.1.1 and Theorem 4.1.4 of [this course](https://ljk.imag.fr/membres/Anatoli.Iouditski/cours/convex/chapitre_4.pdf). Does the theorem extend to an infinite (but discrete) number of variables and associated constraints? If so, do you have a reference?

**Tags:** mathematical-economics, optimization

> **Comments:**
> **username_1**: I don't think "countable dimension" is that useful. Any infinite-dimensional Banach space has uncountable dimension. Actually, the dimension must be at least the cardinality of the continuum.  
> **username_0**: What do you mean? Maybe there exists similar results in uncountable dimension (i.e. for functions instead of series) but that's not the question here, and I am not sure the link between the two is straightforward. The paper presented below works in countable dimension.  
> **username_1**: No infinite-dimensional Banach space has countable dimension, that includes spaces of sequences and series. You can see the standard argument [here](https://math.stackexchange.com/questions/217516/let-x-be-an-infinite-dimensional-banach-space-prove-that-every-hamel-basis-of).  
> **username_0**: No. What this shows is that no infinite-dimensional Banach space has a countable (Hamel) basis. But there can be a countable Schauder basis. In Bachir et al. (2021), Schauder bases are used on a Banach space of countable dimension.  
> **username_1**: "Dimension" refers to the size of a Hamel basis.  
> **username_0**: Ah ok. How should I say then?  
> **username_1**: Maybe a KKT-theorem for sequence spaces.  
> **username_0**: Thank you. I have changed the title from "Karush-Kuhn-Tucker in infinite dimension" to "KKT for series".  

---

## 1 answers

### Answer by username_0 on 2018-09-24. Score: 9 | Accepted answer

Yes, [Bachir et al. (2021)](https://link.springer.com/article/10.1007/s43036-020-00125-y) extend the Karush-Kuhn-Tucker theorem under mild hypotheses, for an infinite number of variables (their Corollary 4.1).

I give hereafter a weaker version of the generalization of Karush-Kuh-Tucker for sequence spaces:

> Let $X\subset\mathbb{R}^{\mathbb{N}}$ be a nonempty convex subset of
> $\mathbb{R}^{\mathbb{N}}$ and let $x^{\*}\in Int\left(X\right)$. Let
> $f,g\_{1},g\_{2},...,g\_{m}:X\rightarrow\mathbb{R}$ be convex functions
> continuous at $x^{\*}$ and term-to-term differentiable at $x^{\*}$, i.e.
> such that the functions
> $f\_{n,x^{\*}}\left(x\_{n}\right):=f\left((x\_1^{\*},...,x\_{n-1}^\*,x\_n,x\_{n+1}^\*,...)\right)$ and
> $g\_{j,n,x^{\*}}\left(x\_{n}\right):=g\_{j}\left((x\_1^{\*},...,x\_{n-1}^\*,x\_n,x\_{n+1}^\*,...)\right)$ are
> differentiable at $x\_{n}$ for all $n\in\mathbb{N}$ and
> $j\in\left\{ 1,2,...,m\right\}$.
>
> (Qualification condition) Suppose that for all $k\in\mathbb{N}^{\*}$
> and for all $x\in X$,
> $$x^{\*}+P^{k}\left(x-x^{\*}\right)=\left(x\_{1},...,x\_{k},x\_{k+1}^{\*},x\_{k+2}^{\*},...\right)\in X$$
> If there exist
> $\left(\lambda\_{j}^{\*}\right)\_{j}\in\left(\mathbb{R}\_{+}\right)^{\mathbb{N}}$
> such that
>
> $$\lambda\_{j}^{\*}g\_{j}\left(x^{\*}\right) =0,\:\forall j\in\left\{
> 1,2,...,m\right\} \quad \quad \quad \quad \quad (1)$$
> $$f\_{n,x^{\*}}^{\prime}\left(x\_{n}^{\*}\right)+\sum\_{j=1}^{m} \lambda\_{j}^{\*}g\_{j,n,x^{\*}}^{\prime}\left(x\_{n}^{\*}\right)=0,\:\forall
> n\in\mathbb{N} \quad \quad (2)$$
>
> (Sufficiency) Then $x^{\*}$ is an optimal solution on $\Gamma:=\left\{
> \left(x\_{i}\right)\_{i}\in
> X\,:\,g\_{1}\left(x\right)\leq0,...,g\_{m}\left(x\right)\leq0\right\} :$
>
> $$f\left(x^{\*}\right)=\underset{x\in\Gamma}{\inf}f\left(x\right)$$
>
> (Necessity) Besides, if $x^{\*}$ is an optimal solution on $\Gamma$ and
> if the Slater condition $Int\left(\Gamma\right)\neq\emptyset$ is
> verified, then there exist unique
> $\left(\lambda\_{j}^{\*}\right)\_{j}\in\left(\mathbb{R}\_{+}\right)^{\mathbb{N}}$
> which verify the (Karush-Kuhn-Tucker) conditions (1) and (2).

The number of constraints has to be finite, but simple constraints like non-negativity constraints can be replaced by an equivalent restriction on the domain of the variables. For example, instead of the constraints $\forall n \in \mathbb{N},\;x\_n \geq 0$ on the domain $\mathbb{R}^{\mathbb{N}}$, one can take $X=(\mathbb{R}\_+)^{\mathbb{N}}$, and the theorem applies.

Note that the (sufficiency) result is easy to prove when one further assumes that the convex Lagrangian $\mathcal L(x, \lambda)=f(x)+\sum\_{j=1}^m\lambda\_j g\_j(x)$ is Gateaux differentiable, with a Gateaux derivative equal to 0 at $u=(x^\*, \lambda^\*)$.

Indeed, a function $h: V \rightarrow \mathbb{R} $ convex and Gateaux differentiable on $V$ verifies $h(v)-h(u) \geq h^\prime(u; v-u), \forall u,v \in V$, where $h^\prime(u; v)$ is the directional derivative of $h$ at $u$ in the direction $v$. (One can see that from the definition of convexity: $h(u)+\theta \left( h(v) -h(u) \right) \geq h\left(u+\theta (v-u)\right)$; subtracting $h(u)$, dividing by $\theta$, and taking the limit when $\theta \rightarrow 0^+$; see [this](https://math.unice.fr/%7Eauroux/EPU/Optim2.pdf) for more details). Applying that inequality to the Lagrangian at $u$ proves that the Lagrangian admits a minimum at $u$, which solves the minimization program: $ f(x^\*) =L(x^\*, \lambda^\*) \leq f(x)+\sum\_{j=1}^m\lambda\_j g\_j(x) \leq f(x), \; \forall x\in \Gamma$.

However, in general, it is not easy to prove that the Gateaux derivative of a convex series (such as an infinite Lagragian) (exists and) equals 0 at some point $u$, unless one uses the result (Theorem 3.14 in [Bachir et al. (2021)](https://link.springer.com/article/10.1007/s43036-020-00125-y)) that the Gateaux derivative is thus equal to the sum of derivatives of each term in the series.


---

