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.Γ. Jun 2 '19 at 20:55
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.