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)

0
votes
0answers
12 views

Hyperbolic set convexity proof

We have the hyperbolic set: $S = \{x \in \Re_{+}^2 | x_1 x_2 \geq 1\}$ and we want to prove the convexity of it. I have started with the classic definition. Given $x,y \in S$, $S$ is a convex set if ...
1
vote
0answers
11 views

Seperation of convex compact sets with affine halfspaces

Let $C_1,C_2,...,C_m$ compact convex sets s.t. $\bigcap C_i = \emptyset$. I want to show that in that case there exsist affine halfspaces $H_i$, such that for every $i=1,2...,m$, $C_i \subset H_i$ ...
0
votes
0answers
23 views

uniform boundedness of a class of functions

Consider a class of (proper closed) convex function on $[0,1]^d$, which we shall denote $\mathcal{F}$. If every element of $\mathcal{F}$ is bounded in $L_2$, say $$\int_{[0,1]^d} |f(x)|^2\ dx\leq 1,$$ ...
0
votes
1answer
44 views

Type of convex function?

I want a convex function $f:\mathbb{R} \to \mathbb{R}$ with the following property: given points $x,d \in \mathbb{R}$, and $\alpha \in (0,1)$, we have $$f(x + \alpha d) \geq \alpha f(x + d).$$ Is ...
1
vote
0answers
17 views

Approximating a set of convex quadratic inequalities by a convex polytope

I have a convex set of the form $$Z = \{x|x^TQ_ix+b_i^Tx+c_i\le0,i=1,\ldots,m\}$$ where each $Q_i\succeq0$, that I wish to approximate by a set of the form $$\hat Z = \{x|Ax\le b\}$$ We can further ...
2
votes
1answer
37 views

Convex decomposition of a vector

Let $(a_i)_{i=1}^n$ be a probability vector, that is, $a_i\geq 0$ and $\sum_i a_i=1$ and let $(U_{ij})_{i,j=1}^n$ be a unistochastic matrix, that is, the pointwise square of a unitary matrix. Now ...
0
votes
0answers
17 views

Convexity of the quadratic form of a matrix

I am going through a research paper where they have made a statement without proof. They have mentioned that ...
0
votes
0answers
16 views

uniformly convex domain and uniformly convex function

I want to ask a question about uniformly convex domain: Suppose $\Omega$ is unifromly convex, i.e. for each point $x_0\in\partial\Omega$, with regualrity $C^2$ smooth. Uniform convexity of domain ...
1
vote
1answer
28 views

Solution set of a quadratic inequality

Let C $\subseteq$ $\Re^n$ be the solution set of a quadrtatic inequality, C = $\{x \in \Re^n | x^TAx +b^Tx + c \leq 0\}$. $A \in \Re$, b $\in \Re^n$ and c $\in \Re$. We want to show: That C is ...
1
vote
1answer
34 views

Prove a certain matrix is positive semidefinte.

Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi$ to be a diagonal matrix with a principal left eigenvector of $P$ on the main diagonal and zeros ...
-1
votes
0answers
24 views

$[f=q]$ is closed implies $f$ is continuous. [on hold]

Define $H=[f=q]$ to be the set of points such that $f(x)=q$. Let us assume that H is closed. Then the complement of H is open and nonempty (since $f$ does not vanish identically - ""i don't understand ...
1
vote
1answer
26 views

Analytical solution to the first PCA direction

It is known that the first PCA direction for a dataset of $n$ points is the unit vector with max variance after projecting the points onto this vector. I wonder whether there are some analytical ...
0
votes
2answers
23 views

convexity of piece wise function

I have a piece-wise function defined on the real line. The pieces are connected continuously, and the second derivative of each piece is strictly positive. Does this means that the function is convex? ...
0
votes
0answers
13 views

Minkowsky Theorem

Theorem: Let $L$ be an $n$-dimensional lattice in $\mathbb R^n$ with fundamental domain $T$, and let $X$ be a bounded symmetric convex subset of $\mathbb R^n$. If $Vol(X)>2^nVol(T)$ then $X$ ...
0
votes
2answers
48 views

Looking for numerical methods for finding roots of convex vector function ${\bf f}({\bf x})={\bf 0}$

Consider the function ${\bf f}:\mathbb{R}^n\to\mathbb{R}^m$ defined as ${\bf f} = (f_1,f_2,\ldots,f_m)$ where each $f_i:\mathbb{R}^n\to\mathbb{R}$ is twice-continuously differentiable convex in ${\bf ...
0
votes
1answer
20 views

Properties of functions having the form $g(x,t) = t f(\frac{x}{t})$

I have been frequently coming across the function $g(x,t) = t f(\frac{x}{t})$ in my course on convex optimization. A friend of mine mentioned that it is the perspective function, but the book on ...
0
votes
0answers
23 views

Prove quasiconvexity of a multivariate function [on hold]

I would like to prove that the following function is quasiconvex: $$ f(x_1,x_2) = -x_1*x_2 -1 $$ How do i prove its quasiconvexity (without augmented Hessian matrix) ?
0
votes
1answer
35 views

Does every strongly convex function has a stationary point?

Say does every differentiable $\mu$-strongly convex function $f:\mathbb{R}^n\mapsto\mathbb{R}$, with $\mu>0$ have a point where its gradient is $0$? If not so which is the minimum you can impose ...
0
votes
0answers
25 views

How to prove the convexity of $f$ if the strict epigraph of $f$ is convex

I have trouble to prove the equivalence of the following two definitions of convex function. For convenience, I list them as follows: Def-A. Let $f : I\to \mathbb{R}$ be a function, where $I$ is (and ...
0
votes
0answers
16 views

Using Taylor's theorem and Lagrange form of the reminder to prove the second order condition for convexity

I try to prove the second order condition for convexity. So far' I've done the following: First, I prove second order => convexity: Let $f$ be a function with positive semi-definite Hessian. Using ...
1
vote
0answers
22 views

Property of Newton step for self-concordant convex functions

Suppose $f(x)$ is a convex and self-concordant function minimized at $x^*$. I have two starting points $\tilde{x}_0$ and $\hat{x}_0$ such that $|\hat{x}_0-x^*| \le |\tilde{x}_0 - x^*|$. We also know ...
1
vote
0answers
14 views

Proofs regarding about all Second Derivative Test cases (Inconclusive & Single Variable)

This is how I would prove f''(c) > 0 that f(c) has local min and I would easily flip the inequalities and state a conclusion for f''(c) < 0 that f(c) has local max. Quick Proof for f''(c) > 0 ...
2
votes
0answers
33 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 ...
2
votes
2answers
30 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
31 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
17 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
15 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
16 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{ , } ...
2
votes
1answer
52 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
60 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
36 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
22 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
21 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
38 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
10 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
28 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
38 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
36 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
41 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
25 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
26 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
55 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 ...
2
votes
1answer
93 views

Segment ordered density conjecture.

I have a set $S\subset\mathbb {R}^2$ with the following property (P) $\forall x,y\in S$, $\forall\mathscr{C}$ a convex set that contains $x$ in its interior, $bd\mathscr{C}\cap [x,y]\subset ...
1
vote
1answer
43 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 ...