Understanding the Hessian Matrix definition

[benjaminplong]

Could someone help me understand the mapping of the objective to the Hessian Matrix? The example below is from the C example included in the src code. I mainly don't understand where the powers come from and what creates the this term, " - 2x_1x_3". Thank you

// Illustrate the solution of a QP
//
// minimize -x_2 + (1/2)(2x_1^2 - 2x_1x_3 + 0.2x_2^2 + 2x_3^2)
//
// subject to x_1 + x_2 + x_3 >= 1; x>=0
const int q_format = kHighsHessianFormatTriangular;
const int q_num_nz = 4;
const int q_start[3] = {0, 2, 3};
const int q_index[4] = {0, 2, 1, 2};
const double q_value[4] = {2.0, -1.0, 0.2, 2.0};

[jajhall]

Assume that the Hessian $Q$, where the objective is $(1/2) x^TQx$ is stored as column-wise as a lower triangular matrix - as the argument below can also be set out in terms of the Hessian stored row-wise as an upper triangular matrix

The entries in the upper triangle of the hessian are not given, but implied by symmetry

The first column has indices (0, 2) and values (2.0, -1.0), so $Q_{11}=2$ and $Q_{31}=-1$. This implies $Q_{13}=-1$ and, together, the three terms give $(1/2)(2x_1^2 - x_3x_1 - x_1x_3)\equiv (1/2)(2x_1^2 - 2x_1x_3)$

Does this help?

[benjaminplong]

This helps some. I have a few more questions.
How does -x_2 get out front?
So the triangular format is what implies Q13 = Q31?
What sets T = 2?
The first q_value for each is a coefficient for Cx_i^2?

[jajhall]

The -x_2 is just the linear term in the objective, corresponding to $c=[0, -2, 0]$ in $c^Tx + (1/2) x^TQx$.

It's due to the symmetry of the Hessian that only a triangular matrix has to be specified. Hence $q_{31}$ defined in the triangular matrix means that there will be an equal $q_{13}$ term.

Not sure what you mean by "What sets T = 2?" The only "T" I see is in $x^T$, where it indicates the transpose of a vector. Does it help if I write out the whole objective function like this

$$\begin{array}{rcl} c^Tx + (1/2) x^TQx&=& \begin{bmatrix} 0\\-2\\0\end{bmatrix}^T\begin{bmatrix} x_1\\x_2\\x_3\end{bmatrix} + (1/2)\begin{bmatrix} x_1\\x_2\\x_3\end{bmatrix}^T\begin{bmatrix} 2&0&-1\\0&0.2&0\\-1&0&2\end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3\end{bmatrix}\\\ &=& \begin{bmatrix} 0&-2&0\end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3\end{bmatrix}+ (1/2)\begin{bmatrix} x_1&x_2&x_3\end{bmatrix}\begin{bmatrix} 2&0&-1\\0&0.2&0\\-1&0&2\end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3\end{bmatrix}\\\ &=& -x_2 + (1/2)(2x_1^2 - 2x_1x_3 + 0.2x_2^2 + 2x_3^2) \end{array}$$

[benjaminplong]

Yes this makes it clear thank you