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)

-1
votes
1answer
26 views
2
votes
1answer
35 views

Convex open neighborhood of compact convex subset

I'm stuck on what ought to be a straightforward topology problem. Say $X$ is a compact convex subset of a locally convex space (everything in sight is assumed Hausdorff). Say $Y\subseteq X$ is a ...
2
votes
1answer
41 views

Boundedness condition of Minkowski's Theorem

Statement: "Let L be a lattice in $R^n$ and $S\subset R^n$ be a convex, bounded set symmetric about the origin. If $Volume(S) > 2^ndet(L)$, then S contains a nonzero lattice vector. Moreover, if ...
0
votes
1answer
36 views

Weighted least squares with nuclear norm minimizaiton, how to optimize?

Nuclear norm minimization is very popularization and formulation is least squares term with nuclear norm term as following, $$\min\limits_{X} ...
1
vote
1answer
22 views

Proximal Operator of $\ell_{\infty,1}$ norm of a matrix

How can I calculate the proximal operator of mixed norm $\ell_{\infty,1}$ for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_{\infty,1} + \frac{1}{2\tau} ||X-Y||_F^2$ where ...
1
vote
0answers
31 views

Gluing two strongly convex function

Definition: We call $f:\mathbb{R}^n\rightarrow \mathbb{R}$ a $\lambda$-strongly convex function iff for every $x,y\in \mathbb{R}^n$ and $t\in[0,1]$ it follows $$f(tx+(1−t)y)\leq ...
-1
votes
2answers
57 views

Triangle Inequality Like Equation [closed]

If we are in $R^2$ and define $d(a,b)$ as the set of points between $a$ and $b$ we can create an equation like this: $$d(x,z) \subseteq d(x,y) \times d(y,z)$$ where the $\subseteq$ is the subset ...
0
votes
0answers
16 views

min max duality

I have been introduced min max duality. When i have a problem : $f:X \to R$ $(Primal) inf (f(x)):x\in A$. Let say that $A=\{x \in X: h(x)=0\}$. I can express my problem : $inf_X sup_Y L(x,y):= ...
4
votes
0answers
22 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 ...
0
votes
1answer
11 views

Discontinuous semiconcave functions

A function $u: \mathbb{R}^n \to \mathbb{R}$ is defined to be semiconcave if there is a positive constant $c$ such that for all $x,z$ $$ u(x-z) + u(x+z) - 2u(x) \leq c |z|^2. $$ Alternatively, one ...
3
votes
1answer
65 views

Relationships between affine closures and convex closures

Let $V$ denote a vector space. Then the following concepts make sense: affine subset of $V$ affine closure (affine "hull") of a subset of $V$ Suppose $V$ is in fact a real vector space. Then the ...
2
votes
1answer
18 views

About the Affine hull and Span.

I'm learning Linear Algebra and Convex Optimization simultaneously, I notice that the affine hull is, to some extent, analogous to the span, but when I read the lines "We define the affine dimension ...
1
vote
0answers
46 views

Show that if A and B are strictly convex, then A + B is strictly convex or provide a counter example.

We have: If A is open: $\exists x,y \in A,$ $x \neq y$ such that $\lambda x+(1-\lambda y)\in \dot A $ (the interior) and $\exists u,v \in B,$ $x \neq y$ such that $\lambda u+(1-\lambda v)\in ...
6
votes
1answer
347 views

Cones of positive semidefinite matrices generated by matrices of rank $1$

Let $S_n$ be the space of real $n \times n$ symmetric matrices and let $S_n^+$ be the convex cone of positive semidefinite matrices in $S_n$. The extremal rays of this cone correspond to the positive ...
2
votes
2answers
38 views

Why a convex cone cannot have more than one extreme point?

The way I define an extreme point is : A point which cannot be defined as a convex combination of two distinct points. I'm not able to extend this and show why a convex cone cannot have more than ...
1
vote
0answers
16 views

Discrete concavity of a log function

I want to prove that the function $f_i(P)=f_i(P_1,..P_i,..,P_K)=log(1+(\frac{a_iP_i}{\eta+\sum\limits_{i'\neq i}a_{i'}P_{i'}}))$ is discetely concave, which means that I should prove: $\forall \lambda ...
0
votes
0answers
11 views

Convergence of backtracking and gradient descent.

I am thinking a bit about the following exercise: Let $f(x) = x_1^2 + x_2^2$ with dom $f = \{ (x_1,x_2):x_1 > 0 \}$. The optimal value of this problem is $p^* =1$, but it is never attained since ...
0
votes
0answers
51 views

Conditional expectation over a convex set

Let $\boldsymbol{X}$ be an $\mathbb{R}^d$-valued absolutely continuous and integrable random vector. Further, let the cdf $F$ of $\boldsymbol{X}$ be strictly increasing in each component on ...
0
votes
1answer
591 views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
1
vote
1answer
24 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
1
vote
1answer
56 views

$\lambda f(x)+(1-\lambda)f(y)=f(\lambda x+(1-\lambda)y)$ implies $f $ linear?

Let $X$ be a Banach space. $f:X \to X$ a continuous function. If we assume that $f$ satisfies the following convexity condition: $$\lambda f(x)+(1-\lambda)f(y)=f(\lambda x+(1-\lambda)y),$$ for all ...
0
votes
1answer
13 views

Are unions, sums (…) of quasiconvex functions again quasiconvex?

for a project I need to prove quasiconvexity of several general functions. Can I argue that the union (or sum, or difference...) of quasiconvex functions is again quasiconvex? I do know that the sum ...
1
vote
1answer
25 views

Congruence Property of Monotone Operators

A map $T$ is called strictly monotone if for $x\ne y$, $\langle u-v,x-y\rangle>0$ for all $u\in T(x),v\in T(y)$. Let $A$ be an $m\times n$ matrix and $b\in\mathbb R^m$. I want to prove that if ...
0
votes
1answer
36 views

Prove that $|\int_C f(z)dz| \le M |z_2 - z_1|$ where $M \gt 0$ such that $|f(z)|\le M; \ \forall \ z \in \Omega$

Let $z_1$ and $z_2$ be any two points in $\Omega$ and let $C$ be any oriented contour in $\Omega$ from $z_1$ to $z_2$. Also, assume that $f:\Omega \to \Bbb{C}$ is analytic on an open convex set ...
2
votes
0answers
27 views

Can a non-convex set be partitioned into a set of nearly convex subsets? [closed]

Consider a non-convex bounded subset $S \subseteq \mathbb{R}^{n}$. Is it always possible to partition this set into a finite set of disjoint subsets \begin{equation} S = \bigcup_{i=1}^{n}s_i, \quad ...
-2
votes
1answer
21 views

Is a distance function on $\mathbb{R}^n$ convex?

Fix $z \in \mathbb{R}^n$. Let $||\cdot||$ be a norm on $\mathbb{R}^n$, and define the distance function $f(x)=||z-x||$ for $x\in \mathbb{R}^n$ Then, is it true that $f(x)$ is convex?
1
vote
0answers
57 views

Proof of some inequality on convex sets in $\mathbb{R}^n$

Suppose $\Omega$ is a strictly convex bounded set with smooth boundary in $\mathbb{R}^n$. If $y \in \partial\Omega$, how can we show that $$\langle(x-y),\nu_y\rangle < 0$$ for all $x \in ...
4
votes
2answers
55 views

does this convex set have a specific name?

Let $x_1,\dots,x_N$ be points of $\mathbb{R}^n$. Define the following set: $\mathcal{A} = \left\{\sum_{j=1}^N a_j x_j : -1 \le a_j \le 1, \, \, \forall j=1,...,N\right\}$. It is an easy exercise to ...
2
votes
2answers
28 views

Uniformly convex and strictly convex

I have the following definitions of uniformly convex and strongly convex Let $f:R^n \to R$ be smooth. (1) $f$ is uniformly convex if there exists $\theta > 0 $ such that $$\Sigma_{i,j}f_{x_i x_j} ...
0
votes
1answer
9 views

Supporting hyperplane of convex function

Below is the appendix B of Evan's PDE book on supporting hyperplanes of convex functions. In the remark (1), he says that the mapping $y\to f(x)+r\cdot(y-x)$ determines the supporting hyperplane to ...
0
votes
1answer
25 views

Parametrizing the Boundary of a Convex Set

Let $K$ be a compact convex set in $\mathbb{R}^2$. In the proof of a proposition in a paper I am reading, they are concerned with parameterizing $\partial K$ in the following way: If $K$ is ...
0
votes
0answers
15 views

How can I find discrete points in convex hull

Say, I have a set of finite numbers of data $S = \{z_1, z_2,...,z_n\}$, $z_i \in \mathbb{Z}^d$, $C$ is the convex hull generated by $S$, that is, $C = conv(S)$. How can I find some discrete points in ...
1
vote
1answer
20 views

Showing that a given function is convex.

I am trying to show that the function $f(x,\vec{y})=\alpha\ln(1+\exp(x+\vec{y}\cdot \vec{z}))+(1-\alpha)\ln(1+\exp(-x-\vec{y}\cdot\vec{z}))$ is a convex function of $(x,\vec{y})$ (where ...
2
votes
1answer
48 views

Non-trivial lower bound approximation of a convex function using the second derivative at the minimum

Say that I am given an infinitely differentiable convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am wondering if I can construct a meaningful lower bound approximation of $f$ using it's ...
2
votes
1answer
34 views

How to show that there's a continuous function separating convex sets of Radon measures?

First, the setup: $X$ is a compact set. By Riesz's representation theorem $C(X)^*=${all Radon measures on $X$}. $K$ is a convex, closed (weak-* sense) set of probability measures. $m$ is a probability ...
3
votes
0answers
34 views

Generalizing convexity of sets

Let $X$ be a subset of some Euclidean space. We say that $X$ is convex if for any two points $p$, $q$ in $X$, the line segment joining $p$ and $q$ is also in $X$. But what if we loosen this definition ...
0
votes
0answers
41 views

Application of the Operator norm $\|.\|_O$ on the differential $df \in \hom(\mathbb{R}^n, \mathbb{R}^m)$

This question origins from my Analysis II Script which gives the following statement (without proof): Lemma Let $U \subset \mathbb{R}^n$ be convex and $f \in C^1(U, \mathbb{R}^k)$ then we have $$ ...
2
votes
1answer
31 views

Strong convergence of convex combinations of a weakly convergent sequence

Consider the Mazur's Lemma (H. Brezis - "Functional analysis, ..."): Assume $(x_n)$ converges weakly to $x$. Then there exists a sequence $(y_n)$ made up of convex combinations of the $x_n$'s that ...
0
votes
0answers
14 views

does convexity implies $g(u)>cu$?

So I have been doing some self study and I was wondering if my results are true, or if I am misreading something. Say we have a function $g$ which is concave on values of $u \in \mathbb{R}$. Then we ...
0
votes
1answer
22 views

convexity and first derivative

Let $\phi$ be a differentiable function on an interval $(a,b)\subset R^1$. If $\phi '$ is non-decreasing, then $\phi$ is convex. But, is the converse true? Does the convexity of $\phi$ necessarily ...
2
votes
0answers
22 views

Takahashi convex metric spaces

A Takahashi convex metric space is a metric space $(X,d)$ such that $\exists W : X \times X \times [0,1] \rightarrow X$ that satisfies : $d (u, W(x,y; \lambda)) \leq \lambda d(u,x) + (1- \lambda) ...
1
vote
1answer
20 views

Show the Gini Coefficient is Quasiconvex

The Gini-coefficient is defined as $$ G(x) = \sum_{i = 1}^n \frac{i}{n} - \sum_{j=1}^{i} \frac{x_{(j)}}{\mathbb{1}^{T}x}, $$ where $x_{i} $ is nonnegative numbers with positive sum. $x_{(j)}$ denotes ...
7
votes
2answers
338 views

About the hyperplane conjecture.

I have recently heard about the hyperplane conjecture and I would like to understand better the problematic behind this conjecture. The hyperplane conjecture: There exists a universal constant ...
1
vote
2answers
31 views

To show $f(x)$ has ONLY one Max in $x\in[0,1]$

I have function $$f(x)=\left(\frac{1-x}{2-x}\right)x^{p-1}~\text{where}~p>1;~x\in[0,1]$$ I want to show that $f(x)$ has ONLY one maximum in $x\in[0,1]$. I get the second derivative as ...
1
vote
1answer
35 views

Show that f(x) is convex

Show that f(x) = inf{g(x1)+h(x2)} is convex subject to x1+x2=x and where g(.) and h(.) are convex functions. Can I just go about this by using the regular definition of a convex function or which ...
-1
votes
1answer
23 views

Convexity/concavity of a strictly increasing and continuous function

Consider a continuous, strictly increasing function $f:\mathbb{R}_{+}\to \mathbb{R}_{+}$ with $f(0)=0$, and $x>f(x)$ for all $x>0$. Is this enough to conclude anything about ...
0
votes
1answer
31 views

Are these two definitions of an affine subspace equivalent?

I've seen the notion of an affine subspace defined differently as follows: $S \subset \mathbb R^3$, non-empty, is an affine subspace if $(1-t)u + tv \in S$ whenever $u,v \in S$. $S$ is an affine ...
0
votes
0answers
33 views

strong convex implies exp-concave

Prove that if f is strong convex (for some m>0) $\mbox(\nabla f(\mathbf{x})-\nabla f(\mathbf{y}))^{T}(\mathbf{x}-\mathbf{y})\geq m||\mathbf{x}-\mathbf{y}||_{2}^{2} $ then f is also ...
0
votes
2answers
34 views

compute the smallest affine subspace containing $S$, where $S=\{(1,1,1),(2,3,4),(1,2,3),(2,1,0)\}$ is a set of vectors in $\mathbb R^3$

I've started to study convexity to enchance my optimization skills. Given a set $S=\{(1,1,1),(2,3,4),(1,2,3),(2,1,0)\}$ of vectors in $\mathbb R^3$ an exercise asks to compute the smallest affine ...
2
votes
1answer
51 views

Identity of the Operator Norm applied to the differential $df$ for convex $U \subset \mathbb{R}^n$ and $f \in C^1(U, \mathbb{R}^k)$

In my Analysis II Script they often use 'special' norms such as the Operator norm to make proofs more 'elegant' or just shorter. There is also the following statement (without a proof) which I can't ...