{"id":313,"date":"2007-02-17T12:46:04","date_gmt":"2007-02-17T12:46:04","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/02\/17\/basics-optimization\/"},"modified":"2007-02-17T12:46:04","modified_gmt":"2007-02-17T12:46:04","slug":"basics-optimization","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/02\/17\/basics-optimization\/","title":{"rendered":"Basics: Optimization"},"content":{"rendered":"

Yet another term that we frequently hear, but which is often not properly understood, is the concept of optimization<\/em>. What is optimization? And how does it work?<\/p>\n

The idea of optimization is quite simple. You have some complex situation, where
\nsome variable of interest (called the target<\/em>) is based on a complex
\nrelationship with some other variables. Optimization is the process of trying to find
\nan assignment of values to the other variables (called parameters<\/em>) that produces a maximum<\/em> or minimum<\/em> value of the target variable, called
\nthe optimum<\/em> or optimal value<\/em> <\/p>\n

The practice<\/em> of optimization is quite a bit harder. It depends greatly
\non the relationships between the other variables. The general process of finding
\nan optimum is called programming<\/em> – not like programming a computer; the term predates the invention of computers. <\/p>\n

<\/p>\n

To make things a bit more formal, we can describe an optimization program in terms of geometry. An optimization problem can be described using a function
\nfrom a space S to a real number. The space S is some subset of a euclidean space ℜn<\/sup> for some N. So we have a function, f:S→ℜ, (that is, a function from the space S to a real number) which we call
\nthe objective function<\/em> if we’re looking for a maximum, or the cost function<\/em> if we’re looking for a minimum.. Each point in S is called a potential<\/em> or feasible<\/em> solution for the objective function. The optimum<\/em> of the objective function f is the point p in S where f(p) is at a maximum that is, p∈S: (∀x∈S:f(p)≥f(x). (If f is a cost function, jut replace the “≥” in the previous with “≤”.) <\/p>\n

The space S is generally defined by a set of constraints<\/em>, which are relationships between the variables\/dimensions of S. If all of the constraints are
\nlinear, and the objective\/cost function is linear in terms of all of the variables,
\nthen the solution process is called linear programming<\/em>. Linear programming problem where all of the values of parameters in the solution must be integers is called an integer programming<\/em>.<\/p>\n

General linear programming – where the values of the variables in the solution can be any real number – is a very tractable problem, which can be solved very efficiently. Integer linear programming, on the other hand, is NP-hard<\/em> – which is a very fancy way of saying that we have absolutely no clue of how to produce an optimal solution in a reasonable amount of time.<\/p>\n

Linear programming turns out to be an extremely useful technique, which solves a large number of very common problems. Most problems of scheduling and resource distribution are ultimately reducible to linear programming. There’s an entire field of applied mathematical research called operations research (OR)<\/em> which is devoted to optimization problems in general, and most work in OR is focused on finding solutions to linear programming problems, or to finding ways of characterizing different problems in terms of the simplest possible linear programming problem.<\/p>\n

There’s also a form of optimization problem of particular interest to computer scientists. Given an optimization problem that has the property that finding the optimal solution involves combining the optimal solutions to multiple overlapping
\nsubproblems, the solution technique is called dynamic programming<\/em>. Dynamic programming works by computing and remembering the solutions to the subproblems, and then finding a way of combining a selection of the solutions to the subproblems to
\ncreate a solution to the full problem.<\/p>\n","protected":false},"excerpt":{"rendered":"

Yet another term that we frequently hear, but which is often not properly understood, is the concept of optimization. What is optimization? And how does it work? The idea of optimization is quite simple. You have some complex situation, where some variable of interest (called the target) is based on a complex relationship with some […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[74],"tags":[],"class_list":["post-313","post","type-post","status-publish","format-standard","hentry","category-basics"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-53","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/313","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=313"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/313\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=313"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}