Tagged Questions

Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (1)

2
votes
0answers
21 views

Is every convex function differentiable amost every where?

If a function $f: D \subset R^n \rightarrow R$ is convex, then for every $x,y \in D$ and $\alpha \in [0,1]$, $$ f(\alpha x + (1 - \alpha)y) \leq \alpha f(x) + (1 - \alpha)f(y). $$ I konw a convex ...
1
vote
2answers
17 views

Every concave function that is nonnegative on its domain is log-concave?

This is a statment from Wiki. I'm not sure why this is true: If: $f(\theta x+(1-\theta y) \geq \theta f( x) + (1-\theta)f(y)$ And $f(\cdot) \geq 0$ then: $$f(\theta x+(1-\theta y) \geq f( ...
1
vote
1answer
21 views

The polar of a set: Importance and Applications

Given a duality $(X,Y)$, for any subset $A\subset X$, we can define the polar set $A^{\circ}\subset Y$. In this sense, the polar relates sets and sets in the dual space. Since cones are sets, we can ...
0
votes
0answers
13 views

What's wrong with the following trace optimization?

I'm reading a paper that has used the augmented Lagrange function for optimization. I've tried to derive one subproblem but got a different answer from that in the paper. Could you help check it ...
0
votes
1answer
9 views

How to express a set as an intersection of halfspaces

I have a set S = {x $\epsilon$ $\mathbb R^n$| $x^Ty \le 1$, $\forall y \epsilon A$} Now, I want to prove that this set is closed and convex. I know that expressing this set as an intersection of ...
0
votes
1answer
12 views

Minkowski sum of convex sets in the plane which are not polygons

Can the Minkowski sum of two convex sets in the plane which are not polygons be a polygon? Explicitly my convex set is of the form $ C= \{(x,y) \in \mathbb{R}^2 : x,y \geq 0 \text{ , } ...
0
votes
0answers
25 views

Uniquness and Exisstence of One Theorem

I need a short and nice Proof for Uniqueness and Existence of the following theorem: Suppose (H, <0,0> ) is a Hilbert space, and M is a closed convex set and $x \in H$, then there is a unique ...
1
vote
1answer
17 views

Is it right for chain rule in trace function?

The objective function is $$ f(X)=\min_X trace(B^TX^TCXBD) $$ we know the following derivatives from Matrix Cookbook, $$ \frac{\delta{trace(B^TX^TCXB)}}{\delta X}=C^TXBB^T+CXBB^T \\ \frac{\delta ...
0
votes
0answers
6 views

Which functions preserve convexity of the cells of a polyhedral tessellation of $\mathbb{R}^n$?

Let $\mathcal{X}_1, \ldots, \mathcal{X}_m \subseteq \mathbb{R}^n$ be disjoint sets with $\bigcup_{i=1}^m \mathcal{X}_i = \mathbb{R}^n$. Furthermore, let each $\mathcal{X}_i$, $i = 1, \ldots, m$, be an ...
6
votes
1answer
59 views

How do you prove $x^2$ is convex using only the definition of convexity?

I apologize beforehand if this is an extremely easy question, I have very limited experience with proving convexity statements. Also, the reason that I choose such a simple example before tackling ...
0
votes
3answers
28 views

Is Jensen's inequality an iff condition on convex functions?

According to wikipedia this is Jensen's inequality: If X is a random variable and φ is a convex function, then: $$\varphi\left(\mathbb{E}[X]\right) \leq \mathbb{E}\left[\varphi(X)\right].$$ Which ...
0
votes
0answers
21 views

Convex sets in $\mathbb R^n$: Do they have a particular form ? Does the gradient of a linear convex function $f$ exist on such a set?

Convex sets in $\mathbb R^n$: Do they have a particular form ? Does the gradient of a linear convex function $f$ exist on such a set ? Suppose that $S$ is a convex set in $\mathbb R$. Then $S$ is ...
0
votes
1answer
34 views

Proof that $f(x) = x^TMx$ is convex

I have been stuck on this problem for a while. After I use the definition of convexity and some algebra, I end with something like this: $$ \lambda f(x^{(1)}) + (1-\lambda)f(x^{(2)}) + ...
1
vote
1answer
17 views

What is affine hull of conv(A)

Consider the set $A = \{(1,0),(0,1),(-1,0),(0,-1)\}$. The convex hull of $A$, i.e. $conv(A)$, should look like the following: (This is also a $l_1$-norm unit ball.) My question is what is the ...
2
votes
0answers
25 views

In what sense is the Bayesian posterior mean a “convex combination”?

This is related to a previous question that hasn't gotten an answer: Definition of convex combination with matrix-vector multiplication Suppose I want to estimate $x \in \mathbb{R}^n$ from two ...
0
votes
1answer
35 views

Arclength comparison of two convex functions

(a) Let $f$ and $g$ be two $C^1([a,b])$ convex functions such $$f(a)=g(a), \ f(b)=g(b)\ \text{ and } \ g(t)\le f(t) \ \text{ for all }t \in [a,b]$$ Then the arclength of the graph of $g$ ...
0
votes
1answer
18 views

Show that $x \mapsto \left( x^{\top} \sigma x , -\mu^{\top}x \right)^{\top}$ transforms a given set into a convex set.

Let's say you have a covariance matrix $\sigma$ and a vector of expected returns $\mu$. Basically $\sigma$ is a symmetric matrix with positive eigenvalues and we can safely assume that $\mu$ is just a ...
1
vote
0answers
38 views

Can't understand a proposition in the analysis of Newton's method

I am reading a paper found here on the Kantorovich analysis of Newton's method http://arxiv.org/pdf/1209.5704.pdf and I am having difficulty understanding a Proposition 6 (Note that Proposition 6 ...
1
vote
0answers
9 views

Function with convex polytopes as sub-levelsets

If a function has convex sub-levelsets then it is quasiconvex. What if it has sub-levelsets that are convex polytopes? Obviously, it is still quasiconvex but is there a name for this class of function ...
1
vote
1answer
25 views

About the slack variable for hinge-loss SVM

The hinge-loss SVM is defined $$ \min_{w,b} \frac{1}{2}w^T w+\sum_{i=1}^{N}\max\{0,1-y_i(w^Tx_i +b)\} $$ By introducing a slack variable $\xi_i$, the optimization problem is changed to $$ ...
2
votes
0answers
35 views

Topological vector space question

$C[0,1]=$ space of all continuous complex valued function over $[0,1]$. Define metric, $d(f,g)={\int_{0}^{1} \frac {|f(x)-g(x)|}{1+|f(x)-g(x)|}}$, for all $f,g\in C[0,1] .$ Let $(C[0,1],\sigma)$ ...
0
votes
2answers
35 views

If $ S \subseteq \mathbb{R}^n$ is finite, show that conv(S) is a closed set…

If $ S \subseteq \mathbb{R}^n$ is finite, show that conv(S) is a closed set. Is the statement still true if S is not finite? Where conv(S) is the convex hull of S. From what I've read, the convex ...
1
vote
0answers
39 views

Distributed convex optimization problem

Consider the optimization problem $$ \min_{ x_1, \ldots, x_N } \sum_{i=1}^{N} f_i( x_i ) \\ \text{s.t.: } \sum_{i=1}^{N} x_i \in X, \ x_i \in X_i \ \forall i \in \{1, \ldots, N\} $$ where $f_1, ...
0
votes
1answer
23 views

Proof that the intersection of any finite number of convex sets is a convex set

How to prove that the intersection of any finite number of convex sets is a convex set? I have no idea.
1
vote
3answers
25 views

union and difference of convex set

suppose X,Y are two convex sets x1, x2 in X and y1, y2 in Y defn of X and Y being convex: tx1+(1-t)x2 in X ty1+(1-t)y2 in Y it is clear that: 1) X+Y is convex. 2) X intersection Y is convex 3) ...
1
vote
4answers
54 views

A function is convex and concave, show that it has the form $f(x)=ax+b$

A function is convex and concave, it is called affine function. That is the function: $$f(tx+(1-t)y)=tf(x)+(1-t)f(y),\, \, t\in (0,1) $$ Force $y=0$(suppose $0$ is in the domain of $f(x)$), we ...
0
votes
2answers
24 views

Is closure of convex hull of C equal to convex hull of closure.

If $C$ is a set in a topological vector space (or in particular a metric space), can we say that $\text{cl}(\text{conv}(C)) = \text{conv}(\text{cl}(C))$, where cl$(\cdot)$ represents closure and ...
1
vote
1answer
42 views

Is this function convex or concave

Consider the following function: $$f:(0, \infty)^2 \rightarrow \mathbb{R}: (\phi,\psi) \rightarrow \frac{\phi}{\psi}$$ Is this function convex or concave? (Or neither?) I tried by calculating the ...
0
votes
1answer
16 views

Algorithm to determine whether a vector $\mathbf{x}$ belongs to a convex set given by its extreme rays?

Let $\mathbf{p}_i$ be a finite set of finite-dimensional real vectors with non-negative components with the property that, for any $k$, $\mathbf{p}_k$ cannot be expressed as a linear combination with ...
1
vote
1answer
27 views

finding a counter example to Caratheodory's convex hull theorem for infinite dimentional space

Recently I learned in class Caratheodory's convex hull theorem which suggests that in a finite dimentional (n) space every x can be written as a convex-combination of maximum (n+1) vectors. I was ...
1
vote
2answers
27 views

Is the algebraic interior relatively open in a closed convex set?

I am struggling with proving or disproving the following: Let $X$ be a locally convex space and let $C\subset X$ be closed convex with non-empty algebraic interior which we denote by $C^i$ (recall ...
2
votes
0answers
37 views

Jensen's inequality: proof by using linear functions

Here's an extract from Stochastic Calculus for Finance Volume 1 by Shreve. I don't understand the statement that says a convex function is the maximum of all linear functions that lie below ...
2
votes
2answers
26 views

Origin of the term `quermassintegral'.

What is the origin of the term `quermassintegral'? I think this is a german word. What would be its literal translation in English? The definition of quermassintegrals from wikipedia: Let ...
1
vote
1answer
32 views

Equivalence of semi concavity of function $g$ and convexity of function $x\mapsto \frac c 2 |x|^2 - g(x)$

$g\in C^2(\mathbb R^n)$ is called semi concave, if there exists $c>0$ such that for all $x,y\in\mathbb R^n$ the following holds: $$g(x+y) - 2g(x) + g(x-y) \leq c|y|^2$$ Now, in Evans "Partial ...
10
votes
0answers
67 views

Does there exist regular planar pentagon?

How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ (treated as a surface) includes 5 points which form a regular planar pentagon?
0
votes
0answers
9 views

How to construct a suitable example in matrix convex

To show that the function $X \to X^{3}$ is generally not matrix convex of order 2 on $S_{+}^{2}$. I cannot find an example and even don't know how to construct one.
0
votes
1answer
29 views

Why a set of positive definite matrices define a half space?

A half-space is a set of the form $\{x|a^Tx \leq b\}$. Also it is stated that the set $\{X\in S^n | z^TXz \geq 0 \}$, with $S^n$ denote the set of symmetric $n\times n$, is a half space$^1$, Can we ...
0
votes
1answer
21 views

Second order cone with quadratic interpretation

Could you please help me to understand how the second part of the equation (quadratic form) derived form the first one? The basic definition of the second-order cone is: $C = \big\{(x,t) \in ...
1
vote
1answer
31 views

discussing the existence of a convex function

If $g$ is a positive function on $[0,1]$ such that $g(x)$ tends to $\infty$ as $x$ tends to $0$, then there is a convex function $h$ on $[0,1]$ such that $ h \leq g$ and $h(x)$ tends to $\infty$ as ...
5
votes
3answers
89 views

If $f$ is continuous and $\,f\big(\frac{1}2(x+y)\big) \le \frac{1}{2}\big(\,f(x)+f(y)\big)$, then $f$ is convex

Let $\,\,f :\mathbb R \to \mathbb R$ be a continuous function such that $$ f\Big(\dfrac{x+y}2\Big) \le \dfrac{1}{2}\big(\,f(x)+f(y)\big) ,\,\, \text{for all}\,\, x,y \in \mathbb R, $$ then how do we ...
0
votes
1answer
27 views

What is the sub-differential of the separable sum $R(w) = \sum^{d}_{j=1} |w_j|$?

Recall the definition of a sub-differential: $$\partial F(w_0) = \{ v : \forall w, F(w)-F(w_0) \geq v \cdot (w - w_0)\} $$ Intuitively, for any w in the domain of the function one can draw a plane ...
1
vote
1answer
29 views

How does $\in$ behave with simple algebra dealing with sub gradients?

I was trying to understand the following optimization problem: $$argmin_{v \in H} {R(v) + \frac{1}{2}||v - w||^2}$$ Assume $R(v)$ is Convex, proper and semi-continuous with a unique minimizer. ...
0
votes
1answer
16 views

Intuitive explanation of why a chord of a convex function has to be a straight line

I was trying to understand the definition of convexity better. A simple definition of convexity is: $$f(tx_1 + (1 -t)x_2) \leq tf(x_1) + (1-t)f(x_2)$$ $\forall x_1,x_2 \in Domain(f)$ Intuitively, ...
1
vote
1answer
29 views

Strong convexity on sets?

Consider the definition of convex functions: $$ f(tx+(1-t)y) \le t f(x)+(1-t)f(y) $$ It is easy to show the definition of the convexity on sets with respect to the above definition (Specifically for ...
0
votes
1answer
36 views

Strictly convex if and only if derivative strictly increasing?

Suppose $f$ is a real-valued function that is differentiable on an open interval $I$. It is well-known that $f^{\prime}$ is increasing on $I$ if and only if $f$ is convex on $I$. Is the following ...
2
votes
0answers
31 views

Affine functions as equality constraints in convex optimization problems

I am studying on an introduction to convex optimization problems. When defining a convex optimization problem, we have a convex object function, $f(x)$, a set of convex functions $g_i(x)$ where the ...
0
votes
0answers
32 views

A property of concave functions

If $\phi$ is a concave functions (that is $-\phi$ is convex) with $\phi(1)=0$ why is it that $\phi(x)\le x-1$?
3
votes
3answers
96 views

Prove that $0 < x < y$ implies $\|x\| < \|y\|$ for any norm.

All vectors are real. Prove that $0 < x < y$ (element-wise) implies $\|x\| < \|y\|$ for any norm. This is probably very basic, but I don't seem to get the hang of it. Edit: it turns out this ...
1
vote
2answers
30 views

Convexity and concavity of discontinuous functions

QUESTION F(x) =-x for x>=0 and F(x)=x for x<=0 Is the function convex/(strictly), concave/(strictly) I have attempted the answer but got strictly concave but isnt a discontinuous function meant ...
0
votes
0answers
24 views

subdifferential and Legendre transform

I have a problem with the following exercise from Evans, Partial Diff. Eq., Chapter 3, problem 6: Let $H:\mathbb R^n\to\mathbb R$ be convex. We say $q$ belongs to the subdifferential of $H$ at $p$, ...