Maximum of a Linear Function subject to Linear and Quadratic Constraints in $\mathbb{R}^4$

The problem can be restated as follows:

Find the maximum of $f(\mathbf{x}) = \mathbf{c^T x}$ , subject to the constraints

$\mathbf{a^T x} = b$ , and $\mathbf{ x^T Q x + e^T x }= R^2$ .

Where, in this problem,

$\mathbf{c^T} = [2, -3, 5, 4]$

$\mathbf{a^T} = [1, 2,-1,3]$

$b = 10$

$\mathbf{Q} = \begin{bmatrix} 1 && 0 && 0 && 0 \\ 0 && 2 && 0 && 0 \\ 0 && 0 && 3 && 0 \\ 0 && 0 && 0 && 4 \end{bmatrix}$

$\mathbf{e^T} = [2, 1, 4, 1]$

$R = 10$

Starting with the linear constraint, $\mathbf{a^T x} = b$ is an equation of a hyperplane in $\mathbb{R}^n$ whose vector equation is

$\mathbf{x = V u + x_0}$ , $\mathbf{u} \in \mathbb{R}^{n-1}$

Upon substituting this into the quadratic constraint, we obtain

$\mathbf{(V u + x_0)^T Q (V u + x_0) + e^T (V u + x_0)} = R^2$

Expanding,

$\mathbf{u^T V^T Q V u + 2 u^T V^T Q x_0 + u^T V^T e} = R^2 - \mathbf{x_0^T Q x_0 - e^T x_0}$

Next, let $\mathbf{u_0 = - (V^T Q V)^{-1} (V^T Q x_0 + 1/2 V^T e) }$ , then

$\large{ \mathbf{(u - u_0)^T (V^T Q V) (u - u0)} = r^2 } \cdots \cdots (1)$

where $r^2 = R^2 - \mathbf{x_0^T Q x_0 - e^T x_0 + u_0^T (V^T Q V) u_0 }$

Equation (1) specifies a ellipsoid in $\mathbb{R}^{n-1}$ .

Now the objective function can be written in terms of $\mathbf{u}$ as

$f = \mathbf{cT x = c^T(V u + x_0) = c^T V u + c^T x_0 }$

Using Lagrange's method, the function is maximum when its gradient is parallel to that of

the contraint specified in (1) , that is,

$\lambda \mathbf{V^T c = (V^T Q V) (u - u_0) }$

Solving for $\mathbf{ (u - u_0) }$ , we get,

$\large{ \mathbf{u - u_0} = \lambda \mathbf{(V^T Q V)^{-1} V^T c} } \cdots \cdots (2)$

Plugging this into equation (1), we get,

$\lambda^2 \mathbf{c^T V (V^T Q V)^{-1} V^T c} = r^2$

and therefore,

$\large{ \lambda = \dfrac{r}{ \sqrt{ \mathbf{c^T V (V^T Q V)^{-1} V^T c} } } }$

Thus, using equation (2), we can calculate $\mathbf{u^*} = \mathbf{u_0 }+ \lambda \mathbf{(V^T Q V)^{-1} V^T c}$ ,

then calculate $\mathbf{x^*} = \mathbf{V u^* + x_0}$ , and finally, find $f^* = \mathbf{c^T x^*} = \mathbf{c^T V u^* + c^T x_0}$ .

Performing these operations for the given values specified in the problem, we obtain,

$\mathbf{x^*} = [4.811961, -1.30077, 1.971166, 3.253581]^T$ , and $f^* = 36.39638$

The desired answer is the sum of these numbers and evaluates to $45.132$