Re: solving set of inequalities

[Petr Korviny]

On 25.1.2010 19:31, John W. Eaton wrote:
> On 25-Jan-2010, Petr Korviny wrote:
>
> | As I mentioned above,
>
> Above?  Your new text appeared as the first thing in the message I
> received, and there was nothing above it.
Sorry, I was writing about text in my earlier posts, my fault.

>   I need to find out solution of set of linear inequalities
> | (to get values of variables x1,x2,x3,...) or to get an information of
> | nonexistence any such solution.
> |
> | At this picture:
> | http://suzelly.opf.slu.cz/~korviny/zzz/octave/excel_solver.png
> | you can see utilization of Excel's Solver add-in I used to get solution of
> | viewed set. "alpha" variable is always set to a number<0;1>, so set of
> | inequalities is linear.
>
> Then why does your problem statement show you maximizing alpha and
> that it has bounds of [0, 1]?

On that picture is statement of complex task and thank you for rewriting this 
example
with "sqp" function, I certainly use it.

In fact I try to divide that problem to two parts/steps:
step 1) set variable alpha to constant number (for example to 0.75)
step 2) then solve set of linear inequalities, which I get with this alpha

According to solution from step 2 I'll change alpha to another number with new
iteration method (step 1) and go to step 2 again. I'll do that until solution 
exists for
that alpha.

My goal is to try to find and optimize this "new iteration method" in step 1, 
because the
inequalities have some specifics characteristics and we think, me (a 
programmer) and my colleague
(a mathematician), that the "new iteration method" could be faster than common 
used methods.

Basic statement is really nonlinear:
Max alpha
s.t.
(1+alpha)*x2 <= x1 <= (3-alpha) * x2
(2+alpha)*x3 <= x1 <= (5-2*alpha) * x3
2*x3 <= x2 <= (3-alpha) * x3
0 <= alpha <= 1, x1+x2+x3=1, x1 >= 0, x2 >= 0, x3 >= 0

If I set alpha=0 (for simplicity) I get this set of linear inequalities:
x2 <= x1
x1 <= 3*x2
2*x3 <= x1
x1 <= 5*x3
2*x3 <= x2
x2 <= 3*x3
x1+x2+x3=1, x1 >= 0, x2 >= 0, x3 >= 0

And to find some method/function(s), how to solve this with Octave, I'm trying.
I should give you all that information at first probably.

Thank you for your time.

> | Finding a solution for this set of linear inequalities is only one step in the
> | process. I'd like to write it all as a script in Octave.
> |
> | All tips and suggestions are welcome.  Thanks
>
> The problem you show in the image is not just a "set of linear
> inequalities".  It is a nonlinear optimization problem.  With some
> rearrangement to get your problem statement into the form accepted by
> Octave's sqp function, I obtain
>
>    x =
>
>       0.538461538452721
>       0.307692307698186
>       0.153846153849093
>       0.749999999995322
>
>    obj = -0.749999999995322
>
> I included alpha as a fourth decision variable, and since you are
> maximizing alpha but sqp minimizes it's objective function, I used
> -alpha as the objective for sqp.  Here's teh code I used:
>
>    x = [1; 1; 1; 1];
>
>    function retval = phi (x)
>      alpha = x(4);
>      retval = -alpha;
>    endfunction
>
>    function retval = g (x)
>      retval = x(1) + x(2) + x(3) - 1;
>    endfunction
>
>    function retval = h (x)
>      alpha = x(4);
>      retval = [x(1)-(1+alpha)*x(2);
>                (3-alpha)*x(2)-x(1);
>                x(1)-(2+alpha)*x(3);
>                (5-2*alpha)*x(3)-x(1);
>                x(2)-2*x(3);
>                (3-alpha)*x(3)-x(2)];
>    endfunction
>
>    lb = [0; 0; 0; 0];
>    ub = [1; realmax; realmax; realmax];
>
>    [x, obj] = sqp (x, @phi, @g, @h, lb, ub)
>
> jwe

Petr