Tag Info

Hot answers tagged

3

Of course not. You can always rescale $A$ and $B$ so their singular values are between $0$ and $1$, but that doesn't affect positive semidefiniteness of $A^T B$.


3

Let $(S_i)$ be a convex set for $i = 1,2,\ldots,n$. For any $x,y \in \cap_{i=1}^n S_i$, $t \in [0, 1]$, we have: For $i = 1,2,\ldots,n$, $x \in S_i$ and $y \in S_i$ implies $tx + (1-t)y \in S_i$ by convexity of $S_i$. Hence $tx + (1-t)y \in \cap_{i=1}^nS_i$. Therefore $\cap_{i=1}^nS_i$ is convex.


3

You're in luck: this is a geometric program. Therefore, the change of variables $$x\rightarrow e^{u}, ~~ y\rightarrow e^{v}, ~~ z\rightarrow e^{w}$$ will get us close, and a few logarithms will get us the rest of the way there. Substitution yields \begin{array}{ll} \text{minimize} & e^{u-v} \\ \text{subject to} & 2 \leq e^u \leq 3 \\ & e^{2u} + ...


3

This is equivalent to the geometric median problem in $\mathbb{R}^2$. That is: for each $z_j$, define $$\bar{z}_j \triangleq \begin{bmatrix} \Re z_j \\ \Im z_j \end{bmatrix}$$ Then the geometric median is the solution of $$\bar{z}=\arg\min \sum_{i=1}^n \|z-\bar{z}_j\|_2.$$ To recover your answer, $z=\bar{z}_1+j\bar{z}_2$. Note that if we were minimizing the ...


3

Historically, in 50s people thought that linear programming is (relatively) easy, nonlinear is difficult. The original idea behind Frank-Wolfe algorithm [original paper] was to break difficult nonlinear problems into sequence of easy linear problems. Given current iterate $x_k$, this was done by minimizing linear approximation to your function $f$, over ...


3

We want to minimize $\|Ma-b\|_2^2 = \displaystyle\sum_{i = 1}^{n}\left[\sum_{j = 1}^{n}(m_{ij}a_j) - b_i \right]^2$ subject to the constraint $\|M\|_{\infty} \le 1$, i.e. $\displaystyle\sum_{j = 1}^{n}|m_{ij}| \le 1$ for all $i$. Let $k = \text{argmax}_{1 \le j \le n}|a_j|$. Split the minimization problem into $n$ problems (one for each $i$). If $|b_i| ...


3

In order to be able to do "normal" algebra in this situation, you just need to justify that $$x \in A + y$$ is equivalent to $$x - y \in A$$ where $V$ is a vector space and $x,y \in V$ and $A \subset V$. This is easy to check. If the first statement holds, then $x = a + y$ for some $a \in A$. Now we really have an equality of elements, so we can do ...


2

I do not fully understand what you would like to ask. However, a possible answer could be the following. A set $A$ is strongly convex, if there is some $m > 0$ with $$ x,y \in A \;\Rightarrow\; \lambda \, x + (1-\lambda) \, y + m \, \lambda \, (1-\lambda) \, \mathbb{B} \subset A, $$ where $\mathbb{B}$ is the unit ball. I must admit that I do not know if ...


2

As $\log$ is a concave function, $$ \log (\theta a + (1-\theta)b )\ge \theta \log a + (1-\theta)\log b $$ Now with $$ a=f(x);b = f(y) $$it follows that $$ \log f(\theta a + (1-\theta)b) \ge \theta \log f(x)+ (1-\theta)\log f(y) $$ More generally, if $f$ is concave with values in $D\subset \Bbb R$ and $g$ is concave increasing and define on $D$ then ...


2

The following discussion will assume the quadratic form $x^H A x$ has only real values (so that the "max" operator can be directly applied to these values), although it is not necessarily positive definite. The maximum will be attained on the boundary $||x|| = c$ (assuming $c \ge 0$) provided $A$ is not negative definite. That is, if $x^H A x \ge 0$ for ...


2

I'm glad you found your answer. For archival purposes I think it would be good to derive the equivalence in a couple of steps, though. At first, you might be tempted to introduce $\xi_i$ by transforming your model from this $$\begin{array}{ll} \text{minimize}_{w,b} & \frac{1}{2}w^T w+\sum_{i=1}^{N}\max\{0,1-y_i(w^Tx_i +b)\} \end{array}$$ to this: ...


2

I am reasonably sure there is no closed form solution to this problem. But this is, in fact, just a nonnegative least squares problem (NNLS). It may not immediately look like it, but thanks to a little Kronecker product magic we can rewrite the objective function in this fashion: $$\|R-PQ\|_F^2 = \|\mathop{\textrm{vec}}(R)-(Q^T\otimes ...


2

You can simply solve some linear equations to show that any point in the plane can be expressed as an affine combination of three vertices, for example $(\pm 1,0)$ and $(0,1)$. $$ \begin{aligned} (x,y)\ &= a(1,0) + b(-1,0) +c(0,1)\\ 1\ &= a+b+c \end{aligned} $$ $$ \Rightarrow (x,y) = \frac{1-y+x}{2}(1,0) + \frac{1-y-x}{2}(-1,0) + y(0,1) $$ Hence ...


2

I believe that preconditioning already gives such function $g$. In this case $g$ is simply multiplication by a matrix. But I don't know of any known acceleration method with non-linear $g$. I assume that you mean that $g$ does not change as the iterations progress. That is, the function $g$ is the same for all iterates. Otherwise, Newton's method is an ...


2

Since $R=KQ$, you can focus on solving for $Q$. So your problem looks like \begin{align} \min_{Q}||J-KQ||_F^2 \end{align} (squaring of the objective won't change the solution, convince yourself). Now, we have $$vec(J-KQ)=vec(J)-(I\otimes K)vec(Q)$$ where $vec(.)$ operator stacks up the columns of argument matrix and $\otimes$ is the kronecker product. Again ...


2

Try $$A=1, \qquad B=-1$$ $1\times 1$ matrices


1

You have \begin{equation} f(y) \geq f(x) + \nabla f(x)'(y-x) + \frac{m}{2} \| y-x \|^2_2, \: \forall x,y \in S. \end{equation} In particular, for $x=x^*,$ it is \begin{equation} f(y) \geq f(x^*) + \nabla f(x^*)'(y-x^*) + \frac{m}{2} \| y-x^* \|^2_2, \: \forall y \in S. \end{equation} Since $x^*$ is a global minimum of $f$ it is $\nabla f(x^*)=0.$ That ...


1

No, it is not possible. That inequality describes a non-convex set, and SOCP necessarily requires convexity. EDIT: Given the response below ("The terms in the bracket are convex by themselves") I thought I would expand further. The convexity of individual functions and terms, frankly, is of far less importance than people often think. After all, $x^2 \geq ...


1

According to the definition of a subgradient that I know (referenced http://web.stanford.edu/class/ee392o/subgrad.pdf and on Wikipedia), a subgradient is not a set, but rather a vector (or a scalar in the case where $f:\mathbb{R}\rightarrow\mathbb{R}$). So, according to these definitions, any element of $\mathbb{R}\times\{0\}$ is a subgradient of your $f$. ...


1

Sorry,I've found the following relations $$ tr(ABC)=tr(BCA)=tr(CAB) $$ then, we have $$ tr(B^TX^TCXBD)=tr(CXBDB^TX^T) $$ then, from the Matrix Cookbook, we have $$ \frac{\delta{tr(EXFX^TG)}}{\delta X}=E^TG^TXF^T+GEXF $$ then, let $$ E=C,F=BD,G=I $$ we could get the answer.


1

Hint: As $f$ is concave and differentiable, it should lie below all its tangents, that is: $$ f(b)\leq f(a)+f'(a)(b-a) $$ for all $a,b \in[0,1)$. On the other hand, for $g$ (easily seen to be differentiable on $(0,1)$) we have: $$g'(z) = \frac{zxf'(zx)-f(zx)}{z^2} $$ which can be proven (using above observation and $f(0)=0$) to be less than or equal to ...


1

Hint for the case $x=1$: $\displaystyle g(z) = \frac{f(z)-f(0)}{z-0}$. What is that the slope of?


1

One of the reasons we like the Huber penalty is that it is the "Moreau-Yosida regularization" of the absolute value function, which means that \begin{equation*} \phi(y) = \inf_u \quad | u | + \frac{1}{2M} (u - y)^2. \end{equation*} So, your optimization problem can be written as \begin{equation*} \operatorname*{minimize}_{x} \quad \sum_i \inf_{u_i} \, |u_i ...


1

The notation $\partial R(w_i)$ is a little confusing so I'll generalize slightly and use a different notation: $$ F(w) = \sum_{i=1}^d f(w_i) $$ Then we claim subgradient of $F$ is: $$ \partial F(w) = (\partial f(w_1), \partial f(w_2) \ldots, \partial f(w_d)) = \{ (v_1, v_2 \ldots, v_d) \in \mathbb{R}^d : v_i \in \partial f(w_i)\} $$ Note that $\partial ...


1

A quite sensible solution (and very commonly used) is simply to solve $K=F U^{-1}$ and symmetrize the result: $\tilde{K}=\frac12(K+K^T)$. This will work well if your $K$ is already close to symmetric. Then you can diagonalize the matrix (guaranteed to work because it's symmetric) and set negative eigenvalues to zero and multiply back. In most cases, these ...


1

As pointed about above, your problem is overdetermined, because you are requiring $KU=F$, even though $U$ is not certain. If you are willing to relax this requirement to, say, $\|KU-F\|\leq\epsilon$ for some choice of norm and a positive $\epsilon$, then you have a shot at solving your problem. If you do something like this, then this problem is a ...


1

For example $K=[0,1]\cup[2,3]$. It is not convex, because the interval $[1,2]\not\subset K$, although its end are in $K$.


1

A set is in $\mathbb{R}^n$ is convex if and only if the line segment between any two points in the set is contained within the set. In $\mathbb{R}$, that just means the set is connected, or in other words an interval. Any compact set that is not connected is not convex.


1

This is the so-called "weighted arithmetic mean geometric mean inequality". See http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means#Weighted_AM.E2.80.93GM_inequality



Only top voted, non community-wiki answers of a minimum length are eligible