0
$\begingroup$

I've got some trouble in determining the function, which contains vectors and matrix, is a convex function or not.

\begin{aligned}\min _{x}k^{T}x\\ s.t. Ax\leq y\end{aligned}

$x$ is $n\times1$ vector, $y$ is $m\times1$ fixed vector and $A$ is $m\times n$ fixed matrix

Is the above problem is convex optimization problem? and why? For this question, should we have to prove both $k^{T}x$ and $Ax\leq y$ are convex functions? If yes, please tell me the detailed steps.

$\endgroup$
  • $\begingroup$ What have you tried so far? Do you know what a linear function is and whether linear functions are convex? $\endgroup$ – Chris Harshaw Dec 5 '19 at 17:35
  • $\begingroup$ Actually, I have no idea about this question. I've read some doc related to convex function. However, I totally don't understand what are they talking about $\endgroup$ – chan sum Dec 5 '19 at 17:41
  • $\begingroup$ Hmmm...do you know what the definition of convex function and convex set are? Is this for a homework assignment or for your own personal use? $\endgroup$ – Chris Harshaw Dec 5 '19 at 17:43
  • $\begingroup$ In general, you have to show/prove that both objective and constraints are convex. $\endgroup$ – user550103 Dec 5 '19 at 17:50
  • $\begingroup$ I think I know what convex set is, but I am not sure the definition of convex function. This is a question in my lecture note, something like a small quiz after the lecture. $\endgroup$ – chan sum Dec 5 '19 at 17:52
2
$\begingroup$

Guide:

A function $f:\mathbb{R}^n \to \mathbb{R}$ is convex if for $\forall \lambda \in (0,1), x_1, x_2 \in \mathbb{R}^n$, $$f(\lambda x_1 + (1-\lambda)x_2) \le \lambda f(x_1) + (1-\lambda )f(x_2).$$

Now let $f(x)=k^Tx$, verify that the condition above holds.

Also prove that $\{x \in \mathbb{R}^n:Ax \le y\}$ is a convex set.

$\endgroup$
  • $\begingroup$ Would you mind to show me the detailed steps for how to proof it? $\endgroup$ – chan sum Dec 7 '19 at 13:04
  • $\begingroup$ give it a try first and I will help to edit your working? You get to learn more if you give a try. For example, try to write out what is $f(\lambda x_1+(1-\lambda)x_2)$ first? $\endgroup$ – Siong Thye Goh Dec 7 '19 at 13:09

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.