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 (3)

4
votes
1answer
314 views

Is the variance concave?

Let $X$ be a discrete random variables with values in the set $\{x_1,\ldots, x_n\}\subset\mathbb{R}$. Denote by $p_i$ the probability that $X=x_i$. We can then regard the variance $Var(X)$ as a ...
4
votes
1answer
301 views

Cancellation law for Minkowski sums

Let $(X,\|\cdot\|)$ be a Banach space and $A,B,C\subset X$ closed bounded non-empty convex subsets. Let $+$ denote the Minkowski symbol for addition. Does the $+$ satisfy: $$A+C\subset B+C\implies ...
4
votes
2answers
270 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone.

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
4
votes
3answers
331 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
4
votes
1answer
156 views

Is the boundary of a compact convex set given by the union of its proper faces?

Let $C$ be a compact convex subset of a finite-dimensional real vector space $V$ with non-empty interior (where $V$ is equipped with the unique Hausdorff linear topology, i.e. with the standard ...
4
votes
3answers
2k views

how to decide if set is convex?

I have two variables, $x$ and $y$, and a few inequalities of the form $f(x,y) \le g(x,y)$. I want to know if the intersection of all $(x,y)$ that satisfy each inequality is convex. Is there some ...
4
votes
2answers
38 views

On a condition when bounded sets in $\mathbb R^n$ is convex ?

Is it true that a bounded set in $\mathbb R^n$ , $n>1$ , is convex iff every straight line through an arbitrary interior point of the set intersects the boundary of the set in exactly two points ? ...
4
votes
1answer
121 views

Axiomatic Bargaining: Nash's Solution

The following text is from the book: Bargaining and Markets by Osborne and Rubinstein, Academic Press Inc. Page 17 under the chapter The Axiomatic Approach: Nash's Solutions:. Two individuals can ...
4
votes
1answer
65 views

Let $S$ be a closed convex set & $x$ be an extreme pt of $S$ then $S-\{x\}$ is

Let $S$ be a closed convex set and $x$ be an extreme point of $S$, then $S-\{x\}$ is Convex Not Convex May or may not be convex I am thinking that the convexity doesn't fail even if we remove the ...
4
votes
2answers
106 views

On the convexity of a particular form of integrals

EDIT: I made some critical corrections below. Let $\mathcal{H}\colon\mathbf{w}\cdot\mathbf{x}+c=0$ be a hypeplane in $\mathbb{R}^n$. Also, let $g\colon\mathbb{R}^n\to\mathbb{R}_+$, be a non-negative, ...
4
votes
1answer
212 views

Convex Functions are Continuous

In W. Rudin's Principles of Mathematical Analysis, we read in Chapter 4 that real-valued functions defined on an open interval $(a,b)\subseteq\Bbb R$ are continuous (specifically, Exercise 23). I am ...
4
votes
2answers
116 views

Showing a quotient $\mathbb{Z}$ module is free

In Fulton's "Introduction to Toric Varieties" he repeatedly uses the following fact. Let $\sigma$ be a strongly convex rational polyhedral cone in a lattice $N$ and let $N_{\sigma}$ be the subgroup ...
4
votes
2answers
338 views

Volume of the projection of the unit cube on a hyperplane

Let $C_n\subset\mathbb{R}^n$ be the $n$-dimensional cube with side $1$, and let $P_k$ be any $k$-dimensional plane, $k\leq n$. What is the maximal $k$-volume $V_{n,k}$ of the projection of $C_n$ on ...
4
votes
2answers
628 views

Proof of an obvious fact about convex polygons.

Consider a closed simple polygon in the plane. It is intuitively obvious that the polygon is convex if and only if all the interior angles measure less than or equal to $\pi$ radians. I have never ...
4
votes
1answer
167 views

Is there a geometric argument that the Legendre transform of a convex function is convex?

I am trying to build intuition on Legendre transforms. Arnold's Mathematical Methods of Classical Mechanics has some nice geometric interpretations, but he does not provide a proof that the Legendre ...
4
votes
1answer
371 views

Hausdorff distance via support function

Let $A$ and $B$ be convex compact sets in $\mathbb{R}^n$. Define $$ h_{+}(A,B) = \inf \left\{ \varepsilon > 0 \mid A \subseteq B+\mathbb{B}_{\varepsilon} \right\} $$ where ...
4
votes
1answer
105 views

Is this function convex when the input vector is positive?

I am wondering if $f(\mathbf{x})$ is convex on the input of a vector of $n$ positive reals $\mathbf{x}$: $$f(\mathbf{x})=\operatorname{Tr}[(\mathbf{A}+\operatorname{diag}(\mathbf{x}))^{-1}]$$ where ...
4
votes
2answers
335 views

Convexity of inverted sum of positive definite matrices

I am currently working with a class of functions, where every function looks like $f(x)=v^T(xA+(1-x)B)^{-1}v,$ where $v\in\mathbb{R}^n$ is an arbitrary vector, $A,B \in \mathbb{R}^{n\times n}$ are ...
4
votes
1answer
506 views

Differentiability of Moreau-Yosida approximation.

I want to show that if $X$ is a reflexive Banach space with norm of class $\mathcal{C}^1$ and $f\colon X\to\mathbb{R}\cup \{+\infty\}$ is convex and lower semicontinuous, then $f_{\lambda}$ is ...
4
votes
1answer
885 views

Proving Helly's theorem

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality. Helly's theorem Let $B_{1},...,B_{m}$ be a collection of convex ...
4
votes
1answer
114 views

Describing a set of normals

In a finite dimensional (think Euclidean) ambient space, let $S$ a compact, convex set and $x$ not in $S$. The two sets can be (weakly) separated, i.e. there exists a vector (normal) that defines a ...
4
votes
1answer
31 views

Image of a bounded sequence by a convex continuous function in a Banach space

Let $(X, \Vert \cdot \Vert)$ be a Banach space, and $f : X \longrightarrow \mathbb{R}$ a convex function, continuous for the norm topology. Suppose that $x_n$ is a sequence which weakly converges to ...
4
votes
1answer
48 views

When the closure of a convex set contains a ball

Suppose $C$ is a convex set in $\mathbb{R}^n$ whose closure contains the open ball $B(x,r)$. Is it true that $C$ contains $B(x,r)$? Motivation: I am asking this because something like this seems to ...
4
votes
2answers
155 views

Product / GM of numbers, with fixed mean, increase as numbers get closer to mean.

I am trying to prove a statement which goes like this. Let $a_i$ and $b_i$ be positive real numbers where $i = 1,2,3,\ldots,n$; where $n$ is a positive integer greater than or equal to $2$, such ...
4
votes
2answers
218 views

Maximizing a ratio of convex matrix functions by minimizing a difference?

Given that $g(.),h(.)$ are twice-differentiable convex quadratic real functions whose domain is the set of all real matrices while the range is the set of positive real numbers, then: Is maximizing ...
4
votes
1answer
119 views

Convexity of Exponential Composite Function

$f:\mathbb{R}_{+}^M\rightarrow\mathbb{R}_+$ is a convex analytic function. For $\mathbf{x}\in\mathbb{R}_{+}^M$ and $y\in\mathbb{R}_{+}$, consider the function ...
4
votes
1answer
204 views

strict convexity with a measure theoretic property

Suppose $(x_n)$ is a positive sequence of reals converging to $x$. Furthermore we have a measure space $(E,\mathcal{E},\mu)$ given, with finite measure $\mu$. There are a measurables nonnegative and ...
4
votes
2answers
113 views

$\int_0^1 u(t)\phi''(t)dt \geq 0,\ \forall \phi\in C_0^1((0,1)), \ \phi\geq 0$. Is $u$ convex?

Suppose that $u\in C([0,1])\cap C^1((0,1))$ satisfies for all $\phi\in C_0^2((0,1))$, $\phi\geq 0$ $$\int_0^1 u(t)\phi''(t)dt \geq 0$$ Can we conclude that $u$ is convex? Note: $C_0^2((0,1))$ is ...
4
votes
1answer
192 views

Convex Alternatives to the Gamma Function?

The Bohr-Mollerup Theorem states that the gamma function is the unique function $f: (0, \infty )\rightarrow \mathbb{R}$ satisfying $f(1)=1,$ $f(x+1) = x f(x),$ and the condition that $\log f$ is ...
4
votes
1answer
252 views

Effect the zero vector has on the dimension of affine hulls and linear hulls

I am currently working through "An Introduction to Convex Polytopes" by Arne Brondsted and there is a question in the exercises that I would like a hint, or a nudge in the right direction, please no ...
4
votes
1answer
69 views

Visualizing Euclidean Algorithm in $\mathbb{Q}(\sqrt{-7})$ and $\mathbb{Q}(\sqrt{-11})$ with Convex Geometry

In an attempt to answer one of the bounty questions, I have started picturing Euclidean division in quadratic fields. In theory we would like the equation: $$ a = b\,q + r ...
4
votes
0answers
25 views

Is a convex salient cone necessarily contained in an open half-space?

A cone $C$ in $\Bbb R^n$ is said to be salient if it does not contain any pair of opposite nonzero vectors; that is, if and only if $C \cap (-C) \subset \{0\}$. Obviously, a cone $C$ such that that ...
4
votes
1answer
116 views

Prove a certain property of linear functionals, using the Hahn-Banach-Separation theorems

I've been trying to solve this question, with no luck so far: Let $X$ be a real linear space, and $\{\|\cdot \|_i\}_{i=1}^{n}$ family of norms on $X$. Let $f$ be a linear functional on $X$ such that ...
4
votes
0answers
85 views

Convexity of $S=\left\{ \frac{\underline{x}^HA\underline{x}}{\underline{x}^H\underline{x}} , \underline{x} \in \mathbb C ^{n}\right\}$

i've to prove that the following set is convex: Let $A \in \mathbb{C}^{n \times n}$ $$S=\left\{ \frac{\underline{x}^HA\underline{x}}{\underline{x}^H\underline{x}} , \underline{x} \in \mathbb C ...
4
votes
0answers
311 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
98 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 ...
4
votes
0answers
110 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 ...
4
votes
0answers
107 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
2answers
103 views

Convexity of polylogarithms

I want to prove the following proposition: The function $w\to (-Li_{5/2}(-e^w))^{2/5}$ is convex on $\mathbb R$. And, as I think, the same is true for the function $w\to (-Li_{p}(-e^w))^{1/p}$ for ...
4
votes
0answers
79 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
1answer
84 views

Is there a notion of 'pre-convex' sets?

A set $A$ in $\mathbb{R}^n$ is convex if for any two points $p,q \in A$ and real $\lambda \in [0,1]$, the point $\lambda p + (1-\lambda)q$ is also in $A$. There are many beautiful theorems about ...
4
votes
0answers
68 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
117 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
1answer
149 views

Convexity of a Given Function

Is the following function convex or concave? $$f(\mathbf{x}) = \frac{1}{N}\sum_{i=1}^N\sqrt{1+\frac{x_i^2}{\left(\frac{1}{N}\sum_{i=1}^{N}x_i\right)^2}},$$ $\mathbf{x} = [x_1,x_2,...,x_N]^T, x_i \ge ...
4
votes
0answers
280 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
81 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
3answers
245 views

Prove one set is a convex hull of another set

Define two sets: $A = \{x \in \{0,1\}^n : \lVert x \rVert_1 \leq k\}$ is a finite set of binary vectors; $B = \{x \in [0,1]^n : \lVert x \rVert_1 \leq k\}$ is an infinite set of real-valued vectors, ...
4
votes
1answer
87 views

A question about pyramids (polytopes)

Let's use the following definition of a face: A nonempty convex subset $F$ of a convex set $C$ is called a face of $C$ if $\alpha x + (1-\alpha) y \in F$ with $x, y \in C$ and $0 < \alpha < 1$ ...
3
votes
2answers
364 views

Are convex hulls of closed sets also closed?

If $X$ is a compact set in $\mathbb R^n$, how can we show that $\operatorname{conv} X$ is compact as well? Can we say something similar without assuming boundedness, i.e., are convex hulls of closed ...
3
votes
3answers
582 views

Show by example that the Minkowski sum of two sets $X+Y$ may be convex even if neither $X$ nor $Y$ are convex

There were two parts to this question. I proved that the Minkowski sum of two sets $X+Y$ is convex whenever $X$ and $Y$ are convex, but how do I prove this second part? "Show by example that the ...