Converting a maximizing problem into a minimizing program using linprog

2020 9 5
2 个回答
回答已采纳
更新时间：2020 9 7
6 次查看（30 天）

0 个投票

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

请先登录，再回答此问题。

 采纳的回答

Bruno Luong
Bruno Luong 2020-9-5

0 个投票

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

6 个评论
显示 4更早的评论 隐藏 4更早的评论

Kevin Wang
Kevin Wang 2020-9-5
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
Bruno Luong 2020-9-5
No. I repeat : "don't touch the rest." leaving anything else unchanged, including A*x <= b
Kevin Wang
Kevin Wang 2020-9-5
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
Bruno Luong 2020-9-6
编辑：Bruno Luong 2020-9-7
"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
Bruno Luong 2020-9-7
编辑：Bruno Luong 2020-9-7
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.

请先登录，再进行评论。

更多回答（1 个）

Alan Stevens
Alan Stevens 2020-9-5

0 个投票

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

2 个评论
显示 无 隐藏 无

Kevin Wang
Kevin Wang 2020-9-5
do you mean that f = -1 then?
How will my constraint vector b be in the minimizing case?
Thanks!
Alan Stevens
Alan Stevens 2020-9-5
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.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

产品

版本

R2019a

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by