Linprog and Max Function

Hi,

I have a question concerning the linprog-Programm in Matlab. I am trying to implement the objective function:

f(d) = Df*d + max(0, g + Dg*d)

where Df, g and Dg are just numbers. Now I am trying to use linprog to minimize this function in respect to d. However, I dont know how to implement the maximum function. I also tries to rewrite the maximum function by using the absolute function and using other methods. However my main problem is that g is suppose to be a constant that is not multiplied by d. All the methods I tried resulted in g being multiplied by d. If you can give me a hand on this, it would be great!

Thank you!

[Austin]

Hi,

thank you for your great answer. I am actually trying to describe a Penalty Method using the SLP Approach. Thanks to your help, I was able to implement the algorithm. Sorry, but I am quite a newbie in Matlab.

If you can give me a hand on one more issue, I will be very grateful:

Now I am trying to further extend my objective function which uses the absolute function (it describes the equality constraints in my Penalty Approach). Can I somehow convey to a linprog format?

f(d) = Df*d + max(0, g + Dg*d) + |h + Dh*d|, where h is also a constant array.

Thank you for your help!

Austin

Answer 1

[Teja Muppirala]

Notice that f(d) = Df*d + max(0, g + Dg*d) + abs(h + Dh*d)

is the same as

f(d) = Df*d + max(0, g + Dg*d) + max(h + Dh*d, -h-Dh*d)

and you should be able to solve it in a similar way as before.

1. Minimize f(d) = (Df+Dh)*d and add h to the result

2. Minimize f(d) = (Df-Dh)*d and subtract h from the result

3. Minimize f(d) = (Df+Dg+Dh)*d and add (g+h) to the result

4. Minimize f(d) = (Df+Dg-Dh)*d and add (g-h) to the result

5. Your answer is the maximum of the above 4 results.

[Austin]

hi,

thanks for your answer. just for clarity: didnt you forget the minimization of f(d) = Df*d and f(d) = (Df+Dg)*d?

Austin

Answer 2

[Titus Edelhofer]

Hi,

if Df, g and Dg are "just numbers", why would you use linprog? The function is piecwise linear, so there are only three points that come into question for realizing the minimum (the breakpoint of the max and the left and right boundary) ...?

Regarding linprog, I doubt you will get rid of the constant "g".

Titus

Answer 3

[Teja Muppirala]

Assuming by "just numbers" you mean "(constant) arrays", you can solve it by solving two linear programming problems.

Step 1. Solve using only Df.

[x{1},f(1)] = linprog(Df,A,b);

Step 2. Solve using Df+Dg, and add g to the result.

[x{2},f(2)] = linprog(Df+Dg,A,b);
f(2) = f(2)+g;

Step 3. The answer to your problem is the maximum of Step 1 and Step 2.

[f_answer,idx] = max(f);
x_answer = x{idx};

You can compare this to what you would get if you used FMINCON instead (though fmincon does not always converges to the right answer).

A = [eye(3); -eye(3)];
b = [1;1;1;1;1;1];
Df = randn(1,3);
Dg = randn(1,3);
g = randn;

F = @(X) Df*X + max(0,g+Dg*X);

[xo,fo] = fmincon(F,[0;0;0],A,b);

[x{1},f(1)] = linprog(Df,A,b);
[x{2},f(2)] = linprog(Df+Dg,A,b);
f(2) = f(2)+g;
[f_answer,idx] = max(f);
x_answer = x{idx};

% Compare with the result from FMINCON
[x_answer xo]
[f_answer fo]

[Austin]

thank you for your answer. you have helped me a lot!