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)

9
votes
2answers
1k views

The measurability of convex sets

How to prove the measurability of convex sets in $R^n$ ? I have seen a proof, but too long and not very intuitive.If you have seen any, please post it here.
3
votes
0answers
250 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 ...
0
votes
1answer
132 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?
0
votes
2answers
41 views

Convexity of a function and constraint

Consider the quadratic function $f(x_1,x_2,x_3,x_4)=x_1+2x_2+4x_4+x_1^2+5x_2^2+3x_3^2x_4^2-4x_1x_2-2x_2x_3+2x_3x_4$. Is f a convex function? Consider a constraint defined using the above function f: ...
4
votes
1answer
292 views

Convex combination

Assume that $I$ is a countable set, and we have $u_i\in \mathbb{R}^n$ for $i\in I$. Suppose that $v=\sum_{i\in I} a_i u_i$ and $\sum_{i\in I}a_i=1$ and $a_i\geq 0$. Can one show that there exists a ...
6
votes
1answer
699 views

Convex hull of an open set…

Let $K$ be a compact convex subset of locally convex topological vector space $E$. Let $U$ be an open subset of $K$. Is $conv(U)$ (the convex hull of $U$) an open subset of $K$ ? You see, it is ...
1
vote
0answers
96 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 ...
11
votes
2answers
2k views

Dual of a dual cone

Any hint on how to prove the following please: Let $K$ be a convex cone, and $K^*$ its dual cone. Prove that $K^{**}$ is the closure of $K$. Thanks!
3
votes
3answers
1k views

Using the definition of a concave function prove that $f(x)=4-x^2$ is concave (do not use derivative).

Let $D=[-2,2]$ and $f:D\rightarrow \mathbb{R}$ be $f(x)=4-x^2$. Sketch this function.Using the definition of a concave function prove that it is concave (do not use derivative). Attempt: ...
3
votes
2answers
809 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
138 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 ...
3
votes
1answer
645 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
213 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
93 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
1answer
104 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 ...
3
votes
1answer
136 views

Can all convex polytopes be realized with vertices on surface of convex body?

Each convex polytope $P$ has a combinatorial type, its so-called face lattice. This lattice is just the poset of all faces of $P$ ordered by inclusion. Given one realization of such a combinatorial ...
1
vote
3answers
145 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 ...
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
1k 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 ...
1
vote
3answers
607 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
442 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
283 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
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 ...
8
votes
1answer
451 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 ...
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 ...
2
votes
1answer
313 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
138 views

Panel structure on epi F**

It is known that, generically, the convex hull of a hypersurface embedded in $\mathbb{R}^n$ has a panel structure of simplices. Of course one can construct embeddings where this is not the case, but ...
1
vote
0answers
65 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}) = ...
3
votes
0answers
75 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 ...
1
vote
1answer
907 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 ...
2
votes
1answer
1k views

Intersection of two (related) concave functions

Question: In general, two concave functions intersect at at most two points. True or False? If false, can you please provide an example. If true, can you please provide a proof. Proving or disproving ...
0
votes
3answers
77 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 ...
2
votes
0answers
75 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 ...
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 ...
4
votes
1answer
297 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
1answer
166 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 \} ...
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
291 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
91 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$. ...
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$, ...
2
votes
1answer
73 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 ...
11
votes
2answers
656 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 ...
2
votes
1answer
494 views

Proximal mapping for composition of functions

Suppose I have a convex function $f(x)$ for which I can easily compute the proximal mapping prox$_f(z) = \arg\min_{x} f(x) + \frac{1}{2}||x-z||^2_2$ is there a simple expression for the proximal ...
4
votes
1answer
128 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 ...
1
vote
1answer
201 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? ...
2
votes
1answer
126 views

Projection of convex polytope

I have a convex polytope $P$ in $R^2$ of $\dim P = \dim\operatorname{aff} P = 2$, $\dim\operatorname{aff}P$ is the dimension of the affine hull of $P$. Let $L$ be the line orthogonal to the normal ...
3
votes
1answer
584 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 ...
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 ...
6
votes
0answers
607 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 ...