Question

请高手帮我看一下我的matlab程序错在哪里了？ max(min{f1,f2,f3,f4,f5,f6,f7})

求7个目标函数的最小值的最大化问题：
f1 = 15 - x(1) - x(8);f2 = 15 - x(2) - x(9);f3 = 15 - x(3) - x(10);f4 = 15 - x(4) - x(11);f5 = 15 - x(5) - x(12);
f6 = 15 - x(6) - x(13);f7 = 15 - x(7) - x(14);
用fminmax，转化为：
F1 = x(1) + x(8) - 15...F7 = x(7) + x(14) -15;
线性约束条件为
x(1) + x(2) + x(3) + x(4) + x(5) + x(6) + x(7) = 28;x(8) + x(9) + x(10) + x(11) + x(12) + x(13) + x(14) = 28;
1=<x(i)<=7;
主程序如下：
function minmax()
x0 = [7,4,1,5,6,2,3,2,3,5,6,7,4,1];
A = [];
b = [];
Aeq = [1,1,1,1,1,1,1,0,0,0,0,0,0,0;0,0,0,0,0,0,0,1,1,1,1,1,1,1];
beq = [28;28];
xm = [1;1;1;1;1;1;1;1;1;1;1;1;1;1];
xM = [7;7;7;7;7;7;7;7;7;7;7;7;7;7];
options = optimset('MaxFunEvals',1500,'MaxIter',5000,'display','iter');
[x,y] = fminimax(@ffun,x0,A,b,Aeq,beq,xm,xM,@ghun,options);
save q x y
function f = ffun(x)
f = [ (x(1) + x(8) - 15);
(x(2) + x(9) - 15);
(x(3) + x(10) - 15);
(x(4) + x(11) - 15);
(x(5) + x(12) - 15);
(x(6) + x(13) - 15);
(x(7) + x(14) - 15)];
function [C,ceq] = ghun(x)
C = [];
V1 = x(1)^2 + x(2)^2 + x(3)^2 + x(4)^2 + x(5)^2 + x(6)^2 + x(7)^2 - 140;
V2 = x(8)^2 + x(9)^2 + x(10)^2 + x(11)^2 + x(12)^2 + x(13)^2 + x(14)^2 - 140;
V3 = x(1)^3 + x(2)^3 + x(3)^3 + x(4)^3 + x(5)^3 + x(6)^3 + x(7)^3 - 784;
V4 = x(8)^3 + x(9)^3 + x(10)^3 + x(11)^3 + x(12)^3 + x(13)^3 + x(14)^3 - 784;
V = [V1;V2;V3;V4];
ceq = V;
题目的本意是x(1)~x(7)和x(8)~x(14)是取任意1~7的数字且两两不等，因此在非线性约束中引入平方和项以及高次项之和使得最优解符合1~7整数。但是加到3次项的时候最优解虽然是非整数，但其满足其余条件，最小的最大值为-7，满足要求，但是当4次项加入时得到的解是错误的，不但不满足整数要求，最小的最大值也不为-7。
不知道怎么写这个程序，请高手来帮助下，谢谢啦！！！

Answer 1

有两点疑问：

1、为了保证整数解且两两不等而引入的非线性等式约束，为什么不从1次方开始（当然，经测试，似乎并无影响）？

2、非线性等式约束的第4次项加入时，为什么认为“得到的解是错误的”？就因为“不但不满足整数要求，最小的最大值也不为-7”吗？

这种原因好像有点说不过去：

（1）要满足整数解的要求，7个变量应该有7个方程的约束，你刚加了两个方程不满足整数解是很正常的；

（2）怎么知道最小的最大值就一定为-7呢？（另，我这里试过，加入第4项约束时，最小最大值的确还是-7）

 

帮你改写了一下非线性约束条件：

function [C,ceq] = ghun(x)
C = [];     
ceq = zeros(14,1);
for i=1:7
    ceq(2*i-1) = sum(x(1:7).^(i+1)) - sum((1:7).^(i+1));
    ceq(2*i) = sum(x(8:14).^(i+1)) - sum((1:7).^(i+1));
end

 

求解得到的结果是：

x =
  Columns 1 through 11
     7     4     1     5     6     2     3     2     3     5     6
  Columns 12 through 14
     7     4     1

y =
    -6
    -8
    -9
    -4
    -2
    -9
   -11

也就是说，最终优化的结果是-2（换用另外一种优化方法得到的结果相同）。

追问

你好！谢谢你关于此问题的解答，
(1)关于一次方的疑问：如你所知，fminmax分为线性约束和非线性约束，一次方应归为线性的，因此我在设置Aeq和beq的时候就已经给出；
(2)如你前面得到的最大最小值是为-7，而且当且仅当7个目标函数的值都为-7时成立，因此变动任何一个参数都会可能使得其中的一个目标函数的值变大。你得到的最终-2的结论有待商榷，或者是我有些地方理解错了。
请指正！

追答

1、我之前没注意到你的线性等式约束是这个含义。其实线性可以看成是非线性的一种特殊情况，也可以放在非线性约束条件中（当然，就算法而言，把线性约束条件当成非线性约束条件处理可能会导致计算量增加，但对于本例而言，感受不到有什么影响）。

2、最优值-2的确是有问题的。我觉得原因是初值选择不当导致的，fminimax并非全局优化的算法，很容易陷入局部最优，尤其是整数约束条件导致其可行解范围不连续，应该更容易陷入局部极值点。我尝试使用初值
x0 = [1:7 7:-1:1];
得到的最优解为-7，但这是否真的是最优解我也不敢妄下结论，只是偶然试到的。如果想有更大机会得到全局最优解，有可能要借助进化算法之类的全局优化方法才行。