1
$\begingroup$

I am looking for the extension of the theorem I found in the book by Luenberger called "Optimization by vector space methods."

Here is the statement of that theorem from Luenberger:

Generalized Kuhn-Tucker Theorem. Let $X$ be a vector space and $Z$ be a normed space having positive cone $P$. Assume that $P$ contains an interior point.

Let $f$ a Gauteaux differentiable real-valued functional on $X$ and $G$ a Gauteaux differentiable mapping from $X$ into $Z$. Assume that the Gateaux differential of are linear in their increments. Suppose that $x_0$ minimizes $f$ subject to $G(x) \le \theta$ and that $x_0$ is a regularity point of the inequality $G(x) \le \theta$. Then there is a $\lambda \in Z, \lambda \ge 0$ such that the Lagrangian \begin{align*} f(x) +< G(x), \lambda> \end{align*} is stationary at $x_0$; furthermore $< G(x_0), \lambda>=0$.

Where regularity point is defined as:

A point $x_0$ is said to be a regularity point of the inequality $G(x) \le \theta$ if $G(x_0) \le \theta$ and there is an $h$ such that $G(x_0)+\delta G(x_0,h) < \theta$.

My Question:

I am looking for an extension of this theorem to more than one constraint. Also what happens to the regularity conditions? I think it should be some statement about linear independence but I am not sure. I would be grateful for any thoughts, reference or comments you might have. Also, if you know of any other sources similar to Luenberger that would be great. Thank you very much.

$\endgroup$
8
  • 2
    $\begingroup$ This theorem looks like it covers multiple constrains. E.g. if you want to have $$G_1(x)\leq \theta_1$$ and $$G_1(x)\leq \theta_1$$, you can apply the theorem to $$G(x)=(G_1(x),G_2(x))\leq (\theta_1,\theta_2)\in Z^2$$. $\endgroup$
    – Leverkuehn
    Mar 24, 2015 at 21:52
  • $\begingroup$ thanks. I thought so too. But what is the regularity conditions? $\endgroup$
    – Boby
    Mar 24, 2015 at 21:54
  • 1
    $\begingroup$ The regularity condition can be applied similarly. E.g. there has to be an $h$ such that $(G_1(x_0),G_2(x_0))+(\delta G_1(x_0,h),\delta G_2(x_0,h)) < (\theta_1,\theta_2)$. $\endgroup$
    – Leverkuehn
    Mar 24, 2015 at 22:08
  • $\begingroup$ Should linear independence come in at some point or is that only for equality constrains? $\endgroup$
    – Boby
    Mar 24, 2015 at 22:10
  • 1
    $\begingroup$ Ha! I'm glad someone answered. I was thinking the same thing but I didn't have time/inclination to pull out the reference and check. $\endgroup$ Mar 26, 2015 at 16:40

1 Answer 1

3
+50
$\begingroup$

I am not an expert in these general optimization criteria, so please treat my answer with care!

First of all, I believe that you stated the theorem incorrectly. $\lambda$ should be in the dual space of $Z$ (and $\lambda\geq 0$ means (as usual) that $\lambda$ is in the dual cone of $P$).

As the inequality constraint $G:X\rightarrow Z$ maps to an arbitrary normed space, it already includes the case of multiple constraints. For example, if you want to consider the two constraints $G_1:X\rightarrow Z_1$ and $G_2:X\rightarrow Z_2$, where $G_i(x)\leq_{P_i} 0$, $i=1,2$, you can simply apply the theorem to $G:X\rightarrow Z_1\times Z_2$, $G(x)=(G_1(x),G_2(x))$, where the cone is given by $P=\{(p_1,p_2),~p_i\in P_i\}$.

Also, the regularity condition carries over. Applied to $G=(G_1,G_2)$ it reads as follows: $x_0$ is regular, if there is an $h\in X$ such that $G_i(x_0)+\delta G_i(x_0,h)<0$ ($i=1,2$).

The question of linear independence is somewhat hidden by the regularity constraint. It appears when you consider finite dimensional spaces. Let $X=\mathbb{R}^m$, $Z=\mathbb{R}^n$ and $P$ the cone of coordinate-wise positive vectors. Then the regularity condition becomes: There is an $h\in\mathbb{R}^m$ such that $$G_i(x_0)+\nabla G_i(x_0) h <0 $$ for $i=1,...,n$. This condition is trivial for $G_i(x_0)<0$, so it only has to be checked for all $i$ with $G_i(x_0)=0$. This is essentially the Mangasarian-Fromovitz constraint qualification. Recall that linear independence of the gradients implies the MFCQ.

As an additional reference

Ito, Kazufumi, and Karl Kunisch. Lagrange multiplier approach to variational problems and applications. Vol. 15. SIAM, 2008

might be helpful.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .