4
$\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$
2
$\begingroup$

Yes, Bachir and Fabre (forthcoming) extend the Karush-Kuhn-Tucker theorem under mild hypotheses, for a finite 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^{*}\right)$ and $g_{j,n,x^{*}}\left(x_{n}^{*}\right):=g_{j}\left(x^{*}\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.

$\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.