10

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. Does the theorem extend to an infinite (but discrete) number of variables and associated constraints? If so, do you have a reference?

bixiou
  • 191
  • 1
  • 9
  • 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 Mar 08 '21 at 18:42
  • 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 Mar 18 '21 at 10:31
  • No infinite-dimensional Banach space has countable dimension, that includes spaces of sequences and series. You can see the standard argument here. – Michael Greinecker Mar 18 '21 at 10:37
  • 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 Mar 18 '21 at 12:24
  • 1
    "Dimension" refers to the size of a Hamel basis. – Michael Greinecker Mar 18 '21 at 13:39
  • Ah ok. How should I say then? – bixiou Mar 25 '21 at 20:07
  • 1
    Maybe a KKT-theorem for sequence spaces. – Michael Greinecker Mar 25 '21 at 20:08
  • Thank you. I have changed the title from "Karush-Kuhn-Tucker in infinite dimension" to "KKT for series". – bixiou Nov 21 '21 at 10:53

1 Answers1

9

Yes, Bachir et al. (2021) 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 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)) that the Gateaux derivative is thus equal to the sum of derivatives of each term in the series.

bixiou
  • 191
  • 1
  • 9