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$
  • $\begingroup$ Solved; replace $-I$ with $I$ and the second slack variable should be different, e.g. $v$ $\endgroup$ – MichaelDeSanta May 3 '15 at 15:53
0
$\begingroup$

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

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