0
$\begingroup$

I want to find a solution to the minimisation problem

$$ \text{min } c^Tx \qquad \text{subject to } Ax=b $$

I have implemented the parametric self-dual simplex by R. Vanderbei in Matlab and it works perfectly with inequality constraints (tested it with multiple examples)

It solves a maximisation problem $$ \text{max } c^Tx \qquad \text{subject to } Ax\leq b $$

I also want it to work with equality constraints, so I've rewritten the equality constraints as inequality constraints (with slack variables $w$): $$ Ax + w\leq b \\ -Ax - w \leq -b $$

(and for the minimisation problem I will need to take $-c^T$). So then the constraints will look like $$ \begin{bmatrix} A & I & 0\\ -A & 0 &-I \end{bmatrix} = \begin{bmatrix} x \\ w \\ w \end{bmatrix} = \begin{bmatrix} b \\ -b \end{bmatrix} $$

Is this the correct approach? Either my implementation or the method is wrong, because my algorithm doesn't work for equality constraints.

$\endgroup$
1
  • $\begingroup$ Solved; replace $-I$ with $I$ and the second slack variable should be different, e.g. $v$ $\endgroup$ May 3, 2015 at 15:53

1 Answer 1

0
$\begingroup$

I replaced $-I$ with $I$ and used a different slack variable $v$, then the algorithm works fine

$\endgroup$

You must log in to answer this question.

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