Asked by Sultan
on 16 Dec 2018

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!

Answer by Torsten
on 19 Dec 2018

Edited by 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.

Answer by Bruno Luong
on 21 Dec 2018

Edited by 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)

Bruno Luong
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)

Bruno Luong
on 23 Dec 2018

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

Sign in to comment.

Answer by Bruno Luong
on 23 Dec 2018

Edited by 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)

Image Analyst
on 26 Dec 2018

Sultan
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

,

.

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.

Sign in to comment.

Answer by Sultan
on 15 Jan 2019

Edited by Sultan
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;

%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);

Torsten
on 16 Jan 2019

Not pseudocode, but CVX:

http://cvxr.com/cvx/

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

Sultan
on 18 Jan 2019

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 5 Comments

## Rik (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#comment_652262

## Torsten (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#comment_652729

## Torsten (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#comment_653233

## Sultan (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#comment_653306

## Torsten (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#comment_656128

Sign in to comment.