使用AMPL求解圆内最大矩形时各求解器结果异常问题咨询

问题背景 #

给定直径60单位的圆，理论上其内接最大矩形面积为1800单位。编写的AMPL模型如下：

param diameter := 60;

param radius := diameter / 2;

var tlX; # top left x of the rectangle
var tlY; # top left y of the rectangle 
subject to tlInside: sqrt(tlX*tlX + tlY*tlY) < radius;  # make sure its inside the circle 

var brX; # bottom right x of the rect
var brY; # bottom right y of the rectangle
subject to brInside: sqrt(brX*brX + brY*brY) <= radius; # make sure its inside the circle 

var xDiff =  brX - tlX;
var yDiff = brY - tlY;

maximize Area: xDiff * yDiff;

使用不同求解器求解时得到异常结果：

• Gurobi求解得到面积为0；
• HiGHS求解得到面积为12.3873，远未达最优值；
• CBC求解得到面积为1820.51，接近理论最优值但变量违反约束；
  其余求解器甚至无法给出解。

核心原因分析 #

1. 非凸优化问题的求解局限性 #

目标函数xDiff * yDiff是二次非线性函数，约束中的sqrt(tlX²+tlY²) < radius属于非线性非凸约束。这类非凸优化问题对求解器的适配性要求极高：

• Gurobi默认专注于凸优化场景，遇到非凸目标时容易收敛到无意义的局部极值点（比如矩形退化为点或线，面积为0）；
• HiGHS主打线性与凸优化求解，在非凸场景下只能找到较差的局部最优解；
• CBC作为开源线性规划求解器，对非线性问题的处理能力有限，无法准确把控非线性约束的边界，导致返回的解违反约束。

2. 约束与变量定义的不合理性 #

• 左上顶点约束使用严格小于< radius，但最优解中矩形顶点必须恰好落在圆周上（内接矩形的顶点在圆边界），严格小于的约束直接排除了最优解所在的边界，迫使求解器在内部寻找次优解，甚至引发求解逻辑混乱；
• 模型未定义矩形的几何合理性约束：比如tlX < brX（左上x坐标小于右下x坐标）、tlY > brY（左上y坐标大于右下y坐标），这会导致xDiff或yDiff可能为负，面积计算失去实际意义，也是求解器返回异常解的诱因之一。

3. 变量冗余与对称性未利用 #

原模型定义了4个变量，但圆内接最大矩形具有中心对称性，最优解必然关于原点对称。完全可以简化变量定义（例如仅定义右上顶点坐标，推导其他顶点），减少变量与约束的复杂度，降低求解难度。

内容的提问来源于stack exchange，提问作者Rojer Vairs