\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{url}
\usepackage{xcolor}
\begin{document}


\begin{center}
\textbf{CSE 203B W21 Homework 3} \\
\end{center}

\noindent{\textbf{Due Time : 11:50pm, Wednesday Feb. 1, 2023}} 
\textbf{Submit to Gradescope \\ Gradescope: \url{https://gradescope.com/} }\\
\\[0.2in]
{\bf In this homework, we work on exercies from text book including level sets of convex, concave, quasi-convex, quasi-concave functions (3.1, 3.2), second-order conditions for convexity on affine sets (3.9), Kullback-Leibler divergence (3.13), saddle points of convex-concave functions (3.14) determination of convex, concave, quasi-convex, quasi-concave functions (3.16), conjugate functions (3.36), and gradient and Hessian of conjugate functions (3.40). Extra assignments are given on softmax functions, dual norms, and a conjugate function.\\ [0.2in]
Exercises are graded by completion, assignments are graded by content. We may just grade a subset of the problems.}\\[0.2in]

\noindent\textbf{I. Exercises from textbook chapter 3 (8 pts)} \\[0.05in]

3.1, 3.2, 3.9, 3.13, 3.14, 3.16, 3.36, 3.40. \\

\noindent\textbf{II. Assignments (42 pts)} \\%\\[0.2in]

\noindent
II. 1. Softmax Functions.

Given a function $f(x)= max_i x_i - min_i x_i$, where $x=[x_i] \in R^n$,
we use a softmax expression $\tilde f(x)= log \sum_i e^{x_i}$ + log \sum_i e^{-x_i}$
to approximate the function $f(x)$.

\noindent
II.1.1. Prove or disprove that function $f(x)$ is convex.

\noindent
II.1.2. Prove or disprove that the approximation function $\tilde f(x)$ is convex. 

\noindent
II.1.3. Show and prove the worst error of the approximation.

\noindent
II.1.4. Design an improved approximation function that improves the worst error.
Show and prove the worst error of the new function.

\noindent
II.1.5. Prove or disprove that your approximation function is convex.\\

\noindent
II. 2. Dual Norm.

Given a dual norm $f(x)= max_{||y||_p \leq 1} y^Tx$, where $x, y \in R^n$.

\noindent
II.2.1. Prove that the function can be expressed as $f(x)=||x||_q$, where $1/p+1/q=1$,
when $p \geq 1$.

\noindent
II.2.2. Does the dual norm $f(x)= max_{||y||_p \leq 1} y^Tx$ remain to be convex when $0 < p < 1$? Explain your answer.

\noindent
II.2.3. Derive the formula of the dual norm $f(x)$ when $0 < p < 1$.\\

\noindent
II. 3. Conjugate Functions. 

Find the conjugate function of the following function.

\noindent
$f(x) = 
\begin{cases}
||Ax+b||_2^2, ~~~~~~~~~~~~~~~~~||Ax+b||_2 \leq \alpha, \\
\alpha (2||Ax+b||_2 - \alpha), ~~~~~~||Ax+b||_2 > \alpha. \\
\end{cases}

\noindent
where $A \in R^{mn}, x \in R^n$, b \in R^m, \alpha \in R_{++}$. \\
 
\end{document}