I have a question regarding the convexity of the system. The formulation I arrived at has the Hessian of the following form,
$$A^TKA = \begin{bmatrix}x_1 & x_2 & ... & x_n \\ y_1 & y_2 & ... & y_n \\ z_1 & z_2 & ... & z_n \\ w_1 & w_2 & ... & w_n \end{bmatrix}\begin{bmatrix}k_1 & 0 & 0 & ... & 0 \\ 0 & k_2 & 0 & ... & 0 \\ \vdots & \vdots &\ddots & \vdots & \vdots \\ 0 & 0 & 0 & ... & k_n\end{bmatrix}\begin{bmatrix}x_1 & y_1 & z_1 & w_1 \\ x_2 & y_2 & z_2 & w_2 \\ \vdots & \vdots & \vdots & \vdots \\ x_n & y_n & z_n & w_n\end{bmatrix}$$
I know that if $K = I_n$, the Hessian matrix is certainly positive semi-definite. However, this is not the case. The matrix $K$ is the $I\odot(3Axx^TA^T - bb^T)$, where $\odot$ represents an element-wise multiplication. Is there a condition on $\{k_n\}$ such that the Hessian is positive semi-definite? Here is what I have tried.
- Inequality. Given $x \in \mathbb{R}^n$, $x^THx \geq 0$. The inequality is somewhat similar to Cauchy-Schwarz inequality but I am not sure if there is anything to go on from there.
- Check for the signs eigenvalue using Descartes' rule of signs, but cannot really work out the conditions for the specific signs of each coeffcient.
- Try 100,000 randomized sets of value in MATLAB. Every time I sample, there seems to be 63% of the total sets that return a positive semi-definite Hessian. I think there should be something going in the matrix.
Thank you very much.
Edit: Remove typo and add more information.
For the original post, I don't know whether the vector $x$ in $K = I\odot(3Axx^TA^T - bb^T)$ is the same vector $x$ in $x^THx \ge 0$.
(1) If these two is not the same vector.
Let $y = Ax$, then $A^TKA$ is positive semi-definite if and only if $\forall y \in range(A), y^TKy \ge 0$. Thus we need \begin{equation} y^TKy = y^T I\odot(3zz^T - bb^T) y = \sum_{i=1}^n y_i^2(3z_i^2-b_i^2), \end{equation} where $z_i, i=1,\dots,n,$ is the given vector such that $z \in range(A)$. We do not have any more information about matrix $A$, so we only could suppose $range(A) = \mathbb{R}^n$. In this sense, to ensure that $y^TKy \ge 0$ can be held for any $y$, we must guarantee that $$k_i = 3z_i^2 - b_i^2 \ge 0, i=1,\dots, m.$$
(2) If these two is the same vector.
Let $y = Ax$, then $A^TKA$ is positive semi-definite if and only if $\forall y \in range(A), y^TKy \ge 0$. Thus we need \begin{equation} y^TKy = y^T I\odot(3yy^T - bb^T) y = \sum_{i=1}^n y_i^2(3y_i^2-b_i^2). \end{equation} Again, due to we do not have any more information about matrix $A$, so we only could suppose $range(A) = \mathbb{R}^n$. In this sense, we need \begin{equation} \min_{y_i} y_i^2(3y_i^2 - b_i^2) \ge 0. \end{equation} And we can find that to obtain the positive semi-definition, we need $b_i = 0$.