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$
7
  • 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$ Oct 18, 2012 at 9:16
  • 2
    $\begingroup$ Downvoters may have many reasons why they choose not to comment. $\endgroup$ Oct 18, 2012 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$ Oct 18, 2012 at 18:37
  • 1
    $\begingroup$ What does “linear systems” in this question mean? $\endgroup$ Oct 19, 2012 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, 2012 at 23:40

3 Answers 3

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$
3
  • $\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$ Oct 28, 2012 at 0:31
  • $\begingroup$ Yes but is it the case that (for example) SDPs are not ? $\endgroup$ Oct 28, 2012 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$ Oct 28, 2012 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$
1
  • $\begingroup$ Ah yes, the wonderful joys of lifting maps. $\endgroup$ Oct 19, 2012 at 0:08
1
$\begingroup$

I think all answers here are pretty good and linear systems admitting tractable solutions is definitely a big factor. I also like Arnab's answer about the ubiquity of linear spaces. But I also feel the need to point out that the instinct to ask this question is certainly not misplaced. Since the question employed some physical intuition, I think some physics context might be useful to illustrate why this is actually a really good question and why there's a slight caveat to the answers.

It is after all true that one of the big reasons why we think quantum mechanics is incomplete, is precisely because the Schrödinger equation, which governs quantum dynamics, is linear. Linear systems do not admit chaos, non-linear systems do. So it would seem that a purely quantum mechanical universe is one that is void of chaos, which doesn't correspond to our universe (quantum chaos is an open question in physics). This has implications for the question of whether quantum computers can be hoped to truly simulate as much as some hope them to, since quantum computers can be thought of as efficient in simulating nature because we don't have to simulate the "quantumness" (this is a bit of an oversimplification, but true to a certain extent).

Even if we look at machine learning, it seems to be the case that non-linear neural nets are needed to be particularly good at learning. Linear systems simply don't do as well here.

So while most of our universe seems perfectly well described by approximations of linearity, it may just very well be that we're missing out on some structure by not being better at computing non-linear systems.

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