Tag Info

New answers tagged

0

The definition of derivatives on the boundary of a domain is not completely agreed upon. My preferred definition of differentiability of a function $f\colon A \to \mathbb R$ with $A\subset \mathbb R^n$ in any point $x_0\in A$ is the following. We say that $f$ is differentiable in $x_0$ if there exists a linear map $L$ such that $$ \lim_{x\to x_0} ...


5

The one dimensional case The result is true if we assume that some integrals are finite. Below I will assume that $\int_0^\infty x \,\mu(dx)=\int_0^\infty x \,\nu(dx)<\infty.$ Emanuele Paolini's argument shows that some such assumption is necessary. Fix $z\in\mathbb{R}$ and $m>0$. The functions $f(x)=(m(x-z)+1)_+$ and $g(x)=m(x-z)_+$ are both ...


6

Take on $\mathbb R$ the measure $d\mu = \frac{dx}{1+x^2}$. Then for every non constant convex function $f(x)$ if the integral is well defined one has $$ \int f(x) d\mu(x) = +\infty $$ since $f(x)>mx$ for either $x\to +\infty$ or $x\to-\infty$. For constant functions the integral only depends on the total mass of the measure $\mu$. Hence you cannot ...


1

No. It is not true. Let $A$ be the unit ball centered in the origin, let $D$ be the points with rational coordinates. Let $U$ be the complement of $A$.


0

It is only true that $U\cap D$ and $A\cap D$ are non-empty. $A\cap U$ can happen to be the empty set. Why $U\cap D$ is nonempty: Because $U$ is open, then for each $u\in U$ there is a ball $B(u,r)$ with center $u$ and some positive radius $r>0$, such that $B(u,r)\subset U$. Now, because $D$ is dense in $\mathbb R^n$ it follows that for each ...


0

Take $V=C[0,1]$ with the uniform norm, $A$ is the subspace of all polynomials (convex), $D=C[0,1]\setminus A$ (dense). But $A\cap D=\emptyset$.


0

First, $U\cap D\cap V=U\cap D$ because $U\subset V$. Second, any non-empty open subset of $V$ intersects $D$, precisely because $D$ is dense in $V$ (this is a definition of dense subset). So yes, $U\cap V\cap D$ is non-empty. Note that we have only used the topology of $V$. There's no need of linearity, convexity, norm, etc.


0

No, the $f_i$'s are not convex in general. A counter-example in any dimension $n$ is the projection onto the $\ell_2$ unit ball $C := \{x \in \mathbb{R}^n | \|x\| \le 1\}$. Indeed, for each $x \in \mathbb{R}^n$ one computes \begin{eqnarray} f(x) := proj_C(x) = \begin{cases}x, &\mbox{ if }\|x\| \le 1,\\\frac{1}{\|x\|}x, &\mbox{ otherwise.}\end{cases} ...


0

I can explain the first question, the author said "if $prox_f$ were a contraction", which is not guaranteed. Banach fixed-point theorem tells us repeatedly applying contraction would find a (here, unique) fixed point. So if $prox_f$ is a contraction, then by repeatedly applying proximal operator will result a fixed point.


0

I'll assume $s \neq 0$, otherwise the problems might be infeasible. For part a), we want to know which point in the halfspace $s^T x \leq r$ is closest to the origin. If $r \geq 0$, then the origin already belongs to this halfspace, so the best choice of $x$ is simply $x = 0$. If $r < 0$, then visually we can see that the shortest way to get from the ...


1

Hint: Use Lagrange multipliers. In both problems, the case $r \ge 0$ is trivially solved by the zero vector. So in what follows, we assume $r < 0$. Also, to ensure feasibility we'll be assuming $s \ne 0$. (a) You can replace $\|x\|$ with $\frac{1}{2}\|x\|^2$ and this won't change the solution (why ?). Now, consider the Lagrangian \begin{eqnarray} L(x, ...


2

No. For example take n=1, C = [0,1]. Then f(x) = 0 if x<0; f(x) = x for x in [0,1] and f(x) = 1 for x>1. And this function is not convex.


1

If $h\colon \Bbb R^k \to \Bbb R$ and $g\colon \Bbb R^n \to \Bbb R^k$, then their composition is given by $$f(x)=h(g(x)) \qquad \qquad \operatorname{dom}(f)=\{x\in\operatorname{dom}(g)\mid g(x)\in \operatorname{dom}(h)\}.$$ We denote by $\tilde h$ the extended-value extension of $h$, which assigns the value $\infty$ ($-\infty$) to points not in ...


2

This is absolutely the case, and it is straight out of the seminal text, Interior Point Polynomial Algorithms in Convex Programming by Yurii Nesterov and Arkadii Nemirovskii. See Section 2.4.3, "Legendre transformation of a self-concordant logarithmically homogeneous barrier." (Or don't. The book is rather... uh... thick. :-)) I don't think this exact ...


1

Let $t \in [0, 1]$. We can construct a sequence of intervals such that $t$ is the only point in their intersection. $C_0 = [0, 1]$, $t \in X_0$ Let $X_{i} = [a, b]$. If $t \in [a, \frac{a+b}{2}]$, then $X_{i+1} = [a, \frac{a+b}{2}]$ If $t \in (\frac{a+b}{2}, b]$, then $X_{i+1} = [\frac{a+b}{2}, b]$ Obviously, it is a sequence of nested intervals, ...


1

Consider the function $$ g(x,x')=f(x')+\langle G(x'),x-x'\rangle. $$ The function $g(\cdot,x')$ is linear for all $x'$, hence, convex. The left inequality means that for all $x\in X$ $$ g(x,x')\le f(x),\quad \forall x'\in X \qquad\text{and}\qquad g(x,x)=f(x), $$ which gives immediately that $$ f(x)=\max_{x'\in X}g(x,x'). $$ Therefore, the function $f$ is ...


1

Yes, it is convex, and only the first inequality is needed. Consider any $a, b \in X$ and $0 < t < 1$. For convenience write $c = ta + (1-t) b$. Taking $x = a$ and $x'=c$, we have $x - x' = (1-t) (a - b)$ so $$f(c) + (1-t) \langle G(c),a-b\rangle \le f(a) \tag{1}$$ Similarly, taking $x=b$ and $x'=c$, we have $$f(c) + t \langle G(c),b-a \rangle \le ...


1

Hint: $$(f+g)(tx_1 +(1-t)x_2)=f(tx_1 +(1-t)x_2)+g(tx_1 +(1-t)x_2)\leq ...$$


1

Try adding the two inequalities.


1

I'm going to assume that we may consider matrix norms. Then in fact, the answer is precisely analogous to the answer given for $\mathbb{R}^n_+$ in your other question. Let $\|X\|_*$ be the nuclear norm of $X\in\mathbb{S}^n$; that is, $$\|X\|_*=\sum_{i=1}^n \sigma_i(X) = \sum_{i=1}^n|\lambda_i(X)|$$ Then we have $$X\in\mathbb{S}^n_+ \quad\Longrightarrow\quad ...


0

(1) If $X$ is a some subset in $\mathbb{R}^n$, $N=1$ : For $x\in X$, $1x\in {\rm conv}\ X$ so that $$ X\subset {\rm conv}\ X $$ $N=2$ : For $x,\ y\in X$, $$ \lambda_1x+\lambda_2 y \in {\rm conv}\ X,\ \lambda_1+ \lambda_2=1,\ \lambda_i\geq 0 $$ That is any line between points in $X$ is in ${\rm conv}\ X$. (2) And $Y:={\rm conv}\ X$ is convex : If $x,\ ...


0

The conic hull does more than just the convex hull of $X \cup \lbrace 0 \rbrace$. You could look at it as the convex hull of every ray from $0$ through points in $X$. Also, the interpretation of the convex hull is incomplete. For example, the convex hull of the points $(0,0), (1,0), (0,1) \in \mathbb{R}^2$ is the filled-in triangle with those vertices. The ...


2

It seems that you can. Take $\|\cdot\|$ to be the $1$-norm, $A = I$, and $c = (1,\dots,1)^T$. In particular, we have $$ x \in \Bbb R^n_+ \iff |x_1| + \cdots + |x_n| \leq x_1 + \cdots + x_n $$


0

@Antoine's explanation works for showing $\lambda_i > 0$. Then $\alpha > 0$ follows from the definition of $\alpha$, because the denominator is forced to be above $0$. Remember, from the Wikipedia proof: "not all of the $\mu_j$ are equal to zero". So we're allowed to define such an $\alpha$.


3

$\lambda_i \geq 0$ for all $i$ by definition of the convex hull. If any $\lambda_i = 0$, then the term $\lambda_i{\bf x}_i$ can be removed from the sum, hence the problem is reduced to the case when $\lambda_i > 0$ for all $i$.


0

The proof for the assertion can be found in "Markov Chains as Random Input Automata" by A. S. Davis. It is an extension of the Birkhoff-von Neumann theorem. Did's answer is based on the constructive proof of this theorem.


1

Checkout my answer to a similar question. It explains what prox operators are, and how they're used in modern convex optimization. It also gives useful references for further reading on the subject. If you still have questions, then we can look at those.


3

Since $\sin(x+\pi)=-\sin(x)$ and $\sin\left(\frac{\pi}{2}-x\right)=\sin\left(\frac{\pi}{2}+x\right)$, it is enough to prove that $\sin x$ is a concave function over $I=\left[0,\frac{\pi}{2}\right]$. The sine function is also continuous, hence it is enough to show midpoint-convexity over the same interval. Since: $$\begin{eqnarray*} ...


3

Just expanding Daniel Fischer's comment, given that $f(x)=e^x$ is a positive and continuous function for which $f(x+y)=f(x)\,f(y)$, we have: $$f\left(\frac{x+y}{2}\right) = \sqrt{f(x)\cdot f(y)}\color{red}{\leq} \frac{f(x)+f(y)}{2}\tag{1}$$ where $\color{red}{\leq}$ follows from the AM-GM inequality. But $(1)$ just gives the midpoint-convexity of $f(x)$, ...


0

We can use the definition of convexity itself. A space S is convex if for any $u,v \in S$ $$\lambda u + (1- \lambda)v \in S \ \forall \ \lambda \in [0,1] $$ Intuitively this means if two points are in the space, then every point between them is in the space. (I can explain further if requested in comments). From here note that the space we want to ...


1

Let's check condition $$ f\Big(\frac{x+y}{2}\Big) \le \frac12 (f(x) + f(y)) $$ for $f(x)=e^x$. So, $$ e^{(x+y)/2} = e^{x/2} e^{y/2} \le \frac12 (e^x + e^y). $$ Denote $a=e^{x/2}$, $b=e^{y/2}$; then, $$ ab \le \frac12 (a^2 + b^2) \Longrightarrow 2ab \le a^2 + b^2 \Longrightarrow (a-b)^2\ge 0 $$ And... it's true!


1

Hint Here is a first step. Direct definition of convexity between points $x,y$ is $$f(hx + (1-h)y) \le hf(x) + (1-h) f(y)$$ Let $y=0$ and use Taylor expansion $e^x = \sum_{k=0}^\infty x^n/n!$ to note that $$ e^{hx} = 1 + (hx) + h^2 x^2 + h^3 x^3 + \ldots $$ and $$ (1-h) + he^x = 1+h + (h + hx + hx^2 + hx^3 + \ldots) = 1 + hx + hx^2 + hx^3 + ...


0

The function $f$ need not be continuous at $a$ and $b$. Consider the example $$f(x):=x^2\quad(-1<x<1),\qquad f(\pm1):=2\ .$$ This $f$ is convex on $[{-1},1]$. It should however, not be too difficult to prove that the limits $\lim_{x\to a+}f(x)$ and $\lim_{x\to b-}f(x)$ exist and are finite if $f$ is defined on all of $[a,b]$.


0

Let $(x_1,x_2) , (y_1,y_2)\in W$ then we have $$2x_1^2 +3x_2^2 \leq 4 ~~,2y_1^2+3y_2^2 \leq 4 $$ then we will have $$2(\lambda x_1)^2+3(\lambda x_2)^2\leq4\lambda^2\leq 4\lambda$$ and $$2((1-\lambda )y_1)^2+3((1-\lambda) y_2)^2\leq4(1-\lambda)^2\leq 4(1-\lambda)$$ then $\lambda (x_1,x_2)+(1-\lambda)(y_1,y_2)\in W$ So $W$ is convex.


3

Your set $$S=\{(x,y)\mid \cos(x+y)\geq \frac{\sqrt 2}{2}\}$$ is not convex. $P_1=(0,0)\in S$ and $P_2=(2 \pi,0)\in S$ however $\frac{P_1+P_2}{2}\notin S$


2

I split the integrand $$ f(t)=\int_0^{+\infty}g(u)e^{G(u)}e^{-G(u+t)}\,dt $$ to stress that convexity of $f$ in $t$ will depend on the term $\phi(u,t)=e^{-G(u+t)}$. For convexity of $f$ it is sufficient to assume that the function $g(u)$ is decreasing (i.e. $u_2>u_1$ gives $g(u_2)\le g(u_1)$). It is not very restrictive I hope since $g$ must be integrable ...


1

(The inclusion of $\ln^a(1+\epsilon)$ in the original definition is quite useful, but not very smooth) Suppose we had a contour $\mu_x$ that descended from $+i\infty$, passing below the real axis at $z_1=1$, and passing up back towards $+i\infty$ at some $z_x\in\Re(x,x+1)$ Then we have residues, for $0 < \Re(a)$ and $x\in\Re(1,\infty)$: $$ f_a(x) = ...


0

Ross B.'s answer confuses me. Zheng Jia's answer is correct but not clear. Let me elaborate a little bit. The general statement does not require differentiability, as convexity already implies the existence of subgradient. The general KKT condition can be stated in terms of subgradient. For any convex program, $(x,y)$ is a pair of primal and dual optimal ...


1

The constraint is not convex: the pairs of values for $(A,B)$ given by $(1,1)$ and $(1,-1)$ satisfy the constraint $|A|=B$, but the pair half-way between them not: $(1,0)$. Only linear equations give rise to convex sets.


0

We can use this criterion. Now pick $x>0$, $y>0$ and remark that $$ f \left( \frac{x+y}{2} \right) \leq \frac{f(x)+f(y)}{2} $$ is equivalent to $$ \frac{1}{2} \left( \frac{1}{x}+\frac{1}{y} \right) \geq \frac{1}{\frac{x+y}{2}}. $$ By some algebraic manipulation, this is in turn equivalent to $(x+y)^2 \geq 4xy$, or $x^2-2xy +y^2 \geq 0$. Of course this ...


0

I think the question is too broad. Some more context might help: what level of convex analysis are you dealing with? Euclidean space $\mathbb R^n$? Banach spaces? One general piece of advice: in many cases (though not all), the important features can be visualized in two dimensions. If at all possible, try to picture the situation in two dimensions or ...


0

Yes, this is what the implied claim is. The right hand side is evidently a linear function of $z$, for every $v$. Taking the maximum over $v$ yields a convex function. The fact that this function is $\log(1+e^{-z})$ is not entirely obvious; in fact, if I had to verify the convexity of the latter I'd probably do it by taking the second derivative.


1

This is one method to obtain solution to system of linear equations $$\frac {\partial E}{\partial u_i}=\lambda r_i+\frac{1}{\theta}\left(u_i-v_i \right)+\beta \left (\sum_{j=1}^Nu_j-1\right )=0 $$ for all $i \in \{1, 2, ..., N\}$ Let $$t = \sum_{j = 1}^{N}u_j$$ We have $$\lambda r_i+\frac{1}{\theta}(u_i-v_i)+\beta t-\beta=0$$ Assuming $\theta \not = 0$ ...


1

Cones are defined by linear inequalities, and for a fan you have that all half spaces defined by an inequality pass through the origin, and when some of these inequalities are saturated (forming linear equations) this defines a face of the cone. So if you intersect two cones, you are simply combining their lists of inequalities and thus a face of the ...


0

I think I figured out the answer by myself… from what I understood, the reasoning here consists in using a very simple theorem mentioned in slide 3-14 : f (Ax + b) is convex if f is convex noting that g(x,t) can be expressed as g(xa) where xa is an "augmented vector variable" : $$x_a = (x,t) = (x_1, …, x_n, t)$$ and also that : $$(Ax + b, c^T x + d) ...


0

Consider the function $f(x,y) = xy$ on $(-\infty,0)$. Then, $f$ is concave (in fact linear) and decreasing in each variable. However, the Hessian of $f$ is indefinite.


2

The go-to method for attacking your problem is the ADMM (Alternating Directions Method of Multipliers). Your can learn ADMM here. For a more in-dept theory, see Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55 (1992) Glowinski, R., Marroco, ...


1

Suppose $x \in \mathrm{ri}(X) \cap X^*$ and $y \in X$ satisfied $f(y) > f(x)$. Because $X$ is convex, $\lambda x + (1 - \lambda) y \in X$ for all $\lambda \in [0, 1]$. But, since $x$ is in the relative interior of $X$, we can always go a little bit further, that is, for some $\varepsilon > 0$, we have $\lambda x + (1 - \lambda) y \in X$ for all ...


1

i think the line number 3, says that the optimal point must be belonged to interior points of function f. in fact, if the function f be concave then, the infimum of the interior point is the optimum point (the maximum value).



Top 50 recent answers are included