intersection

Triangle area problem: REVISITED.

March 31, 2024 math and physics play , , , , ,

[Click here for a PDF version of this post]

On LinkedIn, James asked for ideas about how to solve What is the total area of ABC? You should be able to solve this! using geometric algebra.

I found a couple ways, and this last variation is pretty cool.

fig. 1. Triangle with given areas.

To start with I’ve re-sketched the triangle with the areas slightly more to scale in fig. 1, where areas \( A_1 = 40, A_2 = 30, A_3 = 35, A_4 = 84 \) are given. The aim is to find the total area \( \sum A_i \).

If we had the vertex and center locations as vectors, we could easily compute the total area, but we don’t. We also don’t know the locations of the edge intersections, but can calculate those, as they satisfy
\begin{equation}\label{eqn:triangle_area_problem:20}
\begin{aligned}
\BD &= s_1 \BA = \BB + t_1 \lr{ \BC – \BB } \\
\BE &= s_2 \BC = \BA + t_2 \lr{ \BB – \BA } \\
\BF &= s_3 \BB = \BA + t_3 \lr{ \BC – \BA }.
\end{aligned}
\end{equation}
It turns out that the problem is over specified, and we will only need \( \BD, \BE \). To find those, we may eliminate the \( t_i \)’s by wedging appropriately (or equivalently, using Cramer’s rule), to find
\begin{equation}\label{eqn:triangle_area_problem:40}
\begin{aligned}
s_1 \BA \wedge \lr{ \BC – \BB } &= \BB \wedge \lr{ \BC – \BB } \\
s_2 \BC \wedge \lr{ \BB – \BA } &= \BA \wedge \lr{ \BB – \BA },
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:triangle_area_problem:60}
\begin{aligned}
s_1 &= \frac{\BB \wedge \BC }{\BA \wedge \lr{ \BC – \BB }} \\
s_2 &= \frac{\BA \wedge \BB }{\BC \wedge \lr{ \BB – \BA }}.
\end{aligned}
\end{equation}
Now let’s introduce some scalar area variables, each pseudoscalar multiples of bivector area elements, with \( i = \Be_{1} \Be_2 \)
\begin{equation}\label{eqn:triangle_area_problem:81}
\begin{aligned}
X &= \lr{ \BA \wedge \BB } i^{-1} = \begin{vmatrix} \BA & \BB \end{vmatrix} \\
Y &= \lr{ \BC \wedge \BB } i^{-1} = \begin{vmatrix} \BC & \BB \end{vmatrix} \\
Z &= \lr{ \BA \wedge \BC } i^{-1} = \begin{vmatrix} \BA & \BC \end{vmatrix},
\end{aligned}
\end{equation}
Note that the orientation of all of these has been picked to have a positive orientation matching the figure, and that the
triangle area that we seek for this problem is \( 1/2 \Abs{ \BA \wedge \BB } = X/2 \).

The intersection parameters, after cancelling pseudoscalar factors, are
\begin{equation}\label{eqn:triangle_area_problem:100}
\begin{aligned}
s_1 &= \frac{\BB \wedge \BC }{\BA \wedge \BC – \BA \wedge \BB } = \frac{-Y}{Z – X} \\
s_2 &= \frac{\BA \wedge \BB }{\BC \wedge \BB – \BC \wedge \BA } = \frac{X}{Y + Z},
\end{aligned}
\end{equation}
so the intersection points are
\begin{equation}\label{eqn:triangle_area_problem:120}
\begin{aligned}
\BD &= \BA \frac{Y}{X – Z} \\
\BE &= \BC \frac{X}{Y + Z}.
\end{aligned}
\end{equation}
Observe that both scalar factors are positive (i.e.: \( X > Z \).)

We may now express all the known areas in terms of our area variables
\begin{equation}\label{eqn:triangle_area_problem:140}
\begin{aligned}
A_1 &= \inv{2} \lr{ \BD \wedge \BC } i^{-1} \\
A_1 + A_2 &= \inv{2} \lr{ \BA \wedge \BC } i^{-1} \\
A_1 + A_2 + A_3 &= \inv{2} \lr{ \BA \wedge \BE } i^{-1} \\
A_2 &= \inv{2} \lr{ \lr{\BA – \BD} \wedge \lr{ \BC – \BD } } i^{-1}\\
A_3 &= \inv{2} \lr{ \lr{\BA – \BC} \wedge \lr{ \BE – \BC } } i^{-1}\\
A_5 &= \inv{2} \lr{ \lr{\BB – \BC} \wedge \lr{ \BF – \BC } } i^{-1}.
\end{aligned}
\end{equation}

As mentioned, the problem is over specified, and we can get away with just the first three of these relations to solve for total area. Eliminating \( \BD, \BE \) from those, gives us
\begin{equation}\label{eqn:triangle_area_problem:180}
A_1 = \inv{2} \frac{Y}{X – Z} \lr{ \BA \wedge \BC } i^{-1} = \frac{Z}{2} \lr{ \frac{Y}{X – Z} },
\end{equation}
\begin{equation}\label{eqn:triangle_area_problem:460}
A_1 + A_2 = \inv{2} \lr{ \BA \wedge \BC } i^{-1} = \frac{Z}{2},
\end{equation}
and
\begin{equation}\label{eqn:triangle_area_problem:400}
\begin{aligned}
A_1 + A_2 + A_3 &= \inv{2} \lr{ \BA \wedge \BE } i^{-1} \\
&= \inv{2} \lr{ \BA \wedge \BC } \frac{X}{Y + Z} \\
&= \frac{Z}{2} \frac{X}{Y + Z}.
\end{aligned}
\end{equation}

Let’s eliminate \( Z \) to start with, leaving
\begin{equation}\label{eqn:triangle_area_problem:420}
\begin{aligned}
A_1 \lr{ X – 2 A_1 – 2 A_2 } &= Y \lr{ A_1 + A_2 } \\
\lr{ A_1 + A_2 + A_3 } \lr{ Y + 2 A_1 + 2 A_2 } &= \lr{ A_1 + A_2 } X.
\end{aligned}
\end{equation}
Solving for \( Y \) yields
\begin{equation}\label{eqn:triangle_area_problem:380}
Y = – 2 A_1 – 2 A_2 + \frac{ \lr{A_1 + A_2} X }{ A_1 + A_2 + A_3 } = \lr{ A_1 + A_2 } \lr{ -2 + \frac{X}{A_1 + A_2 + A_3 } },
\end{equation}
and back substution leaves us with a linear equation in \( X \)
\begin{equation}\label{eqn:triangle_area_problem:480}
\lr{ A_1 + A_2}^2 \lr{ -2 + \frac{X}{A_1 + A_2 + A_3 } } = A_1 \lr{ X – 2 A_1 – 2 A_2 }.
\end{equation}

This is easily solved to find
\begin{equation}\label{eqn:triangle_area_problem:500}
\frac{X}{2} = \frac{ \lr{ A_1 + A_2} A_2 \lr{ A_1 + A_2 + A_3 } }{A_2 \lr{ A_1 + A_2} – A_1 A_3 }.
\end{equation}
Plugging in the numeric values for the problem solves it, giving a total triangular area of \( \inv{2} \lr{\BA \wedge \BB } i^{-1} = X/2 = 315 \).

Now, I’ll have to watch the video and see how he solved it.

Triangle area problem

March 30, 2024 math and physics play , , , , , ,

[Click here for a PDF version of this post]

On LinkedIn, James asked for ideas about how to solve What is the total area of ABC? You should be able to solve this! using geometric algebra.

I found one way, but suspect it’s not the easiest way to solve the problem.

To start with I’ve re-sketched the triangle with the areas slightly more to scale in fig. 1, where areas \( A_1, A_2, A_3, A_5\) are given. The aim is to find the total area \( \sum A_i \).

fig. 1. Triangle with given areas.

 

If we had the vertex and center locations as vectors, we could easily compute the total area, but we don’t. We also don’t know the locations of the edge intersections, but can calculate those, as they satisfy
\begin{equation}\label{eqn:triangle_area_problem:20}
\begin{aligned}
\BD &= s_1 \BA = \BB + t_1 \lr{ \BC – \BB } \\
\BE &= s_2 \BC = \BA + t_2 \lr{ \BB – \BA } \\
\BF &= s_3 \BB = \BA + t_3 \lr{ \BC – \BA }.
\end{aligned}
\end{equation}
Eliminating the \( t_i \) constants by wedging appropriately (or equivalently, using Cramer’s rule), we find
\begin{equation}\label{eqn:triangle_area_problem:40}
\begin{aligned}
s_1 \BA \wedge \lr{ \BC – \BB } &= \BB \wedge \lr{ \BC – \BB } \\
s_2 \BC \wedge \lr{ \BB – \BA } &= \BA \wedge \lr{ \BB – \BA } \\
s_3 \BB \wedge \lr{ \BC – \BA } &= \BA \wedge \lr{ \BC – \BA },
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:triangle_area_problem:60}
\begin{aligned}
s_1 &= \frac{\BB \wedge \BC }{\BA \wedge \lr{ \BC – \BB }} \\
s_2 &= \frac{\BA \wedge \BB }{\BC \wedge \lr{ \BB – \BA }} \\
s_3 &= \frac{\BA \wedge \BC }{\BB \wedge \lr{ \BC – \BA }}.
\end{aligned}
\end{equation}
Introducing bivector (signed-area) unknowns
\begin{equation}\label{eqn:triangle_area_problem:80}
\begin{aligned}
\alpha &= \BA \wedge \BB = \begin{vmatrix} \BA & \BB \end{vmatrix} \Be_{12} \\
\beta &= \BB \wedge \BC = \begin{vmatrix} \BB & \BC \end{vmatrix} \Be_{12} \\
\gamma &= \BC \wedge \BA = \begin{vmatrix} \BC & \BA \end{vmatrix} \Be_{12}.
\end{aligned}
\end{equation}
the intersection parameters are
\begin{equation}\label{eqn:triangle_area_problem:100}
\begin{aligned}
s_1 &= \frac{\BB \wedge \BC }{\BA \wedge \BC – \BA \wedge \BB } = \frac{\beta}{-\gamma – \alpha} \\
s_2 &= \frac{\BA \wedge \BB }{\BC \wedge \BB – \BC \wedge \BA } = \frac{\alpha}{-\beta – \gamma} \\
s_3 &= \frac{\BA \wedge \BC }{\BB \wedge \BC – \BB \wedge \BA } = \frac{-\gamma}{\beta + \alpha},
\end{aligned}
\end{equation}
so the intersection points are
\begin{equation}\label{eqn:triangle_area_problem:120}
\begin{aligned}
\BD &= -\BA \frac{\beta}{\gamma + \alpha} \\
\BE &= -\BC \frac{\alpha}{\beta + \gamma} \\
\BF &= -\BB \frac{\gamma}{\beta + \alpha}.
\end{aligned}
\end{equation}

We may now express the known areas in terms of these unknown vectors
\begin{equation}\label{eqn:triangle_area_problem:140}
\begin{aligned}
A_1 &= \inv{2} \Abs{ \BD \wedge \BC } \\
A_2 &= \inv{2} \Abs{ \lr{\BC – \BA} \wedge \lr{ \BD – \BA } } \\
A_3 &= \inv{2} \Abs{ \lr{\BA – \BC} \wedge \lr{ \BE – \BC } } \\
A_5 &= \inv{2} \Abs{ \lr{\BB – \BC} \wedge \lr{ \BF – \BC } },
\end{aligned}
\end{equation}
but
\begin{equation}\label{eqn:triangle_area_problem:160}
\begin{aligned}
\BD – \BA &= -\BA \lr{ 1 + \frac{\beta}{\gamma + \alpha} } \\
\BE – \BC &= -\BC \lr{ 1 + \frac{\alpha}{\beta + \gamma} } \\
\BF – \BC &= -\BB \frac{\gamma}{\beta + \alpha} – \BC,
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:triangle_area_problem:180}
\begin{aligned}
A_1 &= \inv{2} \Abs{ \BA \wedge \BC \frac{\beta}{\gamma + \alpha} } = \inv{2} \Abs{ \gamma} \Abs{ \frac{\beta}{\gamma + \alpha} } \\
A_2 &= \inv{2} \Abs{ \lr{\BC – \BA} \wedge \BA } \Abs{ 1 + \frac{\beta}{\gamma + \alpha} } = \inv{2} \Abs{\gamma} \Abs{ 1 + \frac{\beta}{\gamma + \alpha} } \\
A_3 &= \inv{2} \Abs{ \lr{\BA – \BC} \wedge \BC } \Abs{ 1 + \frac{\alpha}{\beta + \gamma} } = \inv{2} \Abs{\gamma} \Abs{ 1 + \frac{\alpha}{\beta + \gamma} },
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:triangle_area_problem:200}
\begin{aligned}
A_5
&= \inv{2} \Abs{ \lr{\BB – \BC} \wedge \lr{ \BB \frac{\gamma}{\beta + \alpha} + \BC } } \\
&= \inv{2} \Abs{ \BB \wedge \BC – \BC \wedge \BB \frac{\gamma}{\beta + \alpha} } \\
&= \inv{2} \Abs{ \beta } \Abs{ 1 + \frac{\gamma}{\beta + \alpha} }.
\end{aligned}
\end{equation}

This gives us four equations in two (bivector) unknowns
\begin{equation}\label{eqn:triangle_area_problem:220}
\begin{aligned}
4 A_1^2 \lr{ \gamma + \alpha }^2 &= -\gamma^2 \beta^2 \\
4 A_2^2 \lr{ \gamma + \alpha }^2 &= -\gamma^2 \lr{ \alpha + \beta + \gamma }^2 \\
4 A_3^2 \lr{ \gamma + \beta }^2 &= -\gamma^2 \lr{ \alpha + \beta + \gamma }^2 \\
4 A_4^2 \lr{ \alpha + \beta }^2 &= -\beta^2 \lr{ \alpha + \beta + \gamma }^2.
\end{aligned}
\end{equation}
Let’s recast this in terms of area determinants, to eliminate the bivector variables in these equations. To do so, write
\begin{equation}\label{eqn:triangle_area_problem:240}
\begin{aligned}
X &= \begin{vmatrix} \BA & \BB \end{vmatrix} \\
Y &= \begin{vmatrix} \BB & \BC \end{vmatrix} \\
Z &= \begin{vmatrix} \BC & \BA \end{vmatrix}.
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:triangle_area_problem:300}
\begin{aligned}
4 A_1^2 \lr{ Z + X }^2 &= Z^2 Y^2 \\
4 A_2^2 \lr{ Z + X }^2 &= Z^2 \lr{ X + Y + Z }^2 \\
4 A_3^2 \lr{ Z + Y }^2 &= Z^2 \lr{ X + Y + Z }^2 \\
4 A_4^2 \lr{ X + Y }^2 &= Y^2 \lr{ X + Y + Z }^2.
\end{aligned}
\end{equation}
The goal is now to solve this system for \( X \). That solution (courtesy of Mathematica), for the numeric values in the original problem \( A_1 = 40, A_2 = 30, A_3 = 35, A_4 = 84 \), is:

\begin{equation}\label{eqn:triangle_area_problem:280}
\begin{aligned}
X &= \pm 630 \\
Y &= \mp 280 \\
Z &= \mp 140,
\end{aligned}
\end{equation}
so the total area is \( 315 \).

Now, I’ll have to watch the video and see how he solved it. I’d guess in a considerably simpler way.

ECE1505H Convex Optimization. Lecture 4: Sets and convexity. Taught by Prof. Stark Draper

January 25, 2017 ece1505 , , , , , , ,

ECE1505H Convex Optimization. Lecture 4: Sets and convexity. Taught by Prof. Stark Draper

[Click here for a PDF of this post with nicer formatting]

Disclaimer

Peeter’s lecture notes from class. These may be incoherent and rough.

These are notes for the UofT course ECE1505H, Convex Optimization, taught by Prof. Stark Draper, covering [1] content.

Today

  • more on various sets: hyperplanes, half-spaces, polyhedra, balls, ellipses, norm balls, cone of PSD
  • generalize inequalities
  • operations that preserve convexity
  • separating and supporting hyperplanes.

Hyperplanes

Find some \( \Bx_0 \in \mathbb{R}^n \) such that \( \Ba^\T \Bx_0 = \Bb \), so

\begin{equation}\label{eqn:convexOptimizationLecture4:20}
\begin{aligned}
\setlr{ \Bx | \Ba^\T \Bx = \Bb }
&=
\setlr{ \Bx | \Ba^\T \Bx = \Ba^\T \Bx_0 } \\
&=
\setlr{ \Bx | \Ba^\T (\Bx – \Bx_0) } \\
&=
\Bx_0 + \Ba^\perp,
\end{aligned}
\end{equation}

where

\begin{equation}\label{eqn:convexOptimizationLecture4:40}
\Ba^\perp = \setlr{ \Bv | \Ba^\T \Bv = 0 }.
\end{equation}

fig. 1. Parallel hyperplanes.

 

Recall

\begin{equation}\label{eqn:convexOptimizationLecture4:60}
\Norm{\Bz}_\conj = \sup_\Bx \setlr{ \Bz^\T \Bx | \Norm{\Bx} \le 1 }
\end{equation}

Denote the optimizer of above as \( \Bx^\conj \). By definition

\begin{equation}\label{eqn:convexOptimizationLecture4:80}
\Bz^\T \Bx^\conj \ge \Bz^\T \Bx \quad \forall \Bx, \Norm{\Bx} \le 1
\end{equation}

This defines a half space in which the unit ball

\begin{equation}\label{eqn:convexOptimizationLecture4:100}
\setlr{ \Bx | \Bz^\T (\Bx – \Bx^\conj \le 0 }
\end{equation}

Start with the \( l_1 \) norm, duals of \( l_1 \) is \( l_\infty \)

 

fig. 2. Half space containing unit ball.

Similar pic for \( l_\infty \), for which the dual is the \( l_1 \) norm, as sketched in fig. 3.  Here the optimizer point is at \( (1,1) \)

 

fig. 3. Half space containing the unit ball for l_infinity

and a similar pic for \( l_2 \), which is sketched in fig. 4.

 

fig. 4. Half space containing for l_2 unit ball.

Q: What was this optimizer point?

Polyhedra

\begin{equation}\label{eqn:convexOptimizationLecture4:120}
\begin{aligned}
\mathcal{P}
&= \setlr{ \Bx |
\Ba_j^\T \Bx \le \Bb_j, j \in [1,m],
\Bc_i^\T \Bx = \Bd_i, i \in [1,p]
} \\
&=
\setlr{ \Bx | A \Bx \le \Bb, C \Bx = d },
\end{aligned}
\end{equation}

where the final inequality and equality are component wise.

Proving \( \mathcal{P} \) is convex:

  • Pick \(\Bx_1 \in \mathcal{P}\), \(\Bx_2 \in \mathcal{P} \)
  • Pick any \(\theta \in [0,1]\)
  • Test \( \theta \Bx_1 + (1-\theta) \Bx_2 \). Is it in \(\mathcal{P}\)?

\begin{equation}\label{eqn:convexOptimizationLecture4:140}
\begin{aligned}
A \lr{ \theta \Bx_1 + (1-\theta) \Bx_2 }
&=
\theta A \Bx_1 + (1-\theta) A \Bx_2 \\
&\le
\theta \Bb + (1-\theta) \Bb \\
&=
\Bb.
\end{aligned}
\end{equation}

Balls

Euclidean ball for \( \Bx_c \in \mathbb{R}^n, r \in \mathbb{R} \)

\begin{equation}\label{eqn:convexOptimizationLecture4:160}
\mathcal{B}(\Bx_c, r)
= \setlr{ \Bx | \Norm{\Bx – \Bx_c}_2 \le r },
\end{equation}

or
\begin{equation}\label{eqn:convexOptimizationLecture4:180}
\mathcal{B}(\Bx_c, r)
= \setlr{ \Bx | \lr{\Bx – \Bx_c}^\T \lr{\Bx – \Bx_c} \le r^2 }.
\end{equation}

Let \( \Bx_1, \Bx_2 \), \(\theta \in [0,1]\)

\begin{equation}\label{eqn:convexOptimizationLecture4:200}
\begin{aligned}
\Norm{ \theta \Bx_1 + (1-\theta) \Bx_2 – \Bx_c }_2
&=
\Norm{ \theta (\Bx_1 – \Bx_c) + (1-\theta) (\Bx_2 – \Bx_c) }_2 \\
&\le
\Norm{ \theta (\Bx_1 – \Bx_c)}_2 + \Norm{(1-\theta) (\Bx_2 – \Bx_c) }_2 \\
&=
\Abs{\theta} \Norm{ \Bx_1 – \Bx_c}_2 + \Abs{1 -\theta} \Norm{ \Bx_2 – \Bx_c }_2 \\
&=
\theta \Norm{ \Bx_1 – \Bx_c}_2 + \lr{1 -\theta} \Norm{ \Bx_2 – \Bx_c }_2 \\
&\le
\theta r + (1 – \theta) r \\
&= r
\end{aligned}
\end{equation}

Ellipse

\begin{equation}\label{eqn:convexOptimizationLecture4:220}
\mathcal{E}(\Bx_c, P)
=
\setlr{ \Bx | (\Bx – \Bx_c)^\T P^{-1} (\Bx – \Bx_c) \le 1 },
\end{equation}

where \( P \in S^n_{++} \).

  • Euclidean ball is an ellipse with \( P = I r^2 \)
  • Ellipse is image of Euclidean ball \( \mathcal{B}(0,1) \) under affine mapping.

 

fig. 5. Circle and ellipse.

Given

\begin{equation}\label{eqn:convexOptimizationLecture4:240}
F(\Bu) = P^{1/2} \Bu + \Bx_c
\end{equation}

\begin{equation}\label{eqn:convexOptimizationLecture4:260}
\begin{aligned}
\setlr{ F(\Bu) | \Norm{\Bu}_2 \le r }
&=
\setlr{ P^{1/2} \Bu + \Bx_c | \Bu^\T \Bu \le r^2 } \\
&=
\setlr{ \Bx | \Bx = P^{1/2} \Bu + \Bx_c, \Bu^\T \Bu \le r^2 } \\
&=
\setlr{ \Bx | \Bu = P^{-1/2} (\Bx – \Bx_c), \Bu^\T \Bu \le r^2 } \\
&=
\setlr{ \Bx | (\Bx – \Bx_c)^\T P^{-1} (\Bx – \Bx_c) \le r^2 }
\end{aligned}
\end{equation}

Geometry of an ellipse

Decomposition of positive definite matrix \( P \in S^n_{++} \subset S^n \) is:

\begin{equation}\label{eqn:convexOptimizationLecture4:280}
\begin{aligned}
P &= Q \textrm{diag}(\lambda_i) Q^\T \\
Q^\T Q &= 1
\end{aligned},
\end{equation}

where \( \lambda_i \in \mathbb{R}\), and \(\lambda_i > 0 \). The ellipse is defined by

\begin{equation}\label{eqn:convexOptimizationLecture4:300}
(\Bx – \Bx_c)^\T Q \textrm{diag}(1/\lambda_i) (\Bx – \Bx_c) Q \le r^2
\end{equation}

The term \( (\Bx – \Bx_c)^\T Q \) projects \( \Bx – \Bx_c \) onto the columns of \( Q \). Those columns are perpendicular since \( Q \) is an orthogonal matrix. Let

\begin{equation}\label{eqn:convexOptimizationLecture4:320}
\tilde{\Bx} = Q^\T (\Bx – \Bx_c),
\end{equation}

this shifts the origin around \( \Bx_c \) and \( Q \) rotates into a new coordinate system. The ellipse is therefore

\begin{equation}\label{eqn:convexOptimizationLecture4:340}
\tilde{\Bx}^\T
\begin{bmatrix}
\inv{\lambda_1} & & & \\
&\inv{\lambda_2} & & \\
& \ddots & \\
& & & \inv{\lambda_n}
\end{bmatrix}
\tilde{\Bx}
=
\sum_{i = 1}^n \frac{\tilde{x}_i^2}{\lambda_i} \le 1.
\end{equation}

An example is sketched for \( \lambda_1 > \lambda_2 \) below.

 

Ellipse with \( \lambda_1 > \lambda_2 \).

  • \( \lambda_i \) tells us length of the semi-major axis.
  • Larger \( \lambda_i \) means \( \tilde{x}_i^2 \) can be bigger and still satisfy constraint \( \le 1 \).
  • Volume of ellipse if proportional to \( \sqrt{ \det P } = \sqrt{ \prod_{i = 1}^n \lambda_i } \).
  • When any \( \lambda_i \rightarrow 0 \) a dimension is lost and the volume goes to zero. That removes the invertibility required.

Ellipses will be seen a lot in this course, since we are interested in “bowl” like geometries (and the ellipse is the image of a Euclidean ball).

Norm ball.

The norm ball

\begin{equation}\label{eqn:convexOptimizationLecture4:360}
\mathcal{B} = \setlr{ \Bx | \Norm{\Bx} \le 1 },
\end{equation}

is a convex set for all norms. Proof:

Take any \( \Bx, \By \in \mathcal{B} \)

\begin{equation}\label{eqn:convexOptimizationLecture4:380}
\Norm{ \theta \Bx + (1 – \theta) \By }
\le
\Abs{\theta} \Norm{ \Bx } + \Abs{1 – \theta} \Norm{ \By }
=
\theta \Norm{ \Bx } + \lr{1 – \theta} \Norm{ \By }
\lr
\theta + \lr{1 – \theta}
=
1.
\end{equation}

This is true for any p-norm \( 1 \le p \), \( \Norm{\Bx}_p = \lr{ \sum_{i = 1}^n \Abs{x_i}^p }^{1/p} \).

 

Norm ball.

The shape of a \( p < 1 \) norm unit ball is sketched below (lines connecting points in such a region can exit the region).

 

Cones

Recall that \( C \) is a cone if \( \forall \Bx \in C, \theta \ge 0, \theta \Bx \in C \).

Impt cone of PSD matrices

\begin{equation}\label{eqn:convexOptimizationLecture4:400}
\begin{aligned}
S^n &= \setlr{ X \in \mathbb{R}^{n \times n} | X = X^\T } \\
S^n_{+} &= \setlr{ X \in S^n | \Bv^\T X \Bv \ge 0, \quad \forall v \in \mathbb{R}^n } \\
S^n_{++} &= \setlr{ X \in S^n_{+} | \Bv^\T X \Bv > 0, \quad \forall v \in \mathbb{R}^n } \\
\end{aligned}
\end{equation}

These have respectively

  • \( \lambda_i \in \mathbb{R} \)
  • \( \lambda_i \in \mathbb{R}_{+} \)
  • \( \lambda_i \in \mathbb{R}_{++} \)

\( S^n_{+} \) is a cone if:

\( X \in S^n_{+}\), then \( \theta X \in S^n_{+}, \quad \forall \theta \ge 0 \)

\begin{equation}\label{eqn:convexOptimizationLecture4:420}
\Bv^\T (\theta X) \Bv
= \theta \Bv^\T \Bv
\ge 0,
\end{equation}

since \( \theta \ge 0 \) and because \( X \in S^n_{+} \).

Shorthand:

\begin{equation}\label{eqn:convexOptimizationLecture4:440}
\begin{aligned}
X &\in S^n_{+} \Rightarrow X \succeq 0
X &\in S^n_{++} \Rightarrow X \succ 0.
\end{aligned}
\end{equation}

Further \( S^n_{+} \) is a convex cone.

Let \( A \in S^n_{+} \), \( B \in S^n_{+} \), \( \theta_1, \theta_2 \ge 0, \theta_1 + \theta_2 = 1 \), or \( \theta_2 = 1 – \theta_1 \).

Show that \( \theta_1 A + \theta_2 B \in S^n_{+} \) :

\begin{equation}\label{eqn:convexOptimizationLecture4:460}
\Bv^\T \lr{ \theta_1 A + \theta_2 B } \Bv
=
\theta_1 \Bv^\T A \Bv
+\theta_2 \Bv^\T B \Bv
\ge 0,
\end{equation}

since \( \theta_1 \ge 0, \theta_2 \ge 0, \Bv^\T A \Bv \ge 0, \Bv^\T B \Bv \ge 0 \).

 

fig. 8. Cone.

Inequalities:

Start with a proper cone \( K \subseteq \mathbb{R}^n \)

  • closed, convex
  • non-empty interior (“solid”)
  • “pointed” (contains no lines)

The \( K \) defines a generalized inequality in \R{n} defined as “\(\le_K\)”

Interpreting

\begin{equation}\label{eqn:convexOptimizationLecture4:480}
\begin{aligned}
\Bx \le_K \By &\leftrightarrow \By – \Bx \in K
\Bx \end{aligned}
\end{equation}

Why pointed? Want if \( \Bx \le_K \By \) and \( \By \le_K \Bx \) with this \( K \) is a half space.

Example:1: \( K = \mathbb{R}^n_{+}, \Bx \in \mathbb{R}^n, \By \in \mathbb{R}^n \)

 

fig. 12. K is non-negative “orthant”

\begin{equation}\label{eqn:convexOptimizationLecture4:500}
\Bx \le_K \By \Rightarrow \By – \Bx \in K
\end{equation}

say:

\begin{equation}\label{eqn:convexOptimizationLecture4:520}
\begin{bmatrix}
y_1 – x_1
y_2 – x_2
\end{bmatrix}
\in R^2_{+}
\end{equation}

Also:

\begin{equation}\label{eqn:convexOptimizationLecture4:540}
K = R^1_{+}
\end{equation}

(pointed, since it contains no rays)

\begin{equation}\label{eqn:convexOptimizationLecture4:560}
\Bx \le_K \By ,
\end{equation}

with respect to \( K = \mathbb{R}^n_{+} \) means that \( x_i \le y_i \) for all \( i \in [1,n]\).

Example:2: For \( K = PSD \subseteq S^n \),

\begin{equation}\label{eqn:convexOptimizationLecture4:580}
\Bx \le_K \By ,
\end{equation}

means that

\begin{equation}\label{eqn:convexOptimizationLecture4:600}
\By – \Bx \in K = S^n_{+}.
\end{equation}

  • Difference \( \By – \Bx \) is always in \( S \)
  • check if in \( K \) by checking if all eigenvalues \( \ge 0 \).
  • \( S^n_{++} \) is the interior of \( S^n_{+} \).

Interpretation:

\begin{equation}\label{eqn:convexOptimizationLecture4:620}
\begin{aligned}
\Bx \le_K \By &\leftrightarrow \By – \Bx \in K \\
\Bx \end{aligned}
\end{equation}

We’ll use these with vectors and matrices so often the \( K \) subscript will often be dropped, writing instead (for vectors)

\begin{equation}\label{eqn:convexOptimizationLecture4:640}
\begin{aligned}
\Bx \le \By &\leftrightarrow \By – \Bx \in \mathbb{R}^n_{+} \\
\Bx < \By &\leftrightarrow \By – \Bx \in \textrm{int} \mathbb{R}^n_{++}
\end{aligned}
\end{equation}

and for matrices

\begin{equation}\label{eqn:convexOptimizationLecture4:660}
\begin{aligned}
\Bx \le \By &\leftrightarrow \By – \Bx \in S^n_{+} \\
\Bx < \By &\leftrightarrow \By – \Bx \in \textrm{int} S^n_{++}.
\end{aligned}
\end{equation}

Intersection

Take the intersection of (perhaps infinitely many) sets \( S_\alpha \):

If \( S_\alpha \) is (affine,convex, conic) for all \( \alpha \in A \) then

\begin{equation}\label{eqn:convexOptimizationLecture4:680}
\cap_\alpha S_\alpha
\end{equation}

is (affine,convex, conic). To prove in homework:

\begin{equation}\label{eqn:convexOptimizationLecture4:700}
\mathcal{P} = \setlr{ \Bx | \Ba_i^\T \Bx \le \Bb_i, \Bc_j^\T \Bx = \Bd_j, \quad \forall i \cdots j }
\end{equation}

This is convex since the intersection of a bunch of hyperplane and half space constraints.

  1. If \( S \subseteq \mathbb{R}^n \) is convex then\begin{equation}\label{eqn:convexOptimizationLecture4:720}
    F(S) = \setlr{ F(\Bx) | \Bx \in S }
    \end{equation}is convex.
  2. If \( S \subseteq \mathbb{R}^m \) then\begin{equation}\label{eqn:convexOptimizationLecture4:740}
    F^{-1}(S) = \setlr{ \Bx | F(\Bx) \in S }
    \end{equation}is convex. Such a mapping is sketched in fig. 14.

 

fig. 14. Mapping functions of sets.

References

[1] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.