3
$\begingroup$

Show that the following problem is a convex optimization problem.

$f(x,y,z)=2x^2-y+z^2 \rightarrow min! $

$g_1(x,y,z)=y+x\le1$,

$g_2(x,y,z)=z-y\le1$

Convex optimization problem if:

(1) $f(x)\rightarrow min!$

(2) $f(x)$ is convex

(3) all constraints $g_i$ are convex, $ i=1,..,m$

My idea is to calculate the Hessian matrix of the objective function and constraints and check if the matrix is positive (semi) definite, which would imply (strictly) convex function.

$H_f(x,y,z)=\begin{pmatrix} 4&0&0\\0&0&0\\0&0&2\end{pmatrix}$

This is a positvie semidefinite matrix (Eigenvalues $\geq0$)

$\Rightarrow f(x)$ is convex

The Hessian matrix of $g_1$ and $g_2$ is a zero matrix which is both convex and concave.

So the problem is a convex optimization problem.

Is my computation/conclusion correct?

Thank you in advance.

$\endgroup$
1
  • 2
    $\begingroup$ It sounds good. $\endgroup$
    – A.Γ.
    Commented Jun 2, 2019 at 20:55

1 Answer 1

1
$\begingroup$

Your idea is good, since checking via Hessian is a simple technique in case it's easy to calculate it. However, with more complex functions the Hessian can be hard to compute, so it's a good practice to prove convexity using "non derivative" methods.

In your case, ask yourself the following (works for the target function as well as the constraints): What are the atoms ("building blocks") of the function? Do you see a simple decomposition to the function? For example, is the function a summation of convex functions? Recall that summing convex functions maintains convexity.

$\endgroup$

You must log in to answer this question.

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