Tag Info

New answers tagged

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 $A$ does 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, that $x^2$ is 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

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 matrix $A$ is symmetric positive semidefinite. Let $U = \{x ...


1

For a convex optimization problem, the KKT conditions are sufficient for a point to be a global minimizer. And your optimization problem is convex when $f$ is convex and $g_1$ and $g_2$ are affine. Consider the convex optimization problem \begin{align*} \text{minimize} & \quad f(x) \\ \text{subject to} & \quad Ax = b. \end{align*} Here $f:\mathbb ...


1

No, it is not symmetric unless $X$ is a Hilbert space. In the conjectural formula $$\langle x, j(y)\rangle = \langle y, j(x)\rangle\quad (?)$$ the left hand side is linear in $x$, but the right hand side is not, unless $j$ is a linear map. Concrete example: in $\ell^4$, the duality map $j:\ell^4\to \ell^{4/3}$ is $$ j(x) = (x_1^3,x_2^3,x_3^3,\dots) $$ ...


1

Here is a rather tedious solution, I suspect a cleaner solution could be obtained using Michael's remark above, but it doesn't leap out at me at present. Let $f(x) = (\sum_k \lambda_k x_k )(\sum_k {1 \over \lambda_k} x_k)$, and $\Sigma = \{ x | x_k \ge 0, \sum_k x_k = 1 \}$. Since $\Sigma$ is compact and $f$ is continuous, we know the various extrema ...


1

Take $C=\{(a_n )_{n\in\mathbb{N}} \in \ell_{\infty} :\forall_{j\in\mathbb{N}}\hspace{0.5cm} 0\leqslant a_j \leqslant j\}.$ Then $\mbox{recc} (C)=\{0\}$ but $C$ is unbounded.


1

Let $\mathcal{Q}^{n_i}\subseteq\mathbb{R}^{n_i}\times\mathbb{R}$ be the second-order cone of dimension $n_i+1$. Then using your notation, we have $c=f$, $Q=F$, $r=g$, and $$M=-\begin{bmatrix} A_1 \\ c_1 \\ A_2 \\ c_2 \\ \vdots \\ A_m \\ c_m \end{bmatrix} \quad p=-\begin{bmatrix} b_1 \\ d_1 \\ b_2 \\ d_2 \\ \vdots \\ b_m \\ d_m \end{bmatrix} \quad K = ...


0

You could just draw the inequalities and intersect them, and then find the edges of P as lines intersection points.


1

Unfortunately, determining a solution with the smallest number of non-zeros is intractable. It can be expressed as the following binary linear program: \begin{array}{ll} \text{minimize}_{x,y} & \sum_i y_i \\ \text{subject to} & A x = b \\ & 0 \leq x \leq M y \\ & y \in \{0,1\}^n \end{array} where $M$ is a ...


0

This problem can be solved with use of an auxillary problem of the form $$ \operatorname{minimize} p = \sum_i y_i\\ \operatorname{s.t.} \mathbf{Ax} + \mathbf{Ey} = \mathbf{b}\\ \mathbf{x} \geqslant 0\\ \mathbf{y} \geqslant 0. $$ Assuming $\mathbf{b} \geqslant 0$ (can be achieved by multiplying rows of $\mathbf{Ax}=\mathbf{b}$ by $\operatorname{sgn} ...


0

The reason they allow the output matrix to take values between 0 and 1 is simple: the problem is intractable if they do not. Binary programming problems are non-convex, and in the worst case solving them would require examining all $2^{n^2m^2}$ possible $\{0,1\}$ combinations. That quickly becomes intractable for reasonable values of $m$ and $n$. One ...


0

If you already know how to solve the first type of problem, an obvious approach is to make the second problem look like the first. Towards that end, let $$\eqalign{ X' & = XW \cr Y' &= YW \cr \lambda' &= \lambda \, \|W^{-1}\|_* \cr }$$ In terms of the primed variables, the second problem now looks like the first. This transformation ...


0

Here is a partial answer. Let us write $x_i$ and $y_i$ for rows of $X$ and $Y$. Then, \begin{align} \min_X \| X\|_{\infty,1} + \frac1{2\tau} \| X - Y\|_F^2 &= \min_X \Big[ \max_i \| x_i\|_1 + \sum_j \frac1{2\tau} \| x_j - y_j\|_2^2 \Big] \\ &= \min_X \max_i \Big[ \| x_i\|_1 + \sum_j \frac1{2\tau} \| x_j - y_j\|_2^2 \Big]\\ &\ge \max_i \min_X ...


2

Let $C$ be a cone and let $x \in C$. Suppose $x \neq 0$. Then $x$ is a convex combination of the points $y_1 = \frac12 x$ and $y_2 = \frac32 x$, both of which belong to $C$. Explicitly, $x = \frac12 y_1 + \frac12 y_2$. This shows that $x$ is not an extreme point of $C$. It follows that the origin is the only possible extreme point of $C$. (We don't ...


1

Geometric Intuition of Extreme Point: According to your definition of extreme point, geometric intuition of an extreme point in a convex are all corners. For example, in a triangle you extreme points are just the corners. However, in some other convex sets like disk (filled circle), extreme points are all the points on the border. Geometric Intuition of ...


4

As the Hessian is positive semidefinite (even if not invertible), the function remains convex (but maybe not strictly convex). A trivial example is $$ X = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix} $$ where $$ |y - X'w|^2 = (y_1 - w_1)^2 + y_2^2 $$ is a convex function, even if it is constant in the direction $\{ w_1 = const. \}$.


1

A convex polygon can be given either by its vretices or, often more adequate, by inequalities $a_ix+b_iy\ge c_i$ describing the half planes whose intersection is the polygon. With the latter form, a point of the plane is inside the polygon iff all iniequalities hold for its coordinates (or possibly on the boundary if we have equality in at least one of the ...


0

The squared distance from the origin $f(x,y)$ is a convex function and $\Delta$ is a triangle, hence a convex set, so we have that $f$ takes its maximum on $\partial\Delta$. We know that the maximum occurs in $C$ and the minimum on $A$, hence $C$ is the farthest point from the origin and $A$ is the closest one. However, $OA$ and $BC$ are free to be ...


0

Guess what: this is actually a standard least squares problem in disguise. The key is recognizing the Kronecker structure: $$\|Y-AX\|_F = \|\mathop{\textrm{vec}}(Y)-(I_{k\times k}\otimes A)\mathop{\textrm{vec}}(X)\|_2$$ where $\mathop{\textrm{vet}}:\mathbb{R}^{n\times k}\rightarrow\mathbb{R}^{nk}$ converts a matrix to a vector by stacking its columns on top ...


1

You are not saying what constitutes too long in your case or what the dimensions are, but with a standard nonlinear solver such as ipopt, a random problem with $n=1000$ is solved in 0.2 seconds on an old laptop. I guess you could reduce that by a factor of 10 if you manually code a solver for this particular problem. Tested with this snippet of YALMIP code ...


0

Yes, $tx + (1-t)x'$ is a (the) straight line from the point $x$ to $x'$, for values of $t$ between $0$ and $1$. Reversing the positions of $x$ and $x'$ makes no difference, it's still a line - it just runs in the opposite direction as you increase/decrease $t$. And finally, yes, that would be a proof of convexity.


0

$\newcommand{\Reals}{\mathbf{R}}\newcommand{\setA}{\mathcal{A}}$If the points $(x_{j})_{j=1}^{N}$ are linearly independent as vectors in $\Reals^{n}$, the set $\setA$ is the parallelipiped[1] centered at the origin, with a vertex at $-\sum_{j} x_{j}$ and edges $(2x_{j})_{j=1}^{N}$.[2] If the points are linearly dependent, $\setA$ is a projection of a ...


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