0
$\begingroup$

I'm working on a convex quadratic separable min-cost flow problem with the following structure:

$P = \{\min \frac{1}{2}x^tQx + qx : Ex = b, 0 \leq x \leq u\}$

But I'm stuck on deriving the KKT conditions to solve the problem.

Can someone help me with the computation?

Improve this question
$\endgroup$
3
  • $\begingroup$ $\min$ seems to be missing before 1/2. $\endgroup$
    – Dima Pasechnik
    Commented Jul 3, 2019 at 19:55
  • $\begingroup$ yes thank you! corrected! $\endgroup$
    – GaspareG
    Commented Jul 4, 2019 at 9:02
  • $\begingroup$ or.stackexchange.com $\endgroup$
    – Rodrigo de Azevedo
    Commented Jul 6, 2019 at 6:13

1 Answer 1

Reset to default
0
$\begingroup$

The KKT condition is given by introducing relaxation parameters to the objective (derivative equals 0) so that whenever any element of $x$ is above $0$ or below $u$, parameters can increase to allow the system of equations to satisfy but at the same time cause penalties when x is not optimal.

So we have the following linear system that needs to be solved. $$ M=\begin{bmatrix} Q & E^\mathrm{T} & -I & I \\ E & 0 & 0 & 0\\ \end{bmatrix} \begin{bmatrix} x \\ \lambda \\ \mu \\ h \\ \end{bmatrix}=\begin{bmatrix} -q\\ b\\ \end{bmatrix} $$

The KKT conditions are then the above equation for stationary. Your listed conditions for primal feasibility.

complementary slackness:

$$\mu\odot x=0$$

$$h\odot(x-u)=0$$

And $\lambda\ge0,\ \mu\ge0,\ h\ge0$ for dual feasibility.

This is my first ever answer on here. Hope I don't make a mistake.

Improve this answer
$\endgroup$
3
  • $\begingroup$ it looks as if there is an error in the last 2 row of the matrix above, as they together would imply $\mu=0=u$. $\endgroup$
    – Dima Pasechnik
    Commented Jul 4, 2019 at 9:25
  • $\begingroup$ This answer is not correct. For example, the system contains the condition $x=0$ which would be too restrictive. $\endgroup$
    – harfe
    Commented Jul 4, 2019 at 9:26
  • $\begingroup$ @Dima Pasechnik They are actually complementary slackness that don't need to be satisfied. Only the feasibility equations and the stationary point need to be satisfied. $\endgroup$
    – Pui Ho Lam
    Commented Jul 4, 2019 at 11:27

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