9
$\begingroup$

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network flows, edge/vertex cover, travelling salesman etc.) I know that some of them are NP-hard, but the point being that they can be 'framed as a linear program' if not solved optimally.

That got me thinking: We've always been taught systems of linear equations, linear algebra all throughout school/college. And seeing the power of LPs for expressing various algorithms it's kinda fascinating.

Question: Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science? I do understand that they help simplify the understanding and are computationally tractable most of the times but is that it? How good is this 'approximation'? Are we over-simplifying and are the results still meaningful in practice? Or is it just 'nature' i.e. the problems that are the most fascinating are indeed simply linear?

Would it be safe to safe that 'linear algebra/equations/programming' are of the corner stones of CS? If not then what would be a good contradiction? How often do we deal with non-linear stuff (I don't necessarily mean theoretically but also from a 'solveability' standpoint i.e. just saying it's NP doesn't cut it; there should be a good approximation to the problem and would it land up being linear?)

$\endgroup$
  • 4
    $\begingroup$ I didn't downvote, but I don't see why tractability isn't a satisfying answer for you. There are some interesting precise senses in which non-convex problems are intractable eg. arxiv.org/abs/1210.0420 . $\endgroup$ – Colin McQuillan Oct 18 '12 at 9:16
  • 2
    $\begingroup$ Downvoters may have many reasons why they choose not to comment. $\endgroup$ – Tyson Williams Oct 18 '12 at 13:41
  • 1
    $\begingroup$ one way to look at it is that any NP problem can be reduced to integer programming in polynomial time, and then the integer programming problem can be relaxed. but we do use spectral techniques and SDP relaxations, which are quadratic optimization problems that are efficiently solvable. $\endgroup$ – Sasho Nikolov Oct 18 '12 at 18:37
  • 1
    $\begingroup$ What does “linear systems” in this question mean? $\endgroup$ – Tsuyoshi Ito Oct 19 '12 at 22:24
  • 1
    $\begingroup$ linear systems are found all over science period.... its a simplification that gets surprisingly high mileage.... it seems a small corollary to the unreasonable effectiveness of mathematics in the natural sciences .. apparently CS fits this category of "natural sciences".... it is closely allied with physics, arguably increasingly so all the time [eg shrinking transistors, heat dissipation, low level QM, study of energy consumption, entropy, etc].... $\endgroup$ – vzn Oct 19 '12 at 23:40
12
$\begingroup$

The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.

Perhaps what is more relevant is "why do linear systems admit tractable solutions ?" which is not exactly what you asked, but is related. One perspective on this is composability. Since the defining property of a linear system is that $f(x + y) = f(x) + f(y)$, this imparts a kind of "memorylessness" to the system. To build up a solution to a problem I can focus on individual pieces and combine them with no penalty. Indeed, the premise of most algorithms for flow is precisely that.

This memorylessness imparts efficiency: I can break things into pieces, or work iteratively, and I don't lose by virtue of doing so. I can still make bad decisions (c.f. greedy algorithms) but the act of splitting things up itself doesn't hurt me.

This is one reason why linearity has such power. There are probably many others.

$\endgroup$
  • $\begingroup$ I like this answer but to those that argue that linear programming is not the boundary, I respond with: "it's P-complete!" ;). $\endgroup$ – Artem Kaznatcheev Oct 28 '12 at 0:31
  • $\begingroup$ Yes but is it the case that (for example) SDPs are not ? $\endgroup$ – Suresh Venkat Oct 28 '12 at 5:53
  • $\begingroup$ We don't have to have a single boundary, and some boundaries of P (say quadratic programming with positive semi-definite matrix for the squared terms) do seem more general. I didn't mean to disagree, was just pointing out that the boundary is more a matter of taste when picking between P-complete problems. $\endgroup$ – Artem Kaznatcheev Oct 28 '12 at 7:20
5
$\begingroup$

"Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science?"

Here is a partial answer in my mind: I think it is because nature is abound with objects/phenomena - representable by functions which albeit being nonlinear on their operands, are actually members of linear spaces. The wave functions in a Hilbert space, the components in a fourier spectrum, polynomial rings, stochastic processes - they all behave in that fashion. Even very general definitions of curved spaces are built out of composing small charts of flat spaces ( manifolds, Riemann surfaces, .. ). Moreover, nature is full of symmetries and studying symmetries invariably gets into study of linear operators (representation theory, in my mind, is creeping into many areas of computer science ever so ubiquitously).

These are in addition to the cases where the operators themselves are linear in nature.

A large fraction of problems for which we need computer programs, arise either directly as, or are abstracted from, naturally occuring phenomena. Perhaps studying/solving linear systems shouldn't be a great deal of surprise, after all?

$\endgroup$
  • $\begingroup$ Ah yes, the wonderful joys of lifting maps. $\endgroup$ – Suresh Venkat Oct 19 '12 at 0:08

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.