MATLAB Answers

0

How to maximize system of linear equations?

Asked by Clarisha Nijman on 26 Nov 2018
Latest activity Commented on by Clarisha Nijman on 1 Dec 2018
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?

  4 Comments

Show 1 older comment
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
on 26 Nov 2018
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.
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?

Sign in to comment.

1 Answer

Answer by Matt J
on 26 Nov 2018
Edited by Matt J
on 27 Nov 2018
 Accepted Answer

You can use fminimax, e.g.,
fminimax(@(x) A*x, x0)

  6 Comments

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
on 30 Nov 2018
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);
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)

Sign in to comment.