10
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ – Michael Greinecker Mar 8 at 18:42
  • $\begingroup$ 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. $\endgroup$ – bixiou Mar 18 at 10:31
  • $\begingroup$ No infinite-dimensional Banach space has countable dimension, that includes spaces of sequences and series. You can see the standard argument here. $\endgroup$ – Michael Greinecker Mar 18 at 10:37
  • 1
    $\begingroup$ "Dimension" refers to the size of a Hamel basis. $\endgroup$ – Michael Greinecker Mar 18 at 13:39
  • 1
    $\begingroup$ Maybe a KKT-theorem for sequence spaces. $\endgroup$ – Michael Greinecker Mar 25 at 20:08
9
$\begingroup$

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 in infinite dimension:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.