# Tag Info

## New answers tagged convex-analysis

0

No, $f$ does not have to be concave. For a counterexample in dimension $n=2$, let $A$ be the union of the closed unit disc centred at the origin and a single point $P$ with $\lVert P\rVert > 1$. We can compute the area of $A_r$ easily for small $r$ (specifically, $2r\le\lVert P\rVert-1$), $$\mu(A_r)=\pi(1+r)^2+\pi r^2=\pi(1+2r+2r^2).$$ Then, using the ...

0

Is my simple minded argument allowed? The problem of finding $(y,x,z)$ (or $(x,y,z,u,v,w)$) that minimizes $$\min \sqrt{(x-u)^2 +(y-v)^2 + (z-w)^2 }$$ is the same as: $$\min \> (x-u)^2 +(y-v)^2 + (z-w)^2$$ as the square root is a monotonic function. Sum of squares is convex (and $x-u$ etc. is linear). So we are done.

0

The locus of $(x,y,z)$ is a sphere of radius $\sqrt{5}$ The locus of $(u,v,w)$ is a cylinder of radius $1$ , height $4$ and having it's center at $(4,0,6)$ Now consider all the cross sections of the figures which are parallel to the $xz$ plane.The 2 points which minimize this distance is suppose to be in one of these planes.We get the largest cross ...

1

You can use directly the definition of a convex function: $f(tx+(1-t)y)\leq tf(x)+(1-t)f(y),\,\forall t\in [0,1]$. So you have to prove that $$f(x,y,z,u,v,w)=\sqrt{(x-u)^2+(y-v)^2+(z-w)^2}$$ is convex. The whole idea is to see that your function is the second Euclidean norm in $\mathbb R^3$ of the vector $(x-u,y-v,z-w)$ and to use the convexity of the ...

0

Any function which satisfies $f''(x)>0$ and $xf'(x)<f(x)$ on some interval serves as a counterexample.

1

No, it is not necessarily increasing. Consider $f(x)=x^2+1$. This has $f^{\prime\prime}=2>0$, but $h(x)=x+\frac{1}{x}$ is not increasing for all positive $x$: in fact, $h^\prime(x)=1-\frac{1}{x^2} > 0$ only for $x>1$.

0

Subtracting the height of the arc from the height of the line segment we get $$\theta(u_1^2+u_2^2)+(1-\theta)(v_1^2+v_2^2)- [\theta u_1+(1-\theta)v_1]^2 - [\theta u_2 + (1-\theta)v_2 ]^2$$ $$=\theta(u_1^2+u_2^2)+(1-\theta)(v_1^2+v_2^2) \\-\theta^2 u_1^2-(1-\theta)^2v_1^2-2\theta(1-\theta)u_ 1v_1-\theta^2 u_2^2+(1-\theta)^2v_2^2-2\theta(1-\theta)u_ 2v_2$$ ...

3

Fix $b$ any real number, then study $S$ (with $b$ fixed). If it is empty, it is convex, Otherwise, if $x,y \in S$, and $\mu \in [0,1]$, then what about $\mu x + (1-\mu) y$ ? Just compute $f(\mu x + (1-\mu) y) <= \mu f(x) + (1-\mu)f(y)$ by convexity of $f$, and then because $x,y\in S$, $f(x),f(y) \leq b$ (by definition). So $\mu f(x) + (1-\mu)f(y) \leq ... 9 Let$x, y \in S$. Then by definition of a convex set, you need to show that the points$λx+(1-λ)y$are in$S$for any$λ\in[0,1]$. So, by definition of$S$you need to show that$f(λx+(1-λ)y)\le b$. Since, the function$f$is convex you have that $$f(λx+(1-λ)y)\overset{f\text{ convex}}\le λf(x)+(1-λ)f(y)\overset{x,y\in S}\le λb+(1-λ)b=b$$ 0 The level lines$\gamma_c:=f^{-1}(c)$of the function $$f(x,y):=(x-\bar a)(y-\bar b)$$ are hyperbolas centered at$(\bar a,\bar b)$, and having asymptotes$x=\bar a$, resp.,$y=\bar b$. We are looking for the largest$c$such that$\gamma_c$meets the line$\ell: \>x+y=1$. This is the case when$\gamma_c$touches the line$\ell$. Due to symmetry this will ... 0 Solve it using Lagrange's multipliers and you'll get the answer. 0 Consider that you look for the extremum of function $$F=(a-A)(b-B)$$ subjact to$a+b=1$. So, using$b=1-a$, $$F=(a-A) (1-a-B)$$ $$F'=-2 a+A-B+1$$ So, the first derivative cancels for$a=\frac{A-B+1}{2} $for which$F=\frac{(A+B-1)^2}{4} $. But, the second derivative is$F''=-2$which confirms that this a maximum. Now, the problem is :$a >0$? 2 For 3-gons one can consider the circumcircle, and move points along the circle until it is equilateral, without going through nonconvex 3-gons (since there are none). Since both 3-gons can be thus made into equilaterals, a composition of the two deformations takes the first into the second. Suppose true for$n$gons, and consider two$n+1$gons, and take ... 2 Not a complete answer, but I can at least dispose of$h: x \mapsto x^3$. Suppose this is$f \circ g$with$f$,$g$convex. Since$h$is one-to-one on$\mathbb R$we'd need$g$to be one-to-one on$\mathbb R$and$f$to be one-to-one on$g(\mathbb R)$. Now the left and right one-sided derivatives of a convex one-to-one function are either strictly positive ... 4 Convexity-preserving mappings are not necessarily affine unless additional requirements are imposed. For example,$f : \mathbb R^n \to \mathbb R^n$given by$f(x_1, x_2, ... x_n) = (x_1^3, 0, ... 0)$is convexity-preserving but not affine. On the other hand, it has been proved that one-to-one convexity-preserving mappings between real vector spaces$f : ...

1

This is a special case of Jenathon's et al. "structured sparse pca" model with $r = 1$ component / latent factor. Also, your problem specializes the sparsity inducing $\Omega$ penalty to just an $\ell_1$-norm. The model can be optimizes by block coordinate descent via Algorithm 1 of the aforesaid paper, e.g

1

The problem you mention is closely related to the sparse principal component analysis (Sparse PCA). There is a vast literature on this problem including greedy nonconvex algorithms and semidefinite relaxations. Just google "sparse pca" and you will find "highly cited" papers. For your particular formulation, you might want to look at the recent literature ...

-1

Okay so after consultation with @mzp, I discovered that my question was not clear enough. I was considering dictionary order topology, which I didn't make clear in the question or discussion. In that case, I $\times$ I is not convex. Thank you so much everyone. I really appreciate your inputs.

0

A set $X$ is convex if for all $x,y\in X$ and $a\in [0,1]$, $ax+(1-a)y\in X$. Take any $x,y \in I\times I$ and any $a \in [0,1]$ and notice that $$ax+(1-a)y = a \left[\begin{matrix} x_1 \\ x_2 \end{matrix}\right]+(1-a)\left[\begin{matrix} y_1 \\ y_2 \end{matrix}\right] = \left[\begin{matrix} ax_1+(1-a)y_2 \\ ax_2+(1-a)y_2 \end{matrix}\right].$$ The ...

1

Your definition of convexity only applies to subsets of the real numbers. In any higher-dimensional space the correct definition is that for all $a, b \in Y$ and $\lambda \in [0, 1]$ the vector $\lambda a + (1 - \lambda) b$ must lie in $Y$. You can easily verify directly that any cartesian product of convex sets is again convex. Also note that the ...

2

The set is convex. Take any two points $a$ and $b$ in the unit square, consider the line joining them $a+t(b-a)$ where $t\in[0,1]$, and check that the components of every point on the line lie in $[0,1]$.

0

In general, your function $f$ is nonconvex! For example, on $\mathbb R_+^2$ consider $f :(x_1, y_2) \mapsto x_1x_2$. However, the inequality your trying to proof holds for arbitrary $f$ defined as you did. When such an inequality holds, we say $f$ is multiplicatively convex. So then, let's show that your $f$ is multiplicatively convex. Indeed, $$f(x) = ... 0 If f is convex, f(\alpha a + \beta b) \le \alpha f(a) + \beta f(b) where two nonnegative coefficents \alpha \ge 0, and \beta \ge 0$$\alpha + \beta = 1$$Now let \alpha = 0.5*(1 - Y_i/c_i) and \beta = 0.5*(1 + Y_i/c_i) and  a = -kc_i, and b = kc_i and f = e^x$$ e^{kYi} = e^{(1-Y_i/c_i)/2 (-kc_i) + (1+Y_i/c_i)/2 (kc_i)}\le \alpha ...

0

As you say, "partition" doesn't really fit here since that (almost always) would require that none of the sets are empty. I would use the word "decomposition" instead. One example of this use of "decomposition" is in the Hahn decomposition theorem, where either one of the positive and negative sets may be empty.

2

The inequality for large $x$ implies that $\lambda_2\geq1.$ The function $f(x)=\lambda_1+\lambda_3x^2$ determines a parabola centered around the $Y$ axis (where in order to cover the case $\lambda_3=0$ we temporarily agree to call a horizontal line a parabola, as well). Thus for any given $\lambda_2\geq1$ we look for a parabola centered around the $Y$ axis ...

1

Just a hint, not an answer: If the boundary of $C$ is of class $C^2$ then this is rather easy. If $c:(-\varepsilon, \varepsilon) \rightarrow \partial C$ is a smooth curve which attains a minimum at $t=0$, then $$\frac{d}{dt}|c(t)-x|^2|_{t=0}=0= \langle x-c(0), c^\prime(0)\rangle$$ In other words, in such a point every tangent to $\partial C$ is orthogonal ...

1

EDIT: after posting this I noticed from the tags that this is specifically about convex functions. In this case I don't know that to tell you. I'll just leave this answer up, though, in case someone might find it useful for something. This is far from a complete answer, but here's a counterexample: let $$f(x) = \begin{cases} -1 & x < 1 \\ 0 & x ... 3 No, that conclusion does not hold because generally, the product of two convex functions need not be convex. As an example, f(x, y) = x y^{-1} (for x, y > 0) is a posynomial function, but not convex:$$ f(\frac{1+5}{2}, \frac{1+3}{2}) = \frac 32 > \frac 43 = \frac 12 \left( f(1, 1) + f(5, 3)\right) $$2 I think you are about one step away from constructing a counterexample. Consider your last figure. The interiors of regions E_1, E_2, and E_4 are pairwise disjoint convex sets whose union is a proper subset of C. The only convex subsets of C that contain E_1 and do not intersect either E_2 or E_4 are subsets of the closure of E_1. That ... 1 (Incomplete answer, I may get back when I understand these sets better) Connectedness is a necessary condition because we can take I'=I. I will enumerate a few sufficient conditions but I have not been able to unify them. Let us call the property P, so P(C) is an abbreviation for the existence of a connectivity-preserving map f from C\subset\mathbb ... 2 Let p_1 and p_2 belong to the join of A and B.$$\text {Let } q=x p_1+(1-x)p_2 \text { with } x\in [0,1].$$There exist a_1\in A and b_1\in B and r_1\in [0,1] with$$p_1=r_1 a_1+(1-r_1)b_1.$$There exist a_2\in A and b_2 in B and r_2\in [0,1] with$$p_2=r_2 a_2+(1-r_2)b_2.$$Since A and B are convex, we have$$A\supset \{c ...

1

Basically, this comes down to the following algebra exercise. We take convex combinations to represent any $x$ in the join: $$x_1=\alpha_1 a_1 + \beta_1 b_1$$ $$x_2=\alpha_2 a_2 + \beta_2 b_2$$ and then make a convex combination of those: $$\kappa x_1+\gamma x_2=\kappa \alpha_1 a_1 + \kappa \beta_1 b_1 + \gamma \alpha_2 a_2 + \gamma \beta_2.$$ Then, we need ...

1

Using defintion of the convext set, to prove, given any two points in join of two set, the line segment connecting the given two points lies entirely inside the join. You have six cases: Both given points are in set A; Both given points are in set B; one point is in set A, and other point is in set B one point is in set A, other point is in the join but ...

2

Let there be $k$ oriented lines that divide the $n$ points into different left and right sides. There are $2$ trivial lines and $k-2$ nontrivial lines. Let each nontrivial line swing counter-clockwise as far as it can, until it hits two of the points. The nontrivial lines will match with the ordered pairs of the points, of which there are $n(n-1)$. So ...

0

The correct statement is: $X$ is closed and convex iff $$[X^\circ]^\circ = X.$$ "$\Leftarrow$": follows easily, since $A^\circ$ is closed and convex for any $A \subset \mathbb{R}^n$. "$\Rightarrow$": Assume that $X$ is closed and convex. It is easy to check that $X \subset [X^\circ]^\circ$. The other inclusion can be proved by contradiction. Assume that ...

1

To complete gerw's comment and to avoid leaving the question unanswered, let me give an explicit counterexample. The question (letting $g=f'$) is equivalent to the following one: If $g\colon(0,\infty)\to\mathbb{R}$ is continuous, strictly increasing and bounded above, is $g(x+\delta)-g(x)$ convex for $\delta>0$? Here is a counterexample: $$... 2 Sure, you can just add the inequalities. That is, if g is m-strongly convex then, for some a \in \partial g(x)$$ g(y) \ge g(x) + a^T(y-x) + \frac{m}{2}\|y-x\|^2, $$And if h is convex, then for some b \in \partial h(x):$$ h(y) \ge h(x) + b^T(y-x), $$Then by adding we have:$$ g(y) +h(y) \ge g(x) +h(x) + (a+b)^T(y-x) + \frac{m}{2}\|y-x\|^2  ...

0

Indeed both sets are convex! A convex function is necessarily quasi-convex, i.e the sub-level sets $\mathrm{lev}_{\le \alpha} f := \{z | f(z) \le \alpha\}$ are convex. What you have there are sub-level sets of convex functions or intersections of such. For example, $f: (x, y) \mapsto -y$ and $g : (x, y) \mapsto -e^{-x^2} + y$ are convex functions (for ...

1

Of course we can assume $B$ to be bounded. Let $x_n=a_n-b_n$ be a converging sequence in $A-B$. $(b_n)$ is bounded, hence there is a converging subsequence $b_{n_k} \to b$ and we have $b \in B$, since $B$ is closed. We deduce $a_{n_k} = x_{n_k}+b_{n_k}$ is also convergent as the sum of two convergent sequences. Since $A$ is closed, the limit $a$ is in $A$. ...

0

I finally found a solution to the problem $$g*(y) = \underset{x}{\sup}\; \{x^Ty - g(x)\}$$ As we know $$g(y) = \underset{x_1 + x_2 = x}{\inf}\; \{f_1(x_1) + f_2(x_2)\}$$ Now we have $$g*(y) = \underset{x}{\sup}\; \{x^Ty - \underset{x_1 + x_2 = x}{\inf}\; \{f_1(x_1) + f_2(x_2)\} \}$$ $$= \underset{x}{\sup}\; \{x^Ty + \underset{x_1 + x_2 = ... 0 Disclaimer: I'm not an expert when it comes to topology, so be careful with this answer. Let A_r be one such matrix (real or complex, positive semidefinite, with unit trace). Then it has the eigenvalue decomposition:$$A_r = U \Lambda_r U^*,$$where \Lambda_r = \operatorname(\lambda_1,\dots,\lambda_r,0,\dots,0), \lambda_k \ge 0, \sum_k \lambda_k = ... 1 rank(M) = \min\{r|\exists V \in L(m,r), W \in L(n,r). M = V^TW \} where L(m,n) is the space of n\times m matrices is my rewriting of the (intended) meaning of your definition. You should verify that it is equivalent. I think this definition (particularly compared to your definition of rank as the dimension of the image) makes it much easier to answer ... 1 x_4 \mapsto -\frac{1}{x_4} is convex for x_4 < 0 (for example, use derivative test); (x_3, x_4) \mapsto x_3 - \frac{1}{x_4} is a sum of convex functions, and so is convex for any x_3 and x_4 < 0; and so on and so forth. Thus your f is convex when all the denominators are less than 0. 0 I realized that since f is convex, f' is increasing function. Then the inequality above follows. 0 The unit ball of (\mathbb{R}^n,\|\cdot\|_p) is$$B_p=\{x\in\mathbb{R}^n, \|x\|_p\leq 1\}.$$So, if p=\infty, then$$B_\infty=\{x\in\mathbb{R}^n, \forall 1\leq i\leq n, |x_i|\leq 1\}=[-1,1]^n,$$which is a square in \mathbb{R}^2, a cube in \mathbb{R}^3, and is probably named hypercube in general. If p=2, then$$B_2=\{x\in\mathbb{R}^n, ...

2

It is convex for $x_2 < 0$, not for $x_2 > 0$ (there it is concave).

0

Without the AGM nor the weighted AGM inequality. It suffices to consider the case $x> y$ and $a=\alpha \in (0,1).$ Take a fixed $y>0$ and a fixed $a\in (0,1)$ and for $x>0$ let $$g(x)=-a\log x- (1-a)\log y +\log (a x+(1-a)y).$$ We have $$g'(x)=dg(x)/dx=-a/x+a/(a x+(1-a) y)=a(1-a)(x-y)/(ax+(1-a)y).$$ Observe that $g'(y)=0$ and that $x>y\implies ... 3 It's expedient to apply the following result (see for example, Exercise$24$, Chapter$4$of Rudin's Principles of Mathematical Analysis) If$f$is continuous in$(a, b)$such that $$f\left(\frac{x + y}{2}\right) \leq \frac{1}{2}f(x) + \frac{1}{2}f(y)$$ for all$x, y \in (a, b)$, then$f$is convex in$(a, b)$. Notice that$(a, b)\$ can be extended ...

1

The Weighted AM-GM states $$\lambda x+(1-\lambda)y\ge x^{\lambda}y^{1-\lambda}$$ Therefore, we have $$\log(\lambda x+(1-\lambda)y)\ge \log(x^{\lambda}y^{1-\lambda})=\lambda \log(x)+(1-\lambda)\log(y)$$ Therefore the logarithm function is concave and its negative is convex.

0

Any continuous function on a finite-dimensional Banach space is sequentially weakly lower semicontinuous, but not convex. The indicator function of a convex and closed set is sequentially weakly lower semicontinuous, but not continuous.

Top 50 recent answers are included