Converting a maximizing problem into a minimizing program using linprog

Hi guys,

i have a question about the function linprog.

I want to use this function, and according to the matlab database the function linprog can be applied so that it solves for:

In my case i want to maximize the vector x. Can Anyone help me and tell me how to convert it? What effects will it have on the A matrix and the upper / lower bounds?

Thanks a lot!

Kev

Answer 1

[Bruno Luong]

You just need to reverse the sign of f. Don't touch the rest.

[Kevin Wang]

Hi Bruno,

also, if i have as my maximizing problem: A*x smaller or equal to b?

If i reverse the sign of f, do i leave everything else unchanged?

Thanks!

[Bruno Luong]

No. I repeat : "don't touch the rest." leaving anything else unchanged, including A*x <= b

[Kevin Wang]

wait, i leave everything else unchanged even if i want to go from

max x for A*x smaller/equal to b to min x for A*x smaller/equal to b?

just reverse the f function?

[Bruno Luong]

"max x for A*x smaller/equal to b"

What is "max x ..."?

I speak about solving this

x = argmax f'*x
such that A*x <= b, Aeq*x = beq, lo <= x <= hi

which is equivalent to solving this

x = argmin (-f)'*x
such that A*x <= b, Aeq*x = beq, lo <= x <= hi

Thus my recommendation "reverse the sign of f. Don't touch the rest", which requires a single change (Method 1).

• f => -f

You could also do this if you like

y = argmin f'*y
such that (-A)*y <= b, (-Aeq)*y = beq, -hi <= y <= -lo
x = -y

but it clearly much more modifications (4+1):

• A => (-A)
• Aeq => (-Aeq)
• lo => -hi
• hi => -lo
• x => -y

Or if you reuse the same variable name x for x/y (Method 2)

x = argmin f'*x
such that (-A)*y <= b, (-Aeq)*y = beq, -hi <= y <= -lo
x = -x

The modifications (4+1) are:

• A => (-A)
• Aeq => (-Aeq)
• lo => -hi
• hi => -lo
• x => -x

[Bruno Luong]

For a canonic form of LP

x = argmax f'*x
such that A*x <= b, x >= 0

(Method 3) It is also possible to solve the DUAL problem (2)

y = argmin b'*x
such that (-A'*y) <= -f, y >= 0

and finally x is retrieved as

x = Lagrange multiplier of (2)

• f => b
• A = -A'
• b => -f
• x => Lagrange multiplier of (2)

Example:

f = [6; 14; 13];
A = [0.5 2 1;
       1 2 4];
b = [24; 60];

% Primal argmax, method 1
x = linprog(-f, A, b, [], [], zeros(size(f)), [])

% Primal argmax, method 2
x = linprog(f, -A, b, [], [], [], zeros(size(f)));
x = -x

% Dual formulation, method 3
[y, ~, ~, ~, lambda] = linprog(b, -A', -f, [], [], zeros(size(b)), []);
x = lambda.ineqlin

It is also possible formulate the dual for general case, but it gets a bit messy.

[Kevin Wang]

Great,

thanks a lot for your help!

Answer 2

[Alan Stevens]

Minimize -x. The maximum of x will then be the negative of this.

[Kevin Wang]

do you mean that f = -1 then?

How will my constraint vector b be in the minimizing case?

Thanks!

[Alan Stevens]

Unfortunately, I don't have linprog available to check, but have a look at https://uk.mathworks.com/help/optim/examples/maximize-long-term-investments-using-linear-programming.html where there is a maximizing problem that uses linprog.