7
$\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$
5
$\begingroup$

Yes, Bachir, Fabre & Tapia-Garcia extend the Karush-Kuhn-Tucker theorem under mild hypotheses, for an infinite number of variables.

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 (Proposition 3 in Bachir, Fabre & Tapia-Garcia) that the Gateaux derivative is thus equal to the sum of derivatives of each term in the series.

| improve this answer | |
$\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.