TITLE: SOCP with a norm constraint
QUESTION [2 upvotes]: Is it possible to convert this optimization problem into a SOCP:
\begin{eqnarray}
\min && c^T x \\
s.t. && \|A_ix + b_i \|_2 \le c_i^T x + d_i \\
&& \| Dx \|_2 = g
\end{eqnarray}
where $D$ is diagonal. The first constraint is the classic SOCP constraint, but I am not sure whether the second constraint can be converted into a SOCP constraint.

REPLY [2 votes]: This problem is not convex and therefore cannot be represented as an SOCP. However, it is possible to appriximate it using the convex-concave procedure, as described here. To summarize, you replace your constraint $||Dx||_2 = g$ by two constraints:

$||Dx|| \le g$, which is convex
$||Dx|| \ge g$, which is nonconvex

You solve a sequence of SOCP problems, where in each one you replace the constraint (2) by an approximation based on the result from the previous iteration. The approximation is:
$$q^T(Dx) \ge g$$
where $$q = \frac{(D x^{\text{prev}})}{||D x^{\text{prev}}||_2}$$
You can see that the approximation is linear (and therefore convex) and as the difference between $x$ and $x^\text{prev}$ decreases, the approximation gets closer and closer to approximating the original constraint.
Note, that this method does not find the global solution. It is just a heuristic.


TITLE: Solution verification: Some preimage and image proofs of a map
QUESTION [1 upvotes]: Let $f : A \to B$ and let $A_0 \subset A$ and
$B_0 \subset B$.
(a) We will show that $A_0 \subset f^{-1}[f[A_0]]$, with equality
if $f$ is injective.
Proof: let $x \in A_0$, then $f(x) \in f[A_0]$.  This,
by definition of the preimage of $f[A_0]$ under $f$, implies that
$x \in f^{-1}[f[A_0]]$, and therefore
$A_0 \subset f^{-1}[f[A_0]]$.  Assume $f$ is injective, and
let $x \in f^{-1}[f[A_0]]$, which implies $f(x) \in f[A_0]$
for exactly one $x \in f^{-1}[f[A_0]]$.  In other words, there
are no $a \in A_0$ with $a \neq x$ such that $f(a) = f(x) \in f[A_0]$.
Thus, $x \in A_0 \Rightarrow f^{-1}[f[A_0]] \subset A_0$,
and we are done.
(b) We will show that $f[f^{-1}[B_0]] \subset B_0$, with equality
if $f$ is surjective.
Proof: let $y \in f[f^{-1}[B_0]]$, then $y = f(a)$ for some
$a \in f^{-1}[B_0]$, which implies that $f(a) \in B_0$ by
definition of $f^{-1}[B_0]$.  Therefore, $y \in B_0$ and we can
conclude that $f[f^{-1}[B_0]] \subset B_0$.  Assume $f$ is
surjective, and let $y \in B_0$.  Let $y \in B_0$. By surjectivity, then there is some $a \in f^{-1}[B_0]$ such that $f(a) = y$. Therefore, $y \in f[f^{-1}[B_0]]$ which implies the desired result.

REPLY [1 votes]: Right, so I've writtne most of my feedback about your proof in the comments above. This is going to focus on how I would phrase my own arguments. I'm going to actually prove the parts where it says "with equality if $f$ is...."

$A_0 =f^{-1}[f[A_0]]$.

We know that $A_0 \subseteq f^{-1}[f[A_0]]$. Let $x \in f^{-1}[f[A_0]]$. Then, $f(x) \in f[A_0]$. Since $f(x) \in f[A_0]$, there exists an $a \in A_0$ such that $f(a) = f(x)$. Since $f$ is  injective, it follows that $a = x$. But this implies that $x \in A_0$ and we are done.

$B_0=f[f^{-1}[B_0]]$.

We know that $f[f^{-1}[B_0]] \subseteq B_0$. Let $y \in B_0$. Since $f$ is surjective, there is an $x \in A$ such that $f(x) = y$. Then, $x \in f^{-1}[B_0]$. But this implies that $f(x) \in f[f^{-1}[B_0]]$ and this means that $y \in f[f^{-1}[B_0]]$. So, we are done.


text:
\section{Introduction}

The investigation of patterns in families of discrete objects is an active
topic in Combinatorics, with connections to various areas in Mathematics,
as well as  other fields such as Physics, Biology,
Sociology and Computer science
\cite{pp-phylogeny,kitaev-book-11,lackner-17}.
Generally speaking, the notion of pattern occurrence or pattern avoidance can be
described as the presence or, respectively, absence of a substructure inside a larger
structure.
Patterns were first considered for permutations: an occurrence of a pattern $\sigma$
in a permutation $\pi$ is a subword of $\pi$ whose letters appear in the same relative
order  as those in $\sigma$.
For instance, the permutation $132$ occurs as a pattern in $32514$ since the
subsequence $254$ (among others) is ordered in the same way as $132$ (see
Figure~\ref{fig:perm} for an illustration using  matrix representations).
\begin{figure}[h!]
  \begin{center}
    \begin{tikzpicture}[scale=0.4]
    \begin{scope}[xshift=-10cm]
      \draw[step=1.0,black,thin] (1,-3) grid (6,2);
      \node at(3.5,3){$32514$};
      \node at(0.5,1.5){\fs$\tt5$};
      \node at(3.5,1.5){$\bullet$};
      \node at(0.5,0.5){\fs$\tt4$};
      \node at(4.5,-2.5){$\bullet$};
      \node at(0.5,-0.5){\fs$\tt3$};
      \node at(1.5,-0.5){$\bullet$};
      \node at(0.5,-1.5){\fs$\tt2$};
      \node at(2.5,-1.5){$\bullet$};
      \node at(0.5,-2.5){\fs$\tt1$};
      \node at(1.5,-3.5){\fs$\tt 1$};
      \node at(2.5,-3.5){\fs$\tt 2$};
      \node at(3.5,-3.5){\fs$\tt 3$};
      \node at(4.5,-3.5){\fs$\tt 4$};
      \node at(5.5,-3.5){\fs$\tt 5$};
      \node at(5.5,0.5){$\bullet$};
      \node at(-1.2,0){$\pi:$};
 \draw[->,line width=1pt,color=black,opacity=0.5] (7,0) to[bend left,out=20](9,0);

    \end{scope}

    \begin{scope}[xshift=0cm]
      \draw[lightgray](1,-3) grid (2,2);
      \draw[lightgray](2.01,-3) grid (6,-2);
      \draw[lightgray](2.01,-1) grid (6,0);
      \draw[lightgray](4,1) -- (5,1);
      \draw[lightgray](4,2) -- (5,2);
      \draw[thick](2,-2) grid (4,-1);
      \draw[thick](2,0) grid (4,2);
      \draw[thick](5,0) grid (6,2);
      \draw[thick](5,-2) grid (6,-1);

       \node at(0.5,1.5){\fs$\tt5$};
       \node at(0.5,0.5){\fs$\tt4$};
       \node at(0.5,-0.5){\fs$\tt3$};
       \node at(0.5,-1.5){\fs$\tt2$};
       \node at(0.5,-2.5){\fs$\tt1$};
       \node at(1.5,-3.5){\fs$\tt 1$};
       \node at(2.5,-3.5){\fs$\tt 2$};
       \node at(3.5,-3.5){\fs$\tt 3$};
       \node at(4.5,-3.5){\fs$\tt 4$};
       \node at(5.5,-3.5){\fs$\tt 5$};

      \node[lightgray] at(1.5,-0.5){$\bullet$};
      \node[lightgray] at(4.5,-2.5){$\bullet$};
      \node at(3.5,1.5){$\bullet$};
      \node at(3.5,3){$254$};
      \node at(2.5,-1.5){$\bullet$};
      \node at(5.5,0.5){$\bullet$};

   \draw[->,line width=1pt,color=black,opacity=0.5] (7,0) to[bend left,out=20](9,0);
    \end{scope}

    \begin{scope}[xshift=12cm, yshift=2cm]
      \draw[step=1.0,black,thin] (1,-3) grid (4,0);
      \node at(2.5,1){$132$};
      \node at(0.5,-0.5){\fs$\tt 3$};
      \node at(1.5,-2.5){$\bullet$};
      \node at(0.5,-1.5){\fs $\tt 2$};
      \node at(2.5,-0.5){$\bullet$};
      \node at(0.5,-2.5){\fs $\tt 1$};
      \node at(3.5,-1.5){$\bullet$};
      \node at(1.5,-3.5){\fs $\tt 1$};
      \node at(2.5,-3.5){\fs $\tt 2$};
      \node at(3.5,-3.5){\fs $\tt3$};
      \node at(-1.2,-2){$\sigma:$};
    \end{scope}
  \end{tikzpicture}
\caption{An occurrence of the pattern $\sigma=132$ in $\pi=32514$.  $\sigma$ is
obtained by deleting the first and forth column, as well as the third and fifth row of
$\pi$.}
\label{fig:perm}
\end{center}
\end{figure}

The systematic investigation of patterns in permutations and more generally in words began in the 70s with the work of Knuth on sorting permutations using data structures \cite{knuth-art-I}, and later with the work of Simion and Schmidt \cite{restrpermut-85}.
In the last decade the study of patterns in permutations and words has grown
explosively  (see \cite{combperm-bona-04, kitaev-book-11})
and has been extended  in the context of various
other structures  such as set partitions, trees, lattice paths,
fillings of Young diagrams, just to name a few.

For instance, in \cite{spiridonov-fpsac} Spiridonov considered a notion of pattern
occurrence for binary fillings of grid shapes, which  naturally generalizes
permutation pattern occurrence as follows: an  occurrence of a pattern in a filling of
a grid shape $T$ is a filling of a sub-shape (or {\em minor shape}) $S$ of $T$,
obtained by removing some rows and columns of $T$ (see Figure~\ref{fig:grid_pattern}
for two such examples).

\begin{figure}[h!]
\input{figures/grid_pattern}
\caption{Two examples of pattern occurrence in binary fillings of grid shapes
   in the sense of \cite{spiridonov-fpsac}.
In both cases, $S$ is obtained by deleting  two columns and a row of  $T$.}
\label{fig:grid_pattern}
\end{figure}

In a totally different context,  Bacher et al. in  \cite{dyckpp-14} considered a
notion of pattern occurrence for Dyck paths,\, i.e.,  paths on the discrete plane from
$(0,0)$ to $(2n,0)$, $n\in\mathbb{N}$, consisting of up-steps $\U\!\!:\!(1,1)$
and down-steps $\D\!\!:\!(1,-1)$ never going below the $x$-axis. The pattern
occurrence is defined by
deleting   $U$ and $D$-steps so that the resulting path is again a Dyck path
(with fewer steps). See  Figure~\ref{fig:dyckpatt} for an example of a Dyck
path and a
pattern occurrence.

\begin{figure}
\input{figures/patern_examples}
\caption{Two instances of pattern occurrence in the context of  \cite{dyckpp-14}.
  In both examples, $\pa$ is a shorter  Dyck path obtained from the original
  path
  $\pa'$ by  deleting  the  steps  in red. }
\label{fig:dyckpatt}
\end{figure}

Inspired by \cite{dyckpp-14} and \cite{spiridonov-fpsac},
we introduce a notion of patterns for the so called {\em Shi tableaux}, which
are  structures   defined in \cite{FVT13}  to encode  dominant regions of the
($m$-extended) Shi arrangement.
For $m=1$  Shi  tableaux can easily  be  described as binary fillings
of certain Young diagrams.
 More precisely, a {\em Shi tableau} of size $n$ is a
binary filling with $\bullet$ or $\circ$
of a staircase Young diagram of shape $(n,n-1,\ldots,1)$, satisfying  the
property
that if a cell contains $\bullet$  then all cells above and to its left
contain $\bullet$. It is straightforward to see
 (cf. Figure~\ref{fig:dyckshi})
that Shi tableaux of size $n$ biject   to Dyck paths of semilength $n+1$.

\begin{figure}[h!]
  \begin{center}
\input{figures/tableau_paths}
\caption{
	A Shi tableau $T\in \shiT{4}$ and the corresponding Dyck path $\pa\in\dP{5}$.}

\label{fig:dyckshi}
\end{center}
\end{figure}

In accordance with  Spiridonov's definition \cite{spiridonov-fpsac}, the notion of
pattern occurrence in Shi tableaux can be defined by deleting columns and rows.
However, in our pattern we impose a stronger condition; we allow deletions
of rows and columns after which the underlying Young diagram is again a
staircase Young diagram (see Section~\ref{sec:shi} for the precise definition).

Part of the motivation of this work
lies in \cite[\textsection6]{dyckpp-14}, where Bacher et al. ask whether it is possible to
transport the pattern order on Dyck paths along some of the bijections between Dyck
paths and other members of the Catalan family in order to obtain interesting order
structures on different combinatorial objects.

So far, our intuition to work on this subject has been affirmed by the enumerative
results presented here, which hint at interesting connections to the theory of pattern
avoidance for permutations.
This is perhaps not surprising in view of the fact that one of the original
problems of this area, the enumeration of $312$-avoiding permutations, is also
related to Dyck paths.
Furthermore, there are ties to algebraic objects that arise in connection to
crystallographic root systems.
For example, $ad$-nilpotent ideals of a Borel subalgebra of the complex simple Lie
algebra of type $A$ with a bounded class of nilpotence,  studied in
\cite{akop-adnil-02}, can be described using pattern avoidance for Shi tableaux.

This paper is organized as follows.
In Section~\ref{sec:prel} the basic definitions and notation, including
our definition of pattern occurrence on Shi tableaux,
  are provided.

In Section~\ref{sec:ulbounds} we give explicit formulas for the number of
upper and lower covers for each Shi tableau, in the poset defined by
pattern-containment.
In Section~\ref{sec:avoid} we give precise characterizations of pattern
avoidance for each  Shi tableaux of size $2$ and generalize these results
for certain tableaux of larger size.
In the process we encounter $ad$-nilpotent ideals and the bijection on Dyck paths known as the zeta map.
We complete the paper with a short discussion of open problems in Section~\ref{sec:problems} including possible connections to permutations avoiding a pair of patterns.

config: arxiv


TITLE: Easy algebra question: show equality?
QUESTION [1 upvotes]: Let $c:=(u+d)/2$ and $-1<d<0<u$.
Show:

Can you show the steps to arrive from lhs to rhs?

REPLY [2 votes]: $$
\frac{1 + u}{2}(1 + 2c) + \frac{1+d}{2}(1 + c) = \frac{1 + u}{2}(1 + c) + \frac{1 + u}{2}c + \frac{1+d}{2}(1 + c)
$$
$$
=(1 + c)\biggl(\frac{1 + u}{2} + \frac{1 + d}{2} \biggr) + \frac{1 + u}{2}c = (1 + c)\biggl(1 + \frac{u + d}{2}\biggr) + \frac{1 + u}{2}c
$$
$$
= (1 + c)^2 + \frac{1 + u}{2}c
$$