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

### Sultan (view profile)

on 16 Dec 2018
Latest activity Commented on by Sultan

### Sultan (view profile)

on 18 Jan 2019
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!

Torsten

### Torsten (view profile)

on 21 Dec 2018
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

### Sultan (view profile)

on 21 Dec 2018
Thanks Torsten, but In this case, you will always get:
min_B =
Inf
Inf
Inf
max_A =
Inf
Torsten

on 2 Jan 2019
Code edited.

### Torsten (view profile)

on 19 Dec 2018
Edited by Torsten

### Torsten (view profile)

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.

Sultan

### Sultan (view profile)

on 21 Dec 2018
Please provide the code.

Answer by Bruno Luong

### Bruno Luong (view profile)

on 21 Dec 2018
Edited by Bruno Luong

### Bruno Luong (view profile)

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)

Bruno Luong

### Bruno Luong (view profile)

on 21 Dec 2018
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

### Rik (view profile)

on 23 Dec 2018
Comment by Sultan written in a flag:
Right. Please see the original question.
Bruno Luong

### Bruno Luong (view profile)

on 23 Dec 2018
This answer is not longer valid since Sutan has editted and modified his question.

Answer by Bruno Luong

### Bruno Luong (view profile)

on 23 Dec 2018
Edited by Bruno Luong

### Bruno Luong (view profile)

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)

Show 1 older comment
Image Analyst

### Image Analyst (view profile)

on 26 Dec 2018
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

### Sultan (view profile)

on 26 Dec 2018
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

### Rik (view profile)

on 26 Dec 2018
Comment re-posted as question here.

on 15 Jan 2019
Edited by Sultan

### Sultan (view profile)

on 16 Jan 2019

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.

Torsten

### Torsten (view profile)

on 16 Jan 2019
Not pseudocode, but CVX:
http://cvxr.com/cvx/
Bruno Luong

### Bruno Luong (view profile)

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
Sultan

### Sultan (view profile)

on 18 Jan 2019
Bruno Luong you are right.
Thanks!