Tag Info

New answers tagged

0

This is not, actually, a linear program, because you haven't specified S in LP form (and you haven't even said that it is polyhedral). It's convex though. Let $I_\mathcal{S}$ be the indicator function for $\mathcal{S}$; that is $$I_\mathcal{S}(x) = \begin{cases} 0 & x\in\mathcal{S} \\ +\infty & x\not\in\mathcal{S} \end{cases}$$ The convex conjugate ...


2

I would start from a classic: Bertsekas, Dimitri P., and John N. Tsitsiklis. Parallel and distributed computation: numerical methods. Prentice-Hall, Inc., 1989.


0

We call $h$ a subgradient of $f$ at $x$ iff $f(y) -f(x) \ge \langle h, y-x \rangle$ for all $y$. The usual notation for the set of subgradients at $x$ is $\partial f(x)$. The implication 2) $\Rightarrow$ 1) is straightforward. Suppose $h \in \partial f(x) \cap \partial f(y)$. Then we have $f(x) -f(y) \ge \langle h, x-y \rangle$ and $f(y) -f(x) \ge \langle ...


1

The claim is incorrect. Consider the following counter-example: $$A=\left\{ \left(x,y\right)\in\mathbb{R}^{2}:0<x<1\right\} \cup\left\{ \left(0,0\right)\right\}\\a=\left(0,0\right)$$ It is correct if you require $A$ to be closed or $a$ to be in $\text{rel int}A$. Since for every non-empty convex set we have $\text{rel int}A\ne\emptyset$, it implies ...


1

First observe that there exist $0 < a < b < \infty$ such that $a < \vert x_0 \vert < b$ for all $x_0 \in \partial (\Omega_1 \setminus \Omega_2)$, since $\Omega_i$ is bounded, $0 \in \Omega_2$ and $\Omega_2$ is open. Now let $x_0$ and $z$ be arbitrary, satisfying $(*)$. Then $\vert z - x_0 \vert = \delta$, since $x_0 \in \partial B(z,\delta)$. ...


1

The coefficients that arise in an affine combination of three 2D points are called barycentric coordinates. See here and here for more information. These coordinates actually represent the (signed) areas of triangles, as the references explain. When a point is inside a triangle, the three relevant areas are all positive, so the barycentric coordinates ...


1

To show that $g$ is increasing,assume to the contrary that there exists $x,y\in I$ such that $x<y$ but $g(x)>g(y)$. Since $f$ is increasing and $g(x),g(y)\in[0,1]$ then $f(g(x))>f(g(y))\Rightarrow x>y$ which is a contradiction. Now lets prove the second part. Let $x,y\in I$ and put $t=g(x),\:s=g(y)$. By concavity of $f$ we have $$f(\lambda ...


3

If $g(x) = y$, I get $$ h''(x) = \dfrac{f''(y/2) f'(y) - 2 f'(y/2) f''(y)}{4 f'(y)^3} $$ so for $h$ to be convex requires $$ \dfrac{f''(y/2)}{f'(y/2)} \ge 2 \dfrac{f''(y)}{f'(y)}$$ For a counterexample, take $f$ that is strictly concave on $[0,1/2]$ but linear on $[1/2, 1]$, so that if $1/2 \le y < 1$ we have $f''(y) = 0$ but $f''(y/2) < 0$.


1

$T(S, \bar{x}) + \bar{x}$ includes $S$ if $S$ is convex. Note that it is also a cone, i.e. if $y \in T(S, \bar{x})$, then $\lambda y \in T(S, \bar{x})$ for any real $\lambda \geq 0$. To see the first assertion, for any $x \in S$ take a sequence $(x_n)$ of points on the segment $\{(1-\alpha) x + \alpha\bar{x}: \alpha \in [0, 1)\}$ that converges to ...


1

First of all, let's clear something up. Note that the tangent cone is a set of vectors at a point, which is not exactly the set of points in the highlighted region (the two sets contain elements of different "data types"). The question that you seem to be thinking of, then, is whether the tangent cone at a point contains vectors that point from $\bar x$ ...


2

Yes, correct and also true in reflexive Banach spaces. Kakutani's theorem (at least the direction you use in the proof) is also a special case of Banach-Alaoglu theorem. In History of Banach Spaces and Linear Operators, Albrecht Pietsch remarks ... the weak* compactness theorem is an elementary corollary of Tychonoff's theorem. Therefore priority ...


1

Yes. For non-strict inequality $f\le f*\phi$ to hold, you only need $f$ to be convex (no smoothness assumptions) and $\phi$ to be nonnegative normalized ($\int \phi=1$) compactly supported (so we don't get into trouble at infinity) even: $\phi(-x)=\phi(x)$ All of these properties hold in your example. The proof goes: $$\begin{split} f(x) &= \int ...


1

Yes to both questions. First, recall that a closed convex set in a Hilbert space is weakly closed, and that a weakly closed and norm bounded set is weakly compact (Alaoglu's theorem). Let $\epsilon := \inf\{\|x-y\| : x \in A, y \in B\}$. We will show there exist $x \in A$, $y \in B$ with $\|x-y\| = \epsilon$ which proves both statements. Choose a sequence ...


2

Assume that $A$ is bounded. Take $x_n\in A, y_n\in B$ such that $\lim||x_n-y_n||=e$. Since $A$ is bounded - sequence $x_n$ is bounded and so is $y_n$. Thus using Banach-Alaoglu theorem one can choose subsequences $x_{n_k},y_{n_k}$ converging in the weak topology to $x,y$. Now since closed and convex sets are weakly closed (Mazur theorem) one gets that $x\in ...


1

Hint: You correctly compute $$ \frac{d^2\log g}{dx^2} = \frac{f''(f-a)-(f')^2}{(f-a)^2}. $$ When $a=0$, we know this quantity is non-positive, so the numerator is non-positive. Focus just on the numerator. What happens to the numerator when $a$ increases from $0$? Can you say whether this expression remains non-positive? Note that by assumption, $f-a ...


1

No. Consider a smooth function $f$ and let $g(x)=\log(1/f(x))=-\log(f(x))$. Differentiate to get $g'(x)=-f'(x)/f(x)$, and repeat to get $$g''(x)=\frac{\bigl(f'(x)\bigr)^2-f(x)f''(x)}{\bigl(f(x)\bigr)^2}$$ so $g$ is (strictly) concave iff $$\bigl(f'(x)\bigr)^2<f(x)f''(x).$$ If you were to replace $f(x)$ by $f(x)+K$ this inequality becomes instead ...


1

Constructive proof: Consider some nonzero substochastic matrix $P$ with equal-row-sums. Call $P_{is(i)}$ one of the minimal nonzero entries of row $i$, and consider the deterministic matrix $D$ such that $D_{is(i)}=1$ for every $i$ and $D_{ij}=0$ otherwise. Finally, define $m(P)=\min\{P_{ij}\mid P_{ij}\ne0\}$. Then $P-m(P)D$ is a substochastic matrix with ...


2

Yes. Note that there are constants $b, c > 0$ such that $b \|x\|_2 \le \|Ax\|_2 \le c \|x\|_2$ for all $x$. So $f \circ A$ is strongly convex if $f$ is strongly convex (but with a different $m$); if $A$ is onto this is if and only if.


10

Here's the way I like to think about it. I'll start with the finite dimensional space $\Bbb{R}^n$ because it looks like that's where you are, but I'll give an analogy for infinite dimensional spaces as well. The quantity $z^Tx$ represents a linear functional on $\Bbb{R}^n$, that is a linear function which eats a vector and spits out a real number: $$ ...


4

The dual space is a space of linear functionals. If we want to define a norm on the dual space, we do what we always do to measure the "size" of a linear transformation: we use an operator norm. Alternatively, the dual norm of $z$ is the matrix norm of the matrix $z^T$.


2

Dual norm is a particular case of the support function, specifically it is the support function of the unit ball of the original norm. When the unit ball is smooth enough $\|z\|_*$ is the Euclidean distance from the origin to the hyperplane with the normal vector $z$ (of unit Euclidean length) tangent to the ball. The equation of this hyperplane is ...


4

Indeed, in your setting, $f''\geqslant g''$ implies $f\geqslant g$. To show this, note that, since $f(0)=g(0)=0$, for every nonnegative $x$, $$f(x)=\int_0^xf'(t)\,\mathrm dt,\qquad g(x)=\int_0^xg'(t)\,\mathrm dt.$$ Using the hypothesis that $f'(0)=g'(0)=0$, an integration by parts of these identities yields $$f(x)=\int_0^x(x-t)f''(t)\,\mathrm ...


1

As your own example shows non-degeneracy of the Hessian is not necessary. You can easily extend it to any $\mathbb{R}^n$ by taking $f(x)=x_1^4+\dots+x_n^4$. The problem is that non-degeneracy of the Hessian guarantees convexity to quadratic order near each point which is stronger than just strict convexity. In fact, strict convexity can be arbitrarily close ...


0

Its the Gilbert–Johnson–Keerthi (GJK) algorithm, man, see here.


2

Yes, this is true. The direction $$\limsup_{n\to\infty} \inf_G f_n \le \inf_G f$$ is easy and does not require convexity. For the reverse direction, begin by observing that $$M:=\max_{x\in \{0,1/2,1\}}\sup_n |f_n(x)|$$ is finite due to pointwise convergence. Convexity implies that $f_n\le M$ and $f_n\ge -3M$ on $[0,1]$, the latter coming from the fact that ...


0

Another possible method: Given any two points $x,y\in \mathbb{R}^n$, the function is convex on the straight line between them, which is sufficient. This can be shown by observing that $\tilde{f}: t\mapsto f((1-t)x + ty)$ has non-decreasing derivative on $[0,1]$ (draw a picture), and therefore, it is convex.


1

What a great question! The term "log-log convexity" is indeed used to refer to the property you have described. It pops up in literature on polynomial optimization, and also in a bit of a disguised manner in geometric programming. Let's look at the latter case, because to be honest that's what I'm personally familiar with. Consider an expression of the form ...


1

You are correct. Since the slopes are increasing on a convex function then: $$\frac{f(a)-f(b)}{a-b}\ge\frac{f(b+h)-f(b)}{h}$$ where $h>0$ and small enough that $b+h<a$. Letting $h$ tend to $0$ gives the inequality that you describe. However, the inequality may not be strict unless the function is strictly convex.


10

For completeness, I add some numerical details to the excellent answer by Noam D. Elkies. Let $C$ be the cone such that the lateral surface unrolls to a circular sector of angle $2\theta$. There are two sources of distortion: Between two points on lateral surface (worst case: same level, diametrally opposite). This gives $c\ge (\pi/\theta) ...


1

No, you don't need another tool. Parallelogram law is good enough: One has $$4=\|x+y\|^2+\|x-y\|^2\ge \|x+y\|^2+\epsilon^2.$$ So $$\epsilon^2\le 4-\|x+y\|^2=(2-\|x+y\|)(2+\|x+y\|).$$ Can you find the constant $C$ so that $1-\|\frac12(x+y)\|\ge C\epsilon^2$ from here?


2

Let $f(s) = s^p$ for some $p>1$, then for every $s\geq 0$m we have $$f''(s) = \underbrace{p(p-1)}_{>0}\,\underbrace{s^{p-2}\vphantom{)}}_{\geq 0} \geq 0$$ and thus $f$ is convex on the non negative numbers. So for any $x_1,x_2 \in X$ and $t \in (0,1)$ we get $$\frac{1}{p}\|x_1t + (1-t)x_2 \|^p \overset{(1)}{\leq} \frac{1}{p}(t\| x_1\|+(1-t)\|x_2\|)^p ...


17

How about a sharp cone? Suppose the cone's lateral surface unrolls to a circular sector of angle $2\theta$ for some small positive $\theta$. Then: $\bullet$ the base is flat, so any $a,b$ on the base are joined by a line of length $|a-b|$. $\bullet$ if $a$ is on the base and $b$ on the side, then we can choose $\gamma$ to go straight down from $b$ to the ...


2

If you assumed $f''$ continuous, this would be true. As stated, this is false. To give a counterexample, it suffices to construct a differentiable function $g:[-1,1]\to\mathbb R$ such that $g'>0$ everywhere and $\inf g'=0$. Then $f$ will be its antiderivative. The idea is as follows. Take two differentiable functions that have the same tangent line at ...


1

For Question $0$: Suppose points $A,B,C$ are witnesses to the non-concavity of $f$; that is, they are points on the graph of $f$ such that $x_A < x_B < x_C$ and $y_B < y_A + \dfrac{x_B-x_A}{x_C-x_A}(y_C-y_A)$. This is the picture: Claim: If $f$ is $2$-limited, the graph of $f$ can't enter the interior of the shaded regions. (We call the union of ...


1

I would use restrictions to lines: $\phi_{a,b}(t) = f(a+tb)$ where $t\in\mathbb R$ and $a,b\in\mathbb R^2$ and $b\ne 0$. The key points are: $f$ is convex if and only if $\phi_{a,b}$ is convex for every $a,b$. This follows from the fact that definition of convexity involves points on the same line. The Hessian of $f$ is nonnegative definite (aka positive ...


0

Yes this can happen. Let $K_1 = \{(x,y,z) : x^2+y^2\leq z^2 \}$ be the second order cone in $\mathbb{R}^3$, and let $K_2 = \{ t(1,0,-1) : t \geq 0\}$. Then $(0,1,0)$ is not an element of $K_1 + K_2$. But $(0,1,0) = \lim_{t \to \infty} [t(1,0,-1) + (-t,1+1/t,\sqrt{t^2+(1+1/t)^2})]$.


0

One key idea is the connection between balanced absorbing convex sets and (semi-)norms. They are basically one and the same. For every norm the unit ball under that norm is a convex set. Similarly, any balanced bounded absorbing convex set generates a norm via the Minkowski functional (ie: how much do you have to scale the set to hit your point? Define ...


0

To me, the primary relevance of convex spaces is in its very definition: When a space contains two points, it also contains the line segment connecting them. As for convex functions, one justification at calculus level is the uniqueness of local minimum. The most interesting theorem in "real analysis" regarding convex functions is the Jensen's inequality ...


3

Maybe the following can at least partly answer your question. First we look at topological vector spaces in increasing generality: \begin{align*} &\text{finite dimensional vector spaces - Hilbert Spaces - Banach Spaces}\\ &\text{Frechet Spaces - locally convex vector spaces}\\ \end{align*} as Jänich does in his Topology. There he mentions ...


0

I don't think you read the proof right. Not sure how to address your specific question so I'll just explain the proof instead. The first step is to simply show that $(A \cap B)^* \supseteq A^* + B^*$ from first principles. The rest of the proof is to show the reverse inclusion. He shows that $(A^* + B^*)^* \subseteq A^{**} + B^{**}$ by utilizing F2 and ...


1

Mathematics is always a fine line between imposing conditions that are Strong enough to give you tools with which to show interesting results Weak enough to cover interesting applications Strange enough to not be easily analyzed or trivialized The condition of local convexity happens to be Strong enough to leave you with a rich dual theory, due to the ...


1

For Question 0: We are given a continious function $f(x)$ with the 2-limited property. Draw a line $l(x)=f(0)+x\left(f(1)-f(0)\right)$ between $f(0)$ and $f(1)$ and decide whether $f(\frac{1}{2})$ lies above or under the line. It is not possible that $f(\frac{1}{2})$ lies on the line, that violates the 2-limited property. From now assume that ...


1

For Question 1: Take the hyperbola $f(x) = \sqrt{1+x^2}$ through $(0,1)$ with asymptotes $y = \pm x$. Then define $$g(x) = \begin{cases} f(x), & \text{if $x \ne 0$} \\ 0, & \text{if $x = 0$} \\ \end{cases} $$ Then $g$ is neither convex nor concave. But any line through the discontinuous point $(0,0)$ meets the hyperbola at most once, so $g$ is ...


0

One of the goals of the book Convex Optimization by Boyd and Vandenberghe (free online) is to teach people to recognize convex functions. Aside from directly checking the definition or checking the second derivative, there are a bunch of ways of combining functions to create new convex functions. For example, a supremum of convex functions is convex. A ...


0

as you already said, looking at the second derivative is one of the main technices for prooving that a function is convex. As far as i know it suffices for continues functions to show, that $\forall a,b :\frac{f(a)+f(b)}{2} \geq f(\frac{a+b}{2})$ holds. about the function $-ln(g(x))$ (i guess that is what you wanted to write): if you want to prove that smth ...


0

Nothing is wrong. Every monotone function is both quasiconvex and quasiconcave. Indeed, the definition of quasiconvexity amounts to saying that on every closed interval, the function attains its maximum at an endpoint. Same for quasiconcavity, except replace maximum with minimum. Every monotone function has both of these properties.


1

This is not just strictly convex, it's strongly convex. A strictly convex function has at most one unique minimizer on any open interval. But that does not guarantee that a minimizer exists. For instance, $f(x)=e^x$ is strictly convex, but it does not have a minimizer on any open interval. Strong convexity is a stronger condition; it guarantees the ...


1

No, there need not be such an interval. Take $g(x)=x^2$ and $f_0(x)=2x^2$ (this is not yet $f$). Choose a sequence of disjoint intervals converging to $0$, for example $I_n=[2^{-2n},2^{1-2n}]$. Redefine $f_0$ to be linear on each $I_n$; this creates a function $f_1$ which is not strictly convex in any neighborhood of $0$, and still satisfies $f_1\ge g$. But ...


1

As I understand it, the confusion is that the problem is convex in terms of $x$, but not (understood to be) convex in terms of the step size $\alpha$ (given the statement about not jointly convex). However, when we do a line search, we restrict $f$ to another convex set (the line). This, then, is also a convex problem, for which we find the minimum (to give ...


1

For this version, consider $f(x)=(1/4)(x-1)^4+x$ with first derivative $(x-1)^3+1$ positive in an interval $I$ about $1$, but with second derivative $3(x-1)^2$ which has no positive lower bound near $1$, so that $f$ isn't strongly convex on $I$.



Top 50 recent answers are included