# Tag Info

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. Then2 = \| 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 $$f(X):=\{f(x)\in D: x\in X\}.$$ To the proof: Suppose f:D\rightarrow \mathbb{R}. The epigraph for f is defined as $$\operatorname{Epi}(f):=\{(x,a)\in D\times\mathbb{R}: f(x)\leq a\}.$$ 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