Intereting Posts

Local-Global Principle and the Cassels statement.
The shortest distance between any two distinct points is the line segment joining them.How can I see why this is true?
Hensel Lifting and solving with mods
Formula for trace of compact operators on $L^2(\mathbb{R})$ given by integral kernels?
The only group automorphisms of the additive group of real numbers that are also order isomorphisms are multiplication by positive real numbers
Geometric interpretation of complex path integral
Recommendations for Numerical Analysis texts?
Inequality involving the regularized gamma function
how many element of order 2 and 5 are there
Distinguishable painted prisms with six colors (repetition allowed)
Number of Solutions to a Diophantine Equation
Books for high school students starting on college math
Hölder continuous but not differentiable function
A conjecture including binomial coefficients
Why is $\mathbb{R}/{\sim}$ not first countable at $$, where $x \sim y \Leftrightarrow x = y\text{ or }x,y \in \mathbb{Z}$?

The Unit Simplex is defined by:

$$ \mathcal{S} = \left\{ x \in \mathbb{{R}^{n}} \mid x \succeq 0, \, \boldsymbol{1}^{T} 1 = 1 \right\} $$

Orthogonal Projection onto the Unit Simplex is defined by:

- Choosing $\lambda$ to yield sparse solution
- Why is it a requirement that we follow the central path in the interior point method?
- Quasiconvexity of linear-fractional composition
- How the dual LP solves the primal LP
- When is the difference of two convex functions convex?
- Submodularity of the product of two non-negative, monotone increasing submodular functions

$$

\begin{alignat*}{3}

\arg \min_{x} & \quad & \frac{1}{2} \left\| x – y \right\|_{2}^{2} \\

\text{subject to} & \quad & x \succeq 0 \\

& \quad & \boldsymbol{1}^{T} x = 1

\end{alignat*}

$$

- How to formalize $\text{span}(S)=\{c_1v_1+\cdots+c_kv_k\mid v_1,~\cdots,~v_k\in S,~c_1,~\cdots,~c_k\in F\}$ rigorously in first order language?
- Is it possible to define an inner product such that an arbitrary operator is self adjoint?
- Decomposable elements of $\Lambda^k(V)$
- Sign of determinant when using $det A^\top A$
- An inequality on the root of matrix products (part 2 - the reverse case)
- $S\subseteq V \Rightarrow \text{span}(S)\cong S^{00}$
- How to find an intersection of a 2 vector subspace?
- Matrix reciprocal positive to prove $λ_{max}=n$
- Vector spaces of the same finite dimension are isomorphic
- If a field $F$ is such that $\left|F\right|>n-1$ why is $V$ a vector space over $F$ not equal to the union of proper subspaces of $V$

Projection onto the Simplex can be calculated as following.

The Lagrangian in that case is given by:

$$ \begin{align}

L \left( x, \mu \right) & = \frac{1}{2} {\left\| x – y \right\|}^{2} + \mu \left( \boldsymbol{1}^{T} x – 1 \right) && \text{} \\

\end{align} $$

The trick is to leave non negativity constrain implicit.

Hence the Dual Function is given by:

$$ \begin{align}

g \left( \mu \right) & = \inf_{x \succeq 0} L \left( x, \mu \right) && \text{} \\

& = \inf_{x \succeq 0} \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} – {y}_{i} \right) }^{2} + \mu {x}_{i} \right) – \mu && \text{Component wise form}

\end{align} $$

Again, taking advantage of the Component Wise form the solution is given:

$$ \begin{align}

{x}_{i}^{\ast} = { \left( {y}_{i} – \mu \right) }_{+}

\end{align} $$

Where the solution includes the non negativity constrain by Projecting onto $ {\mathbb{R}}_{+} $

The solution is given by finding the $ \mu $ which holds the constrain (Pay attention, since the above was equality constrain, $ \mu $ can have any value and it is not limited to non negativity as $ \lambda $ above).

The objective function (From the KKT) is given by:

$$ \begin{align}

h \left( \mu \right) = \sum_{i = 1}^{n} {x}_{i}^{\ast} – 1 & = \sum_{i = 1}^{n} { \left( {y}_{i} – \mu \right) }_{+} – 1

\end{align} $$

The above is a Piece Wise linear function of $ \mu $ and its Derivative given by:

$$ \begin{align}

\frac{\mathrm{d} }{\mathrm{d} \mu} h \left( \mu \right) & = \frac{\mathrm{d} }{\mathrm{d} \mu} \sum_{i = 1}^{n} { \left( {y}_{i} – \mu \right) }_{+} \\

& = \sum_{i = 1}^{n} -{ \mathbf{1} }_{\left\{ {y}_{i} – \mu > 0 \right\}}

\end{align} $$

Hence it can be solved using Newton Iteration.

I wrote MATLAB code which implements them both at Mathematics StackExchange Question 2338491 – GitHub.

There is a test which compares the result to a reference calculated by CVX.

- What is your favorite application of the Pigeonhole Principle?
- How is $a_n=(1+1/n)^n$ monotonically increasing and bounded by $3$?
- A ring element with a left inverse but no right inverse?
- Is differentiating on both sides of an equation allowed?
- Proof involving norm of an integral
- A surjective linear map into a finite dimensional space is open
- Show that there are infinitely many powers of two starting with the digit 7
- Polynomials such that roots=coefficients
- What is the joint distribution of two random variables?
- Period of decimal for $1/n$, odd part of $n+1$, and primes.
- Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $$
- If $x+\frac1x=5$ find $x^5+\frac1{x^5}$.
- Prove that a connected graph not having $P_4$ or $C_3$ as an induced subgraph is complete bipartite
- What exactly are eigen-things?
- Finding an upperbound for $\sum_{i=2}^{n}\bigg(\prod_{k=2}^{i}\dfrac{p_k-2}{p_k}\bigg)$