首页 > 代码库 > 欧几里德投影(Euclidean projection)

欧几里德投影(Euclidean projection)

Euclidean projection on a set

An Euclidean projection of a point x_0 in mathbf{R}^n on a set mathbf{S} subseteq mathbf{R}^n is a point that achieves the smallest Euclidean distance from x_0 to the set. That is, it is any solution to the optimization problem

 min_x : |x-x_0|_2 ~:~ x in mathbf{S}.

When the set mathbf{S} is convex, there is a unique solution to the above problem. In particular, the projection on an affine subspace is unique.

Example: assume that mathbf{S} is the hyperplane

 mathbf{S} = left{ x in mathbf{R}^3 ~:~ 2x_1 + x_2 -x_3 = 1 right}.

The projection problem reads as a linearly constrained least-squares problem, of particularly simple form:

 min_x : |x|_2 ~:~ 2x_1 + x_2 -x_3 = 1.

The projection of x_0 = 0 on mathbf{S} turns out to be aligned with the coefficient vector a = (2,1,-1). Indeed, components of x orthogonal to a don‘t appear in the constraint, and only increase the objective value. Setting x = t a in the equation defining the hyperplane and solving for the scalar t we obtain t = 1/(a^Ta) = 1/6, so that the projection is x^ast = a/(a^Ta) = (1/3,1/6,-1/6).

================================================

凸集(Convex Set):

Definitions

A subset mathbf{C} of mathbf{R}^n is said to be convex if and only if it contains the line segment between any two points in it:

 forall : x_1, x_2 in mathbf{C}, ;; forall : lambda in [0,1] ~:~ lambda x_1 + (1-lambda)  x_2 in mathbf{C}.

Subspaces and affine sets, such as lines, planes and higher-dimensional ‘‘flat’’ sets, are obviously convex, as they contain the entire line passing through any two points, not just the line segment. That is, there is no restriction on the scalar lambda anymore in the above condition.

---------------------------------------------------------------------

当且仅当mathbf{R}^n上的子集mathbf{C}包含任意二点直接的线段满足:

 forall : x_1, x_2 in mathbf{C}, ;; forall : lambda in [0,1] ~:~ lambda x_1 + (1-lambda)  x_2 in mathbf{C}.
很明显,子空间和仿射集合,诸如直线,平面以及更高维度的水平集均是凸集。

Examples:

  • A convex and a non-convex set.

  • Convex and conic hull of a set of points.

A set is said to be a convex cone if it is convex, and has the property that if x in mathbf{C}, then alpha x in mathbf{C} for every alpha ge 0.