How to maximize system of linear equations?

Hello,

Given:

A=[4 3; -1 7; 5 9; 2 4];

x=[x1;x2];

b=[b1; b2; b3; b4];

How can I maximize the linear system of equations: Ax=b?

[Matt J]

What does it mean to "maximize" a set of equations? Are they constraints in a linear program? If so, what is the objective function? An example with a particular selection of b1,...,b4 may help us to understand.

[Clarisha Nijman]

There are 4 linear equations( in fact level lines (niveaulijnen in dutch) in this example:

4x+3y=b1

-x+7y=b2

5x+9y=b3

2x+4y=b4,

constraints: x,y,b1,b2,b3 and b4 non-negative

Now we should find the optimal values for x and y associated with the maximum possible value of b1, b2, b3 and b4. It is an optimization problem.

[Matt J]

associated with the maximum possible value of b1, b2, b3 and b4

So the idea is to make all b1..b4 as large as possible? Then clearly x=0 and y=Inf are optimal in the example you've shown. They result in b1=b2=b3=b4=Inf.

More generally, though, you cannot simultaneously maximize the right hand side elements b, because they co-depend on the same variables.

[Clarisha Nijman]

Okay, I understand, maybe this example is too simple. In my case I have to minimize the maximal entry of a linear combination of 20 vectors with each 1001 entries. So I was wondering how to find the maximal/optimal entry of such a linear combination of vectors. A linear combination of vectors is a vector; in the simplified example I started with, it is the b-vector on the right hand side. The left hand side is the linear combination. So I need a code/matlab function that can help me to find the maximal entry.

min max (ax+by+cz+......+dv)

where x, y, z and v are vectors and a, b, c and d non-negative scalars. Minmization has as argument the scalars a,b,,c,d. And for simplicity we minimize the maximal entry of the linear combination.

My question is how to find this maximal entry. Is there a matlab function/code I can use?

Answer 1

[Matt J]

You can use fminimax, e.g.,

fminimax(@(x) A*x, x0)

[Clarisha Nijman]

Thanks a lot Matt,

I will study this function!! It seems to be the code I am looking for

[Matt J]

Clarisha's comment moved here:

Hello,

I have been studying this subject, composed a code, but can not get the code running. Can you give me some feedback?

Given data set C, with 4 columns:

0.0038 0.0038 0.0038 0.0038

0.0037 0.0037 0.0037 0.0037

0.0036 0.0036 0.0036 0.0036

0.0034 0.0034 0.0035 0.0035

0.0033 0.0033 0.0034 0.0034

0.0032 0.0032 0.0033 0.0033

0.0031 0.0031 0.0032 0.0033

0.0029 0.0029 0.0031 0.0031

0.0028 0.0028 0.0029 0.0028

0.0027 0.0027 0.0024 0.0023

%
%The less equal constraint matrix
A1=C(:,2:end);
A2=-C(:,2:end);
Aleq=[A1;A2];

%The less equal RHS
bleq=[C(:,1)  -C(:,1)];

Aeq=ones(3,1);
beq=1;

lb=zeros(3,1);
ub=[];

%initial guess
x0=0.1*rand(3,1);

%Defining the objective function
F=zeros(3,1);%pre allocate vector for objective function
function F = myfunc(C)
    for i=1:size(C,1)
        F(i)=C(i,2)*x(2)+C(i,3)*x(3)+C(i,4)*x(4);
    end       
end

[OptArgum, optimalVal] = fminimax(@myfunc,x0,Aleq,bleq,Aeq,beq,lb,ub);  

[Matt J]

Try this,

Cs=C(:,2:4);

[OptArgum, optimalVal] = fminimax(@(x) Cs*x,x0,Aleq,bleq(:),Aeq.',beq,lb,ub);  

[Clarisha Nijman]

The last line of the code:

"[OptArgum, optimalVal] = fminimax(@(x) Cs*x,x0,Aleq,bleq(:),Aeq.',beq,lb,ub); "

is underlined (red), and the comment says:

"Function definition in a script must appear at the end of the file. Move statements to before the function definitions".

[Matt J]

Runs fine for me. Here is my complete implementation.

C=[ 0.0038    0.0038    0.0038    0.0038
    0.0037    0.0037    0.0037    0.0037
    0.0036    0.0036    0.0036    0.0036
    0.0034    0.0034    0.0035    0.0035
    0.0033    0.0033    0.0034    0.0034
    0.0032    0.0032    0.0033    0.0033
    0.0031    0.0031    0.0032    0.0033
    0.0029    0.0029    0.0031    0.0031
    0.0028    0.0028    0.0029    0.0028
    0.0027    0.0027    0.0024    0.0023];


A1=C(:,2:end);
A2=-C(:,2:end);
Aleq=[A1;A2];
%The less equal RHS
bleq=[C(:,1)  -C(:,1)];
Aeq=ones(3,1);
beq=1;
lb=zeros(3,1);
ub=[];
%initial guess
x0=0.1*rand(3,1);
%Defining the objective function

Cs=C(:,2:4);

[OptArgum, optimalVal] = fminimax(@(x) Cs*x,x0,Aleq,bleq(:),Aeq.',beq,lb,ub);  

[Clarisha Nijman]

Ok I see,

Two questions more;

Can you give me some explanation about the first argument of the fminmax code: @(x) Cs*x

Can you give me some explanation about the output? Should I change the tolerance of choose a larger rand initial guess? The output says:

Converged to an infeasible point.

fminimax stopped because the predicted change in the objective function

is less than the default value of the function tolerance but constraints

are not satisfied to within the default value of the constraint tolerance.

<stopping criteria details>

Optimization stopped because the predicted change in the objective function, 0.000000e+00,

is less than options.FunctionTolerance = 1.000000e-06, but the maximum constraint violation,

1.093094e+00, exceeds options.ConstraintTolerance = 1.000000e-06.

Optimization Metric Options

abs(steplength*directional derivative) = 0.00e+00 FunctionTolerance = 1e-06 (default)

max(constraint violation) = 1.09e+00 ConstraintTolerance = 1e-06 (default)