I'm stupid. How to cast in linear programming setting?

[Styhn]

Either Matlab is trolling me or I'm having a massive brainfailure. Here's a homework question I'm trying to work out:

We have 100 dollars that want to invest in gold. There are four suppliers with prizes 1/2, 1, 1/7 and 1/4 dollar per gram of gold. We want to maximize the amount of gold. Formulate this as an LP and solve.

A straightforward question, whose purpose is do get us acquainted with LP software. I'm using SeDuMi (http://sedumi.ie.lehigh.edu/)and yalmip (http://users.isy.liu.se/johanl/yalmip/), along with this function:

Code: Select all

function [opt,vecX]=standardLux(c,A,b)



 n = length(c);
 x = sdpvar(n,1);
%
%
 F = set( A*x <= b );
 F = F + set( x(:) >= 0 );
%
 obj = -c'*x;
%
%
 diagnostics = solvesdp(F,obj,sdpsettings('showprogress',1,'solver','sedumi'))
%
 opt=double(obj);
 vecX=double(x);
 vecX(((abs(vecX)<1e-5))) = 0;

end

My input is as follows:

Code: Select all

A =

    0.5000    1.0000    0.1429    0.2500

b =

   100

c =

    -1
    -1
    -1
    -1

x=standardLux(A',b,c)


The output of which is

Code: Select all

+ Solver chosen : SeDuMi-1.1
+ Processing objective h(x)
+ Processing F(x)
+ Calling SeDuMi-1.1
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, theta = 0.250, beta = 0.500
eqs m = 4, order n = 9, dim = 9, blocks = 1
nnz(A) = 8 + 0, nnz(ADA) = 4, nnz(L) = 4
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.12E+003 0.000
  1 : -5.52E-002 2.72E+001 0.000 0.0243 0.9900 0.9900   0.98  1  1  5.0E+000
  2 : -1.85E-001 8.84E+000 0.000 0.3246 0.9000 0.9000  -0.60  1  1  1.6E+001
  3 : -7.62E-001 4.23E-001 0.000 0.0478 0.9900 0.9900  -1.16  1  1  7.8E+001
  4 : -1.75E+000 5.59E-005 0.126 0.0001 0.9999 0.9999  -1.01  1  1 
Dual infeasible, primal improving direction found.
iter seconds  |Ax|    [Ay]_+     |x|       |y|
  4      0.0  7.1e-015  2.0e-021  5.0e+001  2.6e-023

Detailed timing (sec)
   Pre          IPM          Post
0.000E+000    1.560E-002    0.000E+000   
Max-norms: ||b||=1, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.

diagnostics =

    yalmiptime: 0.0260
    solvertime: 0.0140
          info: 'Infeasible problem (SeDuMi-1.1)'
       problem: 1
        dimacs: [0.5773 0 0 0.5000 -0.5000 -0.5000]

x =

   -0.0189


which is clearly not right. Could someone see where I went wrong? I apologize for the wall of code.

[mfb]

As the mathematical solution is obvious (buy 700 gram from the 1/7-supplier (, sell the 700 gram for ~40000 dollars, buy ~300kg of gold, repeat)) it looks like the interpretation of your code and output requires some knowledge about Matlab, I think this belongs to the coding section?
Agreed, moved. -phlip

[Styhn]

Thanks for moving, mods.

[eta oin shrdlu]

I'm not familiar with these packages, but I see what I think are two problems with your code. First, you're calling

Code: Select all

x=standardLux(A',b,c)

but your function parameters are defined to be taken in a different order as

Code: Select all

function [opt,vecX]=standardLux(c,A,b)

which is undoubtedly confusing things a lot--the return value isn't even the right dimension. (You should be able to debug this in Matlab by either setting a breakpoint in the function or printing out the local variables' values so you can check that they are what you think they ought to be.) Second, solvesdp is trying to minimize obj, and you want to maximize sum(x)=[1 1 1 1]*x. You have tried to fix this twice, once by setting c=[-1 -1 -1 -1]' and then again by setting obj=-c'*x; I think these two signs will cancel out and give you the trivial minimum solution instead of the one you're looking for.

[Styhn]

Ah I see, thank you very much!