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)

1
vote
0answers
28 views

Minimum of two convex functions

I'm having trouble showing the below statement is true. $\hat{\alpha}=\arg\min_\alpha \frac{1}{n} \sum_{i=1}^{n} f(u_i - h(v_i, \alpha))$ where $h(v_i, \alpha)$ is linear in $\alpha$. ...
0
votes
1answer
206 views

Unlike Jensen's Inequality, can we upper bound $\log \sum_{i}{u_i \exp(x_i)}$?

According to Jensen's Inequality, it is not hard to derive the lower bound for $\log \sum_{i}{u_i \exp(x_i)}$ due to the convexity of $\log(\cdot)$: $\log \sum_{i}{u_i \exp(x_i)} \geq \sum_{i}{u_i ...
1
vote
0answers
48 views

Prove that $\{(x, y): x\in ri (dom f), y >f(x)\}\subset ri (epi f)$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
1
vote
2answers
63 views

When does it help to write a function as $f(x) = \sup_\alpha \phi_{\alpha}(x)$ (an upper envelope)?

In this question I was shown a very elegant solution based on writing a function as the upper envelope of a family of linear functions: $$f(x) = \sup_{y\in C} f(y) + \langle \nabla f(y), x-y ...
13
votes
1answer
126 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
1
vote
1answer
81 views

How to determine convexity of the set

Let $S=\left\{(x_1,x_2)\in \mathbb{R}^2: \sqrt[4]{2x_1^4+2x_1^2x_2+x_2^2}\leq 5 \right\}\cap\left\{(x_1,x_2)\in \mathbb{R}^2: \cos(x_1)+3x_1^2+x_2\leq 5 \right\}$ I want to determine, whether S is ...
0
votes
1answer
37 views

How can the function's composite be convex function?

$h$ is a continuous function which is convex and strictly decreasing; $t$ is a continuous function which is strictly increasing; $\operatorname{ran}(t)$ is included in $\operatorname{dom}(h)$. Under ...
0
votes
2answers
65 views

proving that a function is convex

Suppose that $f(x)=\frac{1}{k}|x|^k$ where $k>1$ and $k<\infty$. $x$ here is in $\mathbb{R^n}. $ Is $f$ convex? I am trying to use the definition of convexity but it seems like I would need some ...
0
votes
1answer
41 views

PSD matrices properties

If I have a matrix $X \in R^{n \times n} $ and an index set $ I \subseteq \{1,\dots,n\} $, Is $X_I$ also positive-semidefinite $\forall \ \ I $? Why ? $X_I $ is the submatrix that is formed by ...
0
votes
1answer
50 views

Projection on a convex set

If I have a convex set $ S$ and if I project an $ x$ onto $S$. Is it true that $x $ would project onto a unique element of $S$. Why? What would be considered different if the set $S$ was non-convex?
1
vote
2answers
55 views

Prove that $f(x+h)-f(x) - \langle\nabla f(x), h\rangle\geq 0 \Rightarrow f $ convex

At this link there is a demonstration that for $f$ continuously differentiable on $C \subseteq \mathbb{R}^n$ convex, $f(x+h)-f(x) - \langle\nabla f(x), h\rangle\geq 0 \Rightarrow f $ convex. This ...
1
vote
1answer
33 views

Is a finite integer subset of a convex real set convex?

Specifically, can I take a convex real set, show that the definition of convexity holds for it, and then make claims based on that definition of convexity for an integer subset? I know that the ...
1
vote
2answers
86 views

Is a continuously differentiable function convex if all its partial second derivatives are non-negative?

I'm having trouble understanding the relevant Wikipedia article which begins with a convex set $X$ and then uses functions of single variables for succeeding examples; the MathWorld article seems to ...
0
votes
1answer
96 views

Projection operator and convex sets

I was wondering if the projection operator onto a convex set was differentiable? [ An explanation would be helpful ] .
1
vote
0answers
79 views

Relative Interior and dense subsets

(Due to no answers, I also posted this question here.) Let $A,B\subseteq \mathbb R^d$ be non-empty, such that $B\subseteq \overline A.$ For $S\subseteq\mathbb R^d$ define the relative interior of $S$ ...
1
vote
1answer
89 views

Example of conjugate function of a biquadratic form

An exercise asks me to prove that given the function $$f(\omega) = \frac{\omega^TQ\omega}{2}$$ where $Q$ is invertible, the conjugate function $f^*(\theta) = \sup_{\omega} \left(\langle ...
1
vote
1answer
34 views

Need an analytic expression to find the index of the first positive element of an array

I have an array of length M. The elements of the array are either zero or positive real numbers. I need to derive a function/analytic expression (preferably linear/convex/concave) that finds the index ...
0
votes
1answer
85 views

alternative definition of Affine map

Let $f:X\longrightarrow Y$ be a function on real vector spaces (note that $X,Y$ have arbitrary dimensions). If $T(x)=f(x)-f(0)$ is linear, $f$ is called an affine map. Prove that $f$ is affine if ...
1
vote
1answer
43 views

Motivation : min cut and max flow

Can someone explain the motivation behind the min cut and max flow problem?
0
votes
1answer
284 views

Is exponential of a concave function concave?

is this function: $$\exp\Big(-||Ax||^2\Big)$$ concave in A?? I know that exponential of a convex function is convex, but is exponential of a concave function concave??
1
vote
2answers
194 views

The distribution of barycentric coordinates

Let $\mathcal{X} = \{x_1,\dots,x_n\} \subset \mathbb{R}^d$ and let $Z$ be a random variable uniformly distributed over convex hull of $\mathcal{X}$, denoted as $\text{conv}(\mathcal{X})$. Assuming ...
1
vote
0answers
55 views

Characterizations of convex hull

Let $X = \{x_1,\dotsc,x_n\} \subset \mathbb{R}^2$ be a finite set of points in the plane. No $3$ of them are collinear. I am trying to think of ways to characterize the convex hull ...
1
vote
2answers
76 views

Integral of convex set

Let $D$ be a convex set and $X_1,\dots,X_d$ be integrable random variables. If $X= (X_1,\dots,X_d)$ is in $D$ almost surely, why is it true that the vector $a= (\mathbb{E}X_1,\dots,\mathbb{E}X_d)$ ...
2
votes
1answer
71 views

Prove Convexity

Suppose we have a function $f: \mathbb{R}^n\to \mathbb{R}$ that is given by $f(x) = \prod_{i=1}^n\,(1+x_i^2)$. How can we prove or disprove that the function is convex?
0
votes
1answer
40 views

Convex function with weights not summing to 1

Given a convex function, $x_i$ elements of some vector space (let's call them real numbers if we want), $\lambda_i \geq 0$, $\sum_i \lambda_i = 1$, we have $f\left( \sum_i \lambda_i x_i\right) \leq ...
0
votes
2answers
88 views

If two convex sets have the same closure then their relative interiors are the same

I am having trouble seeing this. I have read and understood the proofs that cl(ri(C))=cl(C) and ri(cl(C))=ri(C). But to conclude that cl(C1)=cl(C2) iff ri(C1)=ri(C2) from the above two equalities? Do ...
1
vote
1answer
37 views

Problem in convex analysis

I found this problem in one of the old exams for convex analysis: Let $A \subseteq \mathbb{R}^n$ be a convex set and $f:A \rightarrow \mathbb{R}$ a convex function. a) Show that $f^{-1}(-\infty,a)$ ...
1
vote
1answer
209 views

Relative interior of the sum of two convex sets

I'd like to show ri(C1-C2)=ri(C1)-ri(C2) without using the fact that relative interior is preserved under linear transformations. I.e. Is there a way to show this by showing both inclusions?
2
votes
1answer
95 views

Affine hull of the intersection of two convex sets

Is it true that the affine hull of the intersection of two convex sets is the intersection of the affine hulls of these sets? Where the intersection of the two convex sets is non empty? Many thanks!
1
vote
1answer
34 views

Matrix convexity of -log

Is $-\log$ a matrix convex function? That is, taking the function $\log:(0,\infty)\rightarrow \mathbb{R}$ is the matrix inequality $$ \log\left((1-t)A+tB \right)\geq (1-t)\log A+ t \log B $$ satisfied ...
3
votes
0answers
48 views

Convex hull of the set of piecewise constant vectors

A piece-wise constant or blocky signal can be defined as follows Definition: Let $p,b\in\mathbb{N}$ such that $b\leq \left(p-1\right)$. Define the set of normalized blocky vectors as the following ...
0
votes
1answer
68 views

Show $f$ concave, $C^2$ implies $f''\leq 0$

Suppose I wanted to show that a concave function $f:(a,b) \to \mathbb{R}$ which is $C^2$ must have negative second derivative at each $x\in (a,b)$. I might try this by finite difference, noting that ...
2
votes
0answers
51 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
0
votes
1answer
30 views

Proportion of domain in which convex function is small

Let $K \subseteq \mathbb R^n$ be a compact convex set with volume $V$, and let $f: K \to [0,1]$ be a convex function with domain $K$. Assume that $\min_{x \in K} f(x) = 0$. I claim that, for every ...
1
vote
1answer
216 views

Convex hull of the union of two nonempty sets

I was reading about convex hulls on Wikipedia (Convex hull) and I read : $ Conv(A \cup B)= Conv(Conv(A) \cup Conv (B))$ where $A$ and $B$ are nonempty sets. I can see intuitively that this equality ...
0
votes
1answer
127 views

Does a convex function with a Lipschitz continuous gradient always have a strong convex conjugate?

I got the answer is 'Yes' from a scribe. But I am confused because: Suppose there is a convex function $f(x)=x^THx$, where $x\in\mathbb{R}^N$ and $H\in\mathbb{R}^{M\times N}$ is positive ...
3
votes
0answers
93 views

On convex functions being continuous

Every convex function is continuous. It usually says "draw this and it will become obvious that the epigraph is not convex. However, when I draw the epigraph of $f: [0,3] \to \mathbb{R}, f(x) = x^2$ ...
0
votes
2answers
40 views

Proving that a certain set is convex

I'm trying to prove that the set $W = \{x \in \mathbb{R}^2 : 2x_{1}^{2} + 3x_{2}^{2} \leq 4\}$ is convex. I've been trying to do this using the definition of W being convex when for all $x, y \in W $ ...
1
vote
0answers
54 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
1
vote
1answer
48 views

average of a bounded convex set

Suppose $X$ is a bounded convex set. We know that the average of any $n$ points of $X$, belongs to it, i.e. if $x_1, x_2, . . . , x_n \in X$ then $\frac{x_1+x_2+\cdots +x_n}{n}\in X$. How can we ...
4
votes
0answers
98 views

Characterization of Convex Polygons

John Lee's Axiomatic Geometry has an interesting characterization of convex and non-convex vertices for polygons. Let $P$ be a polygon. Consider a ray emanating from a vertex of $P$ which does not ...
0
votes
1answer
410 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
1
vote
1answer
803 views

Prove convexity of squared Euclidean norm

I need to prove that the square of the Euclidean norm is convex, so: $||\theta x+(1-\theta)y||^2\leq\theta||x||^2+(1-\theta)||y||^2$. Can I use the triangular inequality (if yes, how?) or should I ...
0
votes
1answer
68 views

A concept for measuring convexity of a set

I was wondering if there is such a concept for measuring the convexity of a set $S\subset \mathbb{R}^2$ (and similarly for $S\subset \mathbb{R}^n)$ with, say, $C^1$ boundary: For now let's assume ...
1
vote
1answer
92 views

Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
5
votes
1answer
265 views

Mean value staying in a convex or a subspace

Let $f : \mathbb{R}^n \to \mathbb{R}^m$ such that $\forall x\in \mathbb{R}^n$, $f(x)\in C$ where $C$ is a convex set of $\mathbb{R}^m$ (respectively $f(x)\in F$ where $F$ is a linear subspace of ...
0
votes
2answers
45 views

convexity and the interior sphere condition

Consider $\Omega $ a open, convex bounded subset of $R^n$. Let $x_0 \in \partial \Omega$. I believe that exists a open ball $B \subset \Omega$ such that $\partial B \cap \partial \Omega = \{ x_0 \}$. ...
2
votes
1answer
49 views

Proof inequality using convexity

I struggling with proofing an inequality. We have to show that $x - y \le (1-\theta)^{-1} x^\theta (x^{1-\theta} - y^{1-\theta})$ holds for all $x, y > 0, \theta \in [0, 1)$. Further we know that ...
0
votes
1answer
76 views

convex function and convex set

Let $f$ be a convex function from $R_{++}^n$ to $R$. If $f(x_i)\geq f(y_i)$, where $x_i,y_i$ in $R_{++}^n$, $i=1,2,...,n$. The question is: is the following inequality true: $$f(\sum_{i=1}^n a_i ...
1
vote
1answer
85 views

Question about relative interior of subsets in $\Bbb R^n$

I would love to get some hint or direction regarding this : If $S\subseteq T$, when $S,T$ are convex, and ${\rm ri}(S) \cap {\rm ri}(T) \neq \emptyset$ then ${\rm ri}(S) \subseteq {\rm ri}(T)$. ...