TITLE: Can someone explain what this theorem and proof is saying
QUESTION [0 upvotes]: can someone please explain what the following theorem and proof is saying.  Thanks in advance

REPLY [1 votes]: Okay, I will first give an example, so you can visualize it. Let $A_1=\{1,2,3\}$, $A_2=\{2,3\}$, $A_3=\{3\}$ Therefore you have that $A_3 \subset A_2 \subset A_1$ and therefore $\bigcup_{i=1}^{3}A_i=A_1$ (since repetition of elements in a set, doesn't count for set cardinality, that is $\{3,3\}=\{3\}$)
If you do this with infinite sets, you will obtain the same result, since $A_1 \supset A_2 \supset A_3 \supset ...$ You have that $\bigcup_{i=1}^{\infty}A_i= A_1$ as shown in the proof.

REPLY [0 votes]: If you have a sequence of sets $\{A_n\}$ with $A_1\supseteq A_2\supseteq\ldots A_n\supseteq\ldots$.
Since, $A_n\subseteq A_1$ for all $n$, $\bigcup A_n\subseteq A_1$, then the other hand $A_1\subseteq\bigcup A_n$.


TITLE: Analogy of Liouville conformal mapping theorem with Mostow rigidity?
QUESTION [6 upvotes]: I often hear mention of two theorems, Mostow's rigidity theorem and Liouville's theorem on conformal mappings, which superficially sound similar:  they say that a set of geometric structures is, if nonempty, big in dimension 2, but small in dimension greater than 2.
(For Mostow's theorem, the set of structures in question is the set of hyperbolic metrics on a manifold; for Liouville's, it's the set of germs of flat metrics in a conformal equivalence class.)
I know that hyperbolic and conformal geometry are closely connected, at least in dimension 2.  I'm curious as to whether this analogy is hinting at one such connection.  Is there a "good reason" for this analogy?

REPLY [1 votes]: There is a connection in some way: if I remember right, you usually prove Mostow rigidity by looking at the hyperbolic space, which is the universal cover of your hyperbolic manifold, then you consider its boundary, which is the flat conformal sphere. Any isometry of the hyperbolic space induces a conformal transformation of its boundary, and vice-versa. But I don't think that you can derive Mostow rigidity from Liouville's conformal theorem.


TITLE: Given p, how do I use the Fitch system to prove $\neg \neg p$?
QUESTION [1 upvotes]: Given p, how do I use the Fitch system to prove $ \neg \neg p $?
I thought it should be as simple as assuming the negative, introducing a contradiction and eliminating the negation to end up with $\neg \neg p$, but I can't even get to step 3 with the Stanford Fitch system:
1) $p$ ---------------------premise
2) | $\neg p$ -----------------assumption
3) | $p \implies \neg p$ -------implication introduction 1,2
4) $\neg \neg p$ -----------------negation elimination 3
Obviously I am not quite getting it with the Fitch system, so any explanation would be greatly appreciated. It does seem trivially obvious that $p \Leftrightarrow \neg \neg p$ but I am having trouble expressing this with Fitch:
1) $p$ ---------------------premise
2) | $\neg p$ -----------------assumption
3) | $p$ -------------------reiteration 1
4) $\neg p \implies p$ ---------implication introduction 2,3
...from here tho, I can't figure out how to get $p \implies \neg p$ which I assume would which along with 4 I think would give me what I need to get $\neg \neg p$ from the negation elimination.

REPLY [2 votes]: $$\begin{align}
(1) & \quad P & \text{Assumption} \\
(2) & \quad \quad \lnot P & \text{Assumption} \\
(3) & \quad \lnot \lnot P & \text{Contradiction of } 1,2 \\
(4) & P \implies \lnot \lnot P & \implies-\text{Intro}
\end{align}$$


TITLE: How to determine smallest $M>0$ such that $(Au,v)≤M\Vert u \Vert \Vert v \Vert?$
QUESTION [1 upvotes]: Let $V=\mathbb R^2$ provided with the euclidean inner product and norm. Given a linear, bounded and strong positive operator
$$A=\begin{bmatrix}
1 & 1 \\
\frac{1}{2} & 3
\end{bmatrix}
$$ is it true that the greatest $\mu>0 $ such that $$(Au,u) ≥ \mu\Vert u\Vert^2$$ is the greatest eigenvalue of A as I assume?
Furthermore, how can I determine the smallest $M>0$ such that $$(Au,v)≤M\Vert u \Vert \Vert v \Vert?$$
I have the assumption to somehow involve the symmetric part $\frac{1}{2}(A+A^T)$ to show is as I have seen something similar before. Some help or hints would be much appreciated.

REPLY [1 votes]: As indicated in the comments below the answer, the $\mu$ in question will be the smallest eigenvalue of $B = (A + A^T)/2$.  One explanation is as follows:

For all $u$, we have $(Au,u) = (Bu,u)$
By the Rayleigh-Ritz theorem (described briefly in the opening blurb here), the minimum value of $(Bu,u)/\|u\|^2$ is the lowest eigenvalue of $B$.

As for $M$: we begin by noting that the largest singular value of $A$ can be described as
$$
\sigma_1(A) = \|A\| = \max_{\|x\| = 1} \|Ax\|
$$
With that and the Cauchy-Schwarz inequality, we note that
$$
(Au,v) \leq \|Au\| \cdot \|v\| \leq \sigma_1(A)\cdot \|u\| \cdot \|v\|
$$
To see that this upper bound is attained (i.e. that there exist $u,v$ such that $(Au,v) = \sigma_1(A)\|u\| \|v\|$), it suffices to take a $u$ such that $\|Au\| = \sigma_1(A)$ and take $v = Au$.


TITLE: Basis and Linear Independence definitions
QUESTION [0 upvotes]: There's something I don't understand about basis.
B is a basis of a space V if:

B is linearly independent.
B spans V

There is also a fact the B is linearly dependent  if you can write one vector as a linear combination of the other.
In addition, I know that every vector in the vector space is a linear combination of this set.
I don't understand how these facts can be true together? If you can write one vector as a linear combination of the other, isn't it dependent?
Thanks,
Alan

REPLY [1 votes]: Linear dependence/independence is a property of an "array" of $k$ vector.

If the array is the sequence of the $n$ vectors of the basis then it is independent.
If the array is the sequence of the $n$ vectors of the basis plus another vector $v$ of the space (therefore an array of $n+1$ vectors) it is dependent, this includes the case of $v$ being equal to one vector of the basis repeated another time

Does it clarify something?


TITLE: Limit of $\lim_{n\to\infty}\sum_{k=1}^{n}\frac{\sigma{(k)}}{k!}$?
QUESTION [1 upvotes]: Evaluate the limit
$$\lim_{n\to\infty}\sum_{k=1}^{n}\dfrac{\sigma{(k)}}{k!}= ?$$
where $\sigma(n)$ is defined as $$\sigma{(N)}=\sum_{d|N}d$$

REPLY [0 votes]: $$\sum_{n=1}^\infty\frac{\sigma(n)}{n!}=\sum_{n=1}^\infty\frac{(id*1)(n)}{n!}=\sum_{n=1}^\infty n\sum_{k=1}^\infty\frac{1}{(kn)!}=\sum_{n=1}^\infty \sum_{t=1}^n e^{e^{2\pi i t/n}}-1$$
$$\sum_{n=1}^\infty\frac{\sigma(n)}{n!}=\sum_{n=1}^\infty \sum_{t=1}^n (\large{e^{e^{2\pi i t/n}}}-1)$$


TITLE: Trace of vectors
QUESTION [3 upvotes]: Does that sound about right?
Given that x is $m\times 1$ and y is $m\times 1$ vectors, show that
$ tr(\mathbf{xy'})=\mathbf{x'y}$.
Attempt:
By using the property of $tr(\mathbf{A'})=tr(\mathbf{A})$,
$tr[\mathbf{xy'}]=tr[(\mathbf{xy'})']$, which is $tr[\mathbf{x'y}]$. But $\mathbf{x'y}$ is a scalar $1\times1$. Thus, $tr[\mathbf{xy'}]=\mathbf{x'y}$.

REPLY [5 votes]: I don't think what you want to do works. It is true that the trace preserves the transpose of a square matrix. But $xy'$ is an $m\times m$ matrix and you are saying that the transpose is $1\times1$?
What is at play here is the fact that $\text{Tr}(AB)=\text{Tr}(BA)$ even if $A$ and $B$ are not square. Indeed, if $A$ is $m\times n$ and $B$ is $n\times m$,
$$
\text{Tr}(AB)=\sum_{k=1}^m(AB)_{kk}=\sum_{k=1}^m\sum_{j=1}^nA_{kj}B_{jk}
=\sum_{j=1}^m\sum_{k=1}^nB_{jk}A_{kj}
=\sum_{j=1}^n(BA)_{jj}=\text{Tr}(BA).
$$


TITLE: How would I find the Jacobian matrix for this set of differential equations?
QUESTION [1 upvotes]: I am working on a nonlinear dynamics problem set and I am uncertain of how to go about finding the Jacobian matrix for this set of equations. I know that you can use taylor expansion and I should end up with a matrix of partial derivatives... I think I have an answer, I just want to double check! Thank you so much!
Here are the equations:
$\dot{x} = y - x^3 - 3x^2 + I$
$\dot{y} = 1 - 5x^2 - y$
NB: I think that the jacobian is $\begin{bmatrix}3x^2 - 6x & 1\\ -10x & -1\end{bmatrix}$ and it will be evaluated at some point (x*, y*).

REPLY [1 votes]: Hint: Your Jacobian is correct.
$$J = \begin{bmatrix}\dfrac{\partial \dot x}{\partial x} & \dfrac{\partial \dot x}{\partial y}\\\dfrac{\partial \dot y}{\partial x} & \dfrac{\partial \dot y}{\partial y}\end{bmatrix} = \begin{bmatrix}3x^2 - 6x & 1\\ -10x & -1\end{bmatrix}$$
Note: The comments state that $I$ is a constant and it can be assumed to be zero.
Now, find the critical points and evaluate the eigenvalues of the Jacobian at each of them.
Update: I find three critical points
$$(x, y) = (-7.98431, -317.746), (-0.361831, 0.345393), (0.346144, 0.400921)$$
Can you proceed?


TITLE: Shortest paths problem : generic algorithm
QUESTION [0 upvotes]: Question :
Answer :
I don't understand the algorithm. Indeed, in the table, I don't understand which vertexes to choose for the "Candidates L" column for each iteration.
I put picture of the statement of the problem and the solution.
Thanks !

REPLY [1 votes]: The "generic algorithm" is a queue-based variant of the Bellman-Ford algorithm.  The use of a queue is motivated by the observation that relaxing an edge only produces a change in the distance of the sink node if the distance of the source node has changed.  To start off the computation, the distance of $v_1$, $d(v_1)$, is "changed" to $0$ and $v_1$ is added to the queue.
At each iteration the vertex of least index is removed from the queue.  Let this vertex be $u$.  All edges out of $u$ are examined.  Let one such edge be $(u,v)$ with weight $W(u,v)$.  If the current $d(v)$ is greater than $d(u) + W(u,v)$, $d(v)$ is updated and $v$ is enqueued.  The process continues until either the queue is empty (as in this case) or a negative cycle is detected.
A detailed explanation of the algorithm is found in Sedgewick and Wayne's Algorithms.


TITLE: Swapping rows in $I$ and transpose
QUESTION [0 upvotes]: Let $I$ denote the $n \times n$ identity matrix. Let $E$ denote $I$ with two arbitrary columns swapped. It seems to be true that then $E^T = E$ in this case (not true if you swap more than $2$!)
Why does this hold? Could someone show me how to prove it? Maybe the proof would provide intuitive insight into why this should indeed be true.

REPLY [1 votes]: Let a permutation $\sigma$ of $\{1,\dots, n\}$ be given.
Starting from the identity matrix $I = [\delta_{i,j}]$, where $\delta_{i,j}$ is the Kronecker symbol, define a matrix $E_\sigma = [\delta_{i,\sigma(j)}]$. Thus the $j$th column of the new matrix is column number $\sigma(j)$ of the old one.
Now $E_\sigma^T = [\delta_{j,\sigma(i)}]_{i,j} = [\delta_{\sigma(i),j}] = [\delta_{i,\sigma^{-1}(j)}] = E_{\sigma^{-1}}$.
When $\sigma$ is simply a transposition, we have $\sigma^{-1} = \sigma$, which explains the phenomenon you referred to. This occurs if and only if $\sigma^2 = 1$.


TITLE: Show that conditions of second derivative test for $g:\mathbb{R}^2 \to \mathbb{R}$ implies that its Hessian is positive definite
QUESTION [0 upvotes]: The following is extracted from Second Derivative Test.

To optimize a function $f:\mathbb{R}^3\to\mathbb{R},$ one can use Second Derivative Test, that is,
$(1)$ if its Hessian matrix $H$ is positive definite (all eigenvalues are positive) at $(a,b,c)$, then the point is a local minimum,
$(2)$ if its Hessian matrix $H$ is negative definite (all eigenvalues are negative) at $(a,b,c)$, then the point is a local maximum.
$(3)$ if its Hessian matrix $H$ contains both positive and negative eigenvalues, then the test is a saddle point.
All other cases are inconclusive.

For $g:\mathbb{R}^2 \to \mathbb{R},$ we have an equivalent way of checking whether a point is local min/max/saddle by checking determinant of $H$ and sign of $g_{xx}.$

Question: Show that for a $2\times 2$ Hessian matrix $H = \begin{pmatrix} g_{xx} & g_{xy} \\
g_{xy} & g_{yy} \end{pmatrix},$ if $\det(H)>0$ and $g_{xx}(a,b)>0$ at some point $(a,b),$ then $H$ is positive definite.

I am trying to show that all eigenvalues $\lambda_1,\lambda_2$ of $H$ are positive.
Note that
$$g_{xx}g_{yy} - g_{xy}^2 = \det(H) = \lambda_1 \cdot \lambda_2 \quad \text{and}\quad g_{xx} + g_{yy} = trace(H) = \lambda_1 + \lambda_2.$$
Since $\det(H)>0,$ so it both eigenvalues $\lambda_1$ and $\lambda_2$ must have the same sign.
I got stuck here. I do not know how to use $g_{xx}>0$ to conclude that $\lambda_1>0$ and $\lambda_2>0.$

REPLY [3 votes]: This is Sylvester's criterion.
For the case of a $2\times 2$ matrix one can just run two steps of Cholesky's decomposition to show that the matrix factors as $B^TB$ and therefore $x^TB^Tx=(Tx)^T(Tx)=\|Tx\|^2\geq0$.
Explicitly
$$B^T=\begin{pmatrix}\sqrt{g_{xx}}&0\\\frac{g_{xy}}{\sqrt{g_{xx}}}&\sqrt{g_{yy}-\frac{g_{xy}^2}{g_{xx}}}\end{pmatrix}$$

You can also finish your argument. If $\lambda_1,\lambda_2\leq0$, then $g_{yy}=\lambda_1+\lambda_2-g_{xx}<0$. But then, multiplying this inequality by the positive number $g_{xx}$ and subtracting the non-negative number $g_{xy}^2$ gives that $g_{xx}g_{yy}-g_{xy}^2<0$. This contradiction tells that $\lambda_1,\lambda_2$ can't be both non-negative. You already showed that they cannot by zero, or of different signs. Therefore, they must be both positive.


TITLE: Meaning of the Planck Temperature
QUESTION [2 upvotes]: I don't understand what makes the Planck Temperature the "absolute hot". To my understanding Temperature is just a measure of the kinetic energy of the particles, so is the Planck Temperature the temperature at which the particles are moving at a speed so close to the speed of light that their behavior can no longer be understood?
If not, what are the formulas that break down as an object is simulated above the Planck Temperature?

REPLY [4 votes]: The meaning of the Planck Temperature is precisely this: IF there exists in the Universe a natural temperature, which is determined by the interplay of the scales of all of quantum mechanics, relativity, gravitation, and thermodynamics - all of whom are understood respectively by the physical constants $\hbar$, $c$, $G$, and $k_B$, then the equation to calculate that temperature from a theory that gives its exact value must be able to be written in the mathematical form
$$T_\mathrm{fundamental} = K \cdot \underbrace{\sqrt{\frac{\hbar c^5}{k_B^2 G}}}_\text{"Planck temperature"}$$
where $K$ is an unknown dimensionless constant. That's it, nothing more. The whole reason is that, given all those scales are involved, the only way you can dimensionally consistently put them all together is that.
But it says nothing else because of that $K$: the actual value of this temperature could be anything. The idea that the Planck temperature is the fundamental temperature is a tact assumption that $K = 1$ or at least $K \approx 1$, but there is nothing about it that says that must be the case. "Heuristically", we'd "like" to think that because "most numbers tend to be about one", but there is no guarantee there at all of anything. $K$ could be 1, but it could also be $10^9$. It could be $10^{-9}$. Heck, it is entirely possible that $T_\mathrm{fundamental}$ is less than one kelvin, that is, that $K \lessapprox 10^{-32}$! There could be some unknown quantum-gravitational effect that only kicks in when things are very cold, colder than we've gotten them and/or only when involving the right substances or looking at the right aspects. That's not "expected", but that's just our prejudice, however "reasonable" we might want to think it.
Our current best model, the Standard Model, is only empirically tested out to temperatures of around $10^{17}\ \mathrm{K}$, or $K \approx 10^{-15}$, and mathematically, the pile of hacks (technically it's not truly a well-founded quantum theory, even!) it is tends to fall apart some ways before we get close to $K = 1$, so we cannot deduce anything useful from tested theory about whether $K \approx 1$ is likely to have real meaning. And finally, it could also be that there are multiple important quantum-gravity temperatures, each of which has an expression like the above, but with a different $K$.


TITLE: Difficulty of "learning" rare instances
QUESTION [8 upvotes]: Is there any result showing that models (say SVM, Neural-Net, kNN, etc) will have difficulty in learning "rare" instances/tail phenomena?

REPLY [10 votes]: In the classic PAC learning (i.e., classification) model, rare instances are not a problem. This is because the learner's test points are assumed to come from the same distribution as the training data. Thus, if a region of space is so sparse as to be poorly represented in the training sample, its probability of appearing during the test phase is low.
You'll need a different learning model, which explicitly looks at type-I and type-II errors, or perhaps some combined precision-recall score. Here again, I don't think there are any results indicating that a specific class of algorithms is particularly poorly suited for this task, but I could be wrong.
The closest I can think of is sensitivity to outliers --- AdaBoost is known to have this property, for example.


TITLE: Use CLT to find the probability
QUESTION [2 upvotes]: $X$ is a discrete random variable with the following density function:
  $$
    f_X(n)
  = \begin{cases}
        c e^{-2} \, \frac{2^n}{n!}
      & n \geq 0, \\
        c 3^n
      & n < 0.
    \end{cases}
$$
  Define the variables $V$ as follows:
  $$
    V
  = \begin{cases}
        0
      & X < 0 \\
        X
      & X \geq 0.
    \end{cases}
$$
  Let $V_1, V_2, V_3, \dotsc$ be a sequence of independent and identically distributed random variables each having the same distribution as $V$.
Use the central limit theorem to approximately find $P(20 < \sum_{i=1}^{20} V_i < 30)$.
(Original image here.)

Not a homework. The entire problem could be found at https://math.stackexchange.com/questions/2885578/find-the-expected-value-of-the-sum-of-random-variables. But it is not that relevant.

My work: In order to use CLT we assume that the variable is normal and then find the mean and std of the random variable.
$\mathbb E[V]=\sum_{n\geq 0}nce^{-2}2^n/n!=2c$
But how to find the variance for the Normal r.v.?
$\mathbb E[V^2]=\sum_{n\geq 0}n^2ce^{-2}2^n/n!=6c$ (not sure if it correct)
So $\operatorname{Var}[V]=6c-4c^2$

REPLY [1 votes]: Based on your calculations (I think they are correct) you can find mean and variance of $\sum_{i=1}^{20}V_i$.
Denoting these by $\mu$ and $\sigma^2$ to be found is: $$P(20<\sum_{i=1}^{20}V_i<30)=P\left(\frac{20-\mu}{\sigma}<\frac{\sum_{i=1}^{20}V_i-\mu}{\sigma}<20<\frac{30-\mu}{\sigma}\right)\approx P\left(\frac{20-\mu}{\sigma}<U<\frac{30-\mu}{\sigma}\right)$$where $U$ has standard normal distribution.


text:
\chapter{Introduction\label{ch:intro}}

This thesis concerns itself broadly with the problem of \emph{optimizing over nonnegative polynomials}. In its simplest form, this problem involves (i) decision variables that are the coefficients of a multivariate polynomial of a given degree, (ii) an objective function that is linear in the coefficients, (iii) constraints that are affine in the coefficients, and (iv) a constraint that the multivariate polynomial be nonnegative over a \emph{closed basic semialgebraic set}, i.e., a set defined by a finite number of polynomial inequalities. We write:
\begin{equation}\label{eq:opt.nonneg}
\begin{aligned}
&\min_{\overrightarrow{p}} &&c(\overrightarrow{p})\\
&\text{subject to } &&A(\overrightarrow{p})=b\\
& &&p(x)\geq 0, \forall x \text{ such that } g_i(x)\geq 0, i=1,\ldots,s,
\end{aligned}
\end{equation}
where $\overrightarrow{p}$ here denotes the coefficients of a multivariate polynomial $p:\mathbb{R}^n \rightarrow \mathbb{R}$ of some degree $d$, $c$ is a linear functional over the coefficients of $p$, $A$ is a linear map that maps the coefficients of $p$ to $\mathbb{R}^m$, $b$ is a vector in $\mathbb{R}^m$, and $g_i, i=1,\ldots,s$, are multivariate polynomials.

This problem appears under different forms in a wide range of applications. One such application is \emph{polynomial optimization}, which is the problem of minimizing a polynomial function over a closed basic semialgebraic set:
\begin{equation*}
\begin{aligned}
&\min_{x\in \mathbb{R}^n} &&p(x)\\
&\text{subject to } &&g_i(x)\geq 0, i=1,\ldots,s.
\end{aligned}
\end{equation*}
Indeed, the optimal value of this problem is equivalent to the largest lower bound on $p$ over the set $\{x\in \mathbb{R}^n|~ g_i(x)\leq 0,i=1,\ldots,s\}$. In other words, we can find the optimal value of the problem above by solving the following ``dual'' problem:
\begin{equation*}
\begin{aligned}
&\max_{\gamma} &&\gamma\\
&\text{subject to } &&p(x)-\gamma \geq 0, \forall x \text{ such that } g_i(x)\geq 0, i=1,\ldots,s.
\end{aligned}
\end{equation*}
This is exactly a problem of optimizing over nonnegative polynomials. Polynomial optimization problems, or POPs, feature in different areas: in power engineering via the optimal power flow problem~\cite{OPF_survey}, in discrete and combinatorial optimization~\cite{laurent2009sums, Stability_number_SOS}, in economics and game theory \cite{sturmfels2002solving}, and in distance geometry~\cite{nie2009sum}, just to name a few. Other applications of the problem of optimizing over nonnegative polynomials appear in control, in particular for searching for Lyapunov functions for dynamical systems~\cite{PabloAliHSCC,PhD:Parrilo, PositivePolyInControlBook, AAA_PhD}, robotics~\cite{ahmadiOR_letters}, and machine learning and statistics \cite{lasserre2009moments}, among other areas.

All these applications motivate the question as to whether (\ref{eq:opt.nonneg}) can be solved efficiently. The answer is unfortunately negative in general. In fact, simply testing whether a given polynomial of degree-4 is nonnegative over $\mathbb{R}^n$ is NP-hard~\cite{nonnegativity_NP_hard}. Past work has hence focused on replacing the nonnegativity condition in (\ref{eq:opt.nonneg}) with a stronger, but more tractable, condition. The idea is that the optimization problem thus obtained can be efficiently solved and upper bounds on the optimal value of (\ref{eq:opt.nonneg}) can be obtained (note that the set over which we would be optimizing would be an inner approximation of the initial feasible set).

A well-known sufficient condition for (global) nonnegativity of a polynomial $p$ is that it be a \emph{sum of squares} (sos), i.e., that it have a decomposition of the form
$$p(x)=\sum_i q_i(x)^2,$$ where $q_i$ are polynomials. Sum of squares polynomials have a long history that dates back at least to the end of the $19^{th}$ century. In 1888, Hilbert showed that not all nonnegative polynomials are sums of squares by proving that these two notions are only equivalent when some conditions on the degree of the polynomial at hand and the number of its variables are met \cite{Hilbert_1888}. His proof was not constructive and it would be another 80 years before the first example of a nonnegative but non-sum of squares polynomial would be presented by Motzkin \cite{MotzkinSOS}. Hilbert's research on sum of squares polynomials led him to include a related question in the list of so-called ``Hilbert problems'', a famous list of 23 open questions, that Hilbert put forward in the year 1900. His $17^{th}$ problem poses the question as to whether every nonnegative polynomial can be written as the ratio of two sums of squares polynomials. This was answered affirmatively by Artin~\cite{artin1927} in 1927.

The beginning of the $21^{st}$ century brought with it a renewed interest in sum of squares polynomials, but from the optimization community this time, rather than the pure mathematics community. This was largely due to the discovery that sum of squares polynomials and \emph{semidefinite programming} are intimately related \cite{NesterovSquared,sdprelax,lasserre2001}. We remind the reader that semidefinite programming (SDP) is a class of optimization problems where one optimizes a linear objective function over the intersection of the cone of positive semidefinite matrices and an affine subspace, i.e., a problem of the type
\begin{equation}\label{eq:SDP}
\begin{aligned}
&\min_{X \in S^{n \times n}} &&tr(CX)\\
&\text{s.t. } &&tr(A_iX)=b_i, i=1,\ldots,m\\
& &&X\succeq 0,
\end{aligned}
\end{equation}
where $S^{n \times n}$ denotes the set of $n \times n$ symmetric matrices, $tr$ denotes the trace of a matrix, and $C,A_i,b_i$ are input matrices of size respectively $n \times n, n \times n, 1\times 1.$ Semidefinite programming comprises a large class of problems (including, e.g., all linear programs), and can be solved to arbitrary accuracy in polynomial time using interior point methods. (For a more detailed description of semidefinite programming and its applications, we refer the reader to \cite{vandenberghe1996semidefinite}.) The key result linking semidefinite programming and sos polynomials is the following: a polynomial $p$ of degree $2d$ is sos if and only if it can be written as$$p(x)=z(x)^TQz(x),$$ for some positive semidefinite matrix $Q$. Here, $z(x)=(1,x_1,\ldots,x_n,x_1x_2,\ldots,x_n^d)$ is the vector of standard monomials of degree $ \leq d$. Such a matrix $Q$ is sometimes called the \emph{Gram} matrix of the polynomial $p$ and it is of size $\binom{n+d}{d}$ if $p$ is of degree $2d$ and has $n$ variables. This result implies that one can optimize over the cone of sos polynomials of fixed degree in polynomial time to arbitrary accuracy. Indeed, searching for the coefficients of a polynomial $p$ subject to the constraint that $p$ be sos can be rewritten as the problem of searching for a positive semidefinite matrix $Q$ whose entries can be expressed as linear combinations of the coefficients of $p$ (this is a consequence of the fact that two polynomials are equal everywhere if and only if their coefficients are equal). In other words, any \emph{sos program}, i.e., a linear optimization problem over the intersection of the cone of sos polynomials with an affine subspace, can be recast as an SDP. (We remark that it is also true that any SDP can be written as an sos program---in fact, this sos program need only involve quadratic polynomials.)

How can sos programs be used to solve problems like (\ref{eq:opt.nonneg})? It turns out that one can produce certificates of nonnegativity of a polynomial $p$ over a closed basic semialgebraic set $$S\mathrel{\mathop{:}}=\{x\in \mathbb{R}^n|~g_i(x)\geq 0, i=1,\ldots,s\}$$ via sum of squares polynomials. Such certificates are called Positivstellens\"atze. We briefly mention one such Positivstellensatz here to illustrate the point we aim to make. Other Positivstellens\"atze as well as additional context is given in Chapter \ref{ch:positiv} of this thesis. The following Positivstellensatz is due to Putinar \cite{putinar1993positive}: under a technical assumption slightly stronger than compactness of $S$ (see Theorem \ref{th:putinar} for the exact statement), if $p$ is positive on $S$, then there exist sos polynomials $\sigma_0,\ldots,\sigma_s$ such that $$p(x)=\sigma_0(x)+\sum_{i=1}^s \sigma_i(x)g_i(x).$$ (Conversely, it is clear that if such a representation holds, then $p$ must be nonnegative on $S$.) Hence, one can replace the condition that $p$ be nonnegative over $S$ in (\ref{eq:opt.nonneg}) by a ``Putinar certificate'' and obtain the following optimization problem:
\begin{equation}\label{eq:sos.prog}
\begin{aligned}
&\min_{\overrightarrow{p},\overrightarrow{\sigma_0},\ldots,\overrightarrow{\sigma_s}} &&C(\overrightarrow{p})\\
&\text{s.t. } &&A(\overrightarrow{p})=b\\
& &&p(x)=\sigma_0(x)+\sum_{i=1}^{s} \sigma_i(x)\cdot g_i(x)\\
& &&\sigma_i(x) \text{ sos for } i=0,\ldots,s.
\end{aligned}
\end{equation}
Note that when the degrees of the polynomials $\sigma_i$ are fixed, this problem is an sos program, which can be recast as an SDP and solved in polynomial time to arbitrary accuracy. This provides an upper bound on the optimal value of (\ref{eq:opt.nonneg}). As the degree of the sos polynomials increases, one obtains a sequence of upperbounds on the optimal value of (\ref{eq:opt.nonneg}) that is nonincreasing. Putinar's Positivstellensatz tells us that if one keeps increasing the degrees of the sos polynomials, one will eventually (and maybe asymptotically) recover the optimal value of (\ref{eq:opt.nonneg}), the caveat being that the degrees needed to recover this optimal value are not known a priori.

We remark that the semidefinite programs arising in this hierarchy can be quite large, particularly if the number of variables and the degrees of $\sigma_i$ are high. Hence, they can be quite slow to solve as semidefinite programs are arguably the most expensive class of convex optimization problems to solve, with a running time that grows quickly with the dimension of the problem \cite{vandenberghe1996semidefinite}.

As a consequence, recent research has focused on making sum of squares optimization more scalable. One research direction has focused on exploiting structure in SDPs \cite{cifuentes2016exploiting,de2010exploiting, Symmetry_groups_Gatermann_Pablo,riener2013exploiting,vallentin2009symmetry,zheng2017fast} or developing new solvers that scale more favorably compared to interior point methods \cite{bertsimas2013accelerated,li2015qsdpnal, nie2012regularization,zhao2010newton}. Another direction involves finding cheaper alternatives to semidefinite programming that rely, e.g., on linear programming or second order cone programming. This, as well as methods to derive certificates of positivity over closed basic semialgebraic sets from certificates of global positivity, is the focus of the first part of this thesis. The second part of this thesis focuses on a special case of the problem of optimizing over nonnegative polynomials: that of optimizing over \emph{convex} polynomials, and applications thereof. In the next section, we describe the contents and contributions of each part of this thesis more precisely.

\section{Outline of this thesis}

\paragraph{Part I: LP, SOCP, and Optimization-Free Approaches to Semidefinite and Sum of Squares Programming.} The first part of this thesis focuses on linear programming, second order cone programming, and optimization-free alternatives to sums of squares (and semidefinite) programming.

Chapter \ref{ch:bp} and Chapter \ref{ch:cholesky} are computational in nature and propose new algorithms for approximately solving semidefinite programs. These rely on generating and solving adaptive and improving sequences of linear programs and second order cone programs.

Chapter \ref{ch:positiv} is theoretical in nature: we show that any inner approximation to the cone of nonnegative homogeneous polynomials that is arbitrarily tight can be turned into a converging hierarchy for general polynomial optimization problems with compact feasible sets. We also use a classical result of Poly\'a on global positivity of even forms to construct an ``optimization-free'' converging hierarchy for general polynomial optimization problems (POPs) with compact feasible sets. This hierarchy only requires polynomial multiplication and checking nonnegativity of coefficients of certain fixed polynomials that arise as products.

We emphasize that the goals in Chapters \ref{ch:bp}, \ref{ch:cholesky}, and \ref{ch:positiv} are different, though they both work with more tractable (but smaller) subclasses of nonnegative polynomials than sum of squares polynomials. For the first two chapters, the goal is to solve in a fast and more efficient manner the sos program given in (\ref{eq:sos.prog}) approximately. In the third chapter, the goal is to provide new converging hierarchies for POPs with compact feasible sets that rely on simpler certificates.

\paragraph{Part II: Optimizing over convex polynomials.} The second part of the thesis focuses on an important subcase of the problem of optimizing over the cone of nonnegative polynomials: that of optimizing over the cone of convex polynomials. The relationship between nonnegative polynomials and convex polynomials may not be obvious at first sight but it be seen easily, e.g., as a consequence of the second-order characterization of convexity: a polynomial $p$ is convex if and only if its Hessian matrix $H(x)$ is positive semidefinite for all $x \in \mathbb{R}^n$. This is in turn equivalent to requiring that the polynomial  $y^TH(x)y$ in $2n$ variables $(x,y)$ be nonnegative. Hence, just as the notion of sum of squares was used as a surrogate for nonnegativity, one can define the notion of \emph{sum of squares-convexity} (\emph{sos-convexity}), i.e., $y^TH(x)y$ be sos, as a surrogate for convexity. One can then replace any constraint requiring that a polynomial be convex, by a requirement that it be sos-convex. The program thus obtained will be an sos program which can be recast as an SDP. Chapters \ref{ch:dc}, \ref{ch:polynorms}, \ref{ch:vikas}, and \ref{ch:mihaela} all present different theoretical and applied questions around this problem.

In Chapter \ref{ch:dc}, this framework is used for a theoretical study of optimization problems known as \emph{difference of convex (dc) programs}, i.e., optimization problems where both the objective and the constraints are given as a difference of convex functions. Restricting ourselves to polynomial functions, we are able to show that any polynomial can be written as the difference of two convex polynomial functions and that such a decomposition can be found efficiently. As this decomposition is non-unique, we then consider the problem of finding a decomposition that is optimized for the performance of the most-widely used heuristic for solving dc programs.

In Chapter \ref{ch:polynorms}, we are interested in understanding when a homogeneous polynomial $p$ of degree $2d$ generates a norm. We show that the $2d^{th}$ root of any strictly convex polynomial is a norm. Such norms are termed \emph{polynomial norms}. We show that they can approximate any norm to arbitrary accuracy. We also show that the problem of testing whether a polynomial of degree $4$ gives rise to a polynomial norm is NP-hard. We consequently provide SDP-based hierarchies to test membership to and optimize over the set of polynomial norms. Some applications in statistics and dynamical systems are also discussed.

 In Chapter \ref{ch:vikas}, we consider a problem that arises frequently in motion planning and robotics: that of modeling complex objects in an environment with simpler representations. The goal here is to contain a cloud of 3D-points within shapes of minimum volume described by polynomial sublevel sets. A new heuristic for minimizing the volume of these sets is introduced, and by appropriately parametrizing these sublevel sets, one is also able to control their convexity.

 In Chapter \ref{ch:mihaela}, we consider an important application in statistics and machine learning: that of \emph{shape-constrained regression}. In this setup, unlike unconstrained regression, we are not solely interested in fitting a (polynomial) regressor to data so as to minimize a convex loss function such as least-squares error. We are also interested in imposing shape constraints, such as monotonicity and convexity to our regressor over a certain region. Motivated by this problem, we study the computational complexity of testing convexity or monotonicity of a polynomial over a box and show that this is NP-hard already for cubic polynomials. The NP-hardness results presented in this chapter are of independent interest, and in the case of convexity are a follow-up result to the main theorem in \cite{ahmadi2013complete} which shows that it is NP-hard to test whether a quartic polynomial is convex \emph{globally}. These computational complexity considerations motivate us to further study semidefinite approximations of the notions of monotonicity and convexity.  We prove that any $C^1$ (resp. $C^2$) function with given monotonicity (resp. convexity) properties can be approximated arbitrarily well by a polynomial function with the same properties, whose monotonicity (resp. convexity) are moreover certified via sum of squares proofs.

 Finally, we remark that for the convenience of the reader, each chapter is written to be completely self-contained.

\section{Related publications}
The material presented in this thesis is based on the following papers.

\paragraph{Chapter 2.} A. A. Ahmadi, S. Dash, and G. Hall. {\it Optimization over structured subsets of positive semidefinite matrices via column generation} (2017). In Discrete Optimization, 24, pp. 129-151.

\paragraph{Chapter 3.} A. A. Ahmadi and G. Hall. \emph{Sum of squares basis pursuit with linear and second order cone programming} (2016). In Algebraic and Geometric Methods in Discrete Mathematics, Contemporary Mathematics.

\paragraph{Chapter 4.} A. A. Ahmadi and G. Hall. \emph{On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity} (2017). Under second round of review in Mathematics of Operations Research.

\paragraph{Chapter 5.} A. A. Ahmadi and G. Hall. \emph{DC decomposition of nonconvex polynomials with algebraic techniques} (2015). In Mathematical Programming, 6, pp.1-26.

\paragraph{Chapter 6.} A. A. Ahmadi, E. de Klerk, and G. Hall. \emph{Polynomial norms} (2017). Under review. Available at ArXiv:1704.07462.

\paragraph{Chapter 7.} A. A. Ahmadi, G. Hall, A. Makadia, A., and V. Sindhwani. \emph{Geometry of 3D environments and sum of squares polynomials} (2017). In the proceedings of Robotics: Science and Systems.

\paragraph{Chapter 8.} A. A. Ahmadi, M. Curmei, G. Hall. \emph{Nonnegative polynomials and shape-constrained regression} (2018). In preparation.\\

\noindent In addition to these papers, the following papers were written during the graduate studies of the author but are not included in this thesis.\\

A. A. Ahmadi, G. Hall, A. Papachristodoulou, J. Saunderson, and Y. Zheng. \emph{Improving efficiency and scalability of sum of squares optimization:recent advances and limitations} (2017). In the proceedings of  the 56th Conference on Decision and Control. \\

E. Abbe, A. Bandeira, and G. Hall. \emph{Exact recovery in the stochastic block model} (2016). In IEEE Transactions on Information Theory, vol. 62, no. 1.

config: arxiv


TITLE: Solving the Kepler problem
QUESTION [2 upvotes]: I'm trying to solve the Kepler problem using the Lagrangian,
$$L = \frac{1}{2} m (\dot{r}^2 + r^2 \dot{\phi}^2) - U(r) $$
which after quite a bit of fiddling with, by noting that the angular momentum $M = mr^2 \dot{\phi}$ is a constant of motion and also $M = 2m\dot{f}$ where $\dot{f}$ s the sectorial velocity, leads to
$$\phi = \int{\frac{M dr/r^2}{\sqrt{2m(E - U(r)) - M^2 / r^2}}}{}$$
Now for the Kepler problem $U(r) \propto 1 / r$ and so $U(r) = \alpha / r$. Plugging that in, we get,
$$\phi = \int{\frac{M}{r^2\sqrt{2m(E + \alpha / r) - M^2  /r^2}}}{dr}$$
However, plugging that integration into WolphramAlpha gives an imaginary solution.
What am I doing wrong?

REPLY [3 votes]: You can use
$$
\frac{d}{dr} \cos^{-1} \left(f\left(r\right)\right) = -\left[1-\left(f\left(r\right)\right)^2\right]^{-1/2} \frac{df}{dr}
$$
with
$$
f\left(r\right) = \frac{M/r - m \alpha/M}{\sqrt{2 m E + m^2 \alpha^2 / M^2}}
$$
to show that
$$
\int dr \frac{M / r^2}{\sqrt{2 m E + 2 m \alpha / r - M^2 / r^2}} = \cos^{-1} \left(\frac{M/r - m \alpha/M}{\sqrt{2 m E + m^2 \alpha^2 / M^2}}\right) + C
$$


TITLE: Index gymnastics with the Riemann tensor
QUESTION [0 upvotes]: We would like to obtain the Ricci tensor from the Riemann tensor.
In most books are contracted the first index with the third one, the second index with the fourth one. Following the same convention, I have obtained these identities. $$g^{ia}g^{lm}{R^k}_{lam}=g^{ia}{R^k}_a=R^{ik}$$ $$g^{im}g^{la}{R^k}_{lam}=-g^{im}g^{la}{R^k}_{lma}=-g^{im}{R^k}_m=-R^{ik}$$ Are they correct?

REPLY [2 votes]: I am not sure why you want the Ricci tensor to have upper indices. If you don't insist on that, but use the more natural version with two lower indices,things become easier: You have to contact the (unique) upper index into one of the two-form indices of the curvature. (Here I am using the interpretation that the Riemann tensor is a two-form with values in endomorphisms of the tangent bundle, which evan available for linear connections without a Riemannian metric.) This fixes Ricci up to sign. The sign is indeed a subtle issue and needs writing out the conventions you use for the Riemann-tensor.