\documentclass[11pt]{article}

%% \def\showanswer{1}

\usepackage{exercises}
\usepackage[numbers]{natbib}
\usepackage{xr}

\externaldocument{ex4-sol}

\usebiggeometry
\bluehyperref

\newcommand{\cg}{\mathop{\textup{cg}}}
\newcommand{\optgap}{\mathsf{gap}}
\newcommand{\size}{\mathop{\textup{size}}}

\begin{document}

\setcounter{section}{8}

\title{ee364m Exercise Set \thesection\
  \ifdefined\showanswer
  Solutions
  \fi
}

\author{Due date: March 6, 11:59pm}
\date{}
\maketitle

In this exercise set, we will develop some of the theory of logarithmically
homogeneous self-concordant functions. This can require some care
with regards to the boundaries of domains of self-concordant functions,
and to that end, we make a slightly extended definition of self concordance.
\begin{definition}
  \label{definition:self-concordance}
  Let $f : \R^n \to \R \cup \{+\infty\}$ be thrice differentiable on its
  domain $\Omega = \dom f$.  Then $f$ is (strongly non-degenerate)
  self-concordant if
  \begin{enumerate}[i.]
  \item it is strictly convex on $\Omega$ (equivalently,
    $\nabla^2 f(x) \succ 0$ for $x \in \Omega$),
  \item for each $x \in \Omega$
    and $v \in \R^n$, the functional $\phi(t) \defeq f(x + tv)$ satisfies
    \begin{equation*}
      \phi'''(t) \le 2 (\phi''(t))^{3/2},
    \end{equation*}
  \item and $f(x) \to \infty$ as $x \to \bd \Omega$.
  \end{enumerate}
\end{definition}
\noindent
Strong non-degeneracy corresponds to strict convexity of $f$
and boundary growth; we assume all self-concordant functions
we work with satisfy this condition without further comment.

\begin{question}
  Let $K \subset \R^n$ be a convex cone with
  interior, and let $f : \interior K \to \R$ be self-concordant
  with domain $\dom f = \interior K$.  Define the
  Hessian and gradient mappings $g(x) = \nabla f(x)$ and $H(x) = \nabla^2
  f(x)$.  We say that $f$ is and $\nu$-logarithmically homogeneous if
  \begin{equation*}
    f(tx) = f(x) - \nu \log t
  \end{equation*}
  for $t > 0$.
  \begin{enumerate}[(a)]
  \item Show that if $f$ is logarithmically homogeneous, then
    \begin{equation}
      \label{eqn:g-homogeneous}
      g(t x) = \frac{1}{t} g(x)
      ~~ \mbox{for~all~} t > 0.
    \end{equation}
  \item Show that if $f$ has gradient satisfying the
    identity~\eqref{eqn:g-homogeneous}, then
    \begin{equation*}
      H(tx) = \frac{1}{t^2} H(x)
      ~~ \mbox{and} ~~ H(x) x = -g(x).
    \end{equation*}
    Use these to show that that the (squared) Newton decrement
    \begin{equation*}
      \lambda^2(x) \defeq \<\nabla f(x), \nabla^2 f(x)^{-1} \nabla f(x)\>,
    \end{equation*}
    is constant and equals
    $\lambda^2(x) = -\<g(x), x\>$.
  \item Show that if $f : \interior K \to \R$ has gradient satisfying the
    identity~\eqref{eqn:g-homogeneous}, then
    \begin{equation*}
      f(t x) = f(x) - \nu \log t,
    \end{equation*}
    where $\nu = \sup_{x \in \dom f} \lambda^2(x)$.
    Use this to conclude that $f$ is $\nu$-logarithmically homogeneous
    if and only if identity~\eqref{eqn:g-homogeneous} holds, and
    in this case, $\nu = \lambda^2(x)$ for any $x$.
  \end{enumerate}
  For the remainder of the question,
  assume that $f : \interior K \to \R$ is $\nu$-logarithmically
  homogeneous.
  \begin{enumerate}[(a)]
    \setcounter{enumi}{3}
  \item Show that $\nabla f(x) \in -K^*$ for any $x \in K$.
  \item \label{item:homogeneous-have-minimizers}
    Use Lemma~\ref{lemma:convex-cones} from
    Exercise~\ref{question:strong-duality} to argue that
    for any $\lambda \in -\interior K^*$, there exists $\alpha > 0$ such
    that $\<-\lambda, x\> \ge \alpha \norm{x}$ for $x \in K$. Then
    show that if $h(t) \defeq f(tx) - \<\lambda, t x\>$, we obtain
    $h'(t) > 0$ whenever $t > 1$ and $\norm{x} > \nu / \alpha$.
    Conclude that
    \begin{equation*}
      f(x) - \<\lambda, x\>
    \end{equation*}
    has a minimizer satisfying $\norm{x} \le \nu / \alpha$.
  \item Use the previous parts and Lemma~\ref{lemma:domain-duality}
    (to follow)
    to show that $\dom f^* = -\interior K^*$.
  \end{enumerate}
  Note that you have shown the following theorem:
  \begin{theorem}
    Let $f$ be self-concordant and
    $\nu$-logarithmically homogeneous
    with domain $\dom f = \interior K$. Then $f^*$ is
    self-concordant, $\nu$-logarithmically homogeneous, and
    $\dom f^* = -\interior K^*$.    
  \end{theorem}
  \noindent (The logarithmic homogeneity of $f^*$ follows
  by the identity $\nabla^2 f(x)^{-1} = \nabla^2 f^*(s)$
  when $\nabla f(x) = s$.)
\end{question}

The following lemmas may be useful for answering
the question.
\begin{lemma}[Boyd and Vandenberghe~\cite{BoydVa04}, Ex.\ 9.19]
  \label{lemma:self-concordant-minimizers-exist}
  Let $f$ be self concordant and assume that $\inf_x f(x) > -\infty$.
  Then $f$ has a minimizer.
\end{lemma}
\begin{lemma}
  \label{lemma:domain-duality}
  Let $f$ be self concordant with domain $\Omega =
  \dom f$. Then $\Omega$ is open, the gradient mapping
  $g(x) \defeq \nabla f(x)$ is injective, and
  $\dom f^* = \{g(x) \mid x \in \Omega\}$
  and is open.
\end{lemma}
\begin{proof}
  That $\Omega$ is open follows because
  \begin{equation*}
    \dom f = f^{-1}(\R)
    = f^{-1}(-\infty, \infty)
  \end{equation*}
  and $f$ is continuous.
  To show injectivity of $g$, suppose $g(x_0) = s$ and $g(x_1) = s$. Then
  $x_0$ and $x_1$ both minimize $f(x) - \<s, x\>$ by the
  Fenchel-Young inequality; this is strictly convex
  and hence $x_0 = x_1$. So $g$ is injective (one-to-one).
  Then again by the equality condition in the Fenchel-Young inequality,
  we have $x = \nabla f^*(s)$ and $f^*(s) = \<x, s\> - f(x) < \infty$
  so that $s \in \dom f^*$. That is,
  \begin{equation*}
    \{g(x) \mid x \in \Omega\} \subset \dom f^*.
  \end{equation*}
  We now show that $\dom f^* \subset \{g(x) \mid x \in \Omega\}$.
  Let $s \in \dom f^*$, so that $\sup_x \<s, x\>
  - f(x) < \infty$. Then $\inf_x f(x) - \<s, x\> > -\infty$, so that the
  self-concordant function $x \mapsto f(x) - \<s, x\>$ has a minimizer
  (Lemma~\ref{lemma:self-concordant-minimizers-exist}). Then
  there exists an $x$ such that $\nabla f(x) - s = 0$, i.e., $g(x) = s$.
\end{proof}

\bibliography{bib364m}
\bibliographystyle{abbrvnat}

\end{document}