# Tag Info

## New answers tagged convex-analysis

0

It's 2-isohedral (which type 1 isn't) and not edge-to-edge. That leaves only types 11-13 which all have an 8-tile lattice so it's not one of those.

0

($\Longleftarrow$) Suppose there exists a function $r: \mathbb{R} \rightarrow \mathbb{R}$ such that $\underset{t \rightarrow +\infty}{\text{lim }}r(t) = +\infty$ and $f(x) \ge r(\|x\|_2)$ for sufficiently large $x$. Then given any $d \in \mathbb{R}^n$, the existence of $\delta > 0$ such that $f(x) \ge r(\|x\|_2) \ge \|d\|_2\|x\|_2$ whenever $\|x\|_2 > ... 0 Yes, your$R$is indeed$\frac{1}{2}$-strongly convex. The particular result you want to prove is a trivial application of Theorem 16 of this paper. To use the aforesaid theorem, simply take$X := diag(w)$, so that the eigenvalues of$X$are the$w_i$'s and its trace norm is simply$\|w\|_1$. In fact the aforementioned paper shows a much bigger result, ... 0 I think that the claim is false. Consider$X = \mathrm{diag}(1, 0, 0)$,$y = 0$and the strictly convex function$J(x) = ||x - (0, 1, 2)^t||_2^2$. Then the minimizer of$|y - X\beta|^2 + \lambda J(\beta)$is clearly$\hat{\beta} = (0, 1, 2)^t$. Or is there another assumption that I read over? 1 The steps for such demostration are indicated in the book of Berg "Computational Geometry. Algorithms and aplications". Exercise 1.1. The convex hull of a set S is defined to be the intersection of all convex sets that contain S. For the convex hull of a set of points it was indicated that the convex hull is the convex set with smallest perimeter. We want to ... 0 Here are some examples to show that the relative order of the$q^{(i)}_{\text{max}}$isn't determined by the relative order of the$N(g_i)$. All functions are$[0,1]\to\mathbb R. \begin{align*} g_1(x) &= \begin{cases} 3 &\text{ifx<\tfrac12$,} \\ -1 &\text{if$x\ge\tfrac12$.} \end{cases} \\ g_2(x) &= \begin{cases} -2 &\text{if ... 0 You might try$f(t,x) = t^{-1/2} x^2$for$t > 0$,$f(0,x) = 0$. 1 The term "logarithmic convex hull" is in use for this object, because it can be obtained by convexifying the image of a domain under the logarithm map, and then coming back. It comes up in complex analysis in several variables, due to the following fact: a domain$D\subset\mathbb{C}^n$is a region of convergence of some power series (centered at$0$) if ... 2 You cannot avoid an exponential blow-up in the number of resulting constraints. As an example, let us look at cross-polytope$P_3$in$\mathbb{R}^n$. It is the convex hull of all vertices obtained by all permutations of$(\pm1,0,\dots,0)$. Hence, it has$2n$vertices and$2^n$facets (see https://en.wikipedia.org/wiki/Cross-polytope) and its ... 0 There is a fair chance you may be talking about the set$\{(z, c) \in \mathbb{R}^{n + 1}|f(z) \ge -c\}$instead. Now, for a proof of the claim, simply use the definition of convexity via epigraphs. Indeed,$f$is a concave function$\iff-f$is a convex function$\iffepi(-f) := \{(z, c) \in \mathbb{R}^{n + 1}|c \ge -f(z)\} = \{(z, c) \in \mathbb{R}^{n ...

1

Well, $$\binom{N}{k}=\frac{\Gamma(N+1)}{\Gamma(N-k+1)\Gamma(k+1)}$$ hence: $$\frac{d^2}{dN^2}\log\binom{N}{k} = \psi'(N+1)-\psi'(N-k+1) = \sum_{n\geq 0}\left(\frac{1}{(n+N+1)^2}-\frac{1}{(n+N-k+1)^2}\right)$$ and it is not difficult to discuss convexity.

2

No, I don't think you will find a guaranteed fast algorithm, as the problem appears intractable in general, if I understand the below paper correctly. A quick search led me to, e.g., On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes, by Hans Raj Tiwary

1

You've misunderstood the definition of a barrier cone. In particular, we have $$\newcommand{ip}[1]{\left\langle #1 \right \rangle} L = \{x^* \mid \exists \beta_{x^*} \text{ such that } \ip{x,x^*} \leq \beta_{x^*} \text{ for all }x \in C\}$$ Or, in other words, $$L = \{x^* \mid \sup_{x \in C} \ip{x,x^*} \text{ is finite}\}$$ If we take $\alpha \,x^*$ ...

2

If it helps think about it like this - in concrete terms If $\lambda =\frac 1 2$ the point $\frac 12 x +\frac 12 y$ is half way between $x$ and $y$. If $\lambda =\frac 1 3$ the point $\frac 13 x +\frac 23 y$ is two thirds third of the way from $x$ and $y$. So as the values of $\lambda$ vary from $1$ to $0$ you get further from $x$ and closer to $y$ along ...

2

You can just look at the simple example, where you are in dimension 1, and you have $\frac{1}{a-bx}$. I don't quite know what you mean by quadratic upper bound, but as $x$ tends to $a/b$ this tends to infinity. any function bounding it would also have to be ill-defined (infinite) at the point $a/b$.

1

Let $z \in \mathbb{R}^n$ be the point to be projected, where "projection" is to be understood as "euclidean projection", i.e the closest-point to $z$. (a) Closed unit ball. By using Lagrange multipliers on the problem $\underset{z^Tz \le 1}{\text{minimize }}\|x - z\|_2^2$, it's not hard to obtain \begin{eqnarray} \text{proj}_{B(0; 1)}(z) = \begin{cases}z, ...

2

Consider the function $$f(x) = \begin{cases} x^2, & x > 0, \\ 0, & x \le 0 \end{cases}$$ on the real line with $Y = \mathbb R\setminus (-2, 1)$. The function $f$ is continuously differentiable, convex, and minimal at $x_0 = 0$. However, the projection of $x_0$ onto $Y$ is $y_0 = 1$ and $f(y_0) = 1 > 0 = f(-2)$. Comments: Connectivity ...

0

So here's what I myself thought of after a good night's sleep: For $1\le m<k$ let \begin{align}U_{m,k}&=\operatorname{span}\{\,c_i-c_m\mid m<i\le k\,\}\\U_m&=\bigcup_{k\ge m}U_{m,k}\\U&=\bigcap_mU_m\end{align} Since $U_{m,m}\subseteq U_{m,m+1}\subseteq U_{m,m+2}\subseteq\ldots$ is eventually stationary, we have $U_m=U_{m,k_m}$ for ...

0

$$\dfrac {\delta^2 f} {\delta x^2}=12x^2-4$$ $$\dfrac {\delta^2 f} {\delta y^2}=2$$ $$\dfrac {\delta^2 f} {\delta z^2}=2$$ $$\dfrac {\delta^2 f} {\delta z\delta x}=0$$ $$\dfrac {\delta^2 f} {\delta z \delta y}=1$$ $$\dfrac {\delta^2 f} {\delta x \delta y}=0$$ $$H=12(3x^2-1)>0,\forall x>\dfrac 1 {\sqrt 3}$$

4

You may look at Rockafellar, Convex Analysis where he defines the recession cone for a non-empty convex set $C$ as $$0^+C=\{y\colon\ x+\lambda y\in C,\ \forall\lambda\ge 0,\ \forall x\in C\}.$$ Theorem 8.2 in the book (not in the preview, unfortunately) says that for a closed convex $C$ the recession cone $0^+C$ consists of exactly your type of limit ...

7

Yes, it is true for $a$ in a dense subset of $C$. First, note that for any fixed $b$, $\lim_{k \to \infty} c_k/|c_k| = \lim_{k \to \infty} (c_k - b)/|c_k - b|$. Thus the set of $v$'s for $C$ is the same as the set of $v$'s for $C - b$. We can choose $b \in C$ and replace $C$ by $C-b$; equivalently, we can assume that $0 \in C$. If $c_k \in C$ with ...

0

Here is an apparently non-standard proof, involving no gradients or Hessians: http://www.cs.bgu.ac.il/~mlt142/CsWiki/Blogs/Post_Karyeh_55db5950bd339?format=standalone

3

You probably need that $C$ is closed. Assume $0\in C$ without loss of generality. Otherwise, if $a\in C$, then $|c_k-a|\to \infty$ and $$\frac{c_k-a}{|c_k-a|} = \frac{c_k}{|c_k|}\frac{|c_k|}{|c_k-a|} - \frac{a}{|c_k-a|} \to v.$$ Let $r\in[0,\infty)$. As $|c_k|\to\infty$, for $k$ sufficiently large, we have $r < |c_k|$ and $\frac r{|c_k|} c_k\in C$ by ...

1

I'm going to suggest you think geometrically here (which includes drawing a picture): Suppose $A,B,C$ are points in the plane with $A$ to the left of $B$ and $B$ to the left of $C.$ The first inequality you cite is of the form $s(A,B) \le s(A,C),$ where $s$ denotes slope. How could this be true unless $B$ lies on or below the line through $A$ and $C?$ And if ...

3

Note: I don't assume strict convexity, so I use weak inequalities. For strictly convex $f$, all the inequalities between expressions of the form $\frac{f(y) - f(x)}{y-x}$ are strict. We have \begin{align} \frac{f(b) - f(a)}{b-a} &= \frac{\bigl(f(b) - f(x)\bigr) + \bigl(f(x) - f(a)\bigr)}{b-a}\\ &= \frac{b-x}{b-a}\cdot\frac{f(b) - f(x)}{b-x} + ...

1

As answered on Mathoverflow, where Jacky silently cross-posted this question There are two questions here: Q1) Which convex pentagons tile the plane? Q2) What are all tilings of the plane by copies of a single convex pentagon? The Wikipedia page you cite concerns Question 1 (though it could make this more explicit); Q1 is contained in Q2, and likely more ...

0

Proposition: $$\text{epi}(f)=\bigcap_{\epsilon>0}\bigl(\text{epi}_S(f)-(0,\epsilon)\bigr).$$ Proof: A simple observation $$f(x)\le y\quad\Leftrightarrow\quad\forall\epsilon>0\colon \ f(x)<y+\epsilon$$ leads directly to (x,y)\in\text{epi}(f)\quad \Leftrightarrow\quad \forall\epsilon>0\colon \ ... 1 First of all remember that, in finite dimensions, every linear functional is continuous. Let p \cdot x=\alpha be an equation of H. Since E is compact, the continuous linear functional x \rightarrow p \cdot x has a minimum \beta and a maximum \gamma in E. Thus \beta \le p \cdot x \le \gamma for every x \in E and there exist x_1,x_2\in E ... 1 Here is an example. Consider the density of two exponential random variables as \begin{align*} f_1(x) &=\lambda_1 \exp(-\lambda_1x) \\ f_2(x) &=\lambda_2 \exp(-\lambda_2x), \end{align*} where \lambda_1 \neq \lambda_2. Consider the sum of these two log concave functions \begin{align*} g(x)=f_1(x)+f_2(x), \end{align*} where the first and second ... 0 Let \theta \in (0,1) and consider\theta \int_0^1 \gamma_1(t)\,dt + (1 - \theta) \int_0^1 \gamma_2(t)\,dt = \int_0^1\theta\gamma_1(t) + (1 - \theta)\gamma_2(t)\,dt.$$Now, to get the desired result you need to be able to prove that \gamma(t) = \theta\gamma_1(t) + (1 - \theta)\gamma_2(t) \in \Gamma_0. Clearly \gamma has the correct fixed ends and is ... 0 Assuming Q is a subspace, then indeed we can: Fix t\in(0,1), and let a_1=\int_0^1\gamma_1(s)ds and a_2=\int_0^1\gamma_2(s) be elements of l(\Gamma_0). Define the following homotopies: H_1(s,y)=((t-1)y+1)\gamma_1(s), H_2(s,y)=(-ty+1)\gamma_2(s), and H_3(s,y)=(1-y)t\gamma_1(s)+y(1-t)\gamma_2(s). This shows that ... 0 The claim is true for strongly convex function, but not generally true for strictly convex functions. The -ve result for strictly convex functions is proved by @Brian M. Scott's counter-example. For strongly convex functions, indeed one would have \begin{eqnarray} \exists m > 0\text{ s.t }f(x) \ge f(0) + f'(0)(x-0) + \frac{m}{2}x^2 = \frac{m}{2}x^2, ... 0 Actually, your tiling is not type 2, 4, or 6. It's actually a two-tile lattice. You can tell by looking at the conditions for each tiling, which are found below the picture in the Wikipedia article. The condition for a type one tiling is that there be two consecutive angles whose sum is 180 degrees, or more formally:$$ B + C = 180^{\circ}A + D + E ...

3

Theorem: Let $X,Y$ be real linear spaces and $f\colon X\times Y\to [-\infty,+\infty]$ be convex. Then $$\phi(x)=\inf_{y\in Y}f(x,y)$$ is convex. Proof: Let $E$ be the image of $\text{epi}(f)$ under the projection $(x,y,\alpha)\to (x,\alpha)$. Then by definition of infimum $$\text{epi}(\phi)=\{(x,\alpha)\in X\times\mathbb{R}\colon \ (x,\beta)\in E,\ ... 1 It is convex! Your first statement that the minimum of convex functions is in general not convex is true, but here you have a lot more structure! In a sense you are projecting onto x. In fact, g is also called the inf-projection of f. Let \lambda \in (0,1) and y_1, y_2 \in J arbitrary:$$ \begin{aligned} g(\lambda x_1 + (1-\lambda) x_2) &= ...

1

Take $(x_0,y_0), (x_1,y_1) \in \mathbb R^n \times (0,\infty)$ and $\lambda \in [0,1]$. You have \begin{align} g[(1-\lambda)(x_0,y_0)+\lambda (x_1,y_1)] &=[(1-\lambda)y_0+\lambda y_1]f\left(\frac{(1-\lambda)x_0+\lambda x_1}{(1-\lambda)y_0+\lambda y_1}\right)\\ &=[(1-\lambda)y_0+\lambda y_1]f\left(\frac{(1-\lambda)y_0(x_0/y_0)+\lambda y_1 ...

0

$f(x) = x -\ln (1+x)$ is a counterexample. More generally, let $g:[0,\infty) \to [0,\infty)$ be any strictly increasing continuous function such that $g(0)=0, g'(0) > 0$ and $\lim_{t\to \infty}g(t)<\infty.$ Then $f(x) = \int_0^x g(t)\,dt$ is a counterexample. (That's how I found $x -\ln (1+x);$ it's the integral of $t/(t+1).$)

2

You can’t. Consider $$f(x)=\sqrt{1+x^2}-1\;;$$ clearly $f(0)=0$. Now $$f'(x)=\frac{x}{\sqrt{1+x^2}}\;,$$ so $f'(0)=0$, and $$f''(x)=\frac{\sqrt{1+x^2}+\frac{x^2}{\sqrt{1+x^2}}}{1+x^2}=\frac{1+2x^2}{(1+x^2)^{3/2}}>0$$ for all $x$, but $$\lim_{x\to\infty}\frac{f(x)}x=1\;.$$

1

The polyhedral cone $K$ is defined as an intersection of a finite number of half-spaces, i.e. $K=\{x\in\mathbb{R}^n\colon Ax\ge 0\}$, where $A\in\mathbb{R}^{m\times n}$. Since $\text{Im}\,A$ is a subspace, it can be represented as a kernel of some matrix $M$, that is $\ker M=\text{Im} A$. Hence, we have $$y=Ax,\ x\in K\qquad\Leftrightarrow\qquad y\in ... 2 Yes, and here is why. Begin with some standard facts about convex conjugates: Conjugation reverses inequalities: if f\le g then f^*\ge g^*. This is immediate from the definition of conjugate function, where the original function appears with the minus sign. The conjugate function is always convex and lower semicontinuous, being the supremum of some ... 0 A. Br¢ndsted and R. T. Rockafellar,"On the subdifferentiability of convex functions", Bull. Amer. Math. Soc. 16 (1965), 605-611. (see section 5) 1 The simplest way to prove this is to take advantage of the fact that a function is convex if and only if its epigraph is convex. In this case, the epigraph is$$\left\{(x,Y,z)\in\mathbb{R}^n\times\mathbb{R}^{n\times n}\times\mathbb{R}\,|\,Y\succ 0,~x^TY^{-1}x\leq z\right\}$$But consider this linear matrix inequality:$$\begin{bmatrix} Y & x \\ x^T & ...

5

Here's how to obtain $2d+1$ components: For $d=1$, let $A_1=[-1,0)$ and $B_1=(0,1]$ Assume we have found $A_{d-1}$, $B_{d-1}$ that produce $2d-1$ components in $d-1$ dimensions. Let \begin{align}A_d&=\{\,(x_1,\ldots,x_d):0<x_d\le1\,\}\cup A_{d-1}\times\{0\},\\B_d&=\{\,(x_1,\ldots,x_d):-1\le x_d<0\,\}\cup B_{d-1}\times\{0\}.\end{align} ...

2

Are you leaving out some assumptions? What if $n=1$ and $Y$ is negative? EDIT: With the new assumptions, we may consider a line segment through $(x,Y)$ space: $x = x_0 + t x_1$, $Y = Y_0 + t Y_1$, where $Y_0$ is positive definite and $Y_1$ is symmetric. It is enough to show that $\left.\dfrac{d^2}{dt^2} (x' Y^{-1} x)\right|_{t=0} \ge 0$. Now if $Z = ... 1 Yes, that looks correct. And you can write down the reflection operator$R$and then define$W$to be symmetric about the line if$RW=W$. Using orthogonal projection, you can write$was \begin{align} w & = w-\left((w-x)-\frac{\langle w-x,y\rangle}{\langle y,y\rangle}y\right)+\left((w-x)-\frac{\langle w-x,y\rangle}{\langle ... 0 integrate a positive function twice, then we get a convex function. So just find a non convex positive function is enough. Say, let f''(x)=\sin(x)+1, then f(x)=x^2-\sin(x) is convex, but f'' is not. 2 It is neither convex nor concave. You can work it out using Bernoulli random variables. Not convex: 1) Let X and Y be i.i.d. Bernoulli with Pr[X=1]=1/2. Then I(X,Y)=0. 2) Let A=B=1 (constants). Then I(A,B)=0. 3) Let (W,Z) = \left\{\begin{array}{ll} (X,Y) & \mbox{with prob 1/2} \\ (A,B) & \mbox{with prob 1/2} ... 0 There has in fact been some controversy over the usefulness of invex functions at all. This article is interesting A critical view on invexity As far as I can tell, the criticism is justified and the definition is vacuous. Please can someone prove me wrong by providing a concrete example of a novel, interesting theorem which cannot be easily proven without ... 0 This is in general not valid. Assume that E is a (infinite) normed space admitting a non continuous convex function g:E\to [0,\infty). Then, the function f:E^2 \to [0,\infty) defined by f(x,y) = g(x) is convex. Further, f is constant and thus continuous on the closed subspace U = \{0 \} \times E. However, f is not continuous on E^2. 1 we now that the domain of the function is:ax+b\gt 0\Rightarrow x\gt\frac{-b}{a}\text{so the domain is:}(\frac{-b}{a},+\infty)f'(x)=\frac{a}{ax+b}$in the domain of the function since we have$x\gt\frac{-b}{a}\Rightarrow ax+b>0 $the sign of$f'(x)=\frac{a}{ax+b}$will be dependent to the sign of$a$so: if$a\gt 0\Rightarrow f'(x)\gt 0\$ and ...

Top 50 recent answers are included