Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Piecewise linear programming

  1. Mar 7, 2015 #1
    Dear Friends
    I have a question about linear programming. It would be great to have your comments or suggestions.
    Consider the followings
    \begin{equation}
    \\
    Y = [y_{1}, y_{2}, \cdots, y_{n}]
    \\
    G = [g_{1}, g_{2}, \cdots, g_{n}]
    \\
    \textbf{X} =
    \begin{pmatrix}
    0 & x_{1,2} & \cdots & x_{1,n} \\
    x_{2,1} & 0 & \cdots & x_{2,n} \\
    \vdots & \vdots & \ddots & \vdots \\
    x_{n,1} & x_{n,2} & \cdots & 0
    \end{pmatrix}
    \\
    \end{equation}
    ##\textbf{X}## is not symmetric. Here I show the ##i##th row of matrix ##\textbf{X}## by subscript ##(i,:)##, e.g., ##X_{(2,:)} = [x_{2,1}, 0, \cdots, x_{2,n}]## is the second row vector of matrix ##\textbf{X}## and subscript ##(:,i)## shows the ##i##th column vector.

    The problem is
    \begin{equation}
    \begin{aligned}
    & \min &Y = \sum_{j=1}^{n} y_{j}\\
    & \text{subject to}
    & X_{(i,:)} G^T \geq A \\
    && X_i \geq 0
    \end{aligned}
    \end{equation}
    in which ##i## is fixed, say ##i=2##, matrix ##G## is known, elements of ##\textbf{X}## are also known except the ##i##th row and ##X_{(i,:)}## should be found. Each of the elements in ##Y_i## is a function of the column vector in ##\textbf{X}## of the same index , i.e.,
    $$
    y_{j} = f(\textbf{X}(:,j))
    $$
    I googled and found that the function ##f## that I am working with is a piecewise linear function! Actually here the problem is not to find the minimum of a piecewise linear function, but to find the minimum of sum over multiple piecewise linear functions!
    Since I am totally new in the filed of linear programming I don't know how such a problem should be solved!
    Does anybody have any comments or know some references about how I could solve this?

    Thanks in advance.
     
  2. jcsd
  3. Mar 8, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    What does ##X_i \geq 0## mean? It does not fit to the other notation.

    As all but one element of X(:,j) is known, it is possible to introduce functions gj which cover those dependencies. Define ##Z=X_{i,:}## and ##Z_j=X_{i,j}##

    $$\text{Maximize}~ Y = \sum_{j=1}^{n} g_j(Z_j)$$
    with the constraint
    $$\sum_{j=1}^{n} Z_j G_j \geq A$$
    and maybe some other constraint I don't understand.

    Depending on how ugly f is, a usual maximization algorithm could work.
     
  4. Mar 8, 2015 #3
    Thank you mfb for your hint.
    I meant ##x_{i,j} \geq 0##.
    ##f## is a convex increasing piecewise linear function. I think it is not ugly that much :)
     
  5. Mar 8, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Oh great, then I would expect a single minimum without additional local minima. Every minimization algorithm should find that. If f is not decreasing, your constraint on the sum should always lead to equality, which means you can directly include it in the parameter space (for example, let one of the unknowns be fixed by all others via this condition).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook