Prove that \(x^{*}=(1,1 / 2,-1)\) is optimal for the optimization problem:$$\begin{align*}\text{minimize} &\quad (1/2) x^{T} P x+q^{T} x+r \\\text{subject to} &\quad -1 \leq x_{i} \leq 1, \ i=1,2,3\end{align*}$$where \(P=\begin{bmatrix}13&12&-2\\12&17&6\\-2&6&12\end{bmatrix}\), \(q=\begin{bmatrix}-22.0\\-14.5\\13.0\end{bmatrix}\), \(r=1\).
证明 \(x^{*}=(1, 1/2, -1)\) 是下述优化问题的最优解：最小化 \((1/2) x^{T} P x+q^{T} x+r\)，约束为 \(-1 \leq x_{i} \leq 1\)（\(i=1,2,3\)），其中\(P、q、r\)为上述给定矩阵和向量/常数。
**Key Criterion**: For a **strictly convex quadratic program (QP)** with box constraints \(l_i \le x_i \le u_i\), a feasible point \(x^*\) is the **unique global optimal point** \(\iff\) it satisfies the **KKT conditions for box constraints**:
$$\nabla f(x^*)_i =
\begin{cases}\ge 0, & x_i^* = l_i \ (\text{lower bound active}) \\= 0, & l_i < x_i^* < u_i \ (\text{interior point}) \\\le 0, & x_i^* = u_i \ (\text{upper bound active})\end{cases}$$where the objective function \(f(x)=(1/2)x^TPx+q^Tx+r\), and its gradient is \(\nabla f(x) = Px + q\) (gradient of convex quadratic function).
Compute \(Px^*\):
$$Px^* = \begin{bmatrix}13&12&-2\\12&17&6\\-2&6&12\end{bmatrix}\begin{bmatrix}1\\0.5\\-1\end{bmatrix} = \begin{bmatrix}13+6+2\\12+8.5-6\\-2+3-12\end{bmatrix} = \begin{bmatrix}21\\14.5\\-11\end{bmatrix}$$Evaluate \(\nabla f(x^*) = Px^* + q\):
$$\nabla f(x^*) = \begin{bmatrix}21\\14.5\\-11\end{bmatrix} + \begin{bmatrix}-22.0\\-14.5\\13.0\end{bmatrix} = \begin{bmatrix}-1\\0\\2\end{bmatrix}$$
1. \(x_1^*=1=u_1\) (upper bound active): \(\nabla f(x^*)_1 = -1 \le 0\) ✔️
2. \(x_2^*=1/2\) (interior point, \(-1<1/2<1\)): \(\nabla f(x^*)_2 = 0\) ✔️
3. \(x_3^*=-1=l_3\) (lower bound active): \(\nabla f(x^*)_3 = 2 \ge 0\) ✔️
All KKT conditions are satisfied. Since \(P \in S_{++}^n\) (positive definite), \(f(x)\) is strictly convex. For a strictly convex function on a convex feasible set, the KKT point is the **unique global optimal point**. Thus \(x^*=(1,1/2,-1)\) is optimal.
---
Give an explicit solution of each of the following linear programs (LP):