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

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?

[Bruno Luong]

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.

[Jing]

Thanks a lot! I think your solution works!

[Bruno Luong]

Glad it works.

I put in separate answer so it can be accepted.

Answer 1

[Bruno Luong]

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.

[Matt J]

I am somewhat surprised that it would work without some care on the fmincon algorithm selection at least. The objective fed to fmincon is a non-differentiable, piecewise linear function.

[Bruno Luong]

In my experience FMINCON (especially with active-set algorithm) can handle somewhat if the function is only differentiable piecewise (and continuous). Afterall ii handles that when the activeset changes (collision between constraints).

We already discuss it on another thread when I use FMINCON to deal with smallest eigen-value of some matrix, which is not differentiable. You are reluctant but the numerical show it works just fine.

[Matt J]

Yes, I remember, but I thought we established that the optimoptions had to be selected in a careful manner.

[Bruno Luong]

Right, for the proble we have discussed usage of active-set algo seems to be necessary

opts = optimoptions(@fmincon, 'Algorithm','Active-set', ...)
[x ...] = fmincon(..., opts);

[Matt J]

In any case, there is no need to use linprog for the inner maximization. The inner max is analytically computable:

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(m, ceil( 1/C));
 
    q=[repelem(C,n-1), 1-C*(n-1), zeros(1,m-n)];
    
    fmax=dot(q,z);
    
    if nargout>1
      ip=1:m; ip(p)=ip;  %unpermute  
      qOptimal=q(ip);
    end
    
end

[Bruno Luong]

Excellent (not check thought). I know inner solution can be directly computed just too lazy to derive.

[Bruno Luong]

Matt: your code does seem not robust for all configurations. You should deal the cases such as

n > m;

1-C*(n-1) > C

[Matt J]

I think the fix is just

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

[Bruno Luong]

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

Answer 2

[Matt J]

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

[Bruno Luong]

I guess there is typo of missing qi in the first consraint(s) <= r.

IMO this formulation is NOT equivalent to min/max.

[Matt J]

No, the constraint is written as intended. To see that it is equivalent to the original problem, take any arbitrary satisfying . Multiplying the first constraint by and summing over i leads to

Since was arbitrary this also implies,

[Bruno Luong]

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]

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.

Answer 3

[Matt J]

For C>=1 (EDIT), your problem can be rewritten

so you should just follow the fminimax documentation with

[Jing]

But in this way, q is not solved. In the problem, both xi and yi are known, but not the qi. It's actually minmax f(q,w,b), rather than f(w,b).

[Matt J]

Once you have found the optimal w and b, the optimal q will be q_j=1 where

and q_k=0 for all other k.

[Bruno Luong]

I don't undestand your method Matt.

where do you enforce the constraints

0<=q<=C ?

And nothing warranty that argmax over a discrete set is argmax of the continuous q.

[Matt J]

I was imagining that C=1. If Q is just the space of convex combination weights, then

Also, if C>1, then clearly we can pretend that C=1 because the second constraint implies, with the positivity of q, that the q_i are all less than 1.

[Matt J]

If 0.5<=C<1, it seems to me that the extension of the above is,

where and is the second largest z component.

You could use ga() to do the outer minimization.

Answer 4

[Matt J]

Using Sion's minimax theorem, the min and the max can be interchanged to give a much simpler problem,

The solution to the min over w is trivial from Cauchy-Schwartz,

The min over b is only finitely achieved (with b=0) when . Incorporating the above, the outer maximization over q reduces to,

which can be solved easily with lsqlin or quadprog.