Consider the following quadratic program

$$\begin{array}{ll} \underset{x_1,x_2,x_3}{\text{minimize}} & x_1 x_2 +\frac{1}{2} x_1^2 + \frac32 x_2^2 + 2 x_3^2 + 2 x_1 + x_2 + 3x_3\\ \text{subject to} & x_1 + x_2 + x_3 = 1\\ & x_1 - x_2=0\\ & x_1, x_2, x_3 \geq 0\end{array}$$

How can I write the objective function in a form of $$\min_x \frac{1}{2}x^TQx+C^Tx$$

Second, we know that when $Q$ is a positive semidefinite matrix, i.e., when $y^TQy\geq 0$ for all $y$, the objective function is a convex function of $x$. Since the feasible set is a polyhedral set, it is a convex set. How can I show this for this specific problem?

Thank you for your help in advance!

  • $\begingroup$ Suppose $Q$ is symmetric and write out the expression of ${1 \over 2} x^T Qx$. Compare coefficients of the $x_i x_i$ terms for $i \le j$. $\endgroup$
    – copper.hat
    Apr 29, 2021 at 22:43

1 Answer 1


We can write $Q$ by examining the coefficient.

Since coefficient of $x_1^2$ is $\frac12$, $Q_{1,1} = 2 (\frac12)=1$.

Since the coefficient of $x_1x_2$ is $1$, we have $Q_{1,2}=Q_{2,1}=1$.

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

To check positive semidefiniteness, try to compute the eigenvalues and verify that they are nonnegative. You don't have to know them exactly, you can also bound them using Gershgorin Theorem.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .