Optimization by Vector Space Methods

What Hacker News says

1. sreanJun 2026
   I love this one

   https://ia801706.us.archive.org/7/items/in.ernet.dli.2015.14...

   Luenberger, Optimization By Vector Space Methods.

   Although it is about a specific application, optimization, it is a good book to get a sense of infinite dimensional vector spaces. I would also recommend Halmos. His book surreptitiously introduces you to that subset of linear algebraic notions that survive inti infinite dimensional spaces.

   thread
2. graycatAug 2023
   (1) Uh, just to mention, while sometimes some norms of math writing are not always made fully clear, in writing with math expressions it is important at least to define the symbols and also good to define the terms, motivate the discussion, give intuitive views, and give examples. In particular, (a) in physics it is standard to have some globally defined, understood, and accepted symbols, e.g., in F = ma, F for force, m for mass, and a for acceleration. (b) Uh, essentially that is not done in math and, instead, in each paper, discussion, text chapter, etc. really should start even from, say,

   R -- the set of real numbers

   n -- a positive whole number

   e -- the base of the natural logarithm

   etc. The paper that is the subject of this thread had some math notation without such definitions.

   (2) My standard, quite clear, go-to source on Kalman filters is the section in (with TeX syntax)

   David G.\ Luenberger, {\it Optimization by Vector Space Methods,\/} John Wiley and Sons, Inc., New York, 1969.\ \

   That's a really good example of some really good math and writing of math.

   Show morethread
3. graycatNov 2018
   Nice answer.

   But since I studied a lot of optimization, I saw my linear programming answer first. On an interview, typically want to give the first correct answer do find.

   My answer is more general, and that is goodness. Indeed, you mentioned that your answer solves a more general question than intended in the OP. So, you seem to like the generality of your answer but not the generality of mine.

   The generality of my answer applies to convex polytopes, convex hulls, in any finite dimension, and dimension 3 should be of interest in some cases, e.g., see if two objects intersect. That might be of interest in some of robotics.

   If the polytopes are determined by points, then my answer solves the problem and we are looking for a separating hyper plane. If each polytope is determined by the intersection of half spaces determined by hyperplanes, then we are looking for a point in common, and again we can use linear programming. So, given points we are looking for a separating hyper plane, and given hyper planes we are looking for a point. Smells like a nice case of duality.

   Farkas lemma, a special case of my solution, is central to the Kuhn-Tucker conditions in nonlinear optimization. Since the ML people are interested in optimization, they might welcome Farkas lemma and my more general solution.

   And, again, my answer really is part of "algorithms and data structures" which was the focus of the questions.

   So, now we are into what is commonly called computational geometry, commonly regarded as part of computer science, and heavily about algorithms. E.g., doing nearest neighbor searches via k-D trees (in Sedgwick) and cutting planes is part of computer science, computational geometry, trees, data structures, and algorithms.

   For the linear programming, just call a subroutine, e.g., IBM's old OSL (optimization subroutine library).

   My more general answer indicates that I would be a good person to work with.

   The question is a separation problem. Well, so as to have readers be more comfortable, I did omit mention of the Hahn-Banach theorem. For curious readers, there are lots of applications of that classic result in D. Luenberger, Optimization by Vector Space Methods.

   "Hard to work with ...". How 'bout hard to please?

   Show morethread
4. graycatMar 2018
   Notice Ulam, Feynman, and von Neumann at Los Alamos in

   http://www-history.mcs.st-and.ac.uk/BigPictures/Ulam_Feynman...

   For the Banach match box problem, that is, flip a fair coin x + y times and find the probability of getting heads exactly x times. So, it's a binomial probability problem.

   A Banach space is a complete, normed linear space. There is a nice chapter on Banach space in

   Walter Rudin, Real and Complex Analysis.

   There are some nice applications of the Hahn-Banach theorem in

   David G. Luenberger, Optimization by Vector Space Methods.

   In

   Patrick Billingsley, Convergence of Probability Measures.

   is a nice presentation of Ulam's result in measure theory Le Cam called tightness: Roughly, IIRC, for any probability measure P and any a > 0 no matter how small, there exists a sphere S of finite radius so that P(S) > 1 - a. Intuitively the probability mass can't just keep avoiding all spheres; eventually some sphere, if large enough, must cover nearly all the mass. There are some cute technical details.

   Once in a paper I used Ulam's result to show that a goofy distribution-free statistical hypothesis test was not trivial. And I've seen other applications.

   The hypothesis test was to improve on our work in artificial intelligence for zero day monitoring for problems in server farms and networks. So, Ulam's tightness has played a role in at least one piece of work intended to be practical!

   IIRC, Ulam was long head of Los Alamos. Once I heard his lecture on the role in evolution of having two sexes.

   There was a Time-Life book on math with a few pages on Ulam. IIRC, Ulam did by hand or mechanical calculator some of the early Monte-Carlo evaluations of critical mass.

   At

   http://www.brainyquote.com/quotes/quotes/s/stanislawu312043....

   is

   "It is still an unending source of surprise for me how a few scribbles on a blackboard or on a piece of paper can change the course of human affairs."

   Stanislaw Ulam

   Show morethread
5. graycatNov 2017
   Part II

   Super simple view: In math, there are sets with elements. That's the logical foundation of essentially all of current pure/applied math. The details are in Zermalo-Fraenkel axiomatic set theory assuming the axiom of choice. E.g., can construct from sets a set that looks like the real numbers we knew about in the 9th grade. Soon define ordered pairs and, then, functions. After that, a huge fraction of everything is functions. The proofs -- as actually written but without the crucial intuitive ideas that permitted finding the proof -- are all essentially just symbol substitution as in basic logic and Whitehead and Russell. Warning: Any math you write for publication should be easily translated back to just sets and symbol substitution; that and nothing else is the criterion. If you also want the proof to be readable by humans, there is more. E.g., in the proof might mention one by one each theorem assumption and where it gets used.

   (iv) Learn linear algebra. Really the subject grew out of Gauss elimination for solving systems of linear equations -- with some additional attention to numerical stability (e.g., partial pivoting, double precision inner product accumulation, and iterative improvement) -- that's nearly always still the way to do it. It's fun to program a good Gauss elimination routine, e.g., just in C.

   There see clearly that any such system of equations has none, one, or infinitely many solutions. Later will discover that the set of all the solutions is an affine subspace, that is, a vector space plus some one vector; that is, a plane that does not pass through the origin. And will discover that the left side with the unknowns is a linear function -- big time stuff.

   So, that start was a small thing for a huge future.

   Next up, we consider n-tuples of real (or complex, here and always in linear algebra) numbers. Then we see how to make the n-tuples a vector space. They are the most important of the vector spaces.

   But should also see the abstract (with no mention of n-tuples) definition of a vector space because (a) the n-tuples are the most important example, (b) even when working with just n-tuples often need the more abstract definition (especially for subspaces, which are often the real interest, e.g., hyperplanes in curve fitting and multivariate statistics), and (c) there are other important vector spaces that are not just n-tuples (in signal processing, sets of random variables, wave functions in quantum mechanics, solutions to some differential equations, and much more).

   So, learn about linear independence and bases (essentially coordinate systems).

   Learn about inner products, distance, angles, and orthogonality. See generalizations of cosines, e.g., the Schwarz inequality, and the Pythagorean theorem.

   Learn about eigenvalues and eigen vectors -- those eigen vectors are often the most important ones in applications, e.g., your favorite coordinate axes.

   Then for the crown jewel, learn about the polar decomposition and, thus, singular values, principal components (e.g., data compression), the core of the normal equations in statistics, etc.

   There is a remark in G. Simmons that the two pillars of mathematical analysis are linearity and continuity. The superposition in physics is essentially linearity. In applied math, linearity is the main tool, the key to the land of milk and honey. Well, a good course in linear algebra is a good start on linearity. In particular, those linear equations solved with Gauss elimination are linear as in linear transformations in, right, linear algebra.

   Then, sure, that version of linearity takes one through much of all of applied math, e.g., Fourier analysis, the fast Fourier transform, X-ray diffraction, Banach space, Hilbert space, the classic Dunford and Schwartz, Linear Operators, etc.

   So, a Banach space is just a vector space where the scalars are the real or complex numbers, there is a norm, that is, a definition of distance, and the space is complete in that norm. Complete is what the rational numbers are not but the real numbers are. Or, complete means that a sequence that appears to converge, that is, converges in the weaker sense of Cauchy, actually does have something to converge to and does. E.g., in the rationals, the approximations to more and more decimal places of pi have nothing to converge to but in the reals do.

   In theorem proving, nice to have completeness. But, sure, computing knows next to nothing about completeness because we compute essentially only with rational numbers. So, can do a lot of work without completeness. Indeed, in applications, often we are just approximating, and the rationals can get as close as we please to pi!

   Banach spaces are not trivial or useless: E.g., based on the Hahn-Banach theorem, there is the grand applied math dessert buffet

   David G. Luenberger, Optimization by Vector Space Methods, John Wiley and Sons.

   A Hilbert space is a Banach space where the norm comes from an inner product.

   E.g., the set of all real valued random variables X such that E[X^2] is finite form a Hilbert space. That the space is complete for those random variables is nearly mind blowing; actually the proof is short.

   (v) There remains Baby Rudin, Principles of Mathematical Analysis.

   There see calculus done with essentially full care, as theorems and proofs. So, again, get lessons in how to write theorems and proofs on the way to being a good mathematician.

   The main content of the book is just showing that a real valued continuous function defined on a closed interval of the reals has a Riemann integral.

   The key is that that interval is compact. So, learn about compactness, which is of quite general usefulness.

   Then with compactness and continuity, have uniform continuity. Now the doors to grandeur start to open: That the Riemann integral works is a short proof. And, later in the book, get the three epsilon proof that the uniform limit of continuous functions is a continuous function (was a question on one of my Ph.D. qualifying exams -- from baby Rudin, I got it!).

   Compactness is so powerful that it is nearly the same as just finiteness -- there's a famous, old paper on that.

   Well for a positive integer n and the set of real number R, in R^n a set is compact if and only if it is closed and bounded. Now we are cleaning up the Riemann integral and a lot of associated stuff.

   At the back, Rudin gives a nice, short definition of a set of the real numbers that has measure zero (without really getting deep into measure theory) and, then, shows the Riemann integral exists if and only if the function is continuous everywhere except on a set of measure zero. Nice. Now an exercise is to find a function that is differentiable but whose derivative is not Riemann integrable. Might look in Gelbaum and Olmstead, Counterexamples in Analysis.

   Also the later editions of baby Rudin cover the exterior algebra of differential forms. That material is of interest in differential geometry, some applications, and general relativity.

   That's an overview of what baby Rudin is about.

   Go through that book carefully and will come out with (a) some good knowledge of the "principles" of the analysis part of pure math and (b) much better skills at doing math derivations, definitions, theorems, and proofs. If you want to write and publish new proofs for, say, AI, baby Rudin is one of your best mentors, maybe your Fairy Godmother?

   For being an applied mathematician, sure, you already guessed, and you were correct, that essentially always in practice the Riemann integral exists; so, why sweat the details? Okay, then just use baby Rudin to learn about compactness, continuity, uniform continuity, measure zero, and more on how to write proofs. And, really, focusing just on compactness, continuity, etc., can pull that off in a few, nice weekends, maybe just one. Then look at that result near the back on the uniform limit of continuous functions is continuous to see how to do such work.

   Sure, Rudin discusses compactness, etc. on metric spaces. Well, easily enough, the set of real numbers R is also a metric space! And for positive integer n, so is R^n.

   So, why say metric space instead of, say, just R^n? Well, first, the theory is cleaner because a metric space has so many fewer assumptions than R^n so that can see more clearly just what assumptions make the results true. Second, maybe some fine day all you will have is just a metric space and, then, can still use the results -- don't hold your breath while waiting for a significant application, either pure or applied, with a non-trivial metric space that isn't also much more! Or, proving the stuff in a metric space is no more difficult, more general, and maybe, and actually, more useful.

   Or, maybe math had the results in R^n and then invented a metric space just to have a place to have just enough to make the results true! So, a metric space was invented to have the least assumptions needed for proving the results; so, what came first were the results, and the metric space definition came later. Maybe!

   Show morethread
6. tnecnivAug 2017
   I don't know why, but people always seem to forget that optimization is an important topic in machine learning that requires study. Boyd's book is the canonical source (and free online). If you want to get some functional analysis background at the same time, you can look at Optimization by Vector Space Methods. It's an older book but it is still worth a read and provides more theoretical foundations than Boyd.
   thread