Piecewise Linear (Affine) Programming

Somdeb Lahiri Somdeb Lahiri
September 27, 2016 AI & Machine Learning
In his paper entitled “Linear Programming and the Simplex Method”, (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: “It is concerned with the problem of maximizing or minimizing a linear function whose variables are required to satisfy a system of linear constraints, a constraint being a linear equation or (weak linear: author’s insertion) inequality”. The application of linear programming in solving problems faced by human society or social groups (which includes industry) is vast and listing them could comprise several volumes.
David Gale continues to say that almost all linear programming applications can be formulated using the framework of activity analysis, which for our purposes may be described as follows. There is a given set of goods. “There is also a set of processes or activities which are specified by amounts of the goods consumed as inputs or produced as outputs”, 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 may be carried out at any non-negative level xj. 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 is a cj which gives the net profit if activity aj is operated at unit level. Given ‘m’ goods and ‘n’ 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 c1x1 + c2x2+…+ cnxn. A compact representation of the above maximization problem is the following.
Given an m- column vector b, an n-row vector cT (where T denotes the transpose of a vector; thus c is an n-column vector) and an m×n matrix A, find an n-column vector x so as to
maximize cTx
subject to Ax ≤ b, x ≥ 0.              (LP)
Here the ith element of activity aj (which is the jth column of A) denoted aij is the amount of good i required as input if activity aj is operated at unit level.
Operations 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 about the use of LP is because constant marginal costs, marginal profits and marginal output might be a hasty over simplification of reality.  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.
A more realistic and non-smooth version of the activity analysis model would assume piecewise affine and concave profit functions (to allow for market imperfections, i.e. imperfect competition) and piecewise affine and convex joint cost (input requirement) functions. It is customary (though imprecise) to refer to piecewise affine functions as piecewise linear functions.
In what follows, let R denote the set of real numbers and let Rn denote the set of all ordered n-tuples of real numbers.
A function f:Rn→R  is said to be piecewise affine and concave (PA concave) if there exists a positive integer K and K (n+1)- row vectors <(ckT, dk)| k= 1,…, K> such that for all x in Rn, f(x) = min{ckTx + dk| k= 1,…, K}.
A function g:Rn→R is said to be piecewise affine and concave (PA convex) if there exists a positive integer K and K (n+1)- row vectors <(akT, qk)| k= 1,…, K> such that for all x in Rn, g(x) = max{akTx + qk| k= 1,…, K}.
A piecewise affine programming problem (PAP) is a maximization problem of the following form.
maximize f(x)
subject to gi(x) ≤ bi, i = 1,…,m, x ≥ 0.               (PAP)
Here f is a PA-concave function, each gi is PA-convex and each bi is a real number.
Suppose f(x) = min{ckTx + dk| k= 1,…, K} and for each iÎ{1,…,m} there exists a positive integer K(i) and K(i) (n+1)- row vectors <(Ai(k)T,qi(k))|k = 1,…,K(i)> such that gi(x) = max{Ai(k)Tx +qi(k)| k= 1,…, K(i)}.
If we were to interpret a PAP as an extension of the LP framework based on activity analysis, then f would represent a profit function, each gi the cost or input requirement function of the ith good, and each bi as the initial endowment of good i.
The nice result that puts a PAP squarely within the domain of LP is the following.
Proposition x* solves PAP if and only there exists a real number u* such that x*, u* solve the following LP problem.
maximize u
subject to ckTx + dk ≥ u,  k= 1,…, K, Ai(k)Tx +qi(k) ≤ bi, k = 1,…,K(i), i = 1,…,m, x ≥ 0.
The implication of the above proposition is that solving a PAP is no 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.
  • Experfy Insights

    Top articles, research, podcasts, webinars and more delivered to you monthly.

  • Somdeb Lahiri

    Tags
    Predictive Analytics
    © 2021, Experfy Inc. All rights reserved.
    Leave a Comment
    Next Post
    K Means Clustering in Text Data

    K Means Clustering in Text Data

    Leave a Reply Cancel reply

    Your email address will not be published. Required fields are marked *

    More in AI & Machine Learning
    AI & Machine Learning,Future of Work
    AI’s Role in the Future of Work

    Artificial intelligence is shaping the future of work around the world in virtually every field. The role AI will play in employment in the years ahead is dynamic and collaborative. Rather than eliminating jobs altogether, AI will augment the capabilities and resources of employees and businesses, allowing them to do more with less. In more

    5 MINUTES READ Continue Reading »
    AI & Machine Learning
    How Can AI Help Improve Legal Services Delivery?

    Everybody is discussing Artificial Intelligence (AI) and machine learning, and some legal professionals are already leveraging these technological capabilities.  AI is not the future expectation; it is the present reality.  Aside from law, AI is widely used in various fields such as transportation and manufacturing, education, employment, defense, health care, business intelligence, robotics, and so

    5 MINUTES READ Continue Reading »
    AI & Machine Learning
    5 AI Applications Changing the Energy Industry

    The energy industry faces some significant challenges, but AI applications could help. Increasing demand, population expansion, and climate change necessitate creative solutions that could fundamentally alter how businesses generate and utilize electricity. Industry researchers looking for ways to solve these problems have turned to data and new data-processing technology. Artificial intelligence, in particular — and

    3 MINUTES READ Continue Reading »

    About Us

    Incubated in Harvard Innovation Lab, Experfy specializes in pipelining and deploying the world's best AI and engineering talent at breakneck speed, with exceptional focus on quality and compliance. Enterprises and governments also leverage our award-winning SaaS platform to build their own customized future of work solutions such as talent clouds.

    Join Us At

    Contact Us

    1700 West Park Drive, Suite 190
    Westborough, MA 01581

    Email: [email protected]

    Toll Free: (844) EXPERFY or
    (844) 397-3739

    © 2025, Experfy Inc. All rights reserved.