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)

18
votes
0answers
454 views

How many points of intersection between an ellipse and an $L_p$-circle?

Consider an ellipse $E$ in the plane, centered at the origin. (In my case, the minor axis points into the nonnegative quadrant.) Let S be an "$L_p$-circle": $S = \{(x,y) : |x|^p + |y|^p = 1\}$, ...
7
votes
0answers
234 views

Theorem about convex sets

I want to prove a theorem (the link is after the whole text here) and in order to do that I need to prove three preliminary statements. I tried to prove them all but I'm already stuck in the first, ...
7
votes
0answers
153 views

What is the shape of the convex $n$-gon which gives the maximum of a function?

Supposing that the length of every edge of the convex $n$-gon $P_1P_2$$\cdots$$P_n$ is 1, what is the shape of the $n$-gon which gives the maximum of the following function $A_n$? ...
6
votes
0answers
177 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
6
votes
0answers
735 views

Farkas Lemma proof

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia: Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
6
votes
0answers
241 views

Behaviour at infinity of a function in terms of first and second derivatives

In a paper (dealing with spectra of certain Schrodinger operators) I found the following assumption for a function $f\in C^\infty(\mathbb R^n;\mathbb R)$: there exists a constant $C>0$ and a ...
5
votes
0answers
70 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
5
votes
0answers
511 views

Gauss-Lucas Theorem (roots of derivatives)

Gauss-Lucas Theorem states: "Let f be a polynomial and $f'$ the derivative of $f$. Then the theorem states that the $n-1$ roots of $f'$ all lie within the convex hull of the $n$ roots ...
5
votes
0answers
199 views

How does one compute a bounding simplex for a set of points?

An algorithm I've implemented to tessellate an N-dimensional space requires starting with a bounding N-simplex. Given a set of $k$ points $S_{0..k-1} \subset R^N$ is there a procedure to find a ...
4
votes
0answers
228 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
4
votes
0answers
81 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 ...
4
votes
0answers
94 views

On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has coordinate-wise Lipschitz constant $M$ (meaning that for all ...
4
votes
0answers
75 views

Space of solutions to $f(x+y) = f(x) + f(y)$ when $f$ is convex

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a nonlinear convex function, and let $x\in\mathbb{R}^n$ be an arbitrary vector. Define the set $\Omega_f(x)$ as $\Omega_f(x) \triangleq ...
4
votes
0answers
50 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
4
votes
0answers
81 views

Cyclically monotone sets on four points

A subset of $\mathcal{X} \times \mathcal{Y} \subset \mathbb{R}^d \times \mathbb{R}^d$ is cyclically monotone if $\sum_{i=1}^n \langle x_i,y_i\rangle \ge \sum_{i=1}^n \langle x_i,y_{i+1}\rangle$, where ...
4
votes
0answers
179 views

Convexity of cubic vector function?

First question in these forums so go easy on me. I have a function $f_i(x):\mathbb{R}^N\to\mathbb{R}$ which is defined by $$f_i(x) = \frac{(x^TAe_i)x^TAx}{(x^TA+b^T){\bf 1}}$$ where ...
4
votes
0answers
80 views

Find optimal measure

Let $\Omega$ be a convex compact set in $\mathbb{R}^n$, $f\colon \Omega \to \mathbb{R}$ be a convex function. Consider an optimization problem $$ \int\limits_{\Omega}f(x)\,\mu(dx) \to ...
4
votes
0answers
419 views

Is every convex-linear map an affine map?

Let's say that a map $f: V \rightarrow W$ between finite-dimensional real vector spaces is convex-linear if $f(\lambda x + (1-\lambda)y) = \lambda f(x) + (1-\lambda)f(y)$ for all $\lambda \in [0,1]$. ...
3
votes
0answers
89 views

Non-trivial compatibility which makes convex functions continuous on $\Bbb R$

Here are the definitions: Let $X$ be a set. Another set $\mathcal C\subseteq \mathcal P(X)$ is called a convexity over $X$ if $\varnothing, X\in\mathcal C$ $\mathcal C$ is closed under arbitrary ...
3
votes
0answers
53 views

What is the smallest possible angle of this polygon?

A convex polygon contains a square with side-length 1 and is contained in a parallel square with side-length 2. What is the smallest possible angle of the polygon? What is its smallest possible area? ...
3
votes
0answers
50 views

Is it always possible to partition a fat shape to fat shapes?

The slimness factor of a geometric 2-dimensional shape is defined (for this question) as the ratio of the side-length of its smallest enclosing square to the side-length of its largest enclosed ...
3
votes
0answers
93 views

What are the extreme points of the set of probability measures on $(\mathbb N, \mathcal{F})$?

Say, we have some $\sigma$-algebra on $\mathbb N$ and let $\mathbb P$ be the set of all probability measures on it. We know that $\mathbb P$ is convex, so I wonder how do the extreme points look like. ...
3
votes
0answers
77 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$ ...
3
votes
0answers
56 views

Biggest ellipse included in a convex polygon

Considering a N edges convex 2D polygon called P. Let's name its vertices $\{p_1, p_2, ..., p_N\}$ described in a counter-clockwise order, with $p_i = (x_i, y_i)$ What would be, and how would one ...
3
votes
0answers
40 views

Random convex shapes containing a ball

I'm interested in the properties of randomly generated convex shapes in $n$-dimensional space. Suppose I were to generate $v$ uniformly distributed random points on the $n$-ball of radius $R$. What ...
3
votes
0answers
83 views

Number of supporting hyperplanes

I know that, for any convex set $S$, there is at least one supporting hyperplane at every point in $B$, the boundary of $S$. Also, there can be more than one supporting hyperplane at the same point in ...
3
votes
0answers
82 views

Averages of a Function

Let $(X,M,\mu)$ a measure space and $f:X \rightarrow \mathbb{C}$ a function in $L^{\infty}(\mu)$. Define $A_f$ as the set of all averages \begin{equation} \frac{1}{\mu(E)} \int_{E} f d \mu ...
3
votes
0answers
100 views

Does convexity of a function guarantee tractability of finding its minimum?

Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not. ...
3
votes
0answers
45 views

Need $f:[0,\infty)\to[0,\infty)$ such that $f$ is not convex but $f(x^p)$ is for $p>1$.

To be more specific I need to find an $f:[0,+\infty)\to[0,+\infty)$ which satisfies the following: (somewhat trivial stuff) The function $f$ is continuous, nondecreasing, there exists $k>0$ such ...
3
votes
0answers
83 views

When is a sequentially closed cone, closed?

Let $X$ be a locally convex, Hausdorff topological vector space and $C\subseteq X$ a convex cone, which is sequentially closed. What are criteria, that would imply that $C$ is closed (in the topology ...
3
votes
0answers
67 views

maps from a convex set to itself

Suppose $S\subset \mathbb{R}^n$ be a closed convex set under Euclidean topology (but not necessarily bounded, example a closed cone). Let $\mathcal{E}(S)=\{L:\mathbb{R}^n\rightarrow \mathbb{R}^n\text{ ...
3
votes
0answers
90 views

On the duality gap for quasiconvex optimisation problems

This stack exchange question got me thinking about quasiconvex analysis. Given a compact,convex subset $X\subset \mathbb{R}^n$ and a quasiconvex function $f:X\rightarrow \mathbb{R}$ Define the ...
3
votes
0answers
80 views

Two convex cones

Consider a convex cone $C$ (in some real vector space), with $C_1$ a convex subcone. I'm led to study elements $v\in C_1$ with the following "relative form" of extremality: if $v=x+y$, with $x,y\in ...
3
votes
0answers
229 views

Convex analysis books and self study.

I have taken some courses in Convex optimization. Now I would like to know a little bit more about the pure mathematical side. Is there any good books in convex analysis? I have read and worked with ...
3
votes
0answers
187 views

How to show that a function is piecewise linear

Let z(t) = min $(c+t d)^T x$ s.t $Ax <= b$ Show that Z(t) is a concave, piecewise linear function of t. I'm really not sure how to even start proving this, I would really ...
3
votes
0answers
41 views

Show that maximisers are in corners

Let $\Pi$ be a rectangle $[a,b] \times [c,d]$ containing $0$: $a < 0 < b$, $c < 0 < d$, let $f(x)$ be a convex continuous function on $\Pi$. Define a functional $$ J(x_1,x_2,x_3) = p_1 ...
3
votes
0answers
50 views

Convex functions: bounding the difference

Suppose you are given a convex function $f: R^d \rightarrow R$. Let us say you are given $x,x' \in R^d$ and there are $x_1, x_2, \ldots, x_n \in R^d$ such that $$\sum_{i=1}^n (x_i - x') = x - x'.$$ ...
3
votes
0answers
217 views

Global optimum of sum of convex functions

Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given $a, b \in ...
3
votes
0answers
73 views

packing for the polytope

Let $X=(X, \|\cdot\|)$ be some normed space. Let $C=[-1,1]^n$ and $H$ be a plane with equation $\sum_{i=1}^nr_i=s, 1\le s\le n.$ (Here $r_i$ are such that $Proba(r_i=1)=Proba(r_i=-1)=1/2$). The ...
3
votes
0answers
99 views

“Round” regions on surface of convex polytope

A convex $d$-polytope $P$ is the convex hull of finitely many points. Given such a polytope with $n \gg d$ vertices, I would like to prove that its surface has to be "round" in some region. Let me ...
3
votes
0answers
281 views

Jensen's Inequality for complex functions

Jensen's inequality states that if $\mu$ is a probability measure on $X$, $\phi$ is convex, and $f$ is a real-valued function, then $$ \int \phi(f) \, d\mu \geq \phi\left(\int f \, d\mu\right).$$ Is ...
3
votes
0answers
78 views

Extreme rays of totally monotone function's cone

A smooth function $f \colon \mathbb{R}^{n}_+ \to \mathbb{R}_{+}$ is said to be totally monotone iff $(-1)^{| \alpha|} \frac{ \partial^{| \alpha |} }{\partial^{\alpha}x} f(x) \geq 0$ for any ...
3
votes
0answers
72 views

Using convexity and separation to prove bounds on norm bound functionals

I'm quoting here a homework problem with two clauses. I've already managed to find a solution for the first clause, and have problems generalizing it for the second clause, I'll go into details after ...
3
votes
0answers
61 views

What proofs are based/use/depend on existance convex hull or convex envelope?

I wonder if there are any is at least one proof of any mathmatical fact that would use convex hull or convex envelope as mathmatical object valuable for that proof?
3
votes
0answers
368 views

Modification of Mazur's lemma

Working through Brézis and solving an exercise I have a question about my solution. It's well known that, if $x_n$ converges weakly to $ x $ in a Banach space $X$, then there exists a sequence ...
3
votes
0answers
367 views

a function and its epigraph

The epigraph of a function $f:\mathbb{R}^{n}\to [-\infty,+\infty]$ is the set of points $(x,\mu)\in\mathbb{R}^{n+1}$ satisfying $f(x)\leq \mu$, and is denoted by $\mathrm{epi}(f)$. I somehow got ...
2
votes
0answers
45 views

Krein-Milman theorem

Let $E$ be a Riesz space with order unit $u$. With $$\left\|f\right\|_u: = \inf\{\lambda \in [0,\infty): -\lambda u\leq f\leq \lambda u\} $$ $E$ becomes a normed space. The following sets are subsets ...
2
votes
0answers
35 views

Lower semicontinuity of a Bochner integral of a convex function

I'm looking for the following result: Let $\Omega \subset \mathbb{R}^n$ be a bounded domain and let $f$. The map $$u \mapsto \int_0^T \int_{\Omega} f(u(t))$$ is lower semicontinuous for $u \in ...
2
votes
0answers
22 views

Convexity in each argument and directional derivative

Let $f(x,y)$ be a continuous function, convex in each argument separately. Does this imply the existence of one-sided directional derivatives in any direction? For example, does there exist (finite or ...
2
votes
0answers
119 views

Convex subsets, Normed spaces, Separating hyperplane

I'm trying to understand the proof of a theorem taken from a textbook. Theorem: If $S_1,S_2$ are disjoint non-empty convex subsets of a real vector space $X$ (which may be infinite dimensional) then ...