# Using KKT to Write a Non-Linear Program

I would like to rewrite this two-level program as a Non Linear Program using KKT conditions

$\min_{x \in X, \space y \in Y} \space f(x)$
$\text{s.t. } \space g(x, y) \leq 0$
$y \in \text{argmin}_{z \in Y} \space F(x,z)$
$\space \space \space \space \space \space \text{s.t.} \space Ax + Bz - b \leq 0$

Here $A$ and $B$ are matrices with dimension $m \times n_x$ and $m \times n_y$ respectively. The idea is to replace the $\text{argmin}$ constraint on the $y$ variables with KKT conditions for a point $(x,y)$.

-

You can write the bilevel program as follows:

$\min_{x \in X, y \in Y} f(x)$
s.t. $g(x,y) \leq 0$
$y = z$
$\nabla_{z} F(x,z) + \mu^\top\nabla_{z}(Ax+Bz-b) = 0$
$Ax + Bz -b \leq 0$
$0 \leq \mu \perp (Ax + Bz -b) \geq 0$

The last line is a complementarity constraint that can also be written:

$\mu_{i} \geq 0$
$\mu_{i} [Ax + Bz - b]_{i} = 0$

This is an MPEC. I'm not sure if this formulation will give you acceptable solutions, but you can try it. There are rules for posing well-posed MPECs: see this paper for details: Baumrucker, B.T., J. G. Renfro and L.T. Biegler “MPEC Problem Formulations in Chemical Engineering Applications,” Computers and Chemical Engineering, 32, pp. 2903-2913 (2008)

-
Thanks for this. Quick question: since $\in argmin_{z\in Y} \space F(x,z)$ - I feel like we should assume x is given and write all derivatives in the KKT conditions as partial derivatives over the z variables... Or would this be wrong? –  Elements Mar 4 '11 at 6:29
Yes, that is correct. $x$ can be thought of as a parameter in the 2nd tier problem. –  Gilead Mar 4 '11 at 6:35

You need to be careful about how you will address the MPEC because, like all MPECs, it satisfies no constraint qualification. What that means is that the usual KKT conditions aren't necessary for optimality: you may find that there exist no Lagrange multipliers or that there exist infinitely many of them (in this case they form half lines). On the other hand, it looks like your MPEC satisfies MPEC-specific qualification conditions. You need to make sure you use an algorithm that aims to satisfy MPEC-specific first-order optimality conditions (typically, the strong stationarity conditions) such as PATH or FilterSQP. See http://neos-server.org/neos for a few such solvers available online.

-