# Tag Info

0

A short answer. Let $x\in E$ and $f\colon D \subseteq E \to \mathbb{R}$. Then in order to use gradient descent in a dual space we choose some $\Phi \colon E \to \mathbb{R}$. Hence, both $\nabla f(x)$ and $\nabla \Phi(x)$ belong to $E^*$, so the equation above is defined correctly. A good interpretation of mirror descent belongs to A. Beck and M.Teboulle in ...

1

The orthogonal projection of $D_\gamma$ onto any line is a connected, compact set with nonempty interior: thus, a closed interval of positive length. The endpoints of this interval correspond to supporting lines. The interior points of the interval correspond to lines $L$ such that $D_\gamma\setminus L$ is disconnected: since $D_\gamma$ is a topological ...

2

If you're going to apply multivariable calculus tools to the distance function, it's best to use the squared distance function: $$f(\omega)=\|x-\omega\|^2,\quad g(\omega)=\langle a,\omega\rangle$$ The minimum is attained in the same place, but this $f$ expands as inner product, allowing for simpler computations: $\nabla f(\omega) = 2(\omega-x)$. So, the ...

0

A good way to see clear in your issues is to assimilate the relavant literature on this subject. Along this line, fairer references (rather than the Boyd article, which is good for its own puprposes) on ADMM are: Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. ...

2

For sure: $$\sin x = \sin^+(x)+\sin^-(x) = \max(0,\sin x)+\min(0,\sin x) \tag{1}$$ and now we just have to integrate twice the previous line to decompose $\sin x$ as a sum of a convex and a concave function.

2

Here is one proof of $(\operatorname{aff} C - \operatorname{aff} C) \subset \operatorname{aff} (C - C)$. Note that $S$ is affine iff $S$ can be written as $\{x_0\}+L$ for some linear space $L$. Let $\operatorname{aff} C = \{x_0\} +L$. Then $\operatorname{aff} C - \operatorname{aff} C = \{x_0\} +L + \{-x_0\} +(-L) = L$, hence $\operatorname{aff} C - ... 1 There are many methods. Here I will suggest one - formulating it as a sum of two non-smooth functions with (relatively) easily computable proximal operators. Then, you can use any method for optimizing a sum of two non-smooth functions, such as Douglas-Rachford. You can re-formulate it as: $$\min_{x,y} ||y||_{\infty} \quad \mathrm{s. t.} ~ Bx = c, y = Ax ... 1 If x \mapsto f(x,t) is convex for each t, and \mu is a positive measure, then x \mapsto \int f(x,t) d\mu(t) is convex. It follows that convex combinations of convex functions are convex. Hence \alpha \to J(c,\alpha) is convex. In particular, since (\alpha,x) = ( \alpha c-I(x))^2u is convex for each x, then (\alpha,x) = \int_\Omega ( \alpha ... 2 As a function of c, it is convex. As a function of \alpha, it is convex. But it is not jointly convex in \alpha and c. 0 1) For your specific objective function "objfun" the minimizer can be found algebrically in one step. e.g. x^*= 0.5(1 + x_{prev}) 2) "fminunc" is a Quasi-Newton method (default) or Trust Region method for finding local minima. It works best when you supply the gradient and hessian of your function. If you choose this route, I suggest you write ... 1 We prove that if A and B are linear manifolds then A+B is also a linear manifold. Indeed, let x,y\in A+B and \lambda\in\mathbb{R}. Then there exist x_a,y_a\in A and x_b,y_b\in B such that x_a+x_b=x and y_a+y_b=y. Then$$ \lambda x+(1-\lambda)y=\lambda(x_a+x_b)+(1-\lambda)(y_a+y_b)=[\lambda x_a+(1-\lambda)y_a]+[\lambda x_b+(1-\lambda)y_b]. ... 0 I don't know if this is particularly helpful in your situation, but you might consider the 'double' Legendre transform. What I mean is the following: Let$f$represent your function. I assume$f: D \to \mathbb{R}$, where$D \subset \mathbb{R}^3$is some suitable domain. The Legendre transform of$f$, denoted by$f^{*}$, is the function defined by ... 2 Actually, from your relation, just apply "ri" to get $$\rm{ri\,conv\,rge}A=\rm{ri}(\rm{ri\,conv\,rge}A)\subset \rm{ri\,rge}A\subset\rm{ri\,conv\,rge}A,$$ from which$\rm{ri\,rge}A=\rm{ri\,conv\,rge}A$is convex. 0 Assume f''(x)<=0 in (a-r,a+r). Then f' is decreasing in this nbd. Now we have f'(a)=0. Consider (f(x)-f(a))/(x-a), x>a. This is f'(c),c>a. Now f'(c)<=0 since f' is decreasing and f'(a)=0,x>a. It follows that f(x)-f(a), upon cross multiplying,is negative. Consider (f(x)-f(a))/(x-a), x=0 since f' is decreasing and f'(a)=0,x 1 I assume$A$is symmetric. Your dual manipulation is incorrect when$Adoes not have full rank. To see why, let's try to compute the dual function (using your notation): \begin{align} g(\eta, \beta) &= \sup_{\alpha \in \mathbb{R}^k} [-c\alpha^TA\alpha + d^T\alpha+\eta^T(\alpha + p) - \beta^T(\alpha -r)] \\ &= \sup_{\alpha \in \mathbb{R}^k} ... 2 I assume you can prove, by definition, thatx^2is strictly convex. Now, you use this result twice: \begin{aligned} ((1-t)x + ty)^4 &= (((1 - t)x + ty)^2)^2 \\ &< ((1-t)x^2 + ty^2)^2 &\quad (x^2 \text{ is strictly convex})\\ &< (1-t)(x^2)^2 + t(y^2)^2 &\quad (x^2 \text { is strictly ... 1 Assuming 0\leq \lambda \leq 1,||\lambda x_1 + (1-\lambda)x_2 - y|| = ||\lambda x_1 + (1-\lambda)x_2 - (\lambda + (1-\lambda))y||\leq ||\lambda x_1 - \lambda y|| + ||(1-\lambda)x_2 - (1-\lambda)y|| = \lambda||x_1 - y|| + (1-\lambda)||x_2 - y|| = \lambda||x_1 - y|| + (1-\lambda)||x_1 - y|| = ||x_1 - y||$$1 I assume you mean the constraint x^T Px + 2c^Tx + s \leq 0. For intuition on the difficulty of this constraint, let us assume we also have constraints x_i \in [0,1] for all i \in\{1, \ldots, n\}. Now consider your single constraint in the special case P=-I, c=(1/2, \ldots, 1/2), s=0:$$ -x^Tx + 1^Tx \leq 0 $$This is equivalent to saying: ... 0 Yes. See, e.g., recent work by Lessard et. al 0 Apply the triangle inequality to ||\lambda(x_1-y)+(1-\lambda)(x_2-y)||. 0 Here I provide a solution only for an inner product space H. Let a=x_1-y and b=x_2-y. Then \|a\|=\|b\|. WLOG, set \|a\|=\|b\|=1 and hence (a,b)\le 1. If (a,b)=1, then a=b. If (a,b)<1, then for \lambda\in [0,1], \begin{eqnarray} f(\lambda)&=&\|\lambda x_1+(1-\lambda)x_2-y\|^2\\ &=&\|\lambda a+(1-\lambda)b\|^2\\ ... 0 For a twice differentiable function f ; f''(x)>0 implies f is strictly convex.. (It is sufficient condition ). Here , f(x)=x^4. So, f''(x)=12x^2>0 for all x\in \mathbb R\setminus \{0\}. So, f is strictly convex in \mathbb R\setminus \{0\}. Now suppose , x=0 & y\in \mathbb R. Then , ... 0 I would do it by squeezing: if f is squeezed between two differentiable functions that have the same value and the same gradient at x_0, then it also has that gradient at x_0. Let's write p_0=P_D(x_0) for brevity. Then two natural functions to use are$$ g(x) = \left((x-p_0)\cdot \frac{x_0-p_0}{\|x_0-p_0\|}\right)^2\quad \text{and} \quad h(x) = ... 2 The process of minimizing\mathcal{L}$to construct the dual results in a formula for$\alpha$as a function of$\beta$and$\eta. This is exactly the connection between the optimal primal and dual variables. 0 It's maybe a little too late, but as I had the same doubt, I decided to write an answer for future. The key is to understand that one supposes your solution is a vertex. If it is not one, is not too hard to find a vertex that is optimal starting from your optimal solution. I shall use the notation Oliver introduced in his comment to the other answer, that is ... 1 This doesn't directly answer your question, but here is a different algorithm you could possibly use to solve the optimization problem \begin{align} \text{minimize} & \quad \frac12 x^T A x + b^T x \\ \text{subect to} & \quad y^T x = 0 \\ & \quad 0 \leq x \leq c \end{align} where the matrixA$is symmetric positive semidefinite. Let$U = \{x ...

1


1

Zonotope. (I have nothing more to say, but say more to satisfy the computer.)

1

Simply specifying that a function is twice differentiable is not enough to guarantee a complexity rate. The best theoretical treatment of second-order methods---that is, methods that exploit both first- and second-derivative information---is probably by Yurii Nesterov and Arkadii Nemirovskii. Their work requires an assumption of self-concordance, which in ...

Top 50 recent answers are included