0
$\begingroup$

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!

$\endgroup$
1
  • $\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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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