Optimize the Max Min over two sets for the given function
2 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Hello Guys,
I have two matricis
and
whose rows represents the extreme points and all the rows of
are also the rows of
i.e.,
, and
. I want to compute the square root of
.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199145/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199146/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199147/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199148/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199149/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199150/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199151/image.png)
I want to solve the following problem.
Since
is convex, and convexity is also preserved under minimization, so the function
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199152/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199153/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199154/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199155/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199156/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199157/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199158/image.png)
which is attained at
. Thus, we can compute the square root of
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199159/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/199160/image.png)
I hope the question is clear.
Thanks!
5 comentarios
Respuestas (4)
Torsten
el 19 de Dic. de 2018
Editada: Torsten
el 19 de Dic. de 2018
max: eps
s.c.
[norm(a_j - sum_{i=1}^{i=k} lambda_i*b_i,2)]^2 >= eps (j=1,...,m)
sum_{i=1}^{i=k} lambda_i = 1
lambda_i >=0
where the a_j are the row vectors of the matrix A and the b_j are the row vectors of the matrix B.
Use "fmincon" to solve for the lambda_i and eps.
Or use "fminimax".
Best wishes
Torsten.
Bruno Luong
el 21 de Dic. de 2018
Editada: Bruno Luong
el 21 de Dic. de 2018
Not sure why this bla-bla about convex that makes your statement confusing. There is no continuous variable in the quantity f2 = max min | a-b |^2. It is straightforward calculation:
A=[2, 3; 1, 4; 3,1];
B=[1,2; 2,4];
n = size(A,2);
AA = reshape(A,[],1,n);
BB = reshape(B,1,[],n);
d2 = sum((AA-BB).^2,3);
f2 = max(min(d2,[],2),[],1)
8 comentarios
Bruno Luong
el 23 de Dic. de 2018
Editada: Bruno Luong
el 23 de Dic. de 2018
This answer is not longer valid since Sutan has editted and modified his question.
Bruno Luong
el 23 de Dic. de 2018
Editada: Bruno Luong
el 15 de En. de 2019
For ant row a_j, the inner equation
argmin_lambda || sum (lambda_i * b_i - a_j) ||^2
lambda >= 0
sum(lambda_i) = 1
can be solved using QUADPROG.
Then loop on j to find the max.
Example:
A = [1 2 4; 2 3 4; 1 2 3];
B = [1 2 4; 1 2 3];
[m,n] = size(A);
k = size(B,1);
H = B*B';
lb = zeros(1,k);
ub = inf(1,k);
f = nan(1,m);
lambda = nan(k,m);
Aeq = ones(1,k);
beq = 1;
C = -A*B';
for j=1:m
[x,fx] = quadprog(H, C(j,:), [], [], Aeq, beq, lb, ub);
lambda(:,j) = x;
f(j) = norm(B'*x - A(j,:)')^2; % == 2*fx + norm(A(j,:))^2
end
fmax = max(f)
4 comentarios
Sultan
el 15 de En. de 2019
Editada: Sultan
el 16 de En. de 2019
6 comentarios
Bruno Luong
el 16 de En. de 2019
@Sultan: "I have optimal value 1.414213580747754"
I suspect that is the 2-norm value at the solution and not the square of the norm as defined in your question.
@Torten: Not pseudocode, but CVX:
Thanks
Ver también
Categorías
Más información sobre Get Started with Optimization Toolbox en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!