Search Results

A nonempty set $S$ in a normed linear space $X$ is called a Chebyshev set if for each $u \in X$ there is exactly one nearest point in $S$ to $u$ (i.e., for a Chebyshev set, nearest points always exist …

Since we are dealing with real number computation, we cannot use the traditional Turing machine for complexity analysis. There will always be some $\epsilon$s lurking in there. That said, when analyz …

Unless I'm mistaken, the following argument provides a solution. Since the Frobenius norm is orthogonally invariant we can assume without loss of generality that $S$ is diagonal. I'll write $Q$ inste …

This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e., \begin{equation*} \text{prox}_f(y) := \operatorname{argmin}\quad \ …

To some extent. Here's some relevant material where group theoretic objects show up in optimization (though a lot of it is convex algebraic geometry). Orbitopes Group majorization and a host of maj …

One approach is to solve the optimization problem: \begin{equation*} \min_x\quad \|Ax-y\|_\infty. \end{equation*} This is a nonsmooth optimization problem, but is amenable to a variety of scalable opt …

Yes, a lot can be said for your special case. Given the notation, I presume you are optimizing over $\mathbb{C}^n$. In this case, see Section 2 in the paper Strong Duality in Nonconvex Quadratic Optim …

The paper cited in my answer here provides a detailed proof of the two-block case of alternating minimization (block coordinate descent). In particular, as mentioned in my comment, the convergence fol …

Your problem is a special case of a Fractional Linear Program, so as such following the recipe provided on Wikipedia you should be able to solve it by using a reformulation to an equivalent linear pro …

As far as I know, there is no "analytic" solution to your problem. Fortunately, this problem happens to be a special case of optimizing (over $\mathbb{C}^n$) a quadratic function subject to two quadra …

If $C$ is positive semidefinite, then so is $\begin{bmatrix} C & C\\ C & C\end{bmatrix}$ for the simple reason that it is nothing but the Kronecker product of $\begin{bmatrix} 1 & 1\\ 1 & 1\end{bmatri …

The function that you have is convex for unitarily invariant norms, but for the (basis dependent) elementwise absolute value, it can clearly break as a trivial counterexample below shows. \begin{equa …

Rather than compute "the" Lipschitz constant, it is much easier to do a backtracking line search that roughly upper-bounds the Lipschitz constant. To get some ideas, on how one might do a simple line …

Building on Nesterov's work, in his Ph.D thesis, Peter Richtarik considers first-order methods with relative error of approximation guarantees. I haven't looked in too closely, but I am sure that a la …

Maybe this is overkill, but I would recommend that you read the masterful paper: Optimizing the spectral radius, by Yurii Nesterov and Vladimir Protasov, 2012. Unless I'm mistaken, your problem is a …