MATLAB Answers

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

조회 수: 114(최근 30일)
Jing
Jing 5 Jan 2021
편집: Matt J 9 Jan 2021
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

Bruno Luong
Bruno Luong 6 Jan 2021
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
Jing 7 Jan 2021
Thanks a lot! I think your solution works!
Bruno Luong
Bruno Luong 7 Jan 2021
Glad it works.
I put in separate answer so it can be accepted.

댓글을 달려면 로그인하십시오.

답변(4개)

Bruno Luong
Bruno Luong 7 Jan 2021
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

표시 이전 댓글 수: 6
Bruno Luong
Bruno Luong 7 Jan 2021
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
Matt J 7 Jan 2021
I think the fix is just
n=min(m, ceil( 1/C));
Bruno Luong
Bruno Luong 7 Jan 2021
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
Matt J 7 Jan 2021
You could reformulate the problem as follows and solve the whole thing with fmincon. No non-differentiable minimizations required.

  댓글 수: 4

표시 이전 댓글 수: 1
Matt J
Matt J 7 Jan 2021
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
Bruno Luong 7 Jan 2021
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
Matt J 8 Jan 2021
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.

댓글을 달려면 로그인하십시오.


Matt J
Matt J 5 Jan 2021
편집: Matt J 7 Jan 2021
For C>=1 (EDIT), your problem can be rewritten
so you should just follow the fminimax documentation with

  댓글 수: 5

표시 이전 댓글 수: 2
Bruno Luong
Bruno Luong 6 Jan 2021
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
Matt J 6 Jan 2021
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
Matt J 6 Jan 2021
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.

댓글을 달려면 로그인하십시오.


Matt J
Matt J 8 Jan 2021
편집: Matt J 8 Jan 2021
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.

  댓글 수: 0

댓글을 달려면 로그인하십시오.

Community Treasure Hunt

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

Start Hunting!

Translated by