# Tag Info

0

$$g(αx_1 + (1−α)x_2) = f (a(αx_1 + (1−α)x_2) + b) = f (α(ax_1 + b) + (1−α)(ax_2 + b)) ≥ α f (ax_1 + b) + (1−α) f (ax_2 + b) (\text{by the concavity of} f ) = αg(x_1) + (1 − α)g(x_2)$$.

0

I guess it holds for $\|X\|_{1}\leq \frac{1}{\|A\|_{1}}$. Let $A$ be a $m\times n$ matrix. Then $A^{T}:\mathbb{R}^{m}\to\mathbb{R}^{n}$ is a linear map. Now if we consider the $\ell_{\infty}$ norm on both $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$, then $\|A\|_{1}=\|A^{T}\|_{op}$, where $\|\cdot\|_{op}$ stands for the operator norm. Therefore \begin{eqnarray} ...

0

What you state shows that $L_1$ is the maximum, but it does not imply that $F$ is concave. In fact, $F$ is not concave on the entire interval $(0,1/a)$. Note that $$F''(1/a) = -2 \log(T) - 2a > 0,$$ since $T < e^{-a}$. So there is a point of inflection between $L_1$ and $1/a$.

0

HINT: A supporting hyperplane of $K$ at $x$ is also a supporting hyperplane of $B$ at $x$.

1

If $H$ is a supporting hyperplane to $K$ at $x$, that means $x\in H$, and $K$ lies entirely on one side of $H$ (including $H$ itself). Describing the hyperplane by a linear equation, $H = \{ y\in \mathbb{R}^n : \lambda(y) = 1\}$ (every Hyperplane has such a representation), we have either $\lambda(k) \leqslant 1$ for all $k\in K$ or $\lambda(k) \geqslant 1$ ...

2

This $\theta$ is the maximum of $2n$ numbers hence finite. By convexity, for every $i$, $$(f(x^*+\delta'e_i)-f(x^*))+(f(x^*-\delta'e_i)-f(x^*))\geqslant0,$$ hence $f(x^*+\delta'e_i)-f(x^*)\geqslant0$ or $f(x^*-\delta'e_i)-f(x^*)\geqslant0$, in particular, $$\max(f(x^*+\delta'e_i)-f(x^*),f(x^*-\delta'e_i)-f(x^*))\geqslant0.$$ Thus $\theta\geqslant0$.

0

In linear programming, an important theorem is that the maximum and minimum values, if any, of a linear function defined on a convex set is attained at the boundary of the set. If the convex set is a polytope, the minimum and maximum (if any) are attained at vertices of the polytope.

0

The constraints aren't sufficient to imply that $(I-X)$ is nonsingular. So the objective isn't continuous on the feasible set, let alone convex. (Maybe there is supposed to be an additional constraint such as being negative semidefinite?) But if you want to form the Lagrangian and differentiate it would be this: L(X,\lambda) = a^T (I-X)^{-1}b + ... 1 Yes, with C=\frac12 (which is sharp, as may be seen by considering a two-dimensional convex set, or an arbitrarily thin pancake if you prefer nondegenerate examples). To prove the inequality with \frac12, first consider the case when the convex set is symmetric under reflection in the plane onto which it's being projected. Then the projection of the ... 2 For any convex sets K and L, the map \mathbb R^n\to\mathbb R, v\mapsto \operatorname{vol}(K\cap (L+v))^{1/n} is concave on its support, which is K-L. (See below.) If K and L are both origin-symmetric, then K\cap (L+v) and K\cap (L-v) are congruent, so they have the same volume, whence \begin{align*} \operatorname{vol}(K\cap L)^{1/n} ... 0 Since \beta = \sup_{s\in(a,t)} \frac{\phi(t)-\phi(s)}{t-s} $$we can take s=u in the case u\in(a,t) to get$$ \beta \ge \frac{\phi(t)-\phi(u)}{t-u} $$Since t-u>0 in this case, this yields$$ (t-u)\beta \ge \phi(t)-\phi(u) $$Rearranging yields the desired inequality. 0 Apparently it is a theorem named Attouch's Theorem proving the convergence of the subdifferentials given some convergence in the functions called epi-convergence. On the convergence of subdifferentials of convex functions Hedy Attouch, Gerald Beer http://link.springer.com/article/10.1007%2FBF01207197?LI=true On the convergence of subdifferentials of ... 1 As already noted in the comments, if f is convex and increasing and g is convex, then f \circ g is convex. If both f and g are \mathcal{C}^2, you can easily show this via derivatives:$$ {(f \circ g)}'' = {((f' \circ g)g')}' = (f'' \circ g) {(g')}^2 + f'(g) g'' \geq 0 $$if f'', f', g'' \geq 0. The proof can be given also for functions which ... 0 Empty sets are convex. Moreover it depends on which topology you consider (e.g. [0,1]\times \{0\} has empty interior in the Euclidean topology of \mathbb{R}^2, but non empty interior in the induced topology). 0 Since you are saying you don't know all the extreme points of the convex set, presumably you have something like an oracle that will tell you whether a point belongs to the set or not. Given such an oracle, choose a random orthonormal basis \{v_i\} and choose a really small \epsilon, and then for your point x in question query the oracle to determine ... 0 Here's a crude but easy bound. Let \triangle be a regular simplex of volume one centred at the origin; WLOG, \triangle is the largest volume simplex contained in A. Then A\subseteq -n\triangle, so \operatorname{vol}(A)\le n^n. (If A is the Euclidean ball circumscribed around \triangle, it satisfies your condition, and \operatorname{vol}(A) ... 0 Second derivative being positive is for strong convexity. There is a subtle difference between strict convexity and strong convexity. A strongly convex function is strictly convex but the converse need not be true. The condition for strict convexity is strict Jensen's inequality as pointed out by Alex R. 0 In addition to the other answer and my other comments, for (a) f_1 is neither convex nor concave. To see (and prove) it, just consider the intersection of the surface z=f_1(x,y) with the vertical plane x+y=10. It's this 1D curve (parametrized by x) : x \mapsto f_1(x,10-x). You can see a plot here (hopefully). Clearly this is neither convex nor ... 0 Yes, it is a core point, since it can be written as a convex combination (with \lambda=1/2) of the points$$x_{ij}=\left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right],\quad \text{ and } \quad z_{ij}=\left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right] $$that lie in Y^c. 1 This is impossible. For a proper convex and lower semicontinuous function the domain of definition of the subdifferential is dense in the domain of f,$$ \mathrm{dom}(f) = \overline{ D(\partial f)}. $$This implies that there is x\in X such that \partial f(x)\ne\emptyset, as for proper convex and lower semicontinuous f it holds \mathrm{dom}(f) \ne ... 1 It's not true. For example, \log I_1(x) is convex for  x > 3.056.... Here's a plot of \dfrac{d^2}{dx^2} \log I_1(x) for 1 < x < 5: In fact, asymptotically as x \to \infty we have$$ \eqalign{I_\nu(x) &\sim \dfrac{e^x}{\sqrt{2\pi x}} (1 + O(1/x))\cr \log I_\nu(x) &\sim \log(1/\sqrt{2\pi}) + x - \dfrac{\log x}{2} + O(1/x)\cr ...

2

This may not be the correct answer, just my guess. I suggest you discuss with your professor or classmates. If $f$ is twice differentiable, the $f^{''}\geq 0$ if and only if it is convex. And the larger $f^{''}$, the more convex it is. We can transform the condition to $P{''}(Q)< -\frac{P^{'}(Q)}{Q}$, where the RHS is positive. This gives an upper bound ...

2

Let $$g(n,k,x)=\sum_{j=0}^{k}\binom{n}{j}x^j(1-x)^{n-j}.$$ Assuming that $n$ is odd and $k<\frac{n}{2}$, and taking, for short, $g(x)=g(n,k,x)$, we just have to prove that $$g^{-1}(1-g(1-x))$$ is a convex function on $[0,1]$. This is equivalent to proving that $$h(x)=g^{-1}(1-g(x))$$ is a convex function on the same interval. $h(x)$ has an ...

1

If the convex set $C$ is closed, then $C$ is an intersection of half spaces $H_u^c=\{x\mid \langle x,u\rangle\leqslant c\}$ for some family $\mathcal H$ of pairs $(u,c)$ in $\mathbb R^n\times\mathbb R$. For every such pair $(u,c)$ in $\mathcal H$, $\langle X,u\rangle\leqslant c$ almost surely and $\langle E(X\mid \mathcal F_0),u\rangle=E(\langle ... 0 Here are some broad strokes. I think they'll lead to a complete proof rather directly. But please let me know if I'm wrong. Since$S$is a convex set, its closure is a convex set. Since$cl(S)$is a convex set, the line segment containing any two points in the set lies in$cl(S)$. Since$x\in \text{int}(S)$, at least part of the line segment connecting ... 1 In the following, we shall work with the following definition of the convex hull of a set$B$in a vector space$V$: Def: Let$V$be a vector space, and let$B \subseteq V$.$P \subseteq V$is called the convex hull of$B$iff$P$is a convex set such that$B \subseteq P$for all convex sets$Q \subseteq V$such that$B \subseteq Q$we have$P \subseteq ...

1

The solutions are unique if the norm of the Banach space is strictly convex: $$\|\lambda x + (1-\lambda)y\| = \lambda \|x\|+ (1-\lambda)\|y\|$$ only if $x=y$ or $\lambda\in\{0,1\}$. Or equivalently, $$\|\lambda x + (1-\lambda)y\| < \lambda \|x\|+ (1-\lambda)\|y\|$$ for all $x\ne y$, $\lambda\in(0,1)$. Now assume that the norm is strictly convex. ...

1

Yes, it is convex. $$f(\lambda x+(1-\lambda) y)\le \lambda f(x) + (1-\lambda) f(y)$$ for $x,y\in \mathbb{R}^n$, $\lambda \in [0,1]\;$. $$\frac{\sum(\lambda x_i+(1-\lambda)y_i)^2}{\sum(\lambda x_i+(1-\lambda)y_i)}\le\lambda \frac{\sum x_i^2}{\sum x_i}+(1-\lambda) \frac{\sum y_i^2}{\sum y_i}$$ So $$\lambda^2\sum x_i^2+(1-\lambda)^2\sum ... 0 We just have to show that$$ x+\frac{f'(x)}{f''(x)}>0 \tag{1}$$holds for any x big enough. We have that g\triangleq \log f on \mathbb{R}^+ is negative, decreasing and convex, so g'=\frac{f'}{f} is negative and increasing. Since f'=f g', we have f'' = f'g'+f g'' . Now (1) is equivalent to:$$ ...

0

I found a flaw in the answer below in the equation $F_1(K^c_1,L^c_1)=\phi F_1(K^a_1,L^a_1)+(1-\phi)F_1(K^a_1,L^a_1)$. As the question pointed out, showingthat $P$ is a cone is straightforward, convexity is not. I have not deleted the answer to see if a fix is possible. Suppose $(X^a_1,X^a_2,K^a,L^a)\in P$ and $(X^b_1,X^b_2,K^b,L^b)\in P$. Then, by ...

0

I eventually found what I was looking for in this paper: M. Ghomi. Optimal smoothing for convex polytopes. Bull. London. Math. Soc. 36 (2004), 483-492.

1

For any real-valued function $h$, $\alpha\in[0,1]$ and $x,y$ in the (convex) domain, let $$D(h,\alpha,x,y)=\alpha h(x)+(1-\alpha)h(y)-h[\alpha x+(1-\alpha)y].$$ Convexity for $h$ means $D(h,\alpha,x,y)\geq 0$ for all $\alpha,x,y$. For your situation, one sufficient condition for $f-g$ to be convex is that $$D(f,\alpha,x,y)\geq D(g,\alpha,x,y)\tag{i}$$ ...

1

$f\ge g$ is not sufficient: for example, take $f(x)=\sqrt{x^2+1}$ and $g(x)=|x|$ (with $X=\mathbb R$); for another, take $f(x)=|x|$ and $g(x)=\max\ \{0,|x|-1\}$.

2

Suppose that $f\colon (a,b)\to \mathbb{R}$ is convex. Consider the function $$F(x,t) = \frac{f(x+t) - f(x)}{t}\quad(t\neq 0).$$ Then $F$ is increasing in each variable. So $F$ is uniformly bounded on each compact subinterval $[c,d]\subset (a,b)$. In particular, $f$ is Lipschitz on $[c,d]$ hence absolutely continuous.

0

You could replace each $u_i$ with $u_i-u_0$, so you would have $k$ linearly independent points plus the origin. This is likely to be less convenient though. In any simplicial complex that isn't just a 1-simplex there is no point that is shared by all the simplices, so the different simplices would have to be defined with respect to different origins. (Edit: ...

0

ended up with the case that if the Hilbert Cube is a convex body, then $t=0$ is the only value that may satisfy $x + ty\in$ Hilbert Cube This is not a complete statement without quantifiers on $x, y$. Did you mean: For all $x,y$? For some $x,y$? For all $x$ and some $y$ dependent on $x$? Etc. Here's a precise statement you can prove: there is $y$ such ...

0

The chord doesn't have to contain a vertex of $P$, as this example shows: $AB$ is clearly longer than $CD$.

2

You can explicitly write down a parametrization of $K$, showing that it's a continuous image of a compact set. But here is a general argument. Claim If $A\subset \mathbb R^n$ is compact and $C$ is the smallest convex set containing $A$, then $C$ is compact. Proof. The set $C$, also known as the convex hull of $C$ consists of all finite convex ...

0

Create a Voronoi diagram then, using edges of the Voronoi regions, create a binary decision tree with depth $O(\ln n)$ to determine the region in which each query point lies. You can do better if you are willing to spend memory. Find a boundary circle where all the regions outside of it are radial, i.e. they look like a WWII Japanese flag and any ray from ...

0

I'm thinking here in terms of a strategy where you spend time analyzing the polygon, then run many queries on many points $q$, so you want to optimize the time per $q$. It would be different if you were given many polygons and only wanted to test one point per polygon. Let $R_{a,b}$ be the half-plane where point $a$ is farther than point $b$. Then ...

1

Hint: If the vertices are sorted by angle (azimuth) from any interior point (e.g. the centeroid), you can achieve $O(\log n)$. If the vertices are in any order, in the worst case you will need $\Omega(n)$ checks. I hope this helps $\ddot\smile$

2

The constraints of optimization problems are typically written as a system of equations and inequalities. In order to ensure that the feasible region is convex, one assumes that the $g_i$ are convex, and the equation constraints are affine linear. That said, linear affine equations always yield a convex feasible set. Nonlinear equations as constraints might ...

1

Edited to add: I guess this answer doesn't really address the OP's question, since it sounds like he wants to write this code from the ground up. First (perhaps this is assumed) you should check that $u_1$ and $u_2$ are vertices of $P$. (Eg, this can be done by checking that the convex hull of $F\setminus\{u_i\}$ is different from the convex hull of ...

2

This is an over-kill, but you can use the software Polymake to compute all edges of a polytope, which is given as a convex hull of a finite set.

0

Every convex function is continuous.

2

Jarvis' March (Gift Wrapping) Algorithm takes $O(nh)$ time, where $h$ is number of points on convex hull. Hint: Suppose algorithm takes $i$ iterations to complete, and $h_k$ be the number of points on the $k$th convex hull $(1 \le k \le i )$. Also, let $n_k$ be the number of points remaining after first $k-1$ iterations. (Note that $n_1 = n, n_{i+1} = 0$). ...

1

Just compute the convex hull of the centers. Since all the circles ('disks' would have been a better and equivalent formulation) have the same radius, the convex hull of the circles is the Minkowski sum of {the convex hull of the centers} and {the unit disk}.

0

Take $f(x) = (\operatorname{sgn} x) x^2$. Then $f$ is strictly monotonic (hence strictly quasi-convex) and $f'(0) = 0$, but $f$ has no local $\max$ or $\min$.

1

The set of points of nondifferentiability can be dense. But you correctly conjectured that it is at most countable. First, convexity implies that for $s<u\le v<t$ we have $$\frac{f(u)-f(s)}{u-s}\leq\frac{f(t)-f(v)}{t-v} \tag{1}$$ Sketch of the proof of (1). First, use the 3-point convexity definition to show this for $u=v$. When $u<v$, proceed ...

0

Maybe the following example fits you: Consider $X := [0,1] \times [0,1[ ~\cup ~\{(0,1),(1,1)\} \subset \mathbb R^2$, equipped with the induced metric, and $Y := [0,1] \subset \mathbb R$, again equipped with the induced metric. Now form the topological space $Z = X \cup Y /\sim$ obtained by the disjoint union where the points $(0,1)$ and $0$, respectively ...

Top 50 recent answers are included