Optimize the Max Min over two sets for the given function

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!

[Rik]

Wasn't this question previously closed for being unclear? Because it is still unclear to me what your question is. Editing the question in a non-meaningfull way just to trigger the reopen is useless, because you will still not get an answer.

[Torsten]

I think you want a and b to be convex combinations of the rows of A and B, don't you ?

Otherwise simply use this code:

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)

[Torsten]

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]

Thanks Torsten, but In this case, you will always get:

min_B =

Inf

Inf

Inf

max_A =

Inf

Please try it.

[Torsten]

Code edited.

Answer 1

[Torsten]

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]

Please provide the code.

Answer 2

[Bruno Luong]

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)

[Torsten]

From the problem formualtion I think that a and b are meant to be convex combinations of the row vectors, not the row vectors themselves. But maybe the result will come out the same - did not think about it in depth.

[Bruno Luong]

But maybe the result will come out the same - did not think about it in depth.

I'm sure both problems are different.

[Sultan]

Bruno Luong Thanks, but it gives the following error.

"Array dimensions must match for binary array op".

Please provide correct one code.

Regards

[Bruno Luong]

This code is correct when using with lastest version of MATLAB. If you ask nicely than you did, then I might give you a work around for older MATLAB version (previous to R2016b).

[Sultan]

Thanks Bruno Luong, I am using R2015a. Plase provide code.

[Bruno Luong]

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]

Comment by Sultan written in a flag:

Right. Please see the original question.

[Bruno Luong]

This answer is not longer valid since Sutan has editted and modified his question.

Answer 3

[Bruno Luong]

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)

[Sultan]

Dear Bruno Luong,

If you can post the code, it will help me a lot.

[Image Analyst]

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]

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

,

.

Please help me in providing the complete program.

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]

Comment re-posted as question here.

Answer 4

[Sultan]

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;
%A = load('matrixA');
%B = load('matrixB');
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.

[Bruno Luong]

See my edited post

[Sultan]

Thanks Bruno Luong, but your solution and my solution for the same matrices are different. I have tested my code for my research problem and it gives the correct answer. In particular to the matrices A and B, I have optimal value 1.414213580747754 and the solution is [0.999808799573007;1.912004269929178e-04] while the optimal value fmax by your code is 1.3339e-08 and solution [0.999860236409300, 6.47702605291456e-05].

Thank you guys!!

[Bruno Luong]

" while the optimal value fmax by your code is 1.3339e-08"

Nope. My code give

fmax = 2

obained for j=2 and

>> lambda(:,2)

ans =

   0.999926050006163
   0.000073949993837

for inputs:

A = [1 2 4; 2 3 4; 1 2 3];
B = [1 2 4; 1 2 3];

I can't check your code since you only posted a pseudo-code.

[Torsten]

Not pseudocode, but CVX:

http://cvxr.com/cvx/

[Bruno Luong]

@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]

Bruno Luong you are right.

Thanks!