I have an objective function that I can write either in quadratic programming (QP) such as $$\sum_{i=1}^N \sum_{j=1}^N C_{ij}^2$$ or as an LP problem $$\sum_{i=1}^N \sum_{j=1}^N |C_{ij}|$$ which can be done by splitting $C_{ij}$ into two parts $C_{ij} = C_{ij}^+ + C_{ij}^-$ and imposing $C_{ij}^{+}>0$ and $C_{ij}^{-}>0$. This doubles the number of optimisation variables.

Both approaches will have additional linear constraints which will be the same.

My question is the following: Is it possible to argue that the LP algorithm will always be faster than the QP algorithm given that we use the state of the art algorithms for each ?

Update: I realise that the solutions will not be the same. But assuming that I want to compare both approaches, I simply want to know which one will in general be faster. In practice I find LP to be faster. But I would like to know if this is a hard rule or does it simply come down to which algorithm I am using and the nature of the problem and constraints.

  • $\begingroup$ How are those equivalent optimization problems? If true, it would be like saying minimizing $\|x\|_2$ is the same as minimizing $\|x\|_1$, unless I'm missing something. $\endgroup$
    – Kirill
    Oct 9 '16 at 21:05
  • $\begingroup$ Can you tell us anything about the other constraints? Are you interested in actually solving some of these problems in practice? If so, how big is $N$ and how many linear constraints are there? $\endgroup$ Oct 9 '16 at 21:11
  • $\begingroup$ To stress Kirill's point: As soon as there are additional constraints, these two formulations are not equivalent. So your question is one of modeling, not mathematics. (If there are no constraints, they are of course equivalent, both having the trivial solution $C=0$.) $\endgroup$ Oct 9 '16 at 21:17
  • 3
    $\begingroup$ Your problems are so tiny that they'll be easy to solve either way. $\endgroup$ Oct 9 '16 at 22:05
  • 1
    $\begingroup$ Thousands of extremely cheap computations are still cheap. If this is the level of complexity you are worried about, then don't worry: a thousand, 30-variable problems should be solvable in a few seconds at most, with either formulation. $\endgroup$ Oct 10 '16 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.