0
$\begingroup$

The optimization function is defined as

$\frac{1}{2}.x^T.A.x$ where $A=\begin{pmatrix} 1 & 0.5 \\ 0.5 & 1 \end{pmatrix}$

How to check if this is a convex or not? I know about the second derivative test and it gives $A$ which should be greater than $0$ in order to be convex but what are we really checking here? how is $A$ compared against $0$?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You have to check wheather $A$ (the hessian of the objetctive function $\frac{1}{2}x^T A x$) is positive semidefinit or not. Here, $A$ is diagonally dominant and symmetric, which implies directly, that A is positive semidefinit, which implies, that your objective function $\frac{1}{2}x^T A x$ is convex.

$\endgroup$
5
  • $\begingroup$ what if I add a constraint to my function such that $x^T.A.x=23$? what will that mean? will it be still convex? $\endgroup$
    – christopher
    Jun 10, 2020 at 19:22
  • 1
    $\begingroup$ The function $f(x)=x^T A x$ is still convex but the feasible set is not convex any more, which makes optimization more difficult in general (your example is trivial since every x of the feasible set is a solution) $\endgroup$
    – Philipp123
    Jun 10, 2020 at 19:33
  • $\begingroup$ How did you test the feasible set for convexity? can you share more details? $\endgroup$
    – christopher
    Jun 10, 2020 at 20:51
  • 1
    $\begingroup$ The set $S:={x : x^T A x =c}$ for c>0 is an ellipse. A convex set C must contain all convex combinations $t x +(1-t)y$ for $x \element C$ and $y \element C$ and $0\leq t \leq 1$. So like a circle, an elipse is not convex but a disc is convex. As example without calculations choose $A=I_2$ the identity, and the constraint $x^T A x =1$. Then (1,0) and (0,1) fulfil the condition but the convex combination (1/2,1/2) does not. $\endgroup$
    – Philipp123
    Jun 10, 2020 at 23:06
  • 1
    $\begingroup$ But the set $S:=\{x: x^T Ax \leq 1 \}$ is convex since this is the area in the elllipse so every connecting line lies into it. $\endgroup$
    – Philipp123
    Jun 10, 2020 at 23:13

You must log in to answer this question.

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