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
1answer
135 views

The two meanings of “convex hull”

Given a finite set of points $P$, we can think of two meanings for the term "convex hull of $P$:" The set of convex combinations of points from $P$, $\sum \alpha_i p_i$ s.t. $\sum \alpha_i = 1 ...
1
vote
0answers
95 views

minimum of the function over symmetric body

Let $X$ be a normed space. Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$. We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
3
votes
1answer
562 views

Why does positive semi-definiteness in this inequality imply a convex set?

I was reading a proof that rewrote an inequality in the form: $$b^Tx +x^T A x \le \alpha$$ for $b,x \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$, and with $A$ positive semidefinite. It then ...
2
votes
1answer
187 views

If a functions epigraph is a convex cone does this imply the function is convex?

I'm inclined to make this claim because the functions epigraph is $\{(x,t) : t \ge f(x)\}$. But to be a convex cone, it must be closed under the usual $$\theta_1 (x_1,t_1) + \theta_2 (x_2,t_2)$$ for ...
2
votes
1answer
91 views

Is the Chebyshev distance convex?

Consider the Chebyshev distance in two dimensions: $$ C[x,y] := \max\left(\text{abs}(x-x_0),\text{abs}(y-y_0)\right) $$ Is $C[x,y]$ a convex function of $(x,y)$? Now I think, say $\frac{dC[x,y]}{dx}$ ...
1
vote
5answers
249 views

Is closure of convex subset of $X$ is again a convex subset of $X$?

Today I was going through my text book exercise and got hold of the following question. Let $X$ be a normed linear space with norm $\lVert\cdot\rVert$ and $A$ is a non empty convex subset of $X$ ...
1
vote
1answer
102 views

Question about piecewise linear paths

I'm having trouble with a concept about piecewise linear paths. I've been looking on the net but I haven't found a definition of it. Consider a finite family of hyperplanes in a finite-dimension real ...
1
vote
3answers
127 views

Is the uniform distribution over a convex set log convex or log concave?

I read in Boyd's text that over convex $C$ such a distribution: $$f(x) = {1\over a} I_C(x)$$ for $I$ the indicator function for $C$ and $a$ the measure of $C$. And that taking $\log 0 = -\infty$ we ...
3
votes
2answers
742 views

Projection onto closed convex set

Show that the function defined by $f(t)=|P_{D}(x+td)-x|$ is nondecreasing, where $D$ is closed convex, $x\in D$, $t\geq 0$, $d\in \mathbb{R}^{n}$ and $P_{D}$ is projection onto D. I tried to solve ...
2
votes
1answer
53 views

notion of the minimum of a function over a polytope

Let $P$ be a polytope with $M$ vertices. (The polytope $P$ is the intersection of the hypercube $0≤x _j ≤1$ with the hyperplane $\sum_{j=1}^nx_j=t$, $0\leq t\leq n$). Suppose that the volume of $P$ ...
1
vote
2answers
953 views

How to judge a discrete function is convex or not?

Assume a discrete function $f\left(n\right)\geq 0$ for $n\in\mathcal{N}$. Can we say $f(n)$ is a convex function if $f(n+1)+f(n-1)-2f(n)\geq0$ ? I don't know why there is no such kind of expression ...
0
votes
3answers
544 views

Subspace is convex and closed set

Let $V$ be a vector space. Would you help me to prove that if $A$ is a subspace of $V$ then $A$ is convex and closed set. I can prove that $A$ is convex (it's easy) and try to prove that $A$ is ...
2
votes
0answers
412 views

Quasiconcavity for the sum of specific quasiconcave functions

I want to show that a function $ψ(a_1,a_0)$, which is separable (additively decomposed) in two quasiconcave functions, is also quasiconcave (QC). I know that the sum of QC functions is not generally ...
2
votes
3answers
263 views

Balanced but not convex?

In a topological vector space $X$, a subset $S$ is convex if \begin{equation}tS+(1-t)S\subset S\end{equation} for all $t\in (0,1)$. $S$ is balanced if \begin{equation}\alpha S\subset S\end{equation} ...
1
vote
2answers
354 views

Gradient of Moreau-Yosida Regularization

Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as $F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$ $Prox_f(x)=\arg\min_y ...
2
votes
1answer
287 views

Running average of a convex function is convex

Let $f(t)$ be a convex function and define $g(t)$ to be the running average of $f(t)$ $$g(t) = \frac{1}{t} \displaystyle\int_0^t f(\tau) ~d\tau$$ Then $g$ is convex. This is easy enough to prove ...
1
vote
0answers
63 views

A convex polynomial inequality.

Let $\phi(x)$ be a convex polynomial of degree $m$ at least two. Note that for $x,q \in \mathbb{R}$ $$\phi(x) + \phi(q) - 2\phi(\frac{x+q}{2}) = ...
8
votes
1answer
402 views

Sequence of convex functions

If a sequence of convex functions $\{ f_n \}$ on [0,1] converges pointwise to a continuous function f, then is the convergence uniform? The questions is almost identical to this one, except that the ...
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 ...
7
votes
4answers
883 views

Why is the affine hull of the unit circle $\mathbb R^2$?

In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $\mathbb R^n$ as $$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + ...
1
vote
0answers
83 views

Duality between extremal points and extremal maps

Suppose I have a convex set $C\subset\mathbb{R}^n$ such that $0\in C$ ad every Cauchy sequence in $C$ converges in $C$, but $C$ need not be bounded. (Actually I want unbounded $C$). Consider the set ...
0
votes
3answers
76 views

Membership based on maximum of a function over the set.

Let $S\subset \mathbb{R}^n$ and let $f(x)$ be a continuous function over $\mathbb{R}^n$. Furthermore, define $s_{\text{max}}:= \sup_{x\in S} \{f(x)\}$ and let $f(x)$ attain its minimum for at least ...
1
vote
3answers
208 views

How to show convexity of a ball in metric space?

If $(X,\|\cdot\|)$ is a normed linear space, then how to show any ball $B(x,r)$ is convex? I know that if $x,y\in A\subset V$ then $[x,y]\subset A$, where $A$ is a convex subset of vector space $V$ ...
2
votes
0answers
70 views

Term for intersection of lattice and convex region?

Is there a special term or convenient phrase for the restriction of a convex region to points of a lattice? This is motivated by wanting to talk about the feasible points of a discrete problem. I'd ...
0
votes
2answers
210 views

distance between a polytope point and a polytope vertex

How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)? How to find a distance from the farest polytope point to the closest ...
2
votes
2answers
336 views

How to compute the image of a polyhedron under a linear transformation

Suppose $P$ is a polyhedron whose representation as a system of linear inequalities is given to us: $$ P = \{ x ~|~ Ax \leq b\}$$ Define $P'$ be the image of $P$ under the linear transformation which ...
2
votes
1answer
113 views

Cancellation of addition on convex sets

I recently found a question about a property of the Minkowski sums. However the question was not properly answered (it used a projection argument which might not be true in a general Banach space). I ...
0
votes
1answer
271 views

Intersection of Two Simplices

How to find vertices a the polytope-intersection of two simplices, if I know the vertices of these simplices. More precisely: Let $T_1$ and $T_2$ be two regular $n-1$ dimensional simplices with ...
1
vote
1answer
84 views

Sub-Modular Set Function?

For a fixed set $B$ and for sets $A_i ,\forall i \in \left \{ 1,2,\dots,n \right \}$ , I define $f(A_i)=\frac{|A_i \cap B|}{2|A_i|-|A_i\cap B|}$, where $|A_i|>0$ is the cardinality of set $A_i$. ...
2
votes
1answer
70 views

Is this operator monotone?

Consider a convex optimization problem. $$\min_{u\in\Re^k} f(u)$$ s.t. $g_i(u)\leq0,\ i=1,\ldots,m$ Let ...
0
votes
1answer
148 views

Ball contained in a convex cone

Let $X$ be a Banach space. Let $C\subset X$ be a closed convex cone with nonempty interior. We denote by $B_X$ and $S_X$ the unit ball and the unit sphere of $X$ respectively. Let $e\in C\cap S_X$, ...
11
votes
2answers
603 views

How to show that $\mathbb R^n$ with the $1$-norm is not isometric to $\mathbb R^n$ with the infinity norm for $n>2$?

Could you please give me a hint to prove that $\mathbb{R}^n$ with the 1-norm $\lvert x\rvert_1=\lvert x_1\rvert+\cdots+\lvert x_n\rvert$ is not isometric to $\mathbb{R}^n$ with the infinity-norm ...
4
votes
1answer
124 views

Is it possible to 'approximate' compact, convex sets in $\ell^2$ by the Hilbert cube

Define $H=\{(x_n)_n\in\ell^2:|x_n|\le \frac1n, n\in\mathbf N\}\subset\ell^2$. This set is known as the Hilbert cube and it is well-known that $H$ is compact, convex and non-empty. Let ...
0
votes
1answer
121 views

How I can find an optimal solution for a model with concave-convex objective function?

My objective function is sum of three functions, 2 linear functions and a concave function ($1-\exp(x)$); constraints of my model are convex. How can I obtain optimal solution from this problem?
1
vote
1answer
184 views

Is concave quadratic + linear a concave function?

Basic question about convexity/concavity: Is the difference of a concave quadratic function of a matrix $X$ given by f(X) and a linear function l(X), a concave function? i.e, is f(X)-l(X) concave? ...
1
vote
1answer
793 views

Quadratic bounds on a convex function

Let $f: \mathbb{R}\rightarrow\mathbb{R}$ be a twice-differentiable convex function. It can shown be that for any $x_0 \in \mathbb{R}$: $f(x) \leq f(x_0) + (x-x_0)f'(x_0) + \frac{(x-x_0)^2}{2}$C ...
3
votes
1answer
516 views

Intersection of two (specific) convex functions

Given are the following two functions: $$g(z) = \left(z-2\right)\left(2+z\left(z-2\right)\right)$$ and $$h(z) = 2\left(z-1\right)^{2}\ln\left(z-1\right),$$ where $z>2$. I would like to show ...
0
votes
1answer
59 views

What is the connection between strong norms and norms coming from scalar products (in pre-hilbert spaces)?

In the best-approximation problem of seperation theorems in convex analysis, there is the notion of a "strong norm", in the sense that If $\| x^1 + x^2 \| = \| x^1 \| + \|x^2 \| $, $x_1 , x_2 ...
4
votes
1answer
163 views

Convex hull approximated from inside by only finite number of elements?

In approximating the convex hull "from inside", i.e. $$ \text{conv}S = \{ x \in \mathbb{R}^n \mid x= \sum_{i=1}^k \lambda_i x^i, x^i \in S, \lambda_i \geq 0, \sum_{i=1}^k \lambda_i= 1 \} ...
1
vote
1answer
93 views

Proving convexity of this set in $\ell^2$

This is a follow-up to the question I posted earlier this week. Consider, for a fixed sequence $(a_n)_n\in\ell^2$ the subspace $$C=\{(x_n)_{n}\in\ell^2 : |x_n|\le a_n\text{ for all ...
4
votes
1answer
289 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 ...
2
votes
0answers
73 views

Find a vector such that its matrix product is positive in every element

Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick ...
2
votes
1answer
113 views

Intersection of 2 $p$-simplices is a finite union of some $p$-simplices

I'm looking for a non-painful proof of this assertion. A p-simplex is defined as the set of all sums $\sum_{i=0}^p t_i x_i$ with $0\leq t_i\leq 1$, $\sum_{i=0}^p t_i=1$ for a geometrically ...
2
votes
1answer
242 views

Convex function on Banach space

Let $(Y,\|\cdot\|)$ a Banach space and $b\colon Y\to \mathbb{R}$ a nonnegative convex function such that, for some $\mathcal{E}>0$, the set $\{y\in Y\,:\, b(y)<\mathcal{E}\}$ is nonempty and ...
1
vote
3answers
112 views

Integral of exponential function

Consider $f$ being a measurable function on $R^n$ such that $$\int_{E} e^{|f|}=1$$ ($E$ measurable) and $f$ vanishes outside $E$ . Then $f\in L^p(R^n)$ for all $p\in (0,\infty)$. I tried using that ...
0
votes
0answers
91 views

Geometry of log-concave density functions and its distribution

Suppose $f:\mathbb{R}^n\rightarrow \mathbb{R}$ is log concave (density function). Consider now the antiderivative (distribution function) $F(t)=\int_{{ x\le t}}f(x)dx$, which is also log concave. We ...
1
vote
1answer
103 views

Where to find information on the Hilbert cube in $\ell^2$

The Hilbert cube $H$ in $\ell^2=\ell^2(\mathbb{R})$ is the subset given by $$H=\lbrace(x_n)=(x_1,x_2,\ldots)\in\ell^2:|x_n|\le2^{-n} \text{ for }n=1,2,\ldots\rbrace.$$ I've heard that ...
1
vote
2answers
89 views

Condition for convexity

Let $f:[a,b]\rightarrow \mathbb R$ be a continuous function such that $$\frac{f(x) - f(a)}{x-a}$$ is an increasing function of $x\in [a,b]$. Is $f$ necessarily convex? What if we also assume that ...
5
votes
2answers
185 views

Are countable intersections of convex sets convex?

Let $X$ be a Banach space $\{C_n\colon n\in\mathbb N\}$ a collection ofconvex sets in $X$. Is the set $$C=\bigcap_{n\in\mathbb N}C_n$$ convex?
1
vote
1answer
144 views

Is the following function convex?

Consider $1\le p,q < \infty , t\in \mathbb R , f,g>0$ then is $g(x)^q[f^pg^{-q} (x)]^t$ convex in the following context? Thanks for help .