# Optimize the Max Min over two sets for the given function

26 ビュー (過去 30 日間)
Sultan 2018 年 12 月 16 日
コメント済み: Sultan 2019 年 1 月 18 日
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 .
I want to solve the following problem.
Since is convex, and convexity is also preserved under minimization, so the function
is convex. Moreover, because every point can be represented as a convex combination of the set of extreme points of A,
which is attained at . Thus, we can compute the square root of
.
I hope the question is clear.
Thanks!

#### 5 件のコメント

Torsten 2018 年 12 月 21 日
Just use the code from above ; it will throw sqrt(max min ||a-b||^2):
m=3;
k=2;
A=[2, 3; 1, 4; 3,1];
B=[1,2; 2,4];
min_B = Inf*ones(m,1)
for i = 1:m
a = A(i,:);
for j = 1:k
b = B(k,:);
min_B(i) = min(min_B(i),norm(a-b)^2);
end
end
max_A = max(min_B);
max_A = sqrt(max_A)
Sultan 2018 年 12 月 21 日
Thanks Torsten, but In this case, you will always get:
min_B =
Inf
Inf
Inf
max_A =
Inf
Torsten 2019 年 1 月 2 日
Code edited.

サインイン to comment.

### 回答 (4 件)

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.

#### 1 件のコメント

Sultan 2018 年 12 月 21 日

サインイン to comment.

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 月 21 日
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(bsxfun(@minus,AA,BB).^2,3);
f2 = max(min(d2,[],2),[],1)
Rik 2018 年 12 月 23 日
Comment by Sultan written in a flag:
Right. Please see the original question.
Bruno Luong 2018 年 12 月 23 日
This answer is not longer valid since Sutan has editted and modified his question.

サインイン to comment.

Bruno Luong 2018 年 12 月 23 日

For ant row a_j, the inner equation
argmin_lambda || sum (lambda_i * b_i - a_j) ||^2
lambda >= 0
sum(lambda_i) = 1
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 件のコメント

Image Analyst 2018 年 12 月 26 日
Well he may be reluctant to since you edited your prior question which invalidated his answer (according to him). Would you promise not to do that again?
Sultan 2018 年 12 月 26 日
I am very sorry everyone, for changing the question. Please have a look of the following one.
I have only two matrices A=[1,2 4; 2, 3, 4; 1, 2,3] and B=[1,2 4; 1, 2,3] in my hands. I want to solve the following problem.
where ,
subject to
,
.
Once it is computed, then I can use ''for loop'' for computing min for all rows of A and then max.
Thanks for sparing time.
Rik 2018 年 12 月 26 日
Comment re-posted as question here.

サインイン to comment.

Sultan 2019 年 1 月 15 日

Is it correct code for the above problem? In place of λ, I have used x.
A = [1 2 4; 2 3 4; 1 2 3]; B = [1 2 4; 1 2 3];
%Given: A; B;
n = size(B,1);
C = B';
D = ones(1,n);
for i = 1:size(A,1)
cvx_begin
variable x(n)
minimize( norm(A(i,:)' - C*x, 2))
subject to
D * x == 1
0 <= x <= 1
cvx_end
optimalValue(i) = cvx_optval^2;
X(:,i) = x;
end
maximumValue = max(optimalValue);
We can also use lsqlin. Thanks everyone for helping me.

#### 6 件のコメント

Torsten 2019 年 1 月 16 日
Not pseudocode, but CVX:
http://cvxr.com/cvx/
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
Sultan 2019 年 1 月 18 日
Bruno Luong you are right.
Thanks!

サインイン to comment.

サインイン してこの質問に回答します。

Translated by