{"id":497,"date":"2016-09-27T16:30:27","date_gmt":"2016-09-27T16:30:27","guid":{"rendered":"http:\/\/kusuaks7\/?p=102"},"modified":"2025-02-26T09:00:21","modified_gmt":"2025-02-26T09:00:21","slug":"piecewise-linear-affine-programming","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/ai-ml\/piecewise-linear-affine-programming\/","title":{"rendered":"Piecewise Linear (Affine) Programming"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tIn his paper entitled \u201cLinear Programming and the Simplex Method\u201d, (Notices of the AMS (March 2007), Volume 54, No:3, pages 364-369), David Gale defines the subject of linear programming in the following manner: \u201cIt is concerned with the problem of maximizing or minimizing a linear function whose variables are required to satisfy a system of linear constraints<\/em>, a constraint being a linear equation or (weak linear: author\u2019s insertion)<\/em> inequality\u201d. The application of linear programming in solving problems faced by human society or social groups (which includes industry) is vast\u00a0and listing them could comprise several volumes.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tDavid Gale continues to say that almost all linear programming applications can be formulated\u00a0using the framework of activity analysis, which for our purposes may be described as follows. There is a given set of goods<\/em>. \u201cThere is also a set of processes or activities<\/em> which are specified by amounts of the goods consumed<\/em> as inputs<\/em> or produced<\/em> as outputs<\/em>\u201d, when the processes are operated at unit level. An activity is represented by a column vector “a”; positive entries of the column vector denote inputs and negative entries denote outputs, when the activity is operated at unit level. Any activity aj<\/sup> may be carried out at any non-negative level xj<\/sup>. There is an initial endowment column vector denoted by b, which specifies the right hand side of the constraints. The initial endowment of a good may be positive (as in the case of natural, human or other resources), negative (as in the case of clean air versus pollution, which is a bad) or zero. Associated with each activity aj<\/sup> is a cj<\/sub> which gives the net profit if activity aj<\/sup> is operated at unit level. Given \u2018m\u2019 goods and \u2018n\u2019 activities, the linear programming problem (LP) is to find activity levels given by a n-vector x that satisfies the constraints and maximizes the total profit c1<\/sub>x1<\/sup> + c2<\/sub>x2<\/sup>+\u2026+ cn<\/sub>xn<\/sup>. A compact representation of the above maximization problem is the following.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nGiven an m- column vector b, an n-row vector cT<\/sup> (where T denotes the transpose of a vector; thus c is an n-column vector) and an m\u00d7n matrix A, find an n-column vector x so as to\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tmaximize cT<\/sup>x\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tsubject to Ax \u2264 b, x \u2265 0.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (LP)\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tHere the ith<\/sup> element of activity aj<\/sup> (which is the jth<\/sup> column of A) denoted aij<\/sub> is the amount of good i required as input if activity aj<\/sup> is operated at unit level.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tOperations research, or management science as it is sometimes referred to, is for most purposes little more than theoretical and applied linear programming, although smooth non-linear functions are invoked for the theory and applications of non-linear programming. Most successful applications of operations research have taken place in industry. However in spite of its initial success and popularity in economics (particularly economic theory), the main reason for people to be hesitant\u00a0about the use of LP is because constant marginal costs, marginal profits and marginal output might be a hasty over simplification of reality.\u00a0 Thus, although smooth cost, smooth production and smooth utility functions were even more counterfactual from any reasonable standpoint, greater faith was reposed on models of rational economic choice that used smooth objective and\/or constraint functions, than on LP models.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nA more realistic and non-smooth version of the activity analysis model would assume piecewise affine and concave<\/em> profit functions (to allow for market imperfections, i.e. imperfect competition) and piecewise affine and convex<\/em> joint cost (input requirement) functions. It is customary (though imprecise) to refer to piecewise affine functions as piecewise linear functions.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tIn what follows, let R denote the set of real numbers and let\u00a0Rn<\/sup> denote the set of all ordered n-tuples of real numbers.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tA function f:Rn<\/sup>\u2192R\u00a0 is said to be piecewise affine and concave<\/em> (PA concave<\/strong>) if there exists a positive integer K and K (n+1)- row vectors <(ck<\/sub>T<\/sup>, dk<\/sub>)| k= 1,\u2026, K> such that for all x in Rn<\/sup>, f(x) = min{ck<\/sub>T<\/sup>x + dk<\/sub>| k= 1,\u2026, K}.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tA function g:Rn<\/sup>\u2192R is said to be piecewise affine and concave<\/em> (PA convex<\/strong>) if there exists a positive integer K and K (n+1)- row vectors <(ak<\/sub>T<\/sup>, qk<\/sub>)| k= 1,\u2026, K> such that for all x in Rn<\/sup>, g(x) = max{ak<\/sub>T<\/sup>x + qk<\/sub>| k= 1,\u2026, K}.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tA piecewise affine programming problem<\/em> (PAP<\/strong>) is a maximization problem of the following form.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tmaximize f(x)\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tsubject to gi<\/sub>(x) \u2264 bi<\/sub>, i = 1,\u2026,m, x \u2265 0.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (PAP)\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tHere f is a PA-concave function, each gi<\/sub> is PA-convex and each bi<\/sub> is a real number.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tSuppose f(x) = min{ck<\/sub>T<\/sup>x + dk<\/sub>| k= 1,\u2026, K} and for each i\u00ce{1,\u2026,m} there exists a positive integer K(i) and K(i) (n+1)- row vectors <(Ai<\/sub>(k)T<\/sup>,qi<\/sub>(k))|k = 1,\u2026,K(i)> such that gi<\/sub>(x) = max{Ai<\/sub>(k)T<\/sup>x +qi<\/sub>(k)| k= 1,\u2026, K(i)}.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tIf we were\u00a0to interpret a PAP as an extension of the LP framework based on activity analysis, then\u00a0f would represent a profit function, each gi<\/sub> the cost or input requirement function of the ith<\/sup> good, and each bi<\/sub> as the initial endowment of good i.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tThe nice result that puts a PAP squarely within the domain\u00a0of LP is the following.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tProposition <\/strong>x*<\/sup> solves PAP if and only there exists a real number u*<\/sup> such that x*<\/sup>, u*<\/sup> solve the following LP problem.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tmaximize u\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tsubject to ck<\/sub>T<\/sup>x + dk <\/sub>\u2265 u,\u00a0 k= 1,\u2026, K, Ai<\/sub>(k)T<\/sup>x +qi<\/sub>(k) \u2264 bi<\/sub>, k = 1,\u2026,K(i), i = 1,\u2026,m, x \u2265 0.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tThe implication of the above proposition is that solving a PAP is no<\/em> more or less difficult than solving an LP. Thus algorithms (or software) that solve an LP can be used to solve a PAP, once the latter has been properly formulated. However economic theory is also concerned with mathematical representation of both qualitative and quantitative properties and most such results in the case of smooth objective functions make use of duality theory. In order to apply duality theory to a PAP and obtain meaningful results, the PAP itself needs to be in a manageable form. To begin with, it may be prudent to assume that each piecewise affine function has at most two affine segments and see how far the analysis proceeds.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Linear programming is a mathematical problem solving technique widely used in various industries to optimize operations and is widely recognized as one of the core concepts of Operations Research. In this post, Professor Lahiri gives a summary of the technicalities of this method. <\/p>\n","protected":false},"author":511,"featured_media":2816,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"content-type":"","footnotes":""},"categories":[183],"tags":[140],"ppma_author":[1609],"class_list":["post-497","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ai-ml","tag-predictive-analytics"],"authors":[{"term_id":1609,"user_id":511,"is_guest":0,"slug":"somdeb-lahiri","display_name":"Somdeb Lahiri","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","user_url":"","last_name":"Lahiri","first_name":"Somdeb","job_title":"","description":"Professor Lahiri is an economist and most of his work is in microeconomics and mathematical methods for business and economics. He has also done research in game theory, choice theory, and optimization theory and has taught various classes in these areas."}],"_links":{"self":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/497","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/users\/511"}],"replies":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/comments?post=497"}],"version-history":[{"count":4,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/497\/revisions"}],"predecessor-version":[{"id":37301,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/497\/revisions\/37301"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media\/2816"}],"wp:attachment":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media?parent=497"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/categories?post=497"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/tags?post=497"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=497"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}