Optimize the Max Min over two sets for the given function
2 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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 Kommentare
Antworten (4)
Torsten
am 19 Dez. 2018
Bearbeitet: Torsten
am 19 Dez. 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
am 21 Dez. 2018
Bearbeitet: Bruno Luong
am 21 Dez. 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 Kommentare
Bruno Luong
am 23 Dez. 2018
Bearbeitet: Bruno Luong
am 23 Dez. 2018
This answer is not longer valid since Sutan has editted and modified his question.
Bruno Luong
am 23 Dez. 2018
Bearbeitet: Bruno Luong
am 15 Jan. 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 Kommentare
Sultan
am 15 Jan. 2019
Bearbeitet: Sultan
am 16 Jan. 2019
6 Kommentare
Bruno Luong
am 16 Jan. 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
Siehe auch
Kategorien
Mehr zu Get Started with Optimization Toolbox finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!