Tag Info

3

If $p$ is rational and $p>=1$, then the p-norm minimization problem can be formulated as an SOCP. This is discussed (among many other places) in Alizadeh, Farid, and Donald Goldfarb. "Second-order cone programming." Mathematical Programming 95(1):3-51, 2003.

2

The Eckart-Young-Mirsky theorem tells us that the best rank $r$ approximation to a possibly non-symmetric matrix $A$ in the 2-norm (also in the Frobenius norm) is given by the first $k$ singular values and singular vectors of the SVD of $A=U\Sigma V^{T}$ as $A=\sum_{i=1}^{k} \sigma_{i} U_{i}V_{i}^{T}$. When $A$ is symmetric and positive semidefinite, this ...

1

The Simplex method is already a "gradient descent" method, in the sense that it follows some descent direction. I wouldn't call it gradient descent, since the gradient does not exist at the basic solutions, but rather a local search or hill descent. Seen as a local search, the neighbors of the current basic solution are all basic solutions that can be ...

1

No, this is not correct. For $f(x)=\arctan x$, Newton's method is $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-(1+x_n^2)\arctan(x_n)$$ so will give $\lvert x_{n+1}\rvert<\lvert x_n\rvert$ if $\lvert x_n\rvert<\xi$, where $\xi\approx 1.39$ is the unique positive solution of $\arctan(\xi)=2\xi/(1+\xi^2)$. For starting value bigger in magnitude that $\xi$,...

1

Consider $y_0 \in A$, let $g_0 = \lambda_0 \nabla J (y_0)$, let $e$ be the all one vector. We know the formula for projection onto $A$ is: $$\Pi_A(z) = z- \left( \frac{z^Te-1}{3}\right)e$$ Also, the formula for projection onto $B$ is : $$\Pi _B (z) = z- \left( \frac{z^Te}{3}\right)e$$ Note that we have \begin{align}\Pi_A(y_0-g) &= (y_0-g_0)- \...

1

Here's a formulation via mixed integer programming (MIP). Define the following decision variables: $y_{ij} = 1$ if we allocate customer $C_i$ to adviser $P_j$, $0$ otherwise $z^\max =$ the maximum policy value among all advisers $z^\min =$ the minimum policy value among all advisers Then the formulation is: \begin{align} \text{minimize} \quad & z^\... 1 Hint. \frac 12(b^T x)^2 = \frac 12(x^T b)(b^T x)\Rightarrow \partial_x\frac 12(b^T x)^2 = b(b^T x)  \left(H+\alpha b b^T\right)x + c = 0\Rightarrow x = -\left(H+\alpha bb^T\right)^{-1}c 

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