Optimize the Max Min over two sets for the given function
2 views (last 30 days)
Show older comments
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 Comments
Answers (4)
Torsten
on 19 Dec 2018
Edited: Torsten
on 19 Dec 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
on 21 Dec 2018
Edited: Bruno Luong
on 21 Dec 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 Comments
Bruno Luong
on 23 Dec 2018
Edited: Bruno Luong
on 23 Dec 2018
This answer is not longer valid since Sutan has editted and modified his question.
Bruno Luong
on 23 Dec 2018
Edited: Bruno Luong
on 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 Comments
Sultan
on 15 Jan 2019
Edited: Sultan
on 16 Jan 2019
6 Comments
Bruno Luong
on 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
See Also
Categories
Find more on Get Started with Optimization Toolbox in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!