Optimizing a quadratic function under a constraint of some of the variables.

Question

I have a quadratic programming problem of the form

$$ f(x) = \frac{1}{2}x^TAx -b^Tx $$

where $x = (x_1,\ldots,x_n)^T$, $b = (b_1,\ldots,b_n)^T$ and $A$ is an symmetric positive definite matrix of dimentions $n \times n$.

Defining $x_c = (x_{i_1},\ldots,x_{i_k})^T$ with $1 \leq i_1 < \ldots < i_k \leq n$ and $q = (q_1,\ldots,q_k)^T$ I want to constraint this problem to have $x_{i_l} = q_l$ for $l=1,\ldots,k$. Such condition is equivalent to require $\left\lVert x_c - q \right\rVert_2^2 = 0$. Using the lagrange multipliers method I can write the lagrangian function as

$$ f(x) = \frac{1}{2}x^T A x - b^T x - \lambda \left\lVert x_c - q \right\rVert_2^2 $$

Differentiation to respect to lambda yields the trivial equality $x_c = q$ and such equality needs to hold for any $\lambda \neq 0$. This is simply telling me I can fix in $f$ the variables $x_c = q$ therefore I need to perform an unconstrained miminization of the function

$$ g(x_u) = \frac{1}{2} x_u^T A'x_u + x_u^t A''x_c -b'^Tx_u $$

Where :

1. $x_u$ is the vector obtaining by removing the components whose indices where in $x_c$
2. $A'$ is obtained by removing the columns and rows from $A$ whose indices where covered in $x_c$
3. $A''$ is obtained by only retaining the columns from $A$ whose indices are in $x_c$ but removing from $A$ the rows whose indices are in $x_c$.
4. $b'$ is obtained by removing the components whose indices are in $x_c$

This yelds

$$ \nabla_{x_u} g = A'x_u +A''x_c-b' = 0 \iff A' x_u = b' - A''x_c \iff x_u = A'^{-1} \left( b' - A''x_c \right) $$

My actual problem is more complicated than this but the gist is the same. Could you tell me if what I did is correct?

Answer 1

We wanted to minimize

$$\min_{x_u} \frac12\begin{bmatrix} x_u^T & x_c^T\end{bmatrix}\begin{bmatrix} A' & A'' \\ A''^T & A_{cc}\end{bmatrix} \begin{bmatrix} x_u \\ x_c\end{bmatrix} -\begin{bmatrix}b^{'T} & b_c^T \end{bmatrix}\begin{bmatrix} x_u \\ x_c\end{bmatrix}$$

Notice that $x_c$ is a constant, hence if we drop the constant part and focus on the parts with $x_u$, we get

$$\min_{x_u} \frac12 x_u^TA'x_u + x_u^TA''x_c-b'^{T}x_u$$

Upon differentiating, we have

$$A'x_u + A''x_c-b'=0$$

$$x_u = A'^{-1}(b'-A''x_c)$$