text:
\begin{document}

\centerline{}
\begin{frontmatter}

\selectlanguage{english}
\title{Global geometry of $T^2$--symmetric spacetimes
\\
with weak regularity}

\selectlanguage{english}
\author[authorlabel1]{Philippe G. LeFloch} and
\ead{pgLeFloch@gmail.com}
\author[authorlabel2]{Jacques Smulevici}
\ead{jacques.smulevici@aei.mpg.de}

\address[authorlabel1]{Laboratoire Jacques-Louis Lions \& Centre National de la Recherche Scientifique,
Universit\'e Pierre et Marie Curie (Paris 6), 4 Place Jussieu, 75252 Paris, France. Blog: philippelefloch.wordpress.com}
\address[authorlabel2]{Max-Planck-Institut f\"ur Gravitationsphysik,
Albert-Einstein-Institut, Am M\"uhlenberg 1, 14476 Potsdam, Germany.}

\medskip
\begin{center}
{\small Received June 15, 2010. Accepted on September 9, 2010.\\

Presented by Yvonne Choquet-Bruhat}
\end{center}

\begin{abstract}
\selectlanguage{english}

We define the class of weakly regular spacetimes with $T^2$--symmetry,
and investigate their global geometrical structure. We formulate
the initial value problem for the Einstein vacuum equations with weak regularity, and
establish the existence
of a global foliation by the level sets of the area $R$ of the orbits of symmetry,
so that each leaf can be regarded as an initial hypersurface.
Except for the flat Kasner spacetimes which are known explicitly, $R$ takes all positive values.
Our weak regularity assumptions only require that the gradient of $R$ is continuous
while the metric coefficients belong to the Sobolev space $H^1$ (or have even less regularity).

\vskip 0.5\baselineskip

\selectlanguage{francais}

\noindent{\bf R\'esum\'e} \vskip 0.5\baselineskip \noindent
{\bf G\'eom\'etrie globale des espaces-temps $T^2$--sym\'etriques de faible r\'egularit\'e. }

Nous dfinissons la classe des espaces-temps  symtrie $T^2$ de faible r\'egularit\'e,
et nous tudions leur gomtrie globale. Nous formulons le problme de donnes initiales pour les quations
d'Einstein sous une faible rgularit.
Nous tablissons l'existence d'un feuilletage global par les surfaces de niveau de la fonction d'aire $R$
des surfaces de symmtrie, de sorte que chaque feuille induit une hypersurface initiale.
A l'exception des espaces-temps plats de Kasner (connus explicitement),
la fonction $R$ prend toutes valeurs positives.
Nos hypothses imposent seulement que le gradient de $R$ est continu
et que les coefficients mtriques sont dans l'espace de Sobolev $H^1$ (ou sont moins rguliers).

\end{abstract}
\end{frontmatter}

\selectlanguage{english}

\section{Introduction}
\label{intro}

We are interested in spacetimes satisfying the Einstein vacuum equations and
we provide a description of the {\sl global geometry} of the development
of an initial data set, having only {\sl weak regularity} but enjoying certain symmetry properties.
We consider a manifold that is diffeomorphic to the torus $T^3$
and initial data that are invariant under an action of the Lie group $T^2$.
This requirement characterizes the so-called {\sl $T^2$--symmetric spacetimes on $T^3$}.
A large literature is available on such spacetimes when sufficiently high regularity is imposed;
cf.~Moncrief \cite{Moncrief}, Chru\'sciel \cite{Chrusciel},
Berger, Chru\'sciel, Isenberg, and Moncrief \cite{BergerChruscielIsenbergMoncrief},
and Isenberg and Weaver \cite{IsenbergWeaver} and, for further references, \cite{Smulevici2}.

The present Note is motivated by recent work by
LeFloch and Stewart \cite{LeFlochStewart,LeFlochStewart2} and LeFloch and Rendall \cite{LeFlochRendall},
who treated Gowdy--symmetric matter spacetimes described by the Einstein-Euler equations.
It was recognized that, due to the formation of shock waves in the fluid and by virtue of the
Einstein equations, only weak regularity on the geometry should be allowed.

Here, we carry out this strategy further,
and encompass (vacuum) spacetimes under less restrictive regularity and symmetry conditions.
Importantly, we present a fully geometric framework within a class of weakly regular spacetimes
and precisely identify the weak regularity conditions allowing us to, both, establish the existence of such spacetimes and tackle the analysis of their global geometric structure.

Even in the smooth class, there remain challenging open problems for these spacetimes,
such as the question of geodesic completeness in the expanding direction
or the structure of singularities in the contracting direction,
and we believe that the new framework and estimates developed in the present work
will be useful to tackle some of these issues.

The initial value problem in general relativity (in the vacuum case) is formulated as follows.
An initial data set for the vacuum Einstein equations is a triple $(\Sigma,h,K)$ such that
$(\Sigma,h)$ is a Riemannian $3$-manifold and
$K$ is a symmetric $2$-tensor field on $\Sigma$,
satisfying the so-called Einstein's constraint equations.
A solution to the initial value problem  with initial data $(\Sigma,h,K)$
is a $(3+1)$-dimensional Lorentzian manifold $(\Mcal,g)$ satisfying the vacuum Einstein equations
(that is,
the Ricci flat condition $\mbox{Ric}=0$),
together with an embedding $\phi: \Sigma \to \Mcal$ such that $\phi(\Sigma)$ is a Cauchy hypersurface of $(\Mcal,g)$
and the pull-back of its first and second fundamental forms coincides with $h$ and $K$, respectively.

Recall that the existence of a unique (up to diffeomorphism) maximal globally hyperbolic
development $(\Mcal,g)$ was established in pioneering work by
Choquet-Bruhat and Geroch \cite{ChoquetBruhat1952,ChoquetBruhatGeroch}
(reviewed in \cite{ChoquetBruhat2009} together with extensive recent material).
The optimal existence result as far as the regularity of the initial data is concerned
is currently given in Klainerman and Rodnianski \cite{KlainermanRodnianski} in the Sobolev space $H^{2+\eps}$ (with $\eps>0$).

\section{Statement of the main result}

By restricting attention to the class of $T^2$--symmetric spacetimes,
our regularity assumptions will go far below the regularity
covered in previous works.
We assume here that the area $R$ of the orbits of $T^2$--symmetry is a $C^1$ function.

Introducing a frame of commuting vector fields $(T,\Theta,X,Y)$ where $X,Y$ are Killing fields,
the remaining components of the metric belong to the Sobolev space $H^1$
on every spacelike slice of a foliation,
except for the cross terms between the Killing fields $X,Y$ and the vector field $\Theta$
which have lower regularity.  (See Section~3, below.)

Importantly, {\sl not all} Christoffel symbols and curvature components make sense as distributions, but
only those that are relevant to formulate the Einstein equations in a weak sense.
To do otherwise, additional regularity would be necessary, as recognized in \cite{LeFlochMardare}.

Under these regularity conditions, our main result
establishes the existence of a weakly regular development,
and provides detailed information about its global geometry.
We refer to the next section and \cite{LS} for the precise terminology used in the following theorem.

\begin{theorem}
\label{theorem61}

\begin{itemize}

\item If $(\Sigma, h, K)$ is a weakly regular $T^2$--symmetric triple,
then the Einstein constraint equations (suitably reformulated) make sense as equality between distributions.
Similarly,
if $(\Mcal,g)$ is a weakly regular $T^2$--symmetric Lorentzian manifold,
then the Einstein equations (suitably reformulated) make sense as equality between distributions.

\item For all weakly regular $T^2$--symmetric initial data set $(\Sigma,h,K)$
with topology $T^3$ and constant area function $R$,
there exists a weakly regular vacuum spacetime with $T^2$--symmetry on $T^3$, $(\Mcal,g)$, which is a development of $(\Sigma, h, K)$ and admits a global foliation by the level sets of the area
$R \in (R_*,\infty)$ (for some $R_* \geq 0$).
Moreover, unless $(\Mcal,g)$ is a flat Kasner spacetime, one has $R_* = 0$.

\end{itemize}

\end{theorem}

The compactness arguments developed in \cite{LS} for the existence proof
are very different from the classical techniques used in the high regularity
case~\cite{Moncrief,BergerChruscielIsenbergMoncrief}. In the rest of this Note, we discuss in further detail the class of initial data and present our new
geometric formulation which is an essential contribution of \cite{LS}.

\section{Weakly regular $T^2$--symmetric manifolds}

While all topological manifolds under consideration are of class $C^\infty$,
the metric structures of interest here have low regularity.
For instance, the Lie derivative $\Lcal_Z h$ of a measurable and locally integrable $2$-tensor
$h$ is defined in the distribution sense, for any $C^1$ vector fields $X,T,Z$, by
\be
\label{284}
(\Lcal_X h) (T,Z) := X(h(T,Z)) - h(\Lcal_X T,Z) - h(T, \Lcal_X Z),
\ee
in which the last two terms are classically defined as locally integrable functions,
but the first one is defined in the distributional sense, only.

\begin{e-definition}
\label{def21}
A {\bf weakly regular $T^2$--symmetric Riemannian manifold} is a compact $C^\infty$ manifold $\Sigma$
endowed with a tensor field $h$ which enjoys the following regularity and symmetry properties:

\begin{enumerate}

\item {\bf Riemannian structure.} The field $h$ is a Riemannian metric with components in $L^\infty(\Sigma)$,
and the associated volume form is continuous.

\item {\bf Symmetry property.} On the Riemannian manifold $(\Sigma,h)$, there exists an action of the Lie group $T^2$
generated
by two (linearly independent, commuting) Killing fields $X,Y$ of class $C^\infty$ (with closed orbits),
satisfying in particular
$\Lcal_X h =0$ and $\Lcal_Y h = 0$
understood in the distributional sense (\ref{284}).

\item {\bf Regularity of the metric on the orbits.} The functions $h(X,X)$, $h(X,Y)$, and $h(Y,Y)$
belong to the Sobolev space $H^{1}(\Sigma;h)$.

\item {\bf Regularity of the area function.}
The orbit area function
\be
\label{ass:rconstant}
R^2 := h(X,X) \, h(Y,Y) - h(X,Y)^2
\ee
(which then lies in $W^{1,1}(\Sigma;h)$) is required to belong to $C^1(\Sigma)$.

\item {\bf Regularity of the metric on the orthogonal of the orbits.}
There exists a {\rm smooth} vector field $\Theta$ defined on $\Sigma$ such that $(\Theta,X,Y)$ form a basis of commuting vector fields and  the vector field
\be
\label{395}
Z := \Theta + a \, X + b \, Y, \qquad Z \in \big\{ X,Y \big\}^\perp, \qquad \Lcal_X Z = \Lcal_Y Z = 0
\ee
implies the regularity $h(Z,Z) \in H^1(\Sigma;h)$.

\end{enumerate}
\end{e-definition}

We refer to such a triple $(X,Y,Z)$ as an {\sl adapted frame} on $\Sigma$. We emphasize that no regularity is required on the derivatives of the ``cross-terms'' $h(X,\Theta)$ and $h(Y,\Theta)$.
We also need to consider the second fundamental form of the initial slice.

\begin{e-definition}
\label{def:t2tri}
A {\bf weakly regular $T^2$--symmetric triple} $(\Sigma,h,K)$
is a weakly regular $T^2$--symmetric Riemannian manifold $(\Sigma,h)$ with adapted frame $(X,Y,Z)$,
satisfying the following conditions:
\begin{enumerate}

\item {\bf Integrability.}
The field $K$ is a symmetric $2$-tensor field on $\Sigma$ such that its components in the basis $(X,Y,Z)$ lies in $L^2(\Sigma)$.

\item {\bf Symmetry property.}
Moreover, $K$ is invariant under the action of the Lie group $T^2$ generated by $(X,Y)$, that is,
$\Lcal_X K = \Lcal_Y K = 0$
understood in the sense of distributions (\ref{284}).

\item {\bf Additional regularity} (associated with the time derivative of the area function):
$$
\Trace^{(2)} (K) := h(X,X) \, K(X,X) + 2 h(X,Y) \, K(X,Y) + h(Y,Y) \, K(Y,Y) \in C(\Sigma).
$$

\end{enumerate}
\end{e-definition}

Our notion of initial data set follows the above two definitions, as we define the curvature of the manifold and impose the constraint equations in the distribution sense.
Such a statement requires to take into account our symmetry assumption in order for the curvature terms to
make sense as distributions.

\section*{\vskip-.9cm Acknowledgments}

\vskip-.4cm The first author (PLF) was partially supported by
the Agence Nationale de la Recherche (ANR) through the grant 06-2-134423 entitled
``Mathematical Methods in General Relativity'' (Math-GR).
The second author (JS) thanks the Albert Einstein Institute for financial support.
 This work was done when the second author (JS) was visiting the Laboratoire Jacques-Louis Lions
 with
 the support of the ANR.

config: arxiv


TITLE: Tower diagram - logic expression? (queen problem)
QUESTION [1 upvotes]: I have given a square which consists of $n \times n$ fields.
I must formulate logical expressions which say:
1) In every row there is $0$ or $1$ tower.
2) In every column there is $0$ or $1$ tower.
For example like this:
-------
|T| | |
-------
| | |T|
-------
| |T| |
-------

I know how to formulate (1) for, say, $3 \times 3$ (let $A_{i,j}$ be true if there is a tower on the field):
$(A_{1,1} \land \lnot A_{1,2} \land \lnot A_{1,3}) \lor$
$(\lnot A_{1,1} \land A_{1,2} \land \lnot A_{1,3}) \lor$
$(\lnot A_{1,1} \land \lnot A_{1,2} \land  A_{1,3}) $ (Row 1)
$(A_{2,1} \land \lnot A_{2,2} \land \lnot A_{2,3}) \lor$
$(\lnot A_{2,1} \land A_{2,2} \land \lnot A_{2,3}) \lor$
$(\lnot A_{2,1} \land \lnot A_{2,2} \land  A_{2,3}) $ (Row 2)
$(A_{3,1} \land \lnot A_{3,2} \land \lnot A_{3,3}) \lor$
$(\lnot A_{3,1} \land A_{3,2} \land \lnot A_{3,3}) \lor$
$(\lnot A_{3,1} \land \lnot A_{3,2} \land  A_{3,3}) $ (Row 3)
2) Works very similar...but how can I say that in general?

REPLY [1 votes]: This is a partial solution, which satisfies conditions 1 and 2 only in part, i.e. the logic expression says that there is at least one tower and at least one absence of a tower in each row and column. I hope this will give you enough of an idea, in terms of approach, to extend it to the at most 1 tower case.
However, I suspect that once the conditions at least one tower and at least one absence of a tower are satisfied by all rows and columns, you're left with one, and only one tower per each row and column, i.e. $n$ towers on a $n\times n$ grid. This seems right since that's the solution to the Queens Problem.
Conditions 1 and 2 can be simplified with an expression that is logically equivalent to the disjunctions of conjuncts that you gave for the $3 \times3$ case. Observe that for each row, conditions 1 and 2 are satisfied if we say that (i) the disjunction of all row elements is true, and (ii) the conjunction of all the row elements is false (or equivalently for (ii), the disjunction of all negated row elements is true, which means that at least one negated row element is true).
This is so because by definition of disjunction (i) forces it to be the case that there's at least one "tower" (using your definition) in the row, i.e. in row $i$, $A_{i,j}$ is true for at least one $j$, and (ii) puts a restriction by ensuring that $A_{i,k}$ is false for at least one $k$ (obviously $j\not=k$).
Note that  (ii) could also be expressed as a disjunction of negated statements, i.e. $\lnot A_{i,k}$ is true for at least one $k$ (this is what I give in the example below).
EXAMPLE: For the $3\times3$ case, each row $i$ must satisfy the following condition:
$$\left ( \underset{j=1}{\overset{3}{\LARGE\lor}}A_{i,j}\right ) \land \left(\underset{j=1}{\overset{3}{\LARGE\lor}}\lnot A_{i,j}\right )$$
And each column $j$ must satisfy the following condition:
$$\left ( \underset{i=1}{\overset{3}{\LARGE\lor}}A_{i,j}\right ) \land \left(\underset{i=1}{\overset{3}{\LARGE\lor}}\lnot A_{i,j}\right )$$
The expression that satisfies 1 and 2 for rows in the general $n\times n$ case is the following (the conjunction at the front makes sure that conditions 1 and 2 hold for each row): $$ \underset{i=1}{\overset{n}{\LARGE\land}} \left[ \left ( \underset{j=1}{\overset{n}{\LARGE\lor}}A_{i,j}\right ) \land \left(\underset{j=1}{\overset{n}{\LARGE\lor}}\lnot A_{i,j}\right )\right]$$
For columns the expression in the general $n\times n$ case is going to be basically identical, with the difference that indices in the conjunction at the front ranges over all columns, and the inner expressions range, for each column, over all rows.
$$ \underset{j=1}{\overset{n}{\LARGE\land}} \left[ \left ( \underset{i=1}{\overset{n}{\LARGE\lor}}A_{i,j}\right ) \land \left(\underset{i=1}{\overset{n}{\LARGE\lor}}\lnot A_{i,j}\right )\right]$$
Putting the two together yields the necessary condition for the entire matrix/square/table:
$$\left [ \underset{i=1}{\overset{n}{\LARGE\land}} \left[ \left ( \underset{j=1}{\overset{n}{\LARGE\lor}}A_{i,j}\right ) \land \left(\underset{j=1}{\overset{n}{\LARGE\lor}}\lnot A_{i,j}\right )\right] \right ] \land \left [ \underset{j=1}{\overset{n}{\LARGE\land}} \left[ \left ( \underset{i=1}{\overset{n}{\LARGE\lor}}A_{i,j}\right ) \land \left(\underset{i=1}{\overset{n}{\LARGE\lor}}\lnot A_{i,j}\right )\right] \right ]$$
Although I suspect that a FOL expression would be much simpler.


TITLE: Base for Fourier series in an interval.
QUESTION [1 upvotes]: INTRODUCTION:
Given the problem $\begin{cases} u_t-u_{xx}=0 & (x,t)\in(0,\pi)\times(0,+\infty) \\ u(x,0)=g(x)&x\in[0,\pi] \\ u_x(0,t)=u(\pi,t) & t>0 \end{cases}$ I was trying to find the solutions with the method of separetion of variables.
After some calculation I find that the solution, trowing the intial condition on the second line, should be $u_k=c_k\cos(\frac{2k+1}{2}x)e^{-(\frac{2k+2}{2})^2t}$ so to satisfy the initial condition a want to find $c_k$ to have a series that express $g(x)$,
I mean solve $\sum_{_{k>0}} c_k\cos(\frac{2k+1}{2}x)=g(x)$ in the interval $[0,\pi]$.
QUESTIONS:
(i) I know that $\{\cos(kx),\sin(kx)\}_k$ is a orthonormal base (respect to the $L^2[-\pi,\pi]$ scalar product) but what can I say about $\cos(\frac{2k+1}{2}x)$ or $\sin(\frac{2k+1}{2}x)$?
(ii) Is it real that $c_k=\frac{2}{\pi}\int g(x)\cos(\frac{2k+1}{2}x)dx$?
(iii) Is there a general rule to find from the standard base other bases?
Here i was thinking that in the theroy of vector spaces, in finite dimension, i know that all the "good" automorphisms are represented by orthogonal matrices, is there any similar thing in infinite dimension using linear operator?
If I miss some details I will add it, if I can, let me know.
Any suggestion, answer, hint.. would be greatful, thanks.

REPLY [1 votes]: (I)

You can calculate that $\{\cos(\frac{2k+1}{2}x)\}_{k=0}^{\infty}$ is orthogonal system on $L_2[0, \pi]$. This is orthogonal system of eigenfunctions of the Sturm–Liouville problem:
$$X''(x) + \lambda X(x) = 0, X'(0) = X(\pi) = 0.\quad\quad(1)$$
Any function $X$, which satisfy $X'(0) = X(\pi) = 0$, can be represented as $X(x) = \sum_{k=0}^{\infty} A_k \cos(\frac{2k+1}{2}x)$.
You can calculate that $\{\sin(\frac{2k+1}{2}x)\}_{k=0}^{\infty}$ is orthogonal system on $L_2[0, \pi]$. This is orthogonal system of eigenfunctions of the Sturm–Liouville problem:
$$X''(x) + \lambda X(x) = 0, X(0) = X'(\pi) = 0.\quad\quad(2)$$
Any function $X$, which satisfy $X(0) = X'(\pi) = 0$, can be represented as $X(x) = \sum_{k=0}^{\infty} A_k \sin(\frac{2k+1}{2}x)$.
These systems do not produce basis of all space $L_2[0, \pi]$, but they produce basis of vector space functions, which satisfy corresponding boundary conditions.

(II) Yes. Because you have $X_k(x) = \cos(\frac{2k+1}{2}x)$ and $T_n(t) = c_k e^{-(\frac{2k+2}{2})^2t}$. $u$ can be represented as $\sum_{k=0}^{\infty} X_k(x) T_n (t)$.
$u(x, 0) = \sum_{k=0}^{\infty} c_k X_k(x) = g(x)$ or $u(x, 0) = \sum_{k=0}^{\infty} c_k \cos(\frac{2k+1}{2}x) = g(x)$. So $c_k = \frac{\langle g, X_k \rangle}{\langle X_k, X_k \rangle}$, where $\langle a, b \rangle = \int_{0}^{\pi} a(x) b(x) dx$.
(III) System of functions $X_k$ can be obtained as eigenfunctions of Sturm–Liouville problem. In your case $u(x, t) = X(x) T(t)$. After substituting into equation $X(x) T'(t)  - X''(X) T(t) = 0$ or $\frac{T'(t)}{T(t)} = \frac{X''(x)}{X(x)} = -\lambda$. Now you have equations: $X''(x) + \lambda X(x) = 0$ and $T'(t) + \lambda T(t) = 0$. Using $u_x(0, t) = X'(0) T(t) = 0$ we get $X'(0) = 0$, and using $u(\pi, t) = X(\pi) T(t) = 0$, we get $X(\pi) = 0$. In these problems we do not need basis of all space, we need basis of functions that satisfy boundary conditions, and we find it as eigenfunctions of the Sturm–Liouville problem.


text:
We consider the problem $\min_{\mathbf{x} \in P} f(\mathbf{x})$, where $P \subseteq \mathbb{R}^n$ is a polytope with vertex set $\text{vert}(P)$, and $f: P \to \mathbb{R}$ is a smooth and strongly convex function. Smooth convex optimization problems over polytopes are an important class of problems that appear in many settings, such as low-rank matrix completion \cite{Grigas_2015}, structured supervised learning \cite{Jaggi2013,Bashiri_2017}, electrical flows over graphs \cite{lyons2005probability}, video co-localization in computer vision \cite{Joulin2014}, traffic assignment problems \cite{Networkflows1993}, and submodular function minimization \cite{Fujishige_2009}. First-order methods in convex optimization rely on movement in the best local direction for descent (e.g., negative gradient), and this is enough to obtain linear convergence for unconstrained optimization. In constrained settings however, the gradient may no longer be a feasible direction of descent, and \textcolor{teal}{traditionally} there are two broad classes of methods traditionally: projection-based methods  (i.e., move in \hme{the} direction of \hme{the} negative gradient, but project to ensure feasibility), and conditional gradient methods (i.e., move in feasible directions that approximate the gradient). Projection-based methods such as projected gradient descent or mirror descent \cite{Nemirovski1983} enjoy dimension independent linear rates of convergence (assuming no acceleration), \hme{e.g.},  $(1-\frac{\mu}{L})$ contraction in the objective per iteration (so that the number of iterations to get an $\epsilon$-accurate solution is $O(\frac{L}{\mu} \log \frac{1}{\epsilon})$), for $\mu$-strongly convex and $L$-smooth functions, but need to compute an expensive projection step (another constrained convex optimization) in (almost) every iteration. On the other hand, conditional gradient methods (such as the Frank-Wolfe algorithm \cite{FrankWolfe1956}) \hme{solely rely on solving} linear optimization (LO) problems in every iteration and the rates of convergence become dimension-dependent, e.g., the away-step Frank-Wolfe algorithm has a linear rate of $(1-\frac{\mu \delta^2}{LD^2})$, where $\delta$ is a polytope dependent geometric constant and $D$ is the diameter of the polytope \cite{Lacoste2015}.

The vanilla Conditional Gradient method (CG) or the Frank-Wolfe algorithm (FW) \cite{FrankWolfe1956,Levitin_1966} has received a lot of interest from the ML community mainly because of its iteration complexity, tractability and sparsity of iterates. In each iteration, the CG algorithm computes the {\it Frank-Wolfe vertex} $\mathbf{v}_t$ with respect to the current iterate and moves towards that vertex:
\begin{align}
    \mathbf{v}_t &= \argmin_{\mathbf{v} \in \text{vert}(P)} \innerprod{\nabla f (\mathbf{x}_t)}{\mathbf{v}},~~ \mathbf{x}_{t+1} = \mathbf{x}_t + \gamma_t (\mathbf{v}_t - \mathbf{x}_t), \quad \gamma_t\in[0,1].
\end{align}
CG's primary direction of descent is $\mathbf{v}_t - \mathbf{x}_t$ ($\bd_t^{\text{FW}}$ in Figure \ref{fig:proj}) and its step-size $\gamma_t$ can be selected, e.g., using line-search; this ensures feasibility of $\mathbf{x}_{t+1}$.
The FW algorithm however, can only guarantee a sub-linear rate of \hme{convergence} $O(1/t)$ for smooth and strongly convex optimization on a \hme{polytope} \cite{FrankWolfe1956,Jaggi2013}. Moreover, this \hme{convergence} rate is tight \cite{Canon_1968,lan_2013}. An active area of research, therefore, has been to find other descent directions that can enable linear convergence.

One reason for vanilla CG's $O(1/t)$ rate is the fact that the algorithm might zig-zag as it approaches the optimal face, slowing down progress \cite{Lacoste2015,Canon_1968}. The key idea for obtaining linear convergence was to use the so-called {\it away steps} that help push iterates to the optimal face:
\begin{align}
    \mathbf{a}_t &= \argmax_{{\mathbf{v}} \in \text{vert}(F)} \innerprod{\nabla f(\mathbf{x}_t)}{{\mathbf{v}}}, \text{ for } F \subseteq P, \label{activeset}\\
    \x_{t+1} &= \x_t + \gamma_t (\x_t-\mathbf{a}_t), \text{ where } \gamma_t \in \mathbb{R}_+ \text{ such that } \x_{t+1}\in P, \label{away}
\end{align}
thus, augmenting the potential directions of descent using directions of the form $\x_t -\mathbf{a}_t$, for some $\mathbf{a}_t \in F$, where the precise choice of $F$ in \eqref{activeset} has evolved in CG variants.

\begin{figure}[t]
    \centering
    \includegraphics[scale = 0.5]{proj-curve.png}
    \hspace{20 pt}
    \includegraphics[scale = 0.53]{zig-zag.png}
     \vspace{-4 pt}
    \caption{\small \textbf{Left:} Piecewise linearity of the parametric projections curve $g(\lambda) = \Pi_P(\mathbf{x}_t - \lambda \nabla f(\mathbf{x}_t))$ (yellow line). The end point is the FW vertex $\mathbf{v}_t$ and $\bd_t^{\text{FW}}$ is the FW direction. Note that $g(\lambda)$ does not change at the same speed as $\lambda$, e.g.,  $g(\lambda)=\mathbf{v}$ for each $\lambda$ such that $\x_t - \lambda \nabla f(\x_t) - \mathbf{v}  \in N_P(\mathbf{v})$ (purple normal cone). \textbf{Right:} Moving along the shadow might lead to arbitrarily small progress even once we reach the optimal face $F^* \ni \x^*$. On the contrary, the away-step FW does not leave $F^*$ after a polytope-dependent iteration \cite{Marcotte1986}.}
    \label{fig:proj}
\end{figure}

As early as 1986, Gu{\'e}lat and Marcotte showed that by adding away steps (with $F=$ minimal face of the current iterate\footnote{The minimal face $F$ with respect to $\mathbf{x}_t$ is a face of the polytope that contains $\x_t$ in its relative interior, i.e., all active constraints at $\x_t$ are tight.}) to vanilla CG, their algorithm has an asymptotic linear convergence rate \cite{Marcotte1986}.

In 2015, Lacoste-Julien and Jaggi \cite{Lacoste2015} showed linear convergence results for CG with away steps\footnote{To the best of our knowledge, Garber and Hazan \cite{Garber_2013} were the first to present a CG variant with global linear convergence for polytopes.} (over $F=$ \hme{convex hull of} the current active set, i.e., a specific convex decomposition of the current iterate). They also showed a linear rate \hme{of convergence} for CG with pairwise-steps (\hme{of the form} $\mathbf{v}_t - \mathbf{a}_t$), another direction of descent. In 2015, Freund et. al \cite{Grigas_2015} showed a $O(1/t)$ convergence for convex functions, with $F$ as the minimal face of the current iterate. In 2016, Garber and Meshi \cite{Garber_2016}
showed that pairwise-steps (over 0/1 polytopes) with respect to non-zero components of the gradient are enough for linear convergence, i.e., they also set $F$ to be the minimal face with respect to $\x_t$. In 2017, Bashiri and Zhang \cite{Bashiri_2017} generalized this result to show linear convergence for the same $F$ for general polytopes (however at the cost of two expensive oracles).

Other related work includes linear convergence for the conditional gradient method over strongly-convex domains with a lower bound on the norm of the optimum gradient \cite{Levitin_1966}, or when the FW-vertex is constrained to a ball around the iterate \cite{lan_2013,Garber_2016}, bringing in regularization-like ideas of mirror-descent variants \hme{to} CG. There has also been extensive work on mixing Frank-Wolfe and gradient descent steps \cite{Braun2018,combettes2020} or solving projections approximately using Frank-Wolfe steps \cite{Lan2017} (with the aim of better computational performance) while enjoying linear convergence \cite{lan_2016,Braun2018}. Our goal in this work is to put these CG variants in perspective and understand desired properties of feasible directions of descent. We summarize related work in Table \ref{summary}.

\textcolor{teal}{Although all these variants obtain linear convergence, their rates depend on polytope-dependent geometric, affine-variant constants (that can be arbitrarily small for non-polyhedral sets like the $\ell_2$-ball) such as the pyramidal width \cite{Lacoste2015}, vertex-facet distance \cite{Beck2017}, eccentricity of the polytope \cite{Lacoste2015} or sparsity-dependent constants \cite{Bashiri_2017}, which have been shown to be essentially equivalent\footnote{Eccentricity $= D/\delta$, where $D$ and $\delta$ are the diameter and pyramidal width of the domain respectively  \cite{Lacoste2015}.} \cite{Pena2015}. The iterates in \hme{CG algorithms} are (basically) affine-invariant, which is the reason why a dimension-dependent factor is unavoidable in the current arguments. Following our work, there have been recent results on extensions using procedures similar to our {\sc Trace-Opt} \hme{procedure} to avoid ``bad'' steps in  CG variants and accordingly obtain linear convergence rates that depend on a slope condition rather than geometric constants \cite{rinaldi2020unifying,rinaldi2020avoiding}.}

\begin{savenotes}
\begin{table}[!t]
\small
    \centering
    \begin{tabular}{|p{5.4 cm}|p{6.7 cm}|p{3.3 cm}|} \hline
         \centering \textbf{Paper} & \centering \textbf{Algorithm} & \textbf{Steps to get $\epsilon$-error} \\ \hline \hline
          \hme{Frank and Wolfe (1956) \cite{frank1956algorithm}} &\hme{ Vanilla FW with the uniform step-size rule $\gamma_t =\frac{2}{t+2}$.}  & \hme{$O\left(\frac{LD^2}{\epsilon}\right )$}  \\  \hline
         Dunn (1979) \cite{dunn1979rates} & Geometric analysis for vanilla CG. & $O\left(\frac{LD^2}{\epsilon}\right )$\\ \hline
         Gu{\'e}lat and Marcotte (1986) \cite{Marcotte1986} & Vanilla FW with $\x^*$ having distance $\Delta > 0$ from the boundary. & $O\left( \kappa \left(\frac{D}{\Delta}\right)^2\log \frac{1}{\epsilon}\right )$  \\  \hline
         Lan (2013) \cite{lan_2013} & Constraining FW vertex to a ball around the current iterate.  & $O\left( \kappa \log \frac{D\mu}{\epsilon}\right)$  \\  \hline
          Freund et. al (2015) \cite{Grigas_2015} & FW with in-face directions (promoting sparsity) as a generalization to away steps. & $O\left(\frac{LD^2}{\epsilon}\right )$  \\  \hline
         Lacoste-Julien and Jaggi (2015) \cite{Lacoste2015} & FW \& away steps (over current active set) for general polytopes (AFW \& PFW). & $O\left( \kappa \left(\frac{D}{\delta}\right)^2\log \frac{1}{\epsilon}\right )$  \\  \hline
         Garber and Hazan (2016) \cite{Garber_2013} & Constraining FW vertex to a ball around the current iterate with a focus on polytopes. & $O\left(\kappa n \rho \log \frac{1}{\epsilon}\right )$  \\  \hline
         Garber and Meshi (2016) \cite{Garber_2016} & Pairwise steps for structured 0/1 polytopes\footnote{These include: the path polytope of a graph (aka the unit flow polytope), the perfect matching polytope of a bipartite graph, and the base polyhedron of a matroid, for which we have efficient algorithms for linear optimization.} using best away vertex in minimal face of iterate (DICG). & $O\left({\kappa \|\x^*\|_0 D^2}\log \frac{1}{\epsilon}\right )$  \\  \hline
         Beck and Shtern (2017) \cite{Bashiri_2017} & FW \& away steps using best away vertex in current active set for specific non-strongly convex objective functions\footnote{They consider objective functions of the form $f(\x)\coloneqq g(\mathbf{E}\x) + \innerprod{\mathbf{b}}{\x}$, where $g$ is strongly convex and $\mathbf{E}$ is a general matrix, so that $f$ is not necessarily strongly convex, \hme{but is gradient dominated via the Hoffman bound.}}. & $O\left( Ln\left(\frac{D}{\Phi}\right)^2\log \frac{1}{\epsilon}\right )$ \\  \hline
             Bashiri and Zhang (2017) \cite{Bashiri_2017} & FW \& Away steps using best away vertex in \hme{the  minimal face of iterate}. & $O\left( n \kappa D^2 H_s \log \frac{1}{\epsilon}\right )$ \\  \hline
         Braun et. al (2018) \cite{Braun2018} & Lazy FW \& gradient descent steps over simplex formed by current active set. & $O\left( K \kappa \left(\frac{D}{\delta}\right)^2\log \frac{1}{\epsilon}\right )$ \\  \hline
          Combettes and Pokutta (2020) \cite{combettes2020} & FW with descent directions better aligned with the negative gradients. &  $O\left( \frac{\kappa}{\alpha^2 \omega} \log \frac{1}{\epsilon}\right )$ \\  \hline
          \textcolor{blue}{Rinaldi and Zeffiro (2020) \cite{rinaldi2020unifying,rinaldi2020avoiding}} & \textcolor{blue}{Use procedure called SSC that chains consecutive FW like descent steps}\footnote{\textcolor{blue}{Following our work, Rinaldi and Zeffiro \cite{rinaldi2020unifying,rinaldi2020avoiding} proposed the SSC procedure, which every iteration chains short first-order feasible descent steps (e.g. AFW steps as opposed to shadow steps) within a ball around the current iterate until sufficient progress is achieved. This could be viewed as an approximation of our \textsc{Trace-Opt} procedure.}}. &  {\textcolor{blue}{\footnotesize $O\left(\gamma \log^{-1}\frac{\tau^2 \kappa }{(1 + \tau)^2} \log \frac{1}{\epsilon}\right )$}} \\  \hline

           {\bf This paper} & Moving along the `shadow' of \hme{the negative} gradient ({\sc Shadow-Walk}). & $O\left({\kappa\beta}\log \frac{1}{\epsilon}\right)$  \\  \hline
        {\bf This paper} & Moving in the `shadow' of \hme{the negative} gradient with FW steps. ({\sc Shadow-CG}) & $O\left({\kappa(D^2+\beta)}\log \frac{1}{\epsilon}\right )$ \\  \hline
    \end{tabular}
    \caption{\small Summary of different descent techniques used in CG variants and their convergence rates. The factor $\kappa \coloneqq L/\mu$ is the condition number of the function and $D$ is the diameter of the domain. Also, $\delta$ is the pyramidal width, $\rho$ and $\Phi$ are notions of vertex-facet distance and $H_s$ is a sparsity-dependent geometric constant. Moreover, $K$ is a parameter for finding approximate FW vertices. The constants $\alpha$ and $\omega$ arise from the gradient alignment procedure. Further, $\tau$ is a directional slope constant and $\gamma$ is the number of iterations performed within SSC. Finally, $\beta$ is the number of breakpoints visited when walking along the shadow of the gradient (within {\sc Trace-Opt}), which depends on the number of facets of the polytope.}
    \label{summary}
    \vspace{-10 pt}
\end{table}
\end{savenotes}

A natural question at this point is why are these different descent directions useful and which of these are necessary for linear convergence. If one had oracle access to the ``best'' local direction of descent for constrained minimization, what would it be and is it enough to \hme{obtain} linear convergence (as in unconstrained optimization)? Moreover, can we avoid rates of convergence that are dependent on the geometry of the polytope? We partially answer these questions below.

\paragraph{Contributions.} We show that the ``best'' local feasible direction of descent, that gives the maximum function value decrease in the diminishing neighborhood of the current iterate $\mathbf{x}_t$, is the {\it directional derivative} $\mathbf{d}_{\mathbf{x}_t}^\Pi$ of the projection of the gradient, which we refer to as the \emph{shadow} of the gradient:  $$\mathbf{d}_{\mathbf{x}_t}^\Pi \coloneqq \lim_{\epsilon \downarrow 0} \frac{\Pi_P(\mathbf{x}_t - \epsilon \nabla f(\mathbf{x}_t)) - \mathbf{x}_t}{\epsilon},$$ where $\Pi_P(\y) = \argmin_{\x\in P}\|\x-\y\|^2$ is the Euclidean projection operator. Further, a continuous time dynamical system can be defined using infinitesimal movement in the shadow direction at the current point:
$\dot{X}(t) = \mathbf{d}_{X(t)}^\Pi,$ with $X(0) = \x_0 \in P$. We show that this ODE is equivalent to that of projected gradient descent (Theorem \ref{ode theorem}), and that it is non-trivial to discretize due to non-differentiability of the curve.

Second, we explore structural properties of shadow steps. For any $\mathbf{x} \in P$, we characterize the curve $g(\lambda) = \Pi_P(\mathbf{x} - \lambda \nabla f(\mathbf{x}))$ as a piecewise linear curve, where the breakpoints of the curve typically occur at points where there is a change in the normal cone (Theorem \ref{elephant}) and show how to compute this curve for all $\lambda\geq0$ (Theorem \ref{invariance}). Moreover, we show the following properties for descent directions:

\noindent
{\bf (i) Shadow Steps ($\bd_{\x_t}^\Pi$)}: These are the \emph{best normalized feasible directions} of descent (Lemma \ref{best local direction}), so that $\|\mathbf{d}_{\mathbf{x}_t} ^\Pi\| = 0$ if and only if $\x_t = \arg\min_{\x\in P}f(\x)$ (Lemma \ref{primal gap optimality}). Hence, $\|\mathbf{d}_{\mathbf{x}_t}^\Pi\|$ is a natural quantity to use for bounding primal gaps without any dependence on geometric constants like those used in other CG variants. We show that multiple shadow steps approximate a single projected gradient descent step (Theorem \ref{invariance}). The rate of linear convergence using shadow steps is dependent on the number of facets (independent of geometric constants but dimension dependent due to number of facets), and {\it{interpolate} smoothly} between projected gradient and conditional gradient methods (Theorem \ref{alg converg1}).

\noindent
{\bf (ii) FW Steps ($\mathbf{v}_t - \mathbf{x}_t$)}: Projected gradient steps provide a contraction in the objective independent of the geometric constants or facets of the polytope; they are also able to ``wrap'' around the polytope by taking unconstrained gradient steps and then projecting. Under mild technical conditions (uniqueness of $\mathbf{v}_t$), the Frank-Wolfe vertices are in fact the projection of an infinite descent in the negative gradient direction (Theorem \ref{FW limit}). This allows the CG methods to wrap around the polytope maximally, compared to PGD methods, thereby giving FW steps a new perspective.

\noindent
{\bf (iii) Away Steps ($\x_t - \mathbf{a}_t$)}: Shadow steps are the {\it best normalized away-direction} with steepest local descent
(Lemma \ref{best local direction}). Shadow steps are in general convex combinations of potential active vertices minus the current iterate (Lemma \ref{lemma away-shadow}) and therefore loose combinatorial properties such as dimension drop in active sets \cite{Bashiri_2017}. Shadow steps can bounce off faces (i.e. visit the same face multiple times - (see Figure \ref{fig:proj} (right) for an example) unlike away steps that use vertices and have a monotone decrease in dimension when they are consecutive.

\noindent
{\bf (vi) Pairwise Steps ($\mathbf{v}_t - \mathbf{a}_t$)}: The progress in CG variants is bounded crucially using the inner product of the descent direction with the negative gradient. In this sense, pairwise steps are simply the {{\it sum of the FW step and away directions}}, and a simple algorithm, the pairwise FW algorithm, that only uses these steps does converge linearly {(with geometric constants)} \cite{Lacoste2015,Bashiri_2017}. Moreover, for feasibility of the descent direction, one requires $\mathbf{a}_t$ to be in the active set of the current iterate (shown in \cite{Bashiri_2017}, and Lemma \ref{best away vertex}, Appendix \ref{sec: shadow-away}).

Armed with these structural properties, we consider a descent algorithm {\sc Shadow-Walk}: trace the projections curve by moving in the shadow or an in-face directional derivative with respect to a fixed iterate, until sufficient progress, then update the shadow based on the current iterate. Using properties of normal cones, we can show that once the projections curve at a fixed iterate leaves a face, it can never visit the face again (Theorem \ref{breakpoints}). We are thus able to break a single PGD step into multiple descent steps, and show linear convergence with rate dependent on the number of facets, but independent of geometric constants like the pyramidal width.

We combine these insights into a novel {\sc Shadow-CG} method which uses FW steps and shadow steps (both over the tangent cone and minimal face), while enjoying linear convergence. This method prioritizes FW steps that achieve maximal ``coarse'' progress in earlier iterations and shadow steps avoid zig-zagging in the latter iterations. Garber and Meshi \cite{Garber_2016} and Bashiri and Zhang \cite{Bashiri_2017} both compute the best away vertex in the minimal face containing the current iterate, whereas the shadow step recovers the best convex combination of such vertices aligned with the negative gradient. Therefore, these previously mentioned CG methods can {\it both} be viewed as approximations of {\sc Shadow-CG}. Moreover, Garber and Hazan \cite{Garber_2013} emulate a shadow computation by constraining the FW vertex to a ball around the current iterate. Therefore, their algorithm can be interpreted as an approximation of {\sc Shadow-Walk}. Finally, we propose a practical variant of {\sc Shadow-CG}, called {\sc Shadow-CG$^2$}, which reduces the number of shadow computations.

\paragraph{Outline.} We next review preliminaries in Section \ref{sec: prelims}. In Section \ref{sec:structure}, we derive theoretical properties of the piecewise-linear projections curve. Next, we derive properties of descent directions in Section \ref{sec:descentdirections} and present the continuous time dynamics for movement along the shadow and its discretization {\sc Shadow-Walk} in Section \ref{sec:appODE}. Finally, we propose {\sc Shadow-CG} and {\sc Shadow-CG$^2$} in Section \ref{sec:shadowCG} and provide computational experiments in Section \ref{sec: computations - main body}.


TITLE: Voltage Increase in a Circuit When Holding a Motor Still
QUESTION [0 upvotes]: My friend and I were trying out a circuit with 6 volts and found that when the motor was spinning slower, the voltage shown on an analog meter was greater. I vaguely guessed that this was caused by the position of the solenoid or wire in the motor, which affected EMF. Could someone please explain?

REPLY [0 votes]: When the motor rotates, the magnetic flux through the loop changes, resulting in an induced emf. Consistent with Lenz's law, this emf always acts to reduce the current in the coil (and is hence called the back emf).
The voltage available to supply current equals the difference between the supply voltage and back emf, that is: $$\varepsilon_{\text{available}} = \varepsilon - \varepsilon_{\text{back}}$$
Now, the back emf can be calculated by using Faraday's law:
$$\Phi_B = BA \text{ cos}\theta = BA \text{ cos } \omega t$$
$$\varepsilon_{\text{back}} = -N\frac{\text{d}\Phi_B}{\text{dt}} = N\omega BA \text{ sin } \omega t$$
Clearly $\varepsilon_{\text{back}}$ varies as $\omega \text{ sin } \omega t$ and hence decreases with a decrease in rotation rate ($\omega$). It then follows that $\varepsilon_{\text{available}} = \varepsilon - \varepsilon_{\text{back}}$ increases, just as you have measured.
You may also have everyday experiences with motors becoming warm when they are prevented from turning (for example when  operating a saw, if the blade becomes jammed it's temperature increases rapidly). This is because $\varepsilon_{\text{back}}$ becomes zero, and hence $\varepsilon_{\text{available}}$ becomes dangerously high.
Hope this helps.


TITLE: Planck's Law. It's $E=hf$ or $E=nhf$?
QUESTION [1 upvotes]: My textbook provides intuition of Planck's Quantum theory which is copied right next.

Max Planck proposed that emission or absorption of energy in a blackbody is discontinuous. It is absorbed or emitted in packets $hf$ or integral multiple of these packets $nhf$. Each packet is called Quantum.
Energy lost or gained is given by;
$E=hf$ where $f$ is the frequency of radiations.

I think the equation which is consistent with the definition above is E=nhf. If not, please explain which thing I am missing.
I have searched it on internet but explanation is given in terms of photon however I want to understand how does $E=hf$ is consistent with the brief description given in my book.

REPLY [1 votes]: The $E = hf$ is the energy of each packet or photon. So if $n$ photons are emitted, the total energy is $E = nhf$.


TITLE: Criteria for $p$ being a prime number.
QUESTION [1 upvotes]: I'm trying to prove the following problem:
$p$ is a prime iff for all $n\in \mathbb{Z}$ with $n\not \equiv 0\mod p$, we have $n^{p-1}\equiv 1 \mod p$.
The ($\Rightarrow$) direction is easy: we have that if $p$ is a prime, then $n\not \equiv 0\mod p$ is equivalent to $(n,p)=1$, and then we use the Fermat's little theorem.
I'm having trouble with the second direction: I've read that the Fermat's little theorem have a converse (Lehmer's theorem) that changes slightly the hypothesis but I don't if it's useful for my problem and how can I use it.

REPLY [0 votes]: Remark: $p$ is prime iff $(p,k)=1$ for all $k$ s.t  $1<k<p$.
Let $k$ s.t $1<k<p$, then by hypothesis we have $k^{p-1}\equiv 1$ mod $p$, hence there exists $m\in \Bbb Z$ s.t $k^{p-1}=1+mp$, so $k.k^{p-2}+(-m)p=1$, by Bezout theorem we get $(k,p)=1$.


TITLE: handshakes with everyone except 1
QUESTION [1 upvotes]: Jim and his wife Jeri attend a party with 4 other married couples. As they enter, Jim and Jeri shake hands with some of the guests, but not with each other. During the evening, each person except 1 shakes hands with some of the guests, but not with their spouse. After the party, Jim asks each guest how many people they shook hands with and got answers 0,1,2,3,4,5,6,7,8. How many people did Jeri shake hands with?

Because of the person with 8 handshakes, Jeri has at least 1 handshake, and this means that person with 0 handshakes is the 8 handshakes person's spouse. Person with 7 handshakes shook hands with person 8 and not with person 0 and his/her spouse, so person 7 too shook hands with Jeri. But now I'm stuck and everything's really confusing... How can I proceed?

REPLY [1 votes]: Let's say the couples are Alice and Art; Betty and Bob; Cathy and Carl; Diane and Dave; and Jeri and Jim.
Jeri didn't shake $8$ hands (else Jim would never have gotten a response of $0$).  So someone from another couple shook $8$ hands.  By symmetry it doesn't matter who.  Let's say Alice shook $8$ hands (every hand except Art's).
Now everyone except Art has $1$ shake, so Art must be $0$ shakes.
Jeri didn't shake $7$ hands (else Jim would not have gotten a response of $1$).  So someone else, say Betty shook $7$ hands.  Then the only person who could have shaken $1$ hand would be Bob.
Continuing like this: One of the other couples shook $6$ and $2$ hands; and one shook $5$ and $3$.
This means that Jeri shook $4$ hands.  (Incidentally, Jim also shook $4$ hands.)