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
2answers
243 views

An Orlicz norm is a norm

I had asked a question pertaining to Orlicz norms here. However, in the book I was reading, it said (and I paraphrase) "It's not difficult to show it is a norm on the space of integrable random ...
7
votes
1answer
148 views

Characterization convex function.

Let be $f:[0,1]\rightarrow\mathbb{R}$ a continuous function such that far all $a,b\in [0,1]$ with $a<b$ $$f\left(\frac{a+b}{2}\right)\leq\frac{1}{b-a}\int_a^b f(x)\,dx.$$ How to prove that $f$ is ...
0
votes
1answer
21 views

Proving that $\lambda_1\textbf{x}_1+\lambda_2\textbf{x}_2\in C$, for convex cone $C$

I'm doing convex analysis studies and I have the following problem to prove: Show that, if $C$ is a convex cone, then $\lambda_1\textbf{x}_1+\lambda_2\textbf{x}_2\in C$, with ...
0
votes
0answers
16 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
21 views

Convex function and its epigraph PROOF

Can someone help prove this statement. Consider a function $f:R^{n} \to R$ and epi $f$ = {$(x,t) \in R^{n+1}$: $x \in R^{n}$, $t \geq f(x)$} A function is convex if and only if its epigraph is a ...
0
votes
0answers
12 views

Duality gap of nonconvex problem

I have an optimization problem (presumably) nonconvex but the objective funtion is increasing, continuous, and smooth. I also have a set of linear constraints which are fulfilled with equality, i.e., ...
0
votes
2answers
30 views

Identity regarding convexity of the logistic loss function

I found the following identity regarding the logistic loss function in these lecture notes (slide 16) from Berkeley university: $$\log(1 + e^{-z}) = \max_{0 \leq v \leq 1} -zv + v\log(v) + ...
0
votes
1answer
14 views

Questions on conditions for convexity of a real function

We have a function $f:[0,1] \rightarrow \mathbb{R}$. We know it is continuous on $[0,1]$. Aside from a set $S$ of measure $0$, we can compute its right derivative, and can show that this right ...
2
votes
0answers
27 views

Extending the notion of convex hull in $\Bbb R^n$

The super convex hull of a set $A \subseteq \Bbb R^n$, is the set of all $\sum_{i=1}^{\infty}\lambda_i x_i$ such that $\lambda_i \geq 0$ and $\sum_{i=1}^{\infty}\lambda_i =1$, which is denoted by ...
3
votes
3answers
133 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
5
votes
1answer
93 views

Non-empty intersection of convex sets

Assume that $X_1,\ldots,X_n$ are open, convex subsets of $\Bbb R^d$ such that for any $i,j,k$ with $1\le i,j,k\le n$, we have $X_i\cap X_j\cap X_k\neq\emptyset$. Is it possible for $\bigcap_{i=1}^n ...
0
votes
0answers
19 views

Maximum intersection of slabs in $\mathbb{R}^n$

Let $K \in \mathbb{R}^n$ be a compact convex set containing the origin and symmetric with respect to the origin. Let $S_i(t_i)$ be a finite set of slabs of various widths and orientations, translated ...
0
votes
1answer
32 views

Minimizing a non-convex rational function of two variables

I need to minimize the following function $$f(x,y)= \frac{a}{x}+\frac{bx}{y}+\frac{cy}{x}+dy+\frac{e}{y}$$ where $a,b,c,d$, and $e$ are positive constants, and $x$ and $y$ are both strictly positive. ...
2
votes
3answers
220 views

I don't understand this proof of the AM-GM inequality?

The proof uses this lemma which I understand: $\mathbf {Lemma}$: Suppose $x$ and $y$ are positive real numbers such that $x>y$. If we decrease $x$ and increase $y$ by some positive quantity $E$ ...
3
votes
1answer
59 views

Strictly increasing and strictly convex function that does not go to negative infinity

Let $f : \mathbb{R} \to \mathbb{R}$ be continuous, strictly increasing, and strictly convex for all $x$. What are necessary and sufficient conditions for $f$ to be bounded below? Strong convexity is ...
0
votes
1answer
24 views

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities.

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities. The convex hull of $x_1, \ldots, x_n \in \mathbb R^n$ is defined ...
0
votes
1answer
283 views

convex hull function in matlab

Is there anyway 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 ...
0
votes
0answers
20 views

Some good reference on convex functions

I want some good reference on convex functions i.e. all of their properties along with their proofs.
0
votes
1answer
30 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
0
votes
0answers
19 views

Does $\mu\coth(\mu)=A\mu^{2}+B$ have at most two positive solutions $\mu$?

Is it true that $$ \frac{\mu\cosh(\mu)}{\sinh(\mu)} = A\mu^{2} + B $$ has at most two solutions $\mu > 0$ for any choice of $A$, $B$? I believe this is true; it looks true when I ...
0
votes
0answers
37 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
2
votes
1answer
22 views

Prove convexity of log modified bessel function

I need to prove that the modified bessel function of the second kind is log convex in the square of the argument. Specifically I'm interested in showing, $\log \mathcal{K}_0(\sqrt{x})$ (zero order) is ...
2
votes
0answers
17 views

Convexity of sigmoid-based squared error loss

Assume $w, a_1,a_2 \in \mathbb{R}^d$ and $\sigma = \dfrac{1}{1+e^{-x}}$ the sigmoid function. Is the following squared difference a convex function? $$J(w)= (\sigma(w^Ta_1)\times \sigma(w^T ...
0
votes
0answers
28 views

The convexity of the range of concave function

Given a concave function $f: X \rightarrow \mathbb{R}^n $ with a convex domain $X \in \mathbb{R}^n$, is the range of $f$ a convex set also?
3
votes
0answers
62 views

Is it always possible to partition a fat shape to fat shapes?

The slimness factor of a geometric 2-dimensional shape is defined (for this question) as the ratio of the side-length of its smallest enclosing square to the side-length of its largest enclosed ...
1
vote
1answer
31 views

Directions of sublevel sets ofa convex function

Let $f:\mathbb R^n \rightarrow \mathbb R$ be a convex (continuous ) function. Let's assume that some sublevel set $L_a:=\{x\in \mathbb R^n : f(x) \leq a\}$, where $a \in \mathbb R$, contains a ...
1
vote
0answers
16 views

Existence criterion for solution in quadratic programming

I have the problem $$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}$$ with $D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}$, $A,Q\in \mathbb{R}^{n\times n}$ and $b,c \in ...
0
votes
0answers
33 views

Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
0
votes
1answer
32 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
1
vote
1answer
65 views

On Stochastic Matrices

Let "stochastic" matrix be the matrix whose rows sum to one and deterministic matrix be a stochastic matrix whose all rows consist of a one and zero. For example $\left [ \begin{array}{ccc} 1 & ...
0
votes
0answers
188 views

Curvature and intersection of convex functions

Take two weakly convex, weakly increasing non-negative functions, $g(x)$ and $h(x)$, domain of $x$ is $[a,d]$, $g(x)=0$ for $x \in [a,b]$, $h(x)=0$ for $x \in [a,c]$, and $g(d)=h(d)$. So $g$ and $h$ ...
-2
votes
3answers
242 views

There is a ray from each point of unbounded convex set that is inside the set.

Let $A$ be a non-empty convex, unbounded set in $\mathbb R^n$. Prove that for each point $a \in A$, there is a non-zero vector $h \in \mathbb R^n$ such that $l = \{x \in \mathbb R^n \mid x=a+th,\ ...
1
vote
1answer
37 views

Convex Combination of 3 point in R2 and Triangle

I am new to convex combination, and I am quite amazed by some easy result. I know that convex combination of 2 points($P_1P_2$) in $R^2$ is all points in the line segment $P_1P_2$. And then I see a ...
0
votes
1answer
40 views

Common subdifferentials of convex function

Let $f: \mathbb R^n \rightarrow \mathbb R$ be a convex function. By a subdifference of $f$ in $x\in \mathbb R^n$ we mean an $h\in \mathbb R^n$ such that $f(x) \geq f(p)+<x-p,h>$ for all ...
2
votes
0answers
23 views

Convex interpolation between two points with given derivatives

Let's say I have two real values $x_1$ and $x_2$, to each of which I associate $y_i$ and $y'_i$ satisfying $$ (y_2-y_1)(y'_2 - y'_1) \geq 0. \tag{1} $$ I would like to find a polynomial ...
0
votes
1answer
36 views

Interesting and intuitive affirmation involving convex sets

Let $\Omega_1$ and $\Omega_2$ two open, bounded and convex domains in $R^n$ with $\Omega_1 \supset \overline{\Omega_2}$ and $0 \in \Omega_2.$ Suppose that for each $x_0 \in \partial (\Omega_1 ...
0
votes
0answers
23 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
15 views

What is the nature of this one dimensional function?

Let $\mathcal{S}$ be a 2-D convex set whose elements can be represented as $(x,y)\in\mathcal{S}$. Let $p_L$ and $p_U$ be two real constants such that $p_L\leq p_U$. For $p\in[p_L,p_U]$, I define the ...
1
vote
1answer
297 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
0answers
49 views

Dual norm of the matrix L1 norm is infinity norm (and vice versa)

Recall that for a given norm $\|\cdot\|$ on $\mathbb{R}^n$, the dual norm is defined as a function $\|\cdot\|_*: \mathbb{R}^n \rightarrow \mathbb{R}$ with: $\|y\|_* = \max \limits_x \{x^Ty: \|x\|\le1 ...
0
votes
1answer
57 views

$F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$ Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex ...
1
vote
2answers
31 views

Suitable composition of concave and convex functions is convex?

Let $f:[0,1]\to[0,1]$ be a strictly increasing continuous concave function with $f(0)=0$ and $f(1)=1$. Let $g$ be the inverse of $f$. Then $g$ is strictly increasing and convex. It seems that the ...
0
votes
2answers
36 views

Basic question about tangent cone

The following is from Prof. Jahn's book " Intro. to the theory of nonlinear optimization" about tangent cone: After definition, he gave an example: My question is: Does the tangent cone include ...
5
votes
1answer
87 views

Continuous linear image of closed, bounded, and convex set of a Hilbert Space is compact

Is my proof of this proposition correct ? And is this proposition well known? Proposition: Let $C$ be a closed, bounded, and convex set in a separable Hilbert space $H$. Let $L : H \to \mathbb{R}^n$ ...
1
vote
1answer
30 views

Convolution of Strictly Convex Function

Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be a $C^2$, strictly convex function, and $\theta_\epsilon$ the standard approximation to identity ...
2
votes
2answers
39 views

Is the distance between disjoint closed convex subsets of a Hilbert space positive? Is it attained?

Let $H$ be an infinite dimensional and separable Hilbert space. Let $A,B$ be infinite, closed and convex subsets of $H$. If $A$ and $B$ are disjoint and if at least one of them is bounded, is the ...
3
votes
2answers
255 views

How to prove that the following function is convex?

I want to prove convexity of the following function: $$f(x) = log_x \left(1 + \frac{(x^a-1)(x^b - 1)}{x-1}\right)$$ for any fixed $a, b \in (0, 1)$ and: $x\in(0,1)$ $x\in(1, \infty)$ I'm trying ...
0
votes
1answer
28 views

Subtracting a constant from log-concave function preserves log-concavity, if the difference is positive

I am trying to work out a question from 'Convex Optimization - Boyd' . Specifically, exercise 3.48: Show that if $f : \mathbb R^n \to \mathbb R$ is log-concave and $a > 0$, then the function $g ...
2
votes
1answer
35 views

Affine to linear like conversion of a concave function

Is the following true: $$\log \left( \frac{1}{f(x)+K}\right)\mathrm{is\;concave}\Longleftrightarrow \log \left( \frac{1}{f(x)}\right)\mathrm{is\;concave},$$ where $K\in\mathbb{R} $ and ...
2
votes
1answer
62 views

Point-wise converging convex functions on $[0,1]$

Suppose we have a sequence of continuous convex functions $\{f_n\}$ defined on $[0,1]$ which converge point-wise to a limit $f$ on $[0,1]$, i.e. for all $x \in [0,1]$ $$\lim_n f_n(x) = f(x).$$ Let $G ...