QuadraticOptimization

hbghlyj

reference.wolfram.com/language/ref/QuadraticOptimization.html
Minimize $2 x^2+20 y^2+6 x y+5 x$ subject to the constraint $-x+y\ge2$:

1. obj = 2 x^2 + 20 y^2 + 6 x y + 5 x;
2. res = QuadraticOptimization[obj, -x + y >= 2, {x, y}]

复制代码

$\{x \rightarrow-1.73214, y \rightarrow 0.267857\}$

The optimal point lies in a region defined by the constraints and where is smallest: Show[Plot3D[obj, {x, -2, 0}, {y, 0, 1}, Sequence[   RegionFunction -> Function[{x, y, z}, -x + y >= 2],    MeshFunctions -> {#3& }, Mesh -> 15,    BoundaryStyle -> Directive[Red, Thick], BoxRatios -> 1,    ImageSize -> Small]], Graphics3D[{Blue, PointSize[0.05], Point[{x, y, obj} /. res]}]] 复制代码

Minimize $x^2+y^2$ subject to the equality constraint $x+y=2$ and the inequality constraints $1 \leq y \leq 2$:

1. res = QuadraticOptimization[
2.   x^2 + y^2, {x + y == 2, 1 <= y <= 2}, {x, y}]

复制代码

$\{x \rightarrow 1 ., y \rightarrow 1.\}$

The optimal point lies where a level curve of $x^2+y^2$ is tangent to the equality constraint: Show[RegionPlot[Evaluate[x^2 + y^2 <= (x^2 + y^2 /. res)],   Sequence[{x, 1/2, 3/2}, {y, 1/2, 3/2}, Epilog -> {Blue, PointSize[0.04], Point[ ReplaceAll[{x, y}, res]]}]], ContourPlot[x + y == 2, {x, 0.5, 1.5}, {y, 0.5, 1.5},   ContourStyle -> Black]] 复制代码

Minimize $2 x^2+20 y^2+6 x y+5 x$ subject to the constraint $-x+y \geq 2, x \in \mathbb{Z}, y \in \mathbb{R}$ :

1. obj = 2 x^2 + 20 y^2 + 6 x y + 5 x;
2. res = QuadraticOptimization[
3.   obj, -x + y >= 2, {x \[Element] Integers, y \[Element] Reals}]

复制代码

$\{x \rightarrow-2, y \rightarrow 0.3\}$

hbghlyj

14.1 Quadratic Optimization: The Positive Definite Case

Proposition 14.2. Given a quadratic function \[ P(x)=\frac{1}{2} x^{\top} A x-x^{\top} b, \] if $A$ is symmetric positive definite, then $P(x)$ has a unique global minimum for the solution of the linear system $A x=b$. The minimum value of $P(x)$ is \[ P\left(A^{-1} b\right)=-\frac{1}{2} b^{\top} A^{-1} b \text {. } \]

目标函数非正定，所以QuadraticOptimization报錯：The objective function is not convex since the quadratic objective matrix is not positive semidefinite

kuing 发表于 2024-4-8 08:22
$\min((\alpha-1)\beta+(\beta-1)\gamma+(\gamma-1)\alpha)=?$必在端点处取最小值。

如果加上$\alpha^2+\beta^2+\gamma^2$就正定了：\[\mathop{\text{QuadraticOptimization}}\limits_{\alpha ,\beta ,\gamma }\left[\begin{array}{l}\alpha ^2+\beta ^2+\gamma ^2\\+(\alpha -1) \beta +(\beta -1) \gamma+ (\gamma -1)\alpha \end{array}\middle|\begin{array}{c}0\leq \alpha \leq 1\\0\leq \beta \leq 1\\0\leq \gamma \leq 1\\4 \alpha +\beta +3 \gamma =\frac{9}{2}\end{array}\right]\]
In[]:=QuadraticOptimization[α^2+β^2+γ^2+(α-1)β+(β-1)γ+(γ-1)α,0<=α<=1&&0<=β<=1&&0<=γ<=1&&4α+β+3γ==9/2,{α,β,γ}]
Out[]={α->0.749997,β->0.0000412172,γ->0.49999}

hbghlyj

hbghlyj 发表于 2024-4-8 16:11
如果加上$\alpha^2+\beta^2+\gamma^2$就正定了

产生一个问题：如果加上$k(\alpha^2+\beta^2+\gamma^2)$就正定了，$k$至少是多少？
$\left(\begin{array}{lll}
k & \frac{1}{2} & \frac{1}{2} \\
\frac{1}{2} & k & \frac{1}{2} \\
\frac{1}{2} & \frac{1}{2} & k
\end{array}\right)$的特征值为$\left\{\begin{array}{l}λ_1 = k + 1\\λ_2 =\frac12 (2 k - 1)\\λ_3 =\frac12 (2 k - 1)\end{array}\right.$令它们全为正，得$k>\frac12$.
例如取$k=\frac12+0.001$，加上$k(\alpha^2+\beta^2+\gamma^2)$就正定了：
PositiveDefiniteMatrixQ[{{1/2+0.001, 1/2, 1/2}, {1/2, 1/2+0.001, 1/2}, {1/2, 1/2, 1/2+0.001}}]

hbghlyj

kuing 发表于 2024-4-8 18:52
那你现在明白了没

明白了！$f(x)$具有全局最小值，当且仅当A是正定的👌

在第21页：

Proposition 14.5. If $A$ is a symmetric matrix, then the function \[ f(x)=\frac{1}{2} x^{\top} A x+x^{\top} b \] has a minimum value iff $A \succeq 0$ and $\left(I-A A^{+}\right) b=0$, in which case this minimum value is \[ p^*=-\frac{1}{2} b^{\top} A^{+} b . \] Furthermore, if $A=U^{\top} \Sigma U$ is an SVD of $A$, then the optimal value is achieved by all $x \in \mathbb{R}^n$ of the form \[ x=-A^{+} b+U^{\top}\left(\begin{array}{l} 0 \\ z \end{array}\right), \] for any $z \in \mathbb{R}^{n-r}$, where $r$ is the rank of $A$.

hbghlyj

kuing 发表于 2024-4-8 18:52
那你现在明白了没

明白了！
无约束的问题：$f(x)=\frac{1}{2} x^{\top} A x+x^{\top} b$
例如$f(α,β,γ)=α^2+β^2+γ^2+(α-1)β+(β-1)γ+(γ-1)α$，
取 $A=\left(\begin{array}{lll}
2 & 1 & 1 \\
1 & 2 & 1 \\
1 & 1 & 2
\end{array}\right),b=\pmatrix{1\\1\\1}$
最小值点：$x=A^{-1}b=$Inverse[{{2, 1, 1}, {1, 2, 1}, {1, 1, 2}}].{{1},{1},{1}}$=\pmatrix{1/4\\1/4\\1/4}$
线性约束问题：可以加$\lambda$化为无约束的问题：

第13页

We shall prove that our constrained minimization problem has a unique solution given by the system of linear equations \[ \begin{aligned} C^{-1} y+A \lambda & =b, \\ A^{\top} y & =f, \end{aligned} \] which can be written in matrix form as \[ \left(\begin{array}{cc} C^{-1} & A \\ A^{\top} & 0 \end{array}\right)\left(\begin{array}{l} y \\ \lambda \end{array}\right)=\left(\begin{array}{l} b \\ f \end{array}\right) . \]

例如$f(α,β,γ)=α^2+β^2+γ^2+(α-1)β+(β-1)γ+(γ-1)α$，线性约束$4\alpha+\beta+3\gamma=\dfrac{9}{2}$.
$\left(\begin{array}{l}
y \\
\lambda
\end{array}\right)=\left(\begin{array}{cc}
C^{-1} & A \\
A^{\top} & 0
\end{array}\right)^{-1}\left(\begin{array}{l}
b \\
f
\end{array}\right) =\left(\begin{array}{lll|l}
2 & 1 & 1 & 4 \\
1 & 2 & 1 & 1 \\
1 & 1 & 2 & 3 \\\hline
4 & 1 & 3 & 0
\end{array}\right)^{-1} \cdot\left(\begin{array}{l}
1 \\
1 \\
1 \\
\frac{9}{2}
\end{array}\right)=$Inverse[{{2,1,1,4},{1,2,1,1},{1,1,2,3},{4,1,3,0}}].{{1},{1},{1},{9/2}}$=\left(\begin{array}{c}
3/4\\
0 \\
1/2 \\
-1
\end{array}\right)$
最小值点$=\left(\begin{array}{c}
3/4\\
0 \\
1/2
\end{array}\right)$
和上面QuadraticOptimization的结果相符：

hbghlyj 发表于 2024-4-8 16:11
Out[]={α->0.749997,β->0.0000412172,γ->0.49999}

hbghlyj

kuing 发表于 2024-4-8 19:13
刚才分割主题时竟然产生了错乱，难道又是时差问题？

不是，是删帖的问题。

hbghlyj

kuing 发表于 2024-4-8 19:13
刚才分割主题时竟然产生了错乱，难道又是时差问题？还是说有自删帖的原因？ ...

因为数据库中，时间是用Unix timestamp表示的，是唯一的，没有时差问题。时差问题只是前台显示的小问题