Optimize the Max Min over two sets for the given function

2 次查看（过去 30 天）
Sultan
Sultan 2018-12-16
评论： 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更早的评论
Sultan
Sultan 2018-12-21
编辑：Sultan 2018-12-21
Thanks Torsten, but In this case, you will always get:
min_B =
Inf
Inf
Inf
max_A =
Inf
Please try it.

请先登录，再进行评论。

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

回答（4 个）

Torsten
Torsten 2018-12-19
编辑：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.
Bruno Luong
Bruno Luong 2018-12-21
编辑：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更早的评论
Rik
Rik 2018-12-23
Comment by Sultan written in a flag:
Right. Please see the original question.
Bruno Luong
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
Bruno Luong 2018-12-23
编辑：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更早的评论
Sultan
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.

请先登录，再进行评论。

Sultan
Sultan 2019-1-15
编辑：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);
We can also use lsqlin. Thanks everyone for helping me.
  6 个评论
显示 4更早的评论
Bruno Luong
Bruno Luong 2019-1-16
@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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by