Optimize the Max Min over two sets for the given function
2 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(4 个)
Torsten
2018-12-19
编辑:Torsten
2018-12-19
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
2018-12-21
编辑:Bruno Luong
2018-12-21
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 个评论
Bruno Luong
2018-12-23
编辑:Bruno Luong
2018-12-23
This answer is not longer valid since Sutan has editted and modified his question.
Bruno Luong
2018-12-23
编辑:Bruno Luong
2019-1-15
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 个评论
Sultan
2019-1-15
编辑:Sultan
2019-1-16
6 个评论
Bruno Luong
2019-1-16
@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
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Get Started with Optimization Toolbox 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!