How to get fminimax work for both max and min objectives?

4 次查看（过去 30 天）

显示更早的评论

Jing 2021-1-5

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/709178-how-to-get-fminimax-work-for-both-max-and-min-objectives

编辑： Matt J 2021-1-9

The objectives is as following:

And the constraints are:

norm(w)<=1

b>0

0<=q<=C and e*q=1, where C is a constant value and e is all ones vector.

What is the right way to right the objective function and constraint for this problem?

3 个评论
显示 1更早的评论隐藏 1更早的评论

Jing 2021-1-7

Thanks a lot! I think your solution works!

Bruno Luong 2021-1-7

编辑：Bruno Luong 2021-1-7

Glad it works.

I put in separate answer so it can be accepted.

请先登录，再进行评论。

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

回答（4 个）

Bruno Luong 2021-1-7

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/709178-how-to-get-fminimax-work-for-both-max-and-min-objectives#answer_592693

I wouldn't use fminmax.

I would use linprog to maximize q as subfunction, and fmincon to minimize z,b.

Beside you should transform b > 0 to b >= epsilon.

9 个评论
显示 7更早的评论隐藏 7更早的评论

Matt J 2021-1-7

I think the fix is just

n=min(m, ceil( 1/C));

Bruno Luong 2021-1-7

编辑：Bruno Luong 2021-1-7

Thanks, now I complete the outer loop

n = 10;
x = randn(n,1);
y = randn(n,1);
C = 0.2;
if n*C < 1
    error('C is too small')
end
W0 = ones(n,1)/sqrt(n);
b0 = 0;
Z0 = [W0; b0];
epsilon = 0;
LB = [-inf(n,1); epsilon];
UB = [];
opts = optimoptions(@fmincon, 'Algorithm','Active-set');
[Z,f] = fmincon(@(Z) innermax(y(:), Z(1:n), x(:), Z(n+1), C), ...
   Z0, ...
    [], [], [], [], ...
    LB, UB, ...
    @(Z) deal(norm(Z(1:n),2)^2-1, []), ...
    opts);
f
W = Z(1:n)
b = Z(n+1)

With Matt's inner optimization

function [fmax, qOptimal] = innermax(y,w,X,b,C)
    [z, p ] = sort( - y.'.*(w.'*X-b.') ,'descend');
    C=min(C,1);
    
    m=numel(z);
    n=min(ceil( 1/C),m); 
    q=[repelem(C,n-1), 1-C*(n-1), zeros(1,m-n)];    
    fmax=dot(q,z);
    
    if nargout>1  
       % Simplified by Bruno
      qOptimal(p)=q;
    end
    
end

请先登录，再进行评论。

Matt J 2021-1-7

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/709178-how-to-get-fminimax-work-for-both-max-and-min-objectives#answer_592828

You could reformulate the problem as follows and solve the whole thing with fmincon. No non-differentiable minimizations required.

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

Bruno Luong 2021-1-7

编辑：Bruno Luong 2021-1-7

But it won't minimizes the inner max.

It provides q is not the one that is argmax, it just find something else, a vector that satisfies the constraint and reduces V. This is not min/max.

I implement it and it does not give the same result.

Matt J 2021-1-8

编辑：Matt J 2021-1-9

OK, well I think the modification that gets it to work is to construct the matrix of vertices V using uniqueperms,

   C=min(C,1);
    
    m=numel(z);
    n=min(m, ceil( 1/C));
 
    V=uniqueperms(  [repelem(C,n-1), 1-C*(n-1), zeros(1,m-n)] );

The rows of V are the extreme points of the set Q and we know the inner max must be achieved at one of these points. Now reformulate as follows:

The solution for q_i will be the row V(i,:) which attains,

The above line of solution of course assumes, of course, that the number of. permutations needed to construct V is manageable, which is, admittedly, a drawback to the approach.

请先登录，再进行评论。