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)

0
votes
2answers
399 views

What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
1
vote
0answers
47 views

General properties of an optimal solution of a convex program

How do we seek certain properties for a solution of a convex minimization problem. For example we want to make sure if the below objective has a symmetric optimal solution: \begin{equation} \min_X ...
1
vote
1answer
35 views

Approximating from the interior of a convex set

In a problem I'm working on I found myself with a point $y\in \mathbb{R}^m$ lying at the boundary of a non-closed convex set $K$. I'd like to express it as as "infinite convex combination" ...
5
votes
2answers
118 views

Why such a function is convex?

Let $f:(a,b)\rightarrow \mathbb R$ be a continuous function satisfying: $$ f(x) \leq \frac{1}{2h} \int_{x-h}^{x+h} f(t) dt $$ for all $x,h$ such that $a\leq x-h<x+h \leq b$. How to show that $f$ ...
0
votes
3answers
78 views

lower bound of a special type of convex functions

Suppose $f$ is a convex, differentiable and $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$. The minimum of $f$ is $0$. ($f$ may not be twice differentiable.) How to show $f(x)\geq\frac{1}{2L}\|\nabla ...
0
votes
1answer
63 views

Is the closure of a set contained in the convex hull?

Let $A\subseteq\mathbb{R}^d$. Do we have $\bar A\subseteq \text{conv}(A)$?Counterexample?
2
votes
3answers
68 views

$\varepsilon$-balls and closed convex sets

I arrived at the following problem during the day. For $\iota\in I$, let $A_\iota\subseteq\mathbb R^d$ be non-empty and closed. For $\varepsilon>0$ let $B_\varepsilon(A_\iota)=\bigcup_{x\in ...
4
votes
2answers
868 views

closure, convex hull and closed convex hull

Is the closure of the convex hull of some set $A\subseteq\mathbb R^d$ equal to the convex hull of the closure of $A$, i.e. $$\text{cl}(\text{conv}(A))=\text{conv}(\text{cl}(A))?$$ If not, what are ...
2
votes
0answers
121 views

A question related to Helly's Theorem on convex sets

I have one question related to differential geometry. Initilally, I am giving some background and my question is after that. Helly's Theorem Let C be a finite family of convex sets in $R^n$ such ...
0
votes
0answers
181 views

Convex Functions on 2 variables over an interval

It is required to show that $f(x) = x_1x_2$ is a convex function on $[a,ma]^T$ where $a\ge 0$ and $m\ge1$.To show convexity we need to show that for $\lambda \in [0,1]$: $f(\lambda x + (1-\lambda ...
1
vote
1answer
125 views

Does every convex-linear map have an affine extension?

There is one step in a proof which I don't manage to show, although it seems to be very easy. Let $A, B$ be real vector spaces, let $S \subset A$ be a convex set and let $\text{aff}(S)$ be its affine ...
2
votes
1answer
20 views

What is the coX of the following

What is the coX of {(x,y) $\in$ $\mathbb R^2$ : y = $1\over1+x$, $x \ge 0$ } ? coX is the convex hull. I couldn't figure out. coX should be the smallest convex set that contains the set but in ...
2
votes
1answer
63 views

Minimal point of a intersection of N convex sets

I would like to prove that the minimal point of a intersection of $N$ convex sets in $\mathbb{R}^2$ is also the minimal point of the intersection of two of the aforementioned sets. Rephrasing the ...
2
votes
1answer
63 views

Are all polytopes also convex hulls?

It seems, at least in the 2-D case, that all polytopes are going to be convex. Does this hold if the dimensions are increased?
2
votes
0answers
60 views

Prove that $\text{int}(\text{dom}(f))$ is a convex set.

Let $f$ be a convex function. I have to prove that $\text{int}(\text{dom}(f))$ is a convex set. (Be careful with $-∞$ )
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 ...
1
vote
0answers
66 views

One to one correspondence in faces of convex sets

Let $C$ be a nonempty convex subset of $\mathbb{R}^{n}$, and let $L$ be a nonempty subspace contained in lin$C.$ Define $C_0$ tobe $C \cap L^{\perp}.$ Show that the faces $F$ of $C$ are in one-to-one ...
4
votes
2answers
417 views

Weakly convex functions are convex

Let us consider a continuous function $f \colon \mathbb{R} \to \mathbb{R}$. Let us call $f$ weakly convex if $$ \int_{-\infty}^{+\infty}f(x)[\varphi(x+h)+\varphi(x-h)-2\varphi(x)]dx\geq 0 \tag{1} $$ ...
1
vote
0answers
92 views

Recognizing binomial mixtures

I'd like to know a procedure to recognize whether a given probability distribution over outcomes $\{0, \dots, n\}$ can be expressed as a mixture of $n$-trial binomial distributions with different ...
2
votes
2answers
276 views

fail of cantor intersection property on closed , bounded , convex sets of integrable functions

This is from my recent homework. I am asked to find a descending nested sequence of closed , bounded , nonempty convex sets $\{D_n\}$ in $L^1(\mathbb{R})$ such that the intersection is empty , where ...
2
votes
1answer
258 views

cantor intersection theorem in banach space

Here is part of the question in my HW. Let$\ \{C_n\}\subset X $ be a bounded nested decreasing sequence of closed and convex sets. I am asked to show that $\bigcap C_n \not= \emptyset$ iff X is ...
4
votes
1answer
637 views

Continuity of a convex function

I'm trying to solve the following problem: Let $f:K\rightarrow \mathbb{R} $, $f$ convex and $K \subseteq \mathbb{R}^n$ convex. Then $f$ is continuous on $K$. I have proved the only case $n=1$, but ...
4
votes
1answer
140 views

Prove that f is continuous

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function on $\mathbb{R}^n$. How to prove that $f$ is continuous?
1
vote
1answer
124 views

Show the existence and uniqueness of a closed ball containing a bounded subset of a Hilbert space

The problem: Assume $A$ is a bounded subset of a Hilbert space $H$. Let $r$ be the infimum of the radii of closed balls containing $A$, so $r = \inf \{s \geq 0 $ $\vert$ there exists $x \in H$ such ...
1
vote
1answer
666 views

How to prove that the closed convex hull of a compact subset of a Banach space is compact?

Can anyone help me with this problem? Prove that if $K$ is a compact subset of a Banach space $X$, then the closed convex hull of $K$ (that is, the closure of the set of all elements of the form ...
1
vote
1answer
115 views

Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
5
votes
2answers
468 views

Are Legendre transforms of non-convex functions useful?

Do Legendre transforms have any applications that do not appeal to convexity? What is the intuitive interpretation of the Legendre transform of a non-convex function?
1
vote
1answer
152 views

Proof that a coordinate-wise convex function is convex?

I feel like this should be straightforward, but does anyone have a proof of the following? Let $f: \mathbb{R}^n \to \mathbb{R}$ satisfy the following. For each coordinate $i$, for an arbitrary vector ...
2
votes
1answer
1k views

Relation between Positive definite matrix and strictly convex function

I have a problem. From wikipedia http://en.wikipedia.org/wiki/Positive-definite_matrix any function can be written as $$z^TMz$$ where z is a column vector and M is a symmetric real matrix. However ...
4
votes
1answer
209 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 ...
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 ...
4
votes
1answer
138 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 ...
3
votes
0answers
221 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
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: ...
8
votes
2answers
820 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.
4
votes
1answer
254 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 ...
2
votes
4answers
383 views

definition of strongly convex

There are several equivalent definitions for strongly convex. For example, some literature said: A function $f$ is strongly convex with modulus $c$ if either of the following holds $$f(\alpha ...
6
votes
1answer
527 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 ...
2
votes
1answer
130 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
94 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
433 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
164 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
83 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
192 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
89 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
111 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
631 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
52 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$ ...
0
votes
2answers
752 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
416 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 ...