New answers tagged

1

In order to invoke Baire you have to assume the closedness of $C$. Otherwise your proof is fine.


2

We have $h'(x) > 0$ for any $x \in \Bbb R$, so to check pseudoconvexity it suffices to check that: $y-x \ge 0 \implies h(y) \ge h(x)$, i.e. just that $h$ is increasing, which is obviously the case. The problem for $g$ is that $g'(0) = 0$, so we can choose, say, $x = 0$ and $y = -1$ to see that the implication doesn't hold.


1

A vector norm (in $\mathbb{R}^n$) is just a function $f:\mathbb{R}^n\to\mathbb{R}$ satisfying certain properties. If you put the positive homogeneity property together with the triangle inequality you get convexity of $f$: Let $\alpha\in[0,1]$, and $x,y\in\mathbb{R}^n$. Then $$f(\alpha x+(1-\alpha)y)\leq f(\alpha x)+f((1-\alpha)y)=\alpha f(x)+(1-\alpha)f(y)...


0

This is because of Cauchy-Schwarz'inequality. Indeed, you have to prove, for any $0\le\lambda, \mu\le1 $, $\lambda+\mu=1$, that $$\lVert\lambda a +\mu b\rVert\le \lambda\lVert a\rVert + \mu\lVert b\rVert $$ which is equivalent to \begin{align*} \lVert\lambda a +\mu b\rVert^2=\lambda^2\lVert a\rVert^2+\mu^2\lVert b\rVert^2 +2\lambda\mu\langle a,b\rangle &...


1

The set of all matrices with off-diagonal elements negative is a convex set, quite obviously. Intersecting convex sets results in a convex set.


2

No. Consider $y(t) = t^m$ and $x(t) = t^n$ for some $n\neq m$. Then $$2 = \| x + y\| = \|x \| + \|y\| $$ but $x\neq \lambda y$.


2

Here is a counter-example for $n=2$. Take $f_1(x) = x_1^2 + x_2^2$, $f_2(x) = 10(x_1-1)^2 + (x_2-1)^2$, both are clearly strictly convex with global minima at $p_1:=(0,0)$ and $p_2:=(1,1)$, respectively. The global minimum of $f_1+f_2$ is at $p_3:=(10/11, 1/2)$, which is not a convex combination of the minima of $f_1$ and $f_2$. Now define $X$ to be an $\...


4

Read the last line: (for any choice of $X\succ0,V$) So, somewhere in the lecture notes the author must have assumed that $X$ is positive definite and $V$ is symmetric. Now, when $X$ is positive definite, the usual convention is that $X^{1/2}$ denotes not an arbitrary square root of $X$ but the unique positive definite square root of $X$. Hence $X^{-1/2}...


1

Here's a proof why $l^p(\mathbb N)$ is not locally convex, this is just for simplicity, it can be easily generalized. If it would be locally convex, then the unit ball $B_1(0)$ would contain a convex neighborhood U of $0$. Then there must be $\delta>0$ with $B_{2\delta}(0)\subset U$, hence also $\mathrm{conv}(B_{2\delta}(0))\subset U\subset B_1(0)$. Let ...


0

We have that $x_1^2+x_2^2=1$ gives the zero locus of a circle of radius $1$. $x_1^2+x_2^2=r^2$ gives a circle of radius $r$. You are taking the set in $\Bbb R^2$ consisting of all points lying on the circles of radius $[1,\infty)$. Take the convex hull of this, is it the same thing. Take the convex hull of any point laying on the locus of $x_1^2+x_2^2=1$. ...


2

$(1,0)$ and $(0,1)$ are in the set, but $(0,0)$ is on the straight line which joins the points and not in the set. So the set isn't convex.


2

Hint: if $x$ is in the unit ball of $c_0$, there is some $i$ such that $|x_i| < 1$. What happens if you increase or decrease $x_i$ a little bit?


1

I don't quite have the whole proof but I think I am close. We know already (using the reasoning you had at the bottom) that each $f_i$ must be quasiconvex and non-negative as well (otherwise you could force $F$ to have a negative value). So now the only question is are the functions psuedoconvex (strictly quasiconvex and continuously differenentiable) and ...


2

Taking the second derivative, we find that $f_n$ (for $n > 0$) is convex when $$ (n-1) t^{2n}-c (n-1)t^n +c^2 n \ge 0$$ The left side is a quadratic $Q(s)$ in $s = t^n$. If $n > 1$, the minimum of the quadratic occurs at $s = c/2$, with $Q(c/2) = (3n+1) c^2/4 > 0$. Thus it is indeed convex. On the other hand, if $0 < n < 1$, the left side ...


2

Hint: as the function is $C^\infty$ you can check if the second derivative is always positive or not. Now, the second derivative is given by $$f_n''(x)=e^{c x^{-n}} n x^{-2-n} (c^2 n-c (-1+n) x^n+(-1+n) x^{2 n}),$$ and as the first terms are positive you only need to check if the expression in the parenthesis is always positive


0

Let $c$ be in the intrinsic core of $C$ according to definition 2. Let $c' \in aff(C)$ be given. Then, $$c' = c + \sum_{i=1}^n \lambda_i \, (c_i - c)$$ for $c_i \in C$. According to definition 2, there is $T > 0$ such that $c + t \, (c_i-c) \in C$ for all $|t| \le T$. W.l.o.g. we can assume $\lambda_i \ge 0$ (otherwise, replace $c_i$ by $\hat c_i = c + T\,...


0

Hope I am interpreting the question correctly, here is my attempt of a proof of the following result: Let $A\subseteq\mathbb{R}^n$ be an open convex set. Then $f:A\to\mathbb{R}$ is a convex function iff for any $\mathbf a\in A$, $\exists\mathbf m\in\mathbb{R}^n$ such that $f(\mathbf x)\geq f(\mathbf a)+\mathbf m\cdot(\mathbf x-\mathbf a)$ for all $\mathbf x\...


4

My claim is that the answer is affirmative by the following Lemma. If two different ellipsoids $E_1,E_2$ with the same (hyper-)volume intersect, there is some ellipsoid $E_3$ enclosing $E_1\cap E_2$ with the property that $V(E_3)< V(E_1)$. Sketch of the proof: I will deal just with the 3D case. $E_1\cap E_2$ is described by something like: $$ \left ...


0

I think that you need to carefully state the conditions on the function $f$. There is not enough information, for instance, to ensure that the function is even defined: You need conditions ensuring that there is a minimum for each $\lambda$. Convex functions are very general creatures, and need not even be continuous. However let us say that $f(x,\lambda):\...


1

I don't think that $f_i,\;1\leq i\leq n$, have to be convex. Maybe this helps: Let's choose $$f_1(x)=1-e^{-x^2},\;x\in\mathbb{R},$$ $$f_i\equiv 0,\; \;2\leq i\leq n.$$ All the $f$ are differentiable and clearly satisfies condition (i) in zero. Now, as they are non negative and strictly quasiconvex (in the graph of the function $f_1$ it is pretty clear, ...


0

You can take $f(x,y) = x^2/y$, $u = (0,1)$, $v = (0,2)$ and $w = (1,2)$. Note that the Hessian of $f$ is positive definite on $\triangle(u,v,w)\setminus[u,v]$ and positive semi-definite on $\triangle(u,v,w)$. But obviously, $f$ is not strictly convex on $[u,v]$.


1

We know that a convex function is also quasiconvex and therefore has lower level sets that are convex sets. Thus if $g_i$ is convex then the set of $x$ such that $g_i(x)\leq 0$ is a convex set. The set $\mathcal{C}$ is the intersection of these sets over $i$. Since the intersection of convex sets is convex, $\mathcal{C}$ is convex. See https://en.wikipedia....


0

For each $x\in X$ let $C_x$ be the closed ball of radius $r$ centred at $x$; note that $x\in C_y$ if and only if $\|x-y\|\le r$ if and only if $y\in C_x$. If $x_1,\ldots,x_{d+1}\in A$, there is an $x\in X$ such that $\{x_1,\ldots,x_{d+1}\}\subseteq C_x$, and it follows from the observation in the first paragraph that $x\in\bigcap_{k=1}^{d+1}C_{x_k}\ne\...


0

First, we know that $e^x$ is a convex, non-decreasing function. \begin{align} (f\circ\exp)(\lambda x_1 + (1 - \lambda)y_1,\lambda x_2 + (1 - \lambda)y_2)=f(\exp(\lambda x_1 + (1 - \lambda)y_1,\lambda x_2 + (1 - \lambda)y_2))\\ \le f(\lambda\exp(x_1)+(1-\lambda)\exp(y_1),\lambda\exp(x_2)+(1-\lambda)\exp(y_2))\\ \le \lambda f(\exp(x_1),\exp(x_2))+(1-\lambda)f(\...


1

You need to show that $\{u<t\}$ is open. Say $u(z)<t$. Since convex functions are continuous there exists $\alpha>0$ so that $$u(z\pm\alpha)<t.$$And now for the same reason there exists $\beta>0$ so that $$u(z\pm\alpha\pm i\beta)<t.$$ So $u<t$ at every corner of that rectangle. Separate convexity shows that $u<t$ on the boundary of ...


0

The case $w = 0$ is obvious, and thus obmitted. For $w > 0$, let $D_w$ be the $(n+1)$-by-$(n+1)$ diagonal matrix with diagonal entries $\underbrace{1,\ldots,1}_{n \text{ times}}$, $w$ respectively. Then, $$\text{epi}(wf) := \{(z, t) \in \mathbb R^{n+1} | wf(z) \le t\} = \{(z, w\tau) | z \in \mathbb R^n, t\in \mathbb R, f(z) \le \tau\} = \{D_w[z\;\tau]^T |...


1

The notation is quite fine. Let $X$ be a set and $f:X\rightarrow D$ a function defined on $X$. Then \begin{equation} f(X):=\{f(x)\in D: x\in X\}. \end{equation} To the proof: Suppose $f:D\rightarrow \mathbb{R}$. The epigraph for $f$ is defined as \begin{equation} \operatorname{Epi}(f):=\{(x,a)\in D\times\mathbb{R}: f(x)\leq a\}. \end{equation} Therefore, for ...


2

A solution to your original problem probably has some components equal to $\pm 1$, but hyperbolic tangent is never equal to $\pm 1$. Thus, the reformulated problem probably has no minimizer. Also, $g $ is probably not convex, so convexity has been lost. You mentioned the projected gradient method. You might also consider FISTA or the TFOCS software package.


1

You have not seen many mentions of approach 2 in the literature (in fact, have you seen any ?) because it is rather ad-hoc and unprincipled. Also, the phrase "... We can then use any convex optimization procedure to solve the unconstrained problem ..." makes little sense since $\tanh$ is all but convex... Short and simple, forget approach 2. It's probably ...


0

The sum of a convex function and a strongly convex function is again strongly-convex. This is a direct application of the definition of strong-convexity. On the other hand, it should be clear that $u \mapsto u^TP_iu$ is strongly convex if $P_i$ is positive definite.


1

I think the line "Let $G$ be a function such that ..." should continue with "... $\text{epi} G = \overline{\text{epi} F}$". Take this $G$. Its epigraph is the closure of $\text{epi} F$, i.e. the smallest closed set to contain $\text{epi} F$. Thus there cannot be any l.s.c. function $\bar{F} \leq F$ with $G(v) < \bar{F}(v)$ in some point $v$. Therefore $...


0

Along the lines of my previous comment: Let $n$ be a positive integer and let $\mathcal{X} \subseteq \mathbb{R}^n$ be a convex set. Motivated by the standard definition of $\mu$-strong convexity, we can define a (possibly nonconvex) function $f:\mathcal{X}\rightarrow\mathbb{R}$ to have “convexity parameter $\mu$” if $\mu$ is the largest real number such ...


1

The dual polyhedron corresponds to the dual set. In fact, for any set $K \subset \mathbb R^n$, you have $K^\circ = (\operatorname{conv}(K \cup \{0\}))^\circ$, where $\operatorname{conv}$ denotes the convex hull. Now, let $P = \operatorname{conv}(\{p_1, \ldots, p_N\})$ be a polyhedron. Then, you have \begin{align}P^\circ &= \{p_1,\ldots, p_N\}^\circ = ...


1

I happened to find the solution to the question I asked during a discussion with my professor yesterday. Turns out, the inequality that I am after is a special case of the Holder's inequality. I am posting the solution here for the benefit of the community at large. The following is the proof of convexity of the function $f(x)=x^{\rho},~\rho>1,~x\geq 0$. ...


0

The "$\Rightarrow$" part is easy. The other direction can be proven by contradiction: Assume that $f$ is not convex. Then, $\operatorname{dom}(f)$ is not convex or there exist $x,y \in \operatorname{dom}(f)$ and $\lambda \in (0,1)$ with $f( \lambda \, x + (1-\lambda) \, y ) > \lambda \, f(x) + (1-\lambda) \, f(y)$. If $\operatorname{dom}(f)$ is not ...


0

Here's a simple solution. A function $f:\mathbb{R}^n\to\mathbb{R}$ is convex iff the set $\Gamma_f=\{(x_1,\cdots,x_n,y)| f(x_1,\cdots,x_n)\leq y \}\in\mathbb{R}^{n+1}$ is convex. Now consider the region above the graph of $g(t)$: $\Gamma_G=\{(t,y)| g(t)\leq y\}$. But this set is just the intersection of $\Gamma_f$ with the plane centered at $x$ generated by ...


3

Given the $J$ he has, note $$ \nabla J_i = \frac{u_i}{\sqrt{u_i^2 +\epsilon}} $$ Thus $$ \nabla^2 J_{ij} = \frac{\partial^2 J}{\partial u_i \partial u_j}= \delta_{ij} \left ( \frac{1}{\sqrt{u_i^2 +\epsilon}} - \frac{u_i^2}{(u_i^2 +\epsilon)^{3/2}}\right)=\frac{\delta_{ij} \epsilon}{(u_i^2 + \epsilon)^{3/2}}$$ The mean value theorem here is given by for $\...


4

So there may be further necessary context, but I think that this is false in general, even for a convex separable function. Take the example of $f(x,y) = x^4 + y^6$. We have \begin{align*} \nabla f(x,y) &= \begin{bmatrix} 4x^3 \\ 6y^5\end{bmatrix}\\ \nabla^2 f(x,y) &= \begin{bmatrix} 12x^2 & 0 \\ 0 & 30y^4\end{bmatrix}\\ \end{align*} Now ...


1

Some numerical results (C++ code here). For each number of points, 10,000,000 sets of points were generated with a 2D normal distribution centered at the origin with a standard deviation of 1. The convex hull was found for each set and counted if the convex hull was a triangle. It looks like for 17 points or more the probability is about 1 in 10,000,000 or ...


1

If $A $ is a real $n \times n $ skew-symmetric matrix, then the operator $T (x) = Ax $ is monotone, but it is not the gradient of a convex function. (The Hessian of a smooth convex function must be symmetric positive semidefinite. )


1

So the answer is in short: "Yes if the map is the gradient of a function." Let $f$ be Gateaux differentiable (same this as differentiable in finite dimensions), and proper, with an open and convex domain. Then $f$ is convex if and only if $f$'s derivative is monotone. See Convex Analysis and Monotone Operator Theory in Hilbert Spaces by Bauschke and ...


4

As proposed in the comments, I posted this question on MathOverflow and it got an answer there. Here is the link: The question on MathOverflow (answered) Thanks to everyone who read the question and thought about it.


0

If $f$ is convex it is straightforward to prove the desired inequality. Conversely, we need to notice that the right-hand side of your inequality is $$ \int_0^1 \left((1-\theta)f(x) + \theta f(y)\right)\mathrm{d}\theta = \frac{f(x)+f(y)}{2}\tag{1} $$ So then, we have $$ \begin{align} &\int_0^1 f(x+\theta (y-x)) \mathrm{d}\theta \leq \int_0^1 \left((1-\...


0

Your problem amounts to the computation of the euclidean projection of the origin $0$ onto the set $P$. There is no general rule for computing this. It all depends on the geometry of $P$, and nothing you've said allows for any simplification of the general problem.


1

Following up from my comment, here is a counterexample where both $f$ and $g$ are convex, continuous, have the desired property $\lim_{x\to\infty}f(x)/g(x) = +\infty$, but their graphs share infinitely many common points: $\hskip2in$ You require that the functions are strictly convex and are defined on $[0, +\infty)$, but it is not difficult to modify the ...


0

If $f$ is strongly convex, then its minimiser set $\arg\min_x f(x)$ is a singleton. In general, a sufficient condition for the minimiser to be bounded (actually, compact) is that $f$ should be lower semicontinuous and level bounded.


0

I think there is something wrong with your inequalities. According to what you're writing, it should be $$ f(y) \leq f(x) + \langle \nabla f(x), y-x\rangle, $$ but instead if $f$ is convex then for every $x,y$ it is $$ f(y) \geq f(x) + \langle \nabla f(x), y-x\rangle, $$ that is, the graph of $f$ lies above its tangent line at a point $x$. This is often ...


0

First, we need to explain the notation $[\cdot]_+$. It is $$ [z]_+ = \max\{z,0\}. $$ If your functions was, instead, defined as $$ r(Z)=\tfrac{2}{3}\inf_{t}\{t+10\mathbb{E}[Z-t]_{+}\}+\tfrac{1}{3}\mathrm{argmin}_{t}\{t+5 \mathbb{E}[Z-t]_{+}\}, $$ it would make sense to ask whether it is convex because $r$ is not single-valued. In fact, this would be the ...



Top 50 recent answers are included