# Tag Info

## New answers tagged convex-analysis

0

$u$ need not be near $\pm e_2$ at all. Consider for example $u = e_3$ and $a_i$ a set of unit vectors lying fairly uniformly on an very small ellipse centered on $e_3$. (It makes sense to talk about an ellipse on the surface of a unit sphere, particularly if the ellipse is tiny so that the surface is nearly flat.) If the major axis of the ellipses is in ...

1

Consider $x$ such that $\|x\| = 1$. Then you also have that $\|-x\| = 1$ but what about $\frac{1}{2}(x+(-x))$? This has norm $0$ and so $\frac{1}{2}(x+(-x))$ is not in the set, i.e. the unit sphere is not closed under convex combinations.

5

What makes a constraint convex is not the convexity (or otherwise) of the functions involved, but rather the convexity of the set of points that satisfy the constraint. The set of points satisfying $\|w\|=1$ is the surface of a norm ball. For the Euclidean norm $\|w\|=\langle w, w\rangle^{1/2}$, it is the surface of an $n$-sphere. These points do not form ...

4

The right hand $\;\binom{2n}n\;$ is the number of sets with $\;n\;$ elements that a set with $\;2n\;$ elements has. Suppose we take the set $\;X=\{1,2,...,n,n+1,...,2n\}\;$ for simplicity, and then we have $$\{1,2,...,n\}\,,\,\,\{1,2,..,n-1,n+1\}\;,\;\;\{1,2,...,n-1,n+2\}\,,\;\ldots,\{1,2,..,n-1,2n\}$$ The above are already $\;n+1\;$ subsets with $\;n\;$ ...

3

Let $A$ and $B$ be two disjoint sets with $n$ elements, and $C=A\cup B$. Consider subsets of $C$ of the form $\lbrace a \rbrace \cup (B \setminus \lbrace b \rbrace)$ for $(a,b)\in A\times B$. There are $n^2$ such subsets, so $\binom{2n}{n} \geq n^2$.

2

If you know both the $V$ and $H$ representations of your original polytope, then each of the two polytopes have vertices given by the original vertices that are all on one side of the hyperplane (i.e. $c \cdot x \leq d$ or $c \cdot x \geq d$), combined with the new vertices given by the vertices of the solution to the combined equations/inequalities $c \cdot ... 1 If the Hessian is positive definite then the function is convex. A differentiable convex function satisfies$f(x)-f(y) \ge Df(y)(x-y)$for all$x,y$. Hence if$Df(x_0) = 0$, then$x_0$must be a (global) minimiser. Proof of above result: Let$\phi(t) = f(y+th)$, then since$\phi$is convex, we have$\phi(t)-\phi(0) \le (1-t) \phi(0)+t \phi(1) - \phi(0) = t ...

1

Your values of $(a,b,c)$ must satisfy $$a,c\leq 0, \quad b/2 \leq \sqrt{ac}$$ if you wish to ensure that $f(x,y)$ is concave; that is, that $Q$ is negative semidefinite. Since you already have three equations for your three unknowns, your problem is overdetermined. You'll want to minimize some sort of fitting error subject to these constraints, which happen ...

1

As noted in the comments (thanks Michael Grant), I was overcomplicating things. It's easy to show non-convexity with respect to $w$. First, consider $w \in \mathbb{R}^{1}$ and show that (the negative of) $f$ is not convex by checking a couple of values of $w$. Secondly, note that $f$ is undefined for $w = \vec{0}$, implying that the $w$ domain of $f$ is ...

2

No, such a region must be convex. Suppose it were not convex, so that there were points $P, Q, R$ with $P, R\in C$, $Q\in\overline{PR}$, but $Q\not\in C$. Then we can WLOG assume $P, R\in int(C)$ (if not, wiggle them a little bit); now the line joining $P$ and $R$ must pass through at least three points not in $C$: a $Q_0$ on the ray $QP$ "past $P$," ...

0

Assume $X\subseteq \mathbb R^n$ is a nonempty convex set. If $X$ has no interior points then $\partial X=\overline X$ is convex and hence path-connected. Hence assume wlog. that $0\in X^\circ$. For $a\in\partial X$ let $P(a)$ be the set of points $p\in \partial X$ that can be reached from $p$ by a path in $\partial X$. Claim. $P(a)$ is a clopen subset of ...

0

Some hints. To simplify the topic, you can suppose your convex $C$ to be closed. Hence compact as bounded. And with a non empty interior in order to avoid your hypothesis to be void. Suppose $C$ convex Then take any point $x \in int(C)$ and a line $L$ going through $x$. The line is convex and the intersection of two convex subsets is convex. So $L \cap C$ ...

2

No. Consider in the plane a "plus sign" that's one point thick, i.e., a union of line segments. It has no interior points, so your condition vacuously holds, but it's not convex. By "a plus sign", I mean $$([-1, 1] \times \{ 0 \} ) \cup ( \{ 0 \} \times [-1, 1]).$$

1

Let $X$ be a nonempty bounded convex subset of $\mathbb R^n$. If $X$ has no interior points, then $\partial X=\overline X$ is again convex and hence path connected. If $X$ does have interior points we may assume wlog. (after translation) that $0$ is an interior point. Consider the map \begin{align}f\colon \partial X&\to S^{n-1}\\ x&\mapsto \frac ... 2 No, it's not true. Let A=\{(x,y)\mid 0<x<1\}. Then A is convex and the closure of A minus the interior of A is \{(x,y)\mid x=0\}\cup\{(x,y)\mid x=1\}. Not connected. If you also require A to be compact then I have a feeling it may be true. 0 See the answer to your question at this thread and discussion on the topic. 0 We have \|a^0-b\|\ge\|a^0-b^0\|\, \forall b\in B. Hence\langle a^0-b^0,\, (a^0-b)-(a^0-b^0)\rangle=\langle a^0-b^0,\, b^0-b\rangle\ge 0\, \forall b\in B.$$Thus,$$\langle g^0,b^0\rangle\ge\langle g^0,b\rangle\, \forall b\in B.$$This implies that \langle g^0,b^0\rangle=\sigma_B(g^0). Similarly, we also have \langle g^0,a^0\rangle=\sigma_A(g^0). ... 0 Following Mercio's comment, it's still the Euclidean algorithm if we make the ovals 2× as big. 1 The orthogonal projection of D_\gamma onto any line is a connected, compact set with nonempty interior: thus, a closed interval of positive length. The endpoints of this interval correspond to supporting lines. The interior points of the interval correspond to lines L such that D_\gamma\setminus L is disconnected: since D_\gamma is a topological ... 2 If you're going to apply multivariable calculus tools to the distance function, it's best to use the squared distance function:$$f(\omega)=\|x-\omega\|^2,\quad g(\omega)=\langle a,\omega\rangle$$The minimum is attained in the same place, but this f expands as inner product, allowing for simpler computations: \nabla f(\omega) = 2(\omega-x). So, the ... 2 Here is a simple explanation if you know some linear algebra and polyhedral geometry: Given d vectors in R^d, that form a d \times d matrix A, the volume of the parallelopiped \{ \sum_i c_i v_i \, | \, 0 \leq c_i \leq 1\} spanned by the vectors is the absolute value of the determinant of A. The volume of the simplex \{ \sum_i c_i v_i \, | \, c_i ... 0 Proof for completeness (compiling the comments). Let f(x)=-2\lambda\|x\|^2. Then f is strongly convex with parameter -\lambda>0. Therefore, V+f is convex. It follows that the graph of V+f lies above any of its tangent planes. So, V+f is bounded from below by a linear function L, and thus V\ge L-f. 5 Let g be the linear function that agrees with f at 0 and \|x\|_2: specifically,$$g(t) = \frac{f(\|x\|_2)}{\|x\|_2} t$$By convexity, f(t)\le g(t) for 0\le t\le \|x\|_2. Assuming f is nondecreasing, we also have |f(t)|=f(t)\le g(t). Hence,$$\|(f(x_1),\cdots,f(x_n))\|_2\leq \|(g(x_1),\cdots,g(x_n))\|_2 = g(\|x\|_2) = f(\|x\|_2)$$... 2 Here is one proof of (\operatorname{aff} C - \operatorname{aff} C) \subset \operatorname{aff} (C - C). Note that S is affine iff S can be written as \{x_0\}+L for some linear space L. Let \operatorname{aff} C = \{x_0\} +L. Then \operatorname{aff} C - \operatorname{aff} C = \{x_0\} +L + \{-x_0\} +(-L) = L, hence \operatorname{aff} C - ... 0 Yes: If a number lies between a and b, then it lies in the interval that a and b lie in. 2 Yes. Intuitively, \lambda a+(1-\lambda) b is between a and b. More formally, assume that a>b (if not, just change the names). Then \lambda a+(1-\lambda)b=b+\lambda(a-b) and$$1-\epsilon <b<b+\lambda(a-b)<b+1(a-b)=a<1+\epsilon$$4 @math110 is right, but you have started with the wrong inequality. You can use concavity instead directly and get:$$\frac{x}{x+y}\ln \left(\frac{a}x \right)+\frac{y}{x+y}\ln \left(\frac{b}y \right) \le \ln\left(\frac{a+b}{x+y} \right)$$Now multiplying throughout by -1 (which flips the fractions in parentheses) gets you what you want. 0 What you have: Set-valued upper semicontinuity is defined as the openness of \{ x : \phi(x)\subset U\} for every open set U. What you want: The lower semicontinuity of f\circ F  means that for every r, the set \{x:f(F(x))>r\} is open. Let's rephrase this to be more similar to 1): for every r>0, the set \{x:F(x)\subset \{y:|y|>r\}\} ... 4 use Cauchy-Schwarz inequality we have$$\left(\dfrac{x^2}{a}+\dfrac{y^2}{b}\right)(a+b)\ge (x+y)^2$$0 If convex set B contains more than one point, there is a convex set A with empty interior such that 0 \in \text{int}(A-B). Namely, if b_1, b_2 \in B, let f be a continuous linear functional such that f(b_1) \ne f(b_2), and let A = \{x: f(x) = (f(b_1) + f(b_2))/2. This shows that your conditions would have to involve A as well as B. 2 Let A= \{ (x,0) | x^2 \le 1\}, B=\{ (x,y) | x^2+y^2 \le 1 , y \ge 0\}. Then A \subset B, but \operatorname{ri} A = (-1,1) \times \{0\}, \operatorname{ri} B = \{ (x,y) | x^2+y^2 < 1 , y > 0\}, hence \operatorname{ri} A \cap \operatorname{ri} B = \emptyset. 1 If x \mapsto f(x,t) is convex for each t, and \mu is a positive measure, then x \mapsto \int f(x,t) d\mu(t) is convex. It follows that convex combinations of convex functions are convex. Hence \alpha \to J(c,\alpha) is convex. In particular, since (\alpha,x) = ( \alpha c-I(x))^2u is convex for each x, then (\alpha,x) = \int_\Omega ( \alpha ... 2 As a function of c, it is convex. As a function of \alpha, it is convex. But it is not jointly convex in \alpha and c. 3 I presume \text{aff} A means the affine hull of A (in some normed linear space), and \text{ri} A is the relative interior of A with respect to this affine hull. No, it's not true. In \mathbb R^2, let A be a line segment, and let B be the union of A with some point not on A. Then \text{ri}(A) is nonempty, but \text{ri}(B) is empty. 1 Here's another way to see it. Assume that c and p are distinct, otherwise the vector from p to c doesn't determine a particular hyperplane. You'd like to show that, for x in \Omega,$$(x - c)\cdot (c-p) \le 0.$$Suppose not, and consider an x in \Omega for which (x - c)\cdot (c-p) > 0. Take a positive \varepsilon and consider the ... 1 We prove that if A and B are linear manifolds then A+B is also a linear manifold. Indeed, let x,y\in A+B and \lambda\in\mathbb{R}. Then there exist x_a,y_a\in A and x_b,y_b\in B such that x_a+x_b=x and y_a+y_b=y. Then$$ \lambda x+(1-\lambda)y=\lambda(x_a+x_b)+(1-\lambda)(y_a+y_b)=[\lambda x_a+(1-\lambda)y_a]+[\lambda x_b+(1-\lambda)y_b]. ...

2

I am assuming that $p \neq c$, that is, $p \in \Omega^\circ$, otherwise any vector passes through $c-p$. The essential idea is that a supporting hyperplace to $\Omega$ at $c$ is also a supporting hyperplane to $B(p,\|c-p\|)$ at $c$, and the direction of this hyperplane is unique. We use the following technical results: If $x \in \Omega^\circ$ and $y \in ... 0 I don't know if this is particularly helpful in your situation, but you might consider the 'double' Legendre transform. What I mean is the following: Let$f$represent your function. I assume$f: D \to \mathbb{R}$, where$D \subset \mathbb{R}^3$is some suitable domain. The Legendre transform of$f$, denoted by$f^{*}$, is the function defined by ... 3 One approach is to prove that a point in the convex hull of a set in$\mathbb R^n$is actually a convex combination of at most$n+1$points, by a natural induction. Then the convex hull is the continuous image of the cartesian product of$n+1$copies of your set and the$n$-simplex, which is compact. A continuous image of compact is compact. 17 The convex hull of$\{\,(x,y)\mid x^2y=1\,\}$is not closed in$\mathbb R^2$(it is the open upper half plane). 2 Actually, from your relation, just apply "ri" to get $$\rm{ri\,conv\,rge}A=\rm{ri}(\rm{ri\,conv\,rge}A)\subset \rm{ri\,rge}A\subset\rm{ri\,conv\,rge}A,$$ from which$\rm{ri\,rge}A=\rm{ri\,conv\,rge}A$is convex. 1 Since$A$is convex, for all$x,z\in A$,$\theta \in [0,1]$,$x + \theta(z-x) \in A$$$\|y - (x + \theta(z-x))\|^2 = \|y - x\|^2 - 2\theta \langle y-x,z-x\rangle + \theta^2\|z-x\|^2$$ So if$\langle y-x,z-x\rangle \le 0$for all$z\in A$, take$\theta=1$in the above equation to show$\|y-z\|^2 \ge \|y - x\|^2$. On the other hand, if for some$z\in A$... 0 Fix$b\in \mathbb {R}.$Suppose$a<b<c.$Let$s(a,b)$be the slope of the line connecting$(a,f(a)),(b,f(b)).$Similarly define$s(b,c).$Key fact:$s(a,b)\le s(b,c).$(Good to draw a picture.) Thus we can define $$m_1 = \sup_{a<b}s(a,b),\,\, , m_2 = \inf_{b<c} s(b,c).$$ Both$m_1,m_2 \in \mathbb {R}$and$m_1\le m_2.$Let$m\in [m_1,m_2].Set ... 0 Taking the Hessian gives $$\frac{\partial^2}{\partial x_j\partial x_k}f(x) =\overbrace{\begin{bmatrix} \frac1{x_1}&0&0&\cdots&0\\ 0&\frac1{x_2}&0&\cdots&0\\ 0&0&\frac1{x_3}&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\frac1{x_n} ... 2 Pick x_0, then there is an affine function g(x) = ax+b such that f(x_0) = g(x_0) and f(x) \ge g(x) for all x. This is true in \mathbb{R}^n as well. The proof relies on a number of facts about convex sets. The proof below is surprisingly technical for a geometrically obvious fact (of course, I may be missing a much simpler proof that utilises the ... 2 I assume you can prove, by definition, that x^2 is strictly convex. Now, you use this result twice:$$ \begin{aligned} ((1-t)x + ty)^4 &= (((1 - t)x + ty)^2)^2 \\ &< ((1-t)x^2 + ty^2)^2 &\quad (x^2 \text{ is strictly convex})\\ &< (1-t)(x^2)^2 + t(y^2)^2 &\quad (x^2 \text { is strictly ... 1 Assuming0\leq \lambda \leq 1$, $$||\lambda x_1 + (1-\lambda)x_2 - y|| = ||\lambda x_1 + (1-\lambda)x_2 - (\lambda + (1-\lambda))y||$$$$\leq ||\lambda x_1 - \lambda y|| + ||(1-\lambda)x_2 - (1-\lambda)y||$$$$= \lambda||x_1 - y|| + (1-\lambda)||x_2 - y||$$$$= \lambda||x_1 - y|| + (1-\lambda)||x_1 - y|| = ||x_1 - y||$$ 1 I assume you mean the constraint$x^T Px + 2c^Tx + s \leq 0$. For intuition on the difficulty of this constraint, let us assume we also have constraints$x_i \in [0,1]$for all$i \in\{1, \ldots, n\}$. Now consider your single constraint in the special case$P=-I$,$c=(1/2, \ldots, 1/2)$,$s=0$: $$-x^Tx + 1^Tx \leq 0$$ This is equivalent to saying: ... 0 Lets denote$A=\{ x: \| x-a \|_2 \leq r\}$and$B=\{ x: \| x-a \|_2 < r\}$, then if$x \in B$, put$R=r-\|x-a\|_2$, and then $$B_R(x) = \{ y : \| y-x\|_2< R \} \subset A$$ This gives that any point in$B$is an interior point of$A$. Now if you take any$x \not\in B$($x$is such that$\|x-a\|_2\geq r$) then for any$R>0$,$B_R(x)$is not totally ... 0 Apply the triangle inequality to$ ||\lambda(x_1-y)+(1-\lambda)(x_2-y)||\$.

Top 50 recent answers are included