Optimize the Max Min over two sets for the given function

3 次查看（过去 30 天）

显示更早的评论

Sultan 2018-12-16

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function

评论： 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 个评论
显示 3更早的评论隐藏 3更早的评论

Sultan 2018-12-21

编辑：Sultan 2018-12-21

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

min_B =

Inf

max_A =

Inf

Please try it.

Torsten 2019-1-2

Code edited.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（4 个）

Torsten 2018-12-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#answer_353094

编辑：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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Sultan 2018-12-21

Please provide the code.

请先登录，再进行评论。

Bruno Luong 2018-12-21

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#answer_353469

编辑：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 个评论
显示 6更早的评论隐藏 6更早的评论

Rik 2018-12-23

Comment by Sultan written in a flag:

Right. Please see the original question.

Bruno Luong 2018-12-23

编辑：Bruno Luong 2018-12-23

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

请先登录，再进行评论。

Bruno Luong 2018-12-23

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#answer_353649

编辑：Bruno Luong 2019-1-15

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)

4 个评论
显示 2更早的评论隐藏 2更早的评论

Sultan 2018-12-26

编辑：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

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 2018-12-26

Comment re-posted as question here.

请先登录，再进行评论。

Sultan 2019-1-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435987-optimize-the-max-min-over-two-sets-for-the-given-function#answer_356524

编辑：Sultan 2019-1-16

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