/
pr3.tex
166 lines (145 loc) · 6.75 KB
/
pr3.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
\documentclass{article}
% Include macros here
\input{macros}
\usepackage{fancyhdr}
%\include{macros}
\usepackage{pifont}
% Number of problem sheet
\newcounter{problemSheetNumber}
\setcounter{problemSheetNumber}{3}
\newcommand{\matlabprob}{\ding{100} \ }
\newcommand{\examprob}{\ding{80} \ }
%\setcounter{section}{\theproblemSheetNumber}
%\renewcommand{\theparagraph}{(\thesection.\arabic{paragraph})}
\newcounter{problems}
\setcounter{problems}{0}
%\setlength{\parindent}{0cm}
\renewcommand{\problem}{\paragraph{(\theproblemSheetNumber.\theproblems)}\addtocounter{problems}{1}}
%\theoremstyle{remark}
%\newtheorem{problem}[problemSheetNumber]{}
\pagestyle{fancy}
\lhead{MATH36061}
\chead{Convex Optimization}
\rhead{October 16, 2016}
\begin{document}
\begin{center}
{\Large {\bf Problem Sheet \theproblemSheetNumber}}
\end{center}
Problems in Part A will be discussed in class. Problems in Part B come with solutions and should be tried at home.
\section*{Part A}
\problem Recall that a norm was a function $\norm{\cdot}$ on $\R^n$ such that
\begin{itemize}
\item $\displaystyle \norm{\vct{x}}\geq 0$ and $\norm{\vct{x}}=0 \Leftrightarrow \vct{x}=\zerovct$;
\item $\displaystyle \norm{\lambda \vct{x}} = |\lambda|\norm{\vct{x}}$ for $\lambda\in\R$;
\item $\displaystyle \norm{\vct{x}+\vct{y}} \leq \norm{\vct{x}}+\norm{\vct{y}}$.
\end{itemize}
The most prominent examples are
\begin{equation*}
\norm{\vct{x}}_2 = \sqrt{\sum_{i=1}^n x_i^2}, \quad \norm{\vct{x}}_1 = \sum_{i=1}^n |x_i|, \quad \norm{\vct{x}}_\infty = \max_{1\leq i\leq n} |x_i|.
\end{equation*}
\begin{itemize}
\item[(a)] Show that for any norm, the {\em norm balls}
\begin{equation*}
B(\vct{p},r) := \{\vct{x} \mid \norm{\vct{x}-\vct{p}}\leq r\}
\end{equation*}
are convex sets.
\item[(b)] To a convex set $C$ with $\zerovct\in \inter C$ we can associate the {\em polar} set
\begin{equation*}
C^* := \{\vct{y}\in \R^n \mid \forall \vct{x}\in C, \ip{\vct{x}}{\vct{y}}\leq 1\}.
\end{equation*}
Show that the polar of a convex set is again convex.
\item[(c)] Describe the polar sets of the norm balls $B(\zerovct,1)$ for the $1$, $2$, and $\infty$ norms.
\end{itemize}
\problem Let $C,D\subseteq \R^n$ be disjoint, non-empty, closed, bounded convex sets. Show that there exists an affine hyperplane $H$ strictly separating $C$ and $D$ (i.e., $C\subset \inter H_-$ and $D\subset \inter H_+$). Hint: consider the set $C-D=\{\vct{x}-\vct{y}\mid \vct{x}\in C, \vct{y}\in D\}$ and use the separation theorem for a convex set and a point from the lecture. Give an example of closed convex sets $C$ and $D$ that cannot be strictly separated by a hyperplane.
\problem (Facility location.) Facility location problems concern the location of points (facilities or devices on a circuit) in a region, some of which are required to be connected by links (streets or wires). The objective is to locate some of the points that are not fixed in a way that minimizes the transport cost along the links. The distance can be measured with respect to the usual Euclidean norm or the $1$-norm.
\begin{itemize}
\item[(a)] Given a rectangular grid, show that the length of a path from coordiante $\vct{x}$ to $\vct{y}$ is given by
\begin{equation*}
d(\vct{x},\vct{y}) := \norm{\vct{x}-\vct{y}}_1.
\end{equation*}
\begin{figure}[h!]
\centering
\begin{tikzpicture}[thick,scale=1.5]
\node (A1) at (0,0) [label=225:{$\vct{x}$}] {};
\node (A2) at (3,2) [label=225:{$\vct{y}$}] {};
\draw[color=black!40] (0,0)--(3,0)--(3,2)--(0,2)--(0,0);
\draw[color=black!40] (0,1)--(3,1);
\draw[color=black!40] (0,2)--(3,2);
\draw[color=black!40] (1,0)--(1,2);
\draw[color=black!40] (2,0)--(2,2);
\draw[thick] (0,0)--(0,1)--(1,1)--(2,1)--(2,2)--(3,2);
\filldraw[black] (0,0) circle (2pt);
\filldraw[black] (3,2) circle (2pt);
\end{tikzpicture}
\caption{Manhattan distance}\label{fig:triangle}
\end{figure}
This is an example of the so-called {\em Manhattan distance}.
\item[(b)] Suppose now that we are given $N$ fixed points $\vct{p}_1,\dots,\vct{p}_N$ in on a fine grid in $\R^2$ and would like to find
a point $\vct{x}$ that minimizes the total $1$-norm distance
\begin{equation*}
\minimize \sum_{i=1}^N \norm{\vct{p}_i-\vct{x}}_1 = \sum_{i=1}^N |p_{i,1}-x_1|+|p_{i,2}-x_2|.
\end{equation*}
Assume in addition that the point $\vct{x}$ is constrained to be in a polyhedral region
\begin{equation*}
P = \{\vct{x} \mid \mtx{A}\vct{x}\leq \vct{b}\}.
\end{equation*}
Formulate this optimal placement problem as a linear programming problem.
\begin{figure}[h!]
\centering
\begin{tikzpicture}[thick,scale=1.5]
\node (A1) at (0,0) [label=225:{$\vct{p}_1$}] {};
\node (A2) at (3,2) [label=180:{$\vct{p}_2$}] {};
\node (A3) at (1,2) [label=225:{$\vct{p}_3$}] {};
\draw[color=black!40,fill=blue!5] (1,0)--(2,0)--(2,1)--(1,1)--(1,0);
\draw (0,0)--(1.7,0.7);
\draw (1,2)--(1.7,0.7);
\draw (3,2)--(1.7,0.7);
\filldraw[black] (0,0) circle (2pt);
\filldraw[black] (1,2) circle (2pt);
\filldraw[black] (3,2) circle (2pt);
\filldraw[blue] (1.7,0.7) circle (2pt);
\node (A4) at (1.7,0.7) [label=270:{$\vct{x}$}] {};
\node (P) at (1,0) [label=45:{$P$}] {};
\end{tikzpicture}
\end{figure}
\end{itemize}
\section*{Part B}
\problem A {\em polyhedron} $P$ is a convex set defined by a system of linear inequalities
\begin{equation*}
P = \{\vct{x}\in \R^n \mid \mtx{A}\vct{x}\leq \vct{b}\},
\end{equation*}
where $\mtx{A}\in \R^{m\times n}$, $\vct{x}\in \R^d$ and $\vct{b}\in \R^m$. A vertex $\vct{z}$ of $P$ is a point of $P$ that can not
be expressed as a convex combination of distinct points in $P$.
For $\vct{z}\in P$, let $\mtx{A}_{\vct{z}}$ denote the matrix consisting of those rows $\vct{a}_i^{\trans}$ of $\mtx{A}$ where $\vct{a}_i^{\trans}\vct{z}=b_i$. For example, in Figure~\ref{fig:triangle} the matrix corresponding to the vertex $\vct{z}=(1,0)^{\trans}$ is given by
\begin{figure}[h!]
\centering
\begin{minipage}{0.3\textwidth}
\centering
\begin{tikzpicture}[thick,scale=1.5]
\draw[fill=blue!5] (-0,0)--(0,1)--(1,0)--(0,0);
%\draw[dashed,color=black!30,->] (0,0)--(1,1);
%\draw[dashed,color=black!30,->] (0,0)--(0,-1);
%\draw[dashed,color=black!30,->] (0,0)--(-1,0);
\end{tikzpicture}
\end{minipage}%
\begin{minipage}{0.7\textwidth}
\begin{equation*}
\mtx{A} = \begin{pmatrix}
1 & 1\\
-1 & 0\\
0 & -1\\
\end{pmatrix}, \quad
\vct{b} = \begin{pmatrix}
1 \\ 0 \\ 0
\end{pmatrix}, \quad
\mtx{A}_{\vct{z}} = \begin{pmatrix}
1 & 1\\
0 & -1
\end{pmatrix}.
\end{equation*}
\end{minipage}
\caption{A triangle}\label{fig:triangle}
\end{figure}
Show that the vertices of $P$ are precisely the points $\vct{z}$ for which $\mtx{A}_{\vct{z}}$ has rank $n$. In particular, every polyhedron has only finitely many vertices.
\problem (Text classification) Consider the vocabulary consisting of the words
\end{document}