10 views (last 30 days)

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

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

Bruno Luong
on 21 Dec 2018

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

Bruno Luong
on 23 Dec 2018

Edited: 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 15 Jan 2019

Edited: Sultan
on 16 Jan 2019

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

Opportunities for recent engineering grads.

Apply TodayFind the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 5 Comments

## 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

⋮## 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

## 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

⋮## 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

## 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

⋮## 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

## 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

⋮## 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

## 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

⋮## 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.