"A mathematical optimization problem, or just optimization problem, has the form minimize f0(x) subject to fi(x) ≤ bi , i = 1, . . . , m. (1.1) Here the vector x = (x1, . . . , xn) is the optimization variable of the problem, the function f0 : R n → R is the objective function, the functions fi : R n → R, i = 1, . . . , m, are the (inequality) constraint functions, and the constants b1, . . . , bm are the limits, or bounds, for the constraints. A vector x ⋆ is called optimal, or a solution of the problem (1.1), if it has the smallest objective value among all vectors that satisfy the constraints: for any z with f1(z) ≤ b1, . . . , fm(z) ≤ bm, we have f0(z) ≥ f0(x ⋆ ). We generally consider families or classes of optimization problems, characterized by particular forms of the objective and constraint functions. As an important example, the optimization problem (1.1) is called a linear program if..."
Boy, and that's just the opening paragraph of the introduction.
Exactly what arcane requisite elite math precursors are necessary to even remotely understand this?
It's more some level of what they call "mathematical maturity", or just experience with math. None of this relies on math past the first or second year of college for a typical STEM degree: linear algebra and vector calculus. But most people aren't used to the notation that is taken for granted here, for example, subscripts on functions.
I know it looks scary if you aren't used to it, but it just takes some practice to pick up. This is far from arcane and elite in the math world!
I still remember the formal prerequisite for one of the more advanced math courses I took at uni: “The mathematical maturity that several years of study in mathematics typically gives” (roughly translated from Swedish). I thought it was kind if pretentious at the time (most other courses listed other courses as prerequisites), but now I think it makes sense.
This is one of those things where the math is actually pretty simple, but the notation is incredibly opaque (in part because things are generalized to hell) if you haven't been exposed to it before.
In layman's terms: you have a set of n variables, a set of m constraints on those variables (like x + y ≤ 3, or x² + y² ≥ 1), and some function you're trying to minimize. Oh, and everything involves real numbers, no fancy stuff like complex numbers or rationals or p-adic integers or Banach spaces.
The book itself gives you a taste of what you need to know to fully understand the material:
> The only background required of the reader is a good knowledge of advanced calculus and linear algebra. If the reader has seen basic mathematical analysis (e.g., norms, convergence, elementary topology), and basic probability theory, he or she should be able to follow every argument and discussion in the book.
> This is one of those things where the math is actually pretty simple, but the notation is incredibly opaque
If you're not used to it, this kind of notation looks like hieroglyphics.
If you are used to it, every vague English-language technical document you see floating around your workplace just reads like a bunch of flailing-arm hand-waving.
Usually, language that tries to simplify or put things in layman's terms is missing important detail for fully specifying the problem. It's like watching the 3 minute version of a recipe on YouTube and thinking you have a good understanding of how it works, but then when you go to make it, you realize they didn't tell you if they used whole-wheat or all-purpose flour, or if they bake at 350 or 450, or in a glass or aluminum pan. If you try to follow the recipe, you might end up with something significantly different. It's not that the quick, intuitive version isn't useful, you can gain a lot of insight and get a high level picture often much quicker than you would reading the complete, fully specified recipe. But if what you want to do is reproduce the recipe exactly, you need the fully specified version. Personally when I'm writing technical documents, I prefer to include both the intuitive overview and the fully specified technical version.
Heh. I make a comment about unclear/inexplicit communication... using a metaphor that itself has little specific concrete meaning. And you write this reply. "Oh no, I have been deconstructed!", I say, laughing, in the voice of the Wicked Witch of the West as she is melting....
Or maybe you were really asking. That's the thing about the Internet. Only the FBI knows you're a dog, and nobody knows what the dog really means.
But if it really was a question, gms7777's sibling reply is good.
From the introduction: "The only background required of the reader is a good knowledge of advanced calculus and linear algebra. If the reader has seen basic mathematical analysis (e.g., norms, convergence, elementary topology), and basic probability theory, he or she should be able to follow every argument and discussion in the book."
It's a graduate-level course. If that paragraph is arcane, the book is probably a few courses in your future.
A someone who followed courses in num op, I can say that yes, indeed, the math concepts are rather basic and not that hard to learn. BUT you have to be at ease with mathematical reasoning because many of the proofs are not that easy to understand, they involve quite a lot of small insights here and there. Nothing really hard, but your brain will definitely have to work to understand these.
So yeah, the necessary concepts to study that course are not much but you have to have a strong habit of thinking in maths to apply them. And that habit comes with a lot of practice...
All this is is mathematical notation version of a data type system. Its telling you the problem search space is represented as vector<n> x, the optimization problem is 'real f(vector<n> x)', the problem constraint is vector<m> b, and the meaning of b is we are going to test 'for i=0; i<m; i++' { is f(x)<=b[i] }
The mathematical entities are straightforward, and the important things to remember in this definitions package are conventions and names: x is the variable vector and its cardinality is n, minimization of a function called f0 is the objective, fi<=bi are the m constraints, and they are numbered starting from 1 to exclude "f0" and avoid the use of a different letter for the objective function.
I must clarify, the function to optimize is f0(x), and the constraints are a set of functions fi that should each be <= bi. You have used a single function for the constraints in your pseudocode.
Getting tripped up by this is like seeing Cyrillic letters in an intro book on Russian and believing those are the hard parts of learning Russian.
As others have said: it's actually fairly straightforward and clear. That paragraph states exactly what they mean by "a mathematical optimization problem".
A simpler version that you might have seen in Calculus for Jocks is one where you are supposed to find the optimum of a single-variate function with no further constraints -- just find the largest or smallest value. You would look for places where the tangent is horizontal (by differentiating) + you would look at the "ends" (by looking at limits).
"Here the vector x..." tells us that this cost function is a bit more complicated: you are not looking for a single input value but a vector of many input values.
"subject to fi(x) <= bi" tells us that there are constraints and what language the authors will use to describe those constraints.
It's really all fairly standard and simple. The hard parts come later.
It can be a bit intimidating but try to read it not as something you need to understand as in a truth revealed but rather as something you need to understand as in these are the terms we’ll be using to represent what we explain in text. I.e. f0 for objective function, fi for constraints etc. Many otherwise approachable books have this wall of conventions in the beginning + a set of proofs that underpin the key thesis. Try to speed through these sections, picking up as many symbols, findings, as you can , but not everything, and when you reach the actual essence you can go back and revisit. The good thing is that this wall in the beginning becomes very common between books the more you read on a topic. In a sense, if you are a programmer, think of this as the schema representation for the actual message to come.
>
Boy, and that's just the opening paragraph of the introduction.
> Exactly what arcane requisite elite math precursors are necessary to even remotely understand this?
You don't have a degree in some STEM area (or even economics)? To me, this rather looks like the kind of basic mathematical notation that you learn and get become perfectly used to in the first two years of your degree course.
Its saying a very simple thing with somewhat convoluted language. First of all for full generality they are treating functions of Rn -> R (if the output is also a vector then it becomes a different type of problem, I believe its called multimodal optimisation).
And the f1, f2, ... fm are simply the (inequality) constraints that all candidate solutions must satisfy.
For example, you might want to maximize the volume of something you want to build from sheet metal, then f0 could be the expression for the volume of body and the constraint could be one inequality ie area(x) <= your_maximum_budget_for_sheet_metal etc
If one reads a few serious introductory math books, starting from set theory, etc., one would get used to this “math” language and find it natural, precise, and effective.
Also, really important to refer to Boyd's prequel book, which is much simpler and can be read by anyone here without any prior background: https://web.stanford.edu/~boyd/vmls
It has tons of code and exercises in Julia and Python. Start here, excellent to get a taste of linear algebra and its applications.
Huh? This is quite straightforward and is simply establishing what terms are used for describing the problem. The problem formulation itself seems to be the same as in any lower level course on optimization that is taught to regular masters students, so it is expected that anyone reading the paper will already know it.
I'm probably the most junior math person here. I got to Advanced Algebra and then Calc 1 and realized I peaked in Advanced Algebra. That being said, judging from just the paragraph one might need an understanding of number theory (sets to be exact), vectors, ...
I always tend to get tripped up in the terminology and the symbols.
Boy, and that's just the opening paragraph of the introduction.
Exactly what arcane requisite elite math precursors are necessary to even remotely understand this?