text:
\documentclass[
    american,a4paper
    ]{scrartcl}

    \usepackage[a4paper,margin=2cm,includefoot]{geometry}

    % ##########################################
    % # Choose the language for the document by editing below line
    % # de = German
    % # en = English
    \newcommand{\lang}{en}
    % ##########################################

    \usepackage{babel}
    \usepackage[utf8]{inputenc}
    \usepackage{csquotes}
    \usepackage{enumitem}
    \usepackage{ifthen}
    \usepackage{lipsum}
    \usepackage{datetime}
    \usepackage{amsfonts}

    \include{translatedHeadings}
    \newcommand{\xmax}{x_{\max}}

    \ifthenelse{\equal{en}{\lang}}
    {
        \selectlanguage{american}
    }{
        \ifthenelse{\equal{de}{\lang}}
        {
            \selectlanguage{ngerman}
        }
        {\selectlanguage{american}}
    }

    \usepackage[
        bibencoding=utf8,
        style=alphabetic
    ]{biblatex}

    \bibliography{bibliography}

    \usepackage{amsmath}
    \title{
        % ##########################################
        % # Insert the title of your paper/thesis here
        % ######
        % Coming up with a good title is hard.
        % It should:
        %  1. capture the contents of the your work
        %  2. not be to broad or generic
        %  3. stick to the truth and don't not oversell
        %  4. use established terms and wordings
        %  5. make people curious about your work
        %  6. use current buzzwords if possilbe (but do it right)
        %  7. not use too many buzzwords :-)
        Modern Bayesian Optimization
        % ##########################################
        \\  \Large{\paperSubTitle{\lang}}} % don't touch this line

    \author{
        % ##########################################
        % # Your name goes here
        % ######
        % wWll, that should be obvious, right?
        Han Liang Wee Eric\\
        {\small PhD Student, NUS}
        % ##########################################
        }
    \date{\formatdate{28}{04}{2021}}
    \pdfinfo
    { /Title (Modern Bayesian Optimization)
    /Author (Han Liang Wee Eric)
    %  /CreationDate (D:YYYYMMDDhhmmss) % this is the format used by pdf for date/time
    %  /Subject (...)
    %  /Keywords ()
    }
    \begin{document}
      \maketitle
        \begin{abstract}

            % ##########################################
            % # Include your Abstract here
            % ######
            % I would strongly suggest to start working on the abstract only
            % after you have answered the 4 questions in Section 1, as this will
            % make it much easier for you to come up with an abstract that
            % is to the point, short, and still summarizing all the most crucial
            % results of your work.
            %
            % The abstract should include the following points:
            %  - a short but to the point introduction of the problem area
            %  - what is the topic/problem, tackled in your work?
            %  - why is the topic/problem of your work relevant? Why should the
            %    reader care about it?
            %  - what are the results/answers of your work?
            %  - how did you gain your results and what is their quality?
            %                %
            % It should NOT be:
            %  - too long/verbose
            %  - too short
            Bayesian Optimization (BO) has been successful (i.e. AlphaGo) in addressing expensive low-dimensional black-box optimization in small continuous search spaces.
            Modern application of machine learning often requires dealing with high-dimensional, often large datasets.
            In addition, search spaces for these problems are not always continuous and are sometimes discrete.
            The research goal is to understand and propose methods to enable the successful application of BO in the digital age.
            In this paper, recent research experiences and future research direction is discussed.
            First, BO and its successes and motivation for this research are briefly discussed.
            Here, we also discuss one of the recent publications dealing with adapting BO to higher dimensions.
            Finally, we present one future research direction in adapting BO to discrete search spaces: combinatorial Bayesian Optimization.
            % ##########################################

        \end{abstract}

        \section{Research Statement}

        \paragraph{Introduction to Bayesian Optimization.}
        Bayesian Optimization (BO) is a popular method for sequential global optimization, and is suited to situations in which the objective black-box function $f$ is expensive to evaluate \cite{snoek2012practical,mockus1994application}.
        For example, we consider finding $\xmax = \arg \max_{x \in {\mathcal X}} f(x)$ for some function $f$.
        If $f$ is known and known/assumed to be convex, we can simply apply convex optimization.
        However, $f$ is not known exactly and/or evaluations expensive and/or noisy in many real problems such as hyperparameter optimization.
        BO can overcome such conditions to find $\xmax$ with the \textit{least} possible number of observations by making two key assumptions:
        surrogate model that will capture our prior beliefs on $f$ and acquisition function that can be inexpensively optimized.
        BO translates the original problem to yet another optimization problem.
        Gaussian Processes (GP) are commonly used as the surrogate because it allows us to model the prior and marginal log-likelihood.
        \paragraph{Motivation.}
        BO has found success in many areas;
        most notably in automatically tuning the game playing hyperparameters of AlphaGo \cite{chen2018bayesian}.
        BO enhanced the playing power of AlphaGo while decreasing resources needed for manual tuning.
        However, such success have been often found in low dimensional \cite{wang2013bayesian} continuous spaces \cite{7352306} with small datasets \cite{ambikasaran2015fast}.
        \paragraph{Active Research.}
        From the lines of inquiry, we discuss possible research directions below:
        \begin{itemize}
            \item \underline{Scaling to higher dimensions:} two approaches via making additional assumptions,
            \begin{itemize}
                \item \underline{Low effective dimensionality,} only few dimensions significantly affect $f$ \cite{chen2012joint}.
                \item \underline{Additive structure,} small subsets of variables interact with each other \cite{kandasamy2015high}.
            \end{itemize}
            \item \underline{Adapting to discrete spaces:} various approaches to tackle the problem,
            \begin{itemize}
                \item \underline{Replace/adapt surrogate model} with random forests or another suitable model \cite{hutter2013evaluation}.
                \item \underline{Introduce smoothness}, attempting to coerce discrete spaces into continous spaces \cite{oh2019combinatorial}.
                \item \underline{Feature engineering}, through feature expansion of discrete with continous variables \cite{daxberger2019mixed}.
            \end{itemize}
            \item \underline{Scaling to more observations:} two common approaches,
            \begin{itemize}
                \item \underline{Replace surrogate model}, similar to above, with another suitable model \cite{hutter2011sequential}.
                \item \underline{Introduce efficient matrix operations}, such as sparsification of covariance matrix \cite{seeger2003fast}.
            \end{itemize}
        \end{itemize}
        We are also interested in other adjacent directions, such as: improving the robustness of BO methods.

        We recently discussed a method via the additive structure assumption \cite{han2020high},
        where we facilitate faster model learning by \emph{reducing the model complexity} while retaining the \emph{sample-efficiency} of existing additive methods.
        Specifically, we constrain the underlying additive structure to trees, so we facilitate scalable learning of the structure learning and optimization of the acquisition function.
        We show that our method is competitive on datasets, and the computation can be significantly reduced while maintaining optimization performance.
        \section{Research Proposal}
        Here, we focus our discussion on adapting BO to discrete spaces.
        Most BO methods are focused on continuous search spaces due to the underlying assumption of using GPs as the prior,
        which relies on the smoothness defined by a kernel to model uncertainty.
        Real-world problems can have a mix of both ordinal and categorical variables, presenting the following issues, that BO is suited to solve:
        \begin{enumerate}
            \item black-box objectives for which gradient-based optimizers are not amenable.
            \item expensive evaluation procedures for which methods with low sample efficiency.
            \item noisy and highly non-linear objectives for which simple and exact solutions are inaccurate.
        \end{enumerate}
        There have been attempts to adapt BO to this problem by simply using continuous kernels and augment the result to become discrete.
        However, some combinations of discrete variables are impossible configurations, and it is difficult for the model to capture.

        \begin{description}[style=unboxed]
            \item [\questionOne{\lang}]
                % ##########################################
                % # Question 1: What is the problem you want to address in your work? /
                %               Was ist das Problem, welches Sie in Ihrer Arbeit bearbeiten wollen?
                % ######
                % The goal of this question is to clearly state what your work is about.
                % What is the problem it is supposed to solve?
                %
                % Answering this question is particular important during the early phases
                % of your work, in order to gain further insight and understanding about what
                % your work is going to cover and address.
                %
                % Answer this question very briefly by stating the problem or research
                % question that you want to address/solve in your work.
                %
                % Your answer should:
                %  - only be 1 sentence (2 sentences max)
                %  - not cover a statement why the topic is relevant
                %    for the industry (this is address by the next question)
                %  - properly use common terms and buzzwords of IT today (similar to the
                %    rules for the abstract)
                %
                % Please acknowledge: the answer to this question should not cover why the
                % problem is important or relevant to anyone (e.g. industry). This will
                % be addressed with the next question.
                Combinatorial Bayesian Optimization, to extend BO to discrete spaces.
                Our method should also work on mixed spaces, ie. both continuous and discrete spaces.
                % ##########################################

            \item [\questionTwo{\lang}]
                % ##########################################
                % # Question 2: Why is it a problem? / Warum ist es ein Problem?
                % ######
                % The goal of this question is to describe why your work is relevant.
                % Why should the reader care? Why is this the problem (of question 1)
                % worth investigating?
                %
                % Answering this question is particular important during the early phases
                % of your work, in order to gain further insight and understanding of the
                % problem domain you are addressing. Further, it is a good checkpoint to
                % ensure that you are addressing issues that are not just theoretical but
                % have real-world applications.
                %
                % Your answer should:
                %  - be 3 - 5 sentences
                %  - give a broader overview of the domain/area where your problem occurs
                %  -- who has this problem?
                %  -- what is the impact of it?
                %  -- which conditions need to be fulfilled for the problem to occur?
                %  -- etc.
                %  - describe the benefit of having the problem resolved
                Optimization in structured domains using BO was raised in \cite{NeurIPS2017};
                BO has sample efficiency and global optimum convergence advantages when compared to other approaches such as evolution or genetic algorithms.
                An application would be deciding on a deep neural network architecture where the parameters may depend on the number of layers \cite{bengio2009learning}.
                There have been attempts to tackle this problem simply using continuous kernels in BO and augment the result to become discrete.
                However, some combinations of discrete variables are impossible configurations that are complex for the model to capture.
                It faces the problem of combinatorial explosion, as instead of modelling the structural dependencies,
                BO embed the discrete variables into a $\mathbb{R}^d$ box.
                These methods work but heavily rely on discretization.
                % ##########################################

            \item [\questionThree{\lang}]
                % ##########################################
                % # Question 3: What is the solution you developed in your work? /
                %               Was ist die Lösung die sie entwickelt haben?
                % ######
                % The goal of this question is to describe the results of your work
                % ans/or solution to the problem of your work.
                %
                % It is hard/impossible to answer this question in the early phases of
                % your work, as usually you do not have results, yet. However, you can
                % already state first ideas that you may have in order to discuss them
                % with your supervisor.
                %
                % Your answer should:
                %  - clearly state all results of your work, that are relevant to your
                %    research problem.
                %  - not oversell your results, stick you what you actually have
                %    accomplished"
                %  - give credit where credit is due. If you created your results based
                %    on the work of others, give them the credit.
                %  - if none of your ideas did not produce any usable solution, state
                %    so - these attempts are also results! By documenting them, it may
                %    prevent others from trying them as well.
                We focus on the important considerations of: allowing information sharing via encoding relationships between the variables (both ordinal and categorical),
                efficiently optimize the discrete variables (selection of the next discrete values) with high sample and computational efficiency,
                encode the constraints between the variables, allowing the model to exploit them.
                We extend COMBO \cite{oh2019combinatorial}, where GP surrogate model is defined over the graph using Graph Fourier Transform (GFT).
                Instead of using an ordered sub-graph for every continuous variable, we do not discretize, considering the continuous variables outside of the graph structure.
                It might be possible to define a kernel grammar over continuous and discrete variables by treating them separately.
                % ##########################################

            \item [\questionFour{\lang}]
                % ##########################################
                % # Question 4: Why is it a solution? / Warum ist es eine Lösung?
                % ######
                % The goal of this question is to describe who you developed your results
                % and what the quality of them are.
                %
                % Your answer should:
                %  - short and to the point
                %  - clearly state how you developed your results
                %  -- what is the chain of reasoning that led to your results/solution
                %  -- what statistics, literature, studies, or other literature did you
                %     base your assumptions on?
                %  - clearly state the quality and applicability of your results
                %  -- reflect your work objectively - there is no perfection in this
                %     world, so your work is not perfect as well. Be aware of that!
                %  -- how did you ensure that your results are accurate? did you:
                %  --- perform experiments?
                %  --- apply any logical deductions?
                %  --- mathematical proofs?
                %  --- implement a "proof of concept" implementation and evaluate?
                %  --- etc.
                %  - clearly state the shortcomings of your work
                %  -- be hones and objective about your own work.
                %  -- In which cases/scenarios are your results applicable?
                COMBO uses hamming distance on both continuous and discrete variables, which works well on discrete variables.
                Hamming distance is an unnatural metric on continuous spaces, which should be instead modelled using a continuous distribution.
                There might be some penalty associated with GFT, such as performance issues, which might need to be addressed.
                % ##########################################
        \end{description}

        \sectionSource{\lang}
        \sectionSourceDescription{\lang}

        % ##########################################
        % # Overview of identified relevant work
        % ######
        % The goal of this section is to provide an overview of the relevant and significant
        % related work identified so far. Make sure that your cited sources are of appropriate
        % quality!
        %
        % Please include:
        %  - a citation of the source using Latex facilities (incl. a generated list of
        %    references)
        %  - a brief descriptions of the source and a statement why this is relevant for
        %    your work (1-2 sentences)
        %
        \begin{description}
            \item[\cite{pmlr-v124-swersky20a}] Use generative model to generate candidates for acquisition optimization. Implementation at \url{https://github.com/google-research/google-research/tree/master/amortized_bo}.
            \item[\cite{daxberger2019mixed}] Decouples the continuous and discrete components of the function using feature expansion. No implementation published.
            \item[\cite{oh2019combinatorial}] Use a combinatorial graph to quantify smoothness on combinatorial search spaces. Implementation at \url{https://github.com/QUVA-Lab/COMBO}.
            \item[\cite{baptista2018bayesian}] Uses second order regression modelling of the interactions. Implementation at \url{https://github.com/baptistar/BOCS}.
            \item[\cite{pmlr-v70-jenatton17a}] Use a surrogate tree model where GPs are at the leafs. No implementation published.
        \end{description}
        Other related methods:
        \begin{enumerate}
            \item Traditional methods; generally not sample efficient and may not converge to global optimum (although sometimes, convergence is guaranteed).
            \begin{enumerate}
                \item Local search methods such as random optimization, hill climbing, simulated annealing, etc.
                \item Evolutionary algorithms.
            \end{enumerate}
            \item Related BO methods; generally unable to handle general constraints over the discrete variables.
            \begin{enumerate}
                \item SMAC \cite{hutter2011sequential} is a BO that uses random forests as a surrogate model, which accommodates mixed variable inputs. However, there are limitations as the frequentist uncertainty estimate provided by random forests may suffer from variance degradation.
                \item TPE \cite{bergstra2013making} uses a non-parametric kernel density estimator to identify inputs, likely to improve upon and unlikely to perform worse than the best input found so far.
            \end{enumerate}
            \item Hyperband \cite{li2017hyperband} is a variant of random search that exploits cheap but less accurate approximations of the objective to allocate resources for function evaluations dynamically.
            \item BOHB \cite{falkner2018bohb} is the model-based counterpart of Hyperband, based on TPE.
            \item Arc-Kernel \cite{swersky2014raiders} is a kernel designed to encode information about which parameters are relevant in a given structure.
        \end{enumerate}
        % ##########################################
      \section*{Acknowledgements}
      We adapted this research template from \cite{Stefan2018}.
      This work is done in collaboration with my PhD supervisor, Prof. Scarlett Jonathan.
      His patience and guidance are greatly appreciated, without which the research would not be possible;
      to family and friends who are of great support.
      \newpage
      \printbibliography
    \end{document}

max_stars_repo_name: eric-vader/research-proposal-template

max_issues_repo_name: eric-vader/research-proposal-template

max_forks_repo_name: eric-vader/research-proposal-template


text:
\section{Patterns}
Patterns are used in the left-hand-side of where and let bindings, in the clauses of matches and in the declarations of functions.

There are several different patterns that can occur in an Amulet program. Though this is a fixed set, they can be combined to match against more complicated data.

\begin{grammar}
<pattern> ::= <literal>
         \alt `(' <pattern> `)'
         \alt `_'
         \alt <var>
         \alt <var> '@' <pattern>
         \alt <constructor pattern>
         \alt <list pattern>
         \alt <vector pattern>
         \alt <tuple pattern>
         \alt <record pattern>
\end{grammar}

\subsection{Wildcards}
Denoted by \texttt{_}, this pattern matches anything and does no binding. As an example, \texttt{let _ = x in e} discards the value x (and is optimized to \texttt{e}). Formally, the set of free variables of an expression in the scope created by a \texttt{_} binder is the same as the set of free variables of the expression.

\subsection{Literal Patterns}
These match against a given literal, that is, a number, string, or character, and bind nothing. Matching on a string is equivalent to matching on a vector of characters. These patterns, however, are not free, as they entail an \texttt{Eq} constraint on the parameter.

\subsection{Capturing patterns}
These can be any valid identifier, matching anything and binding them to the given name. These are semantically equivalent to \texttt{name@_}.

\subsection{At-patterns}
At-patterns are a way to give an otherwise nameless pattern a name. An at-pattern will bind its name to the match of the pattern it was created from in the resulting scope. These take the form of \texttt{name@pattern}.

\subsection{List and Vector Patterns}
List pattern matching syntax exists as syntactic sugar for repeated matching against the \texttt{(::)} constructor. They match against a list of exact size. \texttt{[x,y,z]} is equivalent to \texttt{x::y::z::[]}, where \texttt{x}, \texttt{y} and \texttt{z} are patterns. For matching against a list of at least N elements, the syntax \texttt{[x,y,z] :- xs} is allowed, where \texttt{x}, \texttt{y}, \texttt{z}, and \texttt{xs} are patterns. This is equivalent to \texttt{x::y::z::xs}.

Like list constructing, the destructor is polymorphic across all types within the $\mathtt{List}\ h\ t\ r$ class, allowing matching in the same style as constructing.

The same sugar exists for vectors, but this is builtin rather than sugar. \texttt{[| x, y, z |]} matches against a 3-element vector, while \texttt{[| x, y, z |] :- xs} matches against a vector of \textit{at least} 3 elements. The typical way of matching against the head/tail of a vector is \texttt{[|x|] :- xs}.

\begin{grammar}
<list pattern contents> ::= `'
                       \alt <pattern> \{ `,` <pattern \} [`,']

<list pattern>          ::= `[' <list pattern contents> `]'

<vector pattern>        ::= `[|' <vector pattern contents> `|]'
                       \alt <pattern> `:-' <pattern>
\end{grammar}

\subsection{Tuple patterns}
Tuple patterns are used to extract multiple variables from tuples

\begin{grammar}
<tuple pattern> ::= `(' <pattern> \{ `,' <pattern> \} [`,'] `)'
\end{grammar}

\subsection{Constructor Patterns}
Constructor patterns match against a value constructor, and thus are used for destructuring abstract data, such as lists. Obviously constructor patterns can be used to match against the multiple cases of sum types.

The basic form is \texttt{Name}. This matches against a nullary constructor. For constructors with more fields, the form is \texttt{(Name p$_1$ … p$_n$)}. This binds everything that the set of \texttt{p$_1$ … p$_n$} binds. For example, \texttt{(Ratio\ _\ _)} doesn’t bind anything.

As with functions, constructors can be matched (and applied) in infix form. For example, \texttt{(_\ \`{}Ratio\`{}\ _)} is equivalent to \texttt{(Ratio\ _\ _)}

\begin{grammar}
<constructor pattern> ::= <name> \{ <pattern> \}
                     \alt <pattern> <name> <pattern>
                     \alt <pattern> \lit{\`{}} <name> \lit{\`{}} <pattern>
\end{grammar}

\subsubsection{Record Patterns}
Record patterns are used to match over records. They share the same syntax as record constructors, though with pattern on the RHS rather than expressions:

\begin{grammar}
<record field ptrn>  ::= <identifier> `=' <expr>

<record fields ptrn> ::= <record field ptrn> \{ `,' <record field ptrn> \} [`,']

<record ptrn> ::= `\{' `\}'
        \alt `\{' <record fields ptrn> `\}'
        \alt `\{' <ptrn> `|' <record fields ptrn> `\}'
\end{grammar}

It is worth noting that this pattern requires that the specified fields exist on the matchee. For instance the following would not typecheck:

\begin{minted}{ocaml}
match { x = 1 } with
| { x = a, y = b } -> sqrt $ a^2 + b^2
| _ -> 0
\end{minted}

As the \texttt{y} field does not appear on the matchee.

ext: tex

max_stars_repo_name: SquidDev/amulet

max_issues_repo_name: SquidDev/amulet

max_forks_repo_name: SquidDev/amulet


text:
\section{Optimization Problems}\label{sec:Optimization}

Many important applied problems involve finding the best way to
accomplish some task. Often this involves finding the maximum or
minimum value of some function: the minimum time to make a certain
journey, the minimum cost for doing a task, the maximum power that can
be generated by a device, and so on. Many of these problems can be
solved by finding the appropriate function and then using techniques
of calculus to find the maximum or the minimum value required.

Generally such a problem will have the following mathematical form:
Find the largest (or smallest) value of $f(x)$ when $a\le x\le
b$. Sometimes $a$ or $b$ are infinite, but frequently the real world
imposes some constraint on the values that $x$ may have.

Such a problem differs in two ways from the local maximum and minimum
problems we encountered when graphing functions: We are interested
only in the function between $a$ and $b$, and we want to know the
largest or smallest value that $f(x)$ takes on, not merely values that
are the largest or smallest in a small interval. That is, we seek not
a local maximum or minimum but a \ifont{global} (or \ifont{absolute})
maximum or minimum.

\begin{formulabox}[Guidelines to solving an optimization problem.]
\begin{enumerate}
	\item Understand clearly what is to be maximized or minimized and what the contraints are.
	\item Draw a diagram (if appropriate) and label it.
	\item Decide what the variables are. For example, $A$ for area, $r$ for radius, $C$ for cost.
	\item Write a formula for the function for which you wish to find the maximum or minimum.
	\item Express that formula in terms of only one variable, that is, in the form $f(x)$. Usually this
				is accomplished by using the given constraints.
	\item Set $f'(x)=0$ and solve. Check all critical values and endpoints to determine the extreme value(s) of $f(x)$.
\end{enumerate}
\end{formulabox}

\begin{example}{Largest Rectangle}{largestrectangle}
 Find the largest rectangle (that is, the rectangle with largest
area) that fits inside the graph of the parabola $\ds y=x^2$ below the
line $y=a$ ($a$ is an unspecified constant value), with the top side of
the rectangle on the horizontal line $y=a$; see
Figure~\ref{fig:rectangle optimization}.)
\end{example}

\begin{solution}
We want to find the maximum value of some function $A(x)$ representing
area.  Perhaps the hardest part of this problem is deciding what $x$
should represent. The lower right corner of the rectangle is at
$\ds (x,x^2)$, and once this is chosen the rectangle is completely
determined. So we can let the $x$ in $A(x)$ be the $x$ of the parabola
$\ds f(x)=x^2$.  Then the area is
$$
	A(x)=(2x)(a-x^2)=-2x^3+2ax.
$$
We want
the maximum value of $A(x)$ when $x$ is in $\ds [0,\sqrt{a}]$. (You might
object to allowing $x=0$ or $\ds x=\sqrt{a}$, since then the ``rectangle''
has either no width or no height, so is not ``really'' a
rectangle. But the problem is somewhat easier if we simply allow such
rectangles, which have zero area.)

Setting $\ds 0=A'(x)=6x^2+2a$ we get $\ds x=\sqrt{a/3}$ as the only critical
value. Testing this and the two endpoints, we have
$\ds A(0)=A(\sqrt{a})=0$ and $\ds A(\sqrt{a/3})=(4/9)\sqrt{3}a^{3/2}$. The
maximum area thus occurs when the rectangle has dimensions
$\ds 2\sqrt{a/3}\times (2/3)a$.
\end{solution}

\figure[H]
\centerline{\vbox{\beginpicture
		\normalgraphs
		%\ninepoint
		\setcoordinatesystem units <1.25truecm,0.6truecm>
		\setplotarea x from -3 to 3, y from 0 to 9
		\axis left shiftedto x=0 /
		\axis bottom shiftedto y=0 /
		\setquadratic
		\plot  -3 9 0 0 3 9 /
		\setlinear
		\putrule from -1.5 2.25 to 1.5 2.25
		\putrule from -1.5 2.25 to -1.5 7
		\putrule from 1.5 2.25 to 1.5 7
		\putrule from -1.5 7 to 1.5 7
		\put {$y=a$} [l] <5pt,0pt> at 3 7
		\put {$(x,x^2)$} [tl] <3pt,-1pt> at 1.5 2.25
		\put {$\bullet$} at 1.5 2.25
		\setdashes
		\plot -3 7 3 7 /
		\endpicture}}
\caption{Rectangle in a parabola. \label{fig:rectangle optimization}}
\endfigure

\begin{example}{Largest Cone}{largestcone}
If you fit the largest possible cone inside a sphere, what fraction of the
volume of the sphere is occupied by the cone?  (Here by ``cone'' we mean a
right circular cone, i.e., a cone for which the base is perpendicular to
the axis of symmetry, and for which the cross-section cut perpendicular to
the axis of symmetry at any point is a circle.)
\end{example}

\begin{solution}
Let $R$ be the radius of the sphere, and let $r$ and $h$ be the base radius
and height of the cone inside the sphere.  What we want to maximize is the
volume of the cone: $\ds \pi r^2h/3$.  Here $R$ is a fixed value, but
$r$ and $h$ can vary.  Namely, we could choose $r$ to be as large as
possible---equal to $R$---by taking the height equal to $R$; or we
could make the cone's height $h$ larger at the expense of making $r$ a
little less than $R$.  See the cross-section depicted in
Figure~\ref{fig:cone in sphere}. We
have situated the picture in a convenient way relative to the $x$ and
$y$ axes, namely, with the center of the sphere at the origin and the
vertex of the cone at the far left on the $x$-axis.

Notice that the function we want to maximize, $\ds \pi r^2h/3$,
depends on {\it two} variables.  This is frequently the case, but
often the two variables are related in some way so that ``really''
there is only one variable. So our next step is to
find the relationship and use it to solve for one of the variables in
terms of the other, so as to have a function of only one variable to
maximize.  In this problem, the condition is apparent in the figure:
the upper corner of the triangle, whose coordinates are $(h-R,r)$,
must be on the circle of radius $R$.  That is,
$$
	(h-R)^2+r^2=R^2.
$$
We can solve for $h$ in terms of $r$ or for $r$ in terms of $h$.
Either involves taking a square root, but we notice that the volume
function contains $\ds r^2$, not $r$ by itself, so it is easiest to solve
for $\ds r^2$ directly: $\ds r^2=R^2-(h-R)^2$.
Then we substitute the result into $\ds \pi r^2h/3$:
\begin{eqnarray*}
V(h)&=\pi(R^2-(h-R)^2)h/3\cr
&=-{\pi\over3}h^3+{2\over3}\pi h^2R\cr
\end{eqnarray*}
We want to maximize $V(h)$ when $h$ is between 0 and $2R$.  Now we
solve $\ds 0=f'(h)=-\pi h^2+(4/3)\pi h R$, getting $h=0$ or $h=4R/3$.
We compute $V(0)=V(2R)=0$ and $\ds V(4R/3)=(32/81)\pi R^3$. The maximum is
the latter; since the volume of the sphere is $\ds (4/3)\pi R^3$, the
fraction of the sphere occupied by the cone is
$${(32/81)\pi R^3\over (4/3)\pi R^3}={8\over 27}\approx 30\%.$$
\end{solution}

\figure[H]
\centerline{\vbox{\beginpicture
		\normalgraphs
		%\ninepoint
		\setcoordinatesystem units <2cm,2cm>
		\setplotarea x from -1.2 to 1.2, y from -1.2 to 1.2
		\axis left shiftedto x=0 /
		\axis bottom shiftedto y=0 /
		\setquadratic
		\circulararc 360 degrees from 1 0 center at 0 0
		\setlinear
		\plot -1 0 0.5 .866 0.5 -0.866 -1 0 /
		\put {$(h-R,r)$} [bl] <2pt,2pt> at 0.5 .866
		\endpicture}}
\caption{Cone in a sphere. \label{fig:cone in sphere}}
\endfigure

\begin{example}{Containers of Given Volume}{containersvolume}
You are making cylindrical containers to contain a given volume.  Suppose
that the top and bottom are made of a material that is $N$ times as
expensive (cost per unit area) as the material used for the lateral side of
the cylinder.

Find (in terms of $N$) the ratio of height to base radius of
the cylinder that minimizes the cost of making the containers.
\end{example}

\begin{solution}
Let us first choose letters to represent various things: $h$ for the
height, $r$ for the base radius, $V$ for the volume of the
cylinder, and $c$ for the cost per unit area of the lateral side of
the cylinder; $V$ and $c$ are constants, $h$ and $r$ are variables.
Now we can write the cost of materials:
$$
  c(2\pi rh)+Nc(2\pi r^2).
$$
Again we have two variables; the relationship is provided by the fixed
volume of the cylinder: $\ds V=\pi r^2h$. We use this
relationship to eliminate $h$ (we could eliminate $r$, but it's a little easier
if we eliminate $h$, which appears in only one place in the above formula
for cost).  The result is
$$
   f(r)=2c\pi r{V\over\pi r^2}+2Nc\pi r^2={2cV\over r}+2Nc\pi r^2.
$$
We want to know the minimum value of this function when $r$ is in
$(0,\infty)$.
We now set $\ds 0=f'(r)=-2cV/r^2+4Nc\pi
r$, giving $\ds r={\root 3 \of {V/(2N\pi)}}$.
Since $\ds f''(r)=4cV/r^3+4Nc\pi$ is positive when $r$ is positive, there
is a local minimum at the critical value, and hence a global minimum
since there is only one critical value.

Finally, since $\ds h=V/(\pi r^2)$,
$$
{h\over r}={V\over\pi r^3}={V\over \pi(V/(2N\pi))}=2N,
$$
so the minimum cost occurs when the height $h$ is $2N$ times the
radius. If, for example, there is no difference in the cost of
materials, the height is twice the radius (or the height is equal to
the diameter).
\end{solution}

\begin{example}{Rectangles of Given Area}{rectanglesofgivenarea}
Of all rectangles of area 100, which has the smallest perimeter?
\end{example}

\begin{solution}
First we must translate this into a purely mathematical problem in
which we want to find the minimum value of a function.
If $x$ denotes one of the sides of the rectangle, then the adjacent side
must be $100/x$ (in order that the area be 100).  So the function we want
to minimize is
$$
  f(x)=2x+2{100\over x}
$$
since the perimeter is twice the length plus twice the width of the
rectangle. Not all values of $x$ make sense in this problem: lengths
of sides of rectangles must be positive, so $x>0$. If $x>0$ then so is
$100/x$, so we need no second condition on $x$.

We next find $f'(x)$ and set it equal to zero: $\ds 0=f'(x)=2-200/x^2$.
Solving $f'(x)=0$ for $x$ gives us $x=\pm 10$. We are interested only
in $x>0$, so only the value $x=10$ is of interest. Since $f'(x)$ is
defined everywhere on the interval $(0,\infty)$, there are no more
critical values, and there are no endpoints. Is there a local maximum,
minimum, or neither at $x=10$? The second derivative is
$\ds f''(x)=400/x^3$, and $f''(10)>0$, so there is a local minimum. Since
there is only one critical value, this is also the global minimum, so the
rectangle with smallest perimeter is the $10\times10$ square.
\end{solution}

\begin{example}{Maximize your Profit}{maximizeyourprofit}
You want to sell a certain number $n$ of items in order to maximize your
profit.  Market research tells you that if you set the price at \$1.50, you
will be able to sell 5000 items, and for every 10 cents you lower the price
below \$1.50 you will be able to sell another 1000 items.  Suppose that
your fixed costs (``start-up costs'') total \$2000, and the per item cost
of production (``marginal cost'') is \$0.50.

Find the price to set per
item and the number of items sold in order to maximize profit, and also
determine the maximum profit you can get.
\end{example}

\begin{solution}
The first step is to convert the problem into a function maximization
problem. Since we want to maximize profit by setting the price per
item, we should look for a function $P(x)$ representing the profit
when the price per item is $x$. Profit is revenue minus costs, and
revenue is number of items sold times the price per item, so we get
$P=nx-2000-0.50n$. The number of items sold is itself a function of
$x$, $n=5000+1000(1.5-x)/0.10$, because $ (1.5-x)/0.10$ is the number
of multiples of 10 cents that the price is below \$1.50.
Now we substitute for $n$ in the profit function:
\begin{eqnarray*}
  P(x)&=(5000+1000(1.5-x)/0.10)x-2000- 0.5(5000+1000(1.5-x)/0.10)\cr
&=-10000x^2+25000x-12000\cr
\end{eqnarray*}
We want to know the maximum value of this function when $x$ is
between 0 and $1.5$. The derivative is $P'(x)=-20000x+25000$, which
is zero when $x=1.25$. Since $P''(x)=-20000<0$, there must be a local
maximum at $x=1.25$, and since this is the only critical value it must
be a global maximum as well. (Alternately, we could compute
$P(0)=-12000$, $P(1.25)=3625$, and $P(1.5)=3000$ and note that
$P(1.25)$ is the maximum of these.) Thus the maximum profit is \$3625,
attained when we set the price at \$1.25 and sell 7500 items.
\end{solution}

\begin{example}{Minimize Travel Time}{minimizetraveltime}
 Suppose you want to reach a point $A$ that is located across the
sand from a nearby road (see Figure~\ref{fig:minimize travel time}).
Suppose that the road is straight, and $b$ is the distance from $A$ to
the closest point $C$ on the road.  Let $v$ be your speed on the road,
and let $w$, which is less than $v$, be your speed on the sand.  Right
now you are at the point $D$, which is a distance $a$ from $C$.  At
what point $B$ should you turn off the road and head across the sand
in order to minimize your travel time to $A$?
\end{example}

\begin{solution}
Let $x$ be the distance short of $C$ where you turn off, i.e., the distance
from $B$ to $C$.  We want to minimize the total travel time.  Recall
that when traveling at constant velocity, time is distance divided by velocity.

You travel the distance
$\ds \overline{DB}$ at speed $v$, and then the distance $\ds \overline{BA}$ at
speed $w$.  Since $\ds \overline{DB}=a-x$ and, by the Pythagorean theorem,
$\ds \overline{BA}=\sqrt{x^2+b^2}$, the total time for the trip is
$$
   f(x)={a-x\over v}+{\sqrt{x^2+b^2}\over w}.
$$
We want to find the minimum value of $f$ when $x$ is between 0 and $a$.
As usual we
set $f'(x)=0$ and solve for $x$:
$$
\displaylines{
  0=f'(x)=-{1\over v}+{x\over w\sqrt{x^2+b^2}}\cr\\
  w\sqrt{x^2+b^2}=vx\cr\\
  w^2(x^2+b^2) = v^2x^2\cr\\
w^2b^2=(v^2-w^2)x^2\cr\\
x={wb\over\sqrt{v^2-w^2}}
}$$
Notice that $a$ does not appear in the last expression, but $a$ is not
irrelevant, since we are interested only in critical values that are
in $[0,a]$, and $\ds wb/\sqrt{v^2-w^2}$ is either in this interval or not.
If it is, we can use the second derivative to test it:
$$
f''(x) = {b^2\over (x^2+b^2)^{3/2}w}.
$$
Since this is always positive there is a local minimum at the critical
point, and so it is a global minimum as well.

If the critical value is not in $[0,a]$ it is larger than $a$. In this
case the minimum must occur at one of the endpoints. We can compute
\begin{eqnarray*}
f(0)&=\ds{a\over v}+{b\over w}\cr
\\
f(a)&=\ds{\sqrt{a^2+b^2}\over w}\cr
\end{eqnarray*}
but it is difficult to determine which of these is smaller by direct
comparison. If, as is likely in practice, we know the values of $v$,
$w$, $a$, and $b$, then it is easy to determine this. With a little
cleverness, however, we can determine the minimum in general. We have seen that
$f''(x)$ is always positive, so the derivative $f'(x)$ is always increasing.
We know that at $\ds wb/\sqrt{v^2-w^2}$ the derivative is zero, so for
values of $x$ less than that critical value, the derivative is
negative. This means that $f(0)>f(a)$, so the minimum occurs when $x=a$.

So the upshot is this: If you start farther away from $C$ than
$\ds wb/\sqrt{v^2-w^2}$ then you always want to cut across the sand
when you are a distance $\ds wb/\sqrt{v^2-w^2}$ from point $C$. If you
start closer than this to $C$, you should cut directly across the sand.
\end{solution}

\figure[H]
\centerline{\vbox{\beginpicture
		\normalgraphs
		%\ninepoint
		\setcoordinatesystem units <1cm,1cm>
		\setplotarea x from 0 to 5, y from 0 to 3
		\axis bottom shiftedto y=0 /
		\setlinear
		\setplotsymbol ({\tenrm.})
		\plot 1 0 2.5 0 4 3 /
		\setdashes
		\putrule from 4 0 to 4 3
		\multiput {$\bullet$} at 1 0 2.5 0 4 3 4 0 /
		\put {$x$} [b] <0pt,3pt> at 3.25 0
		\put {$a-x$} [b] <0pt,3pt> at 1.75 0
		\put {$A$} [b] <0pt,4pt> at 4 3
		\put {$D$} [t] <0pt,-4pt> at 1 0
		\put {$B$} [t] <0pt,-4pt> at 2.5 0
		\put {$C$} [t] <0pt,-4pt> at 4 0
		\put {$b$} [l] <3pt,0pt> at 4 1.5
		\endpicture}}
\caption{Minimizing travel time. \label{fig:minimize travel time}}
\endfigure

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Opensolutionfile{solutions}[ex]
\section*{Exercises for Section \ref{sec:Optimization}}

\begin{enumialphparenastyle}

%%%%%%%%%%%
%\begin{ex}
%Let $\ds f(x) = \cases{1 + 4 x -x^2 & for $x\leq3$\cr
%            (x+5)/2          &for $x>3$\cr}$
%
%\item{} Find the maximum value and minimum values of $f(x)$ for $x$ in $[0,4]$.
%Graph $f(x)$ to check your answers.
%\begin{sol}
% max at $(2,5)$, min at $(0,1)$
%\end{sol}
%\end{ex}

%%%%%%%%%%
\begin{ex}
Find the dimensions of the rectangle of largest area having fixed perimeter $100$.
\begin{sol}
 $25\times 25$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
Find the dimensions of the rectangle of largest area having fixed perimeter
$P$.
\begin{sol}
 $P/4\times P/4$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
A box with square base and no top is to hold a volume $100$.  Find
the dimensions of the box that requires the least material for the
five sides.  Also find the ratio of height to side of the base.
\begin{sol}
 $\ds w=l=2\cdot 5^{2/3}$, $\ds h=5^{2/3}$, $\ds h/w=1/2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 A box with square base is to hold a volume
$200$. The bottom and top are formed by folding in flaps from all four
sides, so that the bottom and top consist of two layers of cardboard.
Find the dimensions of the box that requires the least material.
Also find the ratio of height to side of the base.
\begin{sol}
 $\ds \root 3\of {100}\times\root 3\of {100}\times 2\root 3\of
{100}$, $h/s=2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
A box with square base and no top is to hold a volume $V$.  Find (in terms
of $V$) the dimensions of the box that requires the least material for the
five sides.  Also find the ratio of height to side of the base.  (This
ratio will not involve $V$.)
\begin{sol}
 $\ds w=l=2^{1/3}V^{1/3}$, $\ds h=V^{1/3}/2^{2/3}$, $h/w=1/2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
You have $100$ feet of fence to make a rectangular play area alongside the
wall of your house.  The wall of the house bounds one side.  What is the
largest size possible (in square feet) for the play area?
\begin{sol}
 $1250$ square feet
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
You have $l$ feet of fence to make a rectangular play area alongside the
wall of your house.  The wall of the house bounds one side.  What is the
largest size possible (in square feet) for the play area?
\begin{sol}
 $\ds l^2/8$ square feet
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
\label{ex:manufacturing}
Marketing tells you that if you set the price of an item at \$10
then you will be unable to sell it, but that you can sell 500 items for
each dollar below \$10 that you set the price.  Suppose your fixed costs total
\$3000, and your marginal cost is \$2 per item.  What is the most profit
you can make?
\begin{sol}
 \$5000
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
Find the area of the largest rectangle that fits inside a semicircle of
radius $10$ (one side of the rectangle is along the diameter of the
semicircle).
\begin{sol}
 $100$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
Find the area of the largest rectangle that fits inside a semicircle of
radius $r$ (one side of the rectangle is along the diameter of the
semicircle).
\begin{sol}
 $\ds r^2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
For a cylinder with surface area $50$, including
the top and the bottom, find the ratio of height to
base radius that maximizes the volume.
\begin{sol}
 $h/r=2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
For a cylinder with given surface area $S$, including
the top and the bottom, find the ratio of height to
base radius that maximizes the volume.
\begin{sol}
 $h/r=2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
You want to make cylindrical containers to hold 1 liter using the
least amount of construction material.  The side is made from a
rectangular piece of material, and this can be done with no material
wasted.  However, the top and bottom are cut from squares of side $2r$, so
that $\ds 2(2r)^2=8r^2$ of material is needed (rather than $\ds 2\pi r^2$, which is
the total area of the top and bottom).  Find the dimensions of the
container using the least amount of material, and also find the
ratio of height to
radius for this container.
\begin{sol}
 $r=5$, $h=40/\pi$, $h/r=8/\pi$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
You want to make cylindrical containers of a given volume $V$ using the
least amount of construction material.  The side is made from a
rectangular piece of material, and this can be done with no material
wasted.  However, the top and bottom are cut from squares of side $2r$, so
that $\ds 2(2r)^2=8r^2$ of material is needed (rather than $\ds 2\pi r^2$, which is
the total area of the top and bottom).  Find the optimal ratio of height to
radius.
\begin{sol}
 $8/\pi$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
Given a right circular cone, you put an upside-down cone inside it so that
its vertex is at the center of the base of the larger cone and its base is
parallel to the base of the larger cone.  If you choose the upside-down
cone to have the largest possible volume, what fraction of the volume of
the larger cone does it occupy?  (Let $H$ and $R$ be the height and base
radius of the larger cone, and let $h$ and $r$ be the height and base
radius of the smaller cone.  Hint: Use similar triangles to get an equation
relating $h$ and $r$.)
\begin{sol}
 $4/27$
\end{sol}
\end{ex}

%%%%%%%%%%%
%\begin{ex}
%In example~\xrefn{exam:sand and road}, what happens if
%$w\ge v$ (i.e., your speed on sand is at least your speed on the
%road)?
%\begin{sol}
% Go direct from $A$ to $D$.
%\end{sol}
%\end{ex}

%%%%%%%%%%
\begin{ex}
A container holding a fixed volume is being made in the shape of a cylinder
with a hemispherical top.  (The hemispherical top has the same radius
as the cylinder.)  Find the ratio of height to radius of the cylinder which
minimizes the cost of the container if (a) the cost per unit area of the
top is twice as great as the cost per unit area of the side, and the
container is made with no bottom; (b) the same as in (a), except that the
container is made with a circular bottom, for which the cost per unit area is
1.5 times the cost per unit area of the side.
\begin{sol}
 (a) 2, (b) $7/2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 A piece of cardboard is 1 meter by $1/2$ meter. A square is
to be cut from each corner and the sides folded up to make an open-top
box. What are the dimensions of the box with maximum possible volume?
\begin{sol}
 $\ds{\sqrt3\over6}\times{\sqrt3\over6}+{1\over2}\times
{1\over4}-{\sqrt3\over 12}$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
\label{exercise: cardboard box} (a) A square piece of cardboard of side $a$ is used to make
an open-top box by cutting out a small square from each corner and
bending up the sides.  How large a square should be cut from each
corner in order that the box have maximum volume? (b) What if the
piece of cardboard used to make the box is a rectangle of sides $a$
and $b$?
\begin{sol}
 (a) $a/6$, (b) $\ds (a+b-\sqrt{a^2-ab+b^2})/6$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 A window consists of a rectangular piece of clear glass with
a semicircular piece of colored glass on top; the
colored glass transmits only $1/2$ as much light per unit area as the
the clear glass.  If the distance from
top to bottom (across both the rectangle and the semicircle) is
2 meters and the window may be no more than 1.5 meters wide, find the
dimensions of the rectangular portion of the window that lets through
the most light.
\begin{sol}
 $1.5$ meters wide by $1.25$ meters tall
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 A window consists of a rectangular piece of clear glass with
a semicircular piece of colored glass on top.  Suppose that the
colored glass transmits only $k$ times as much light per unit area as
the clear glass ($k$ is between $0$ and $1$).  If the distance from
top to bottom (across both the rectangle and the semicircle) is a
fixed distance $H$,
find (in terms of $k$) the ratio of vertical side to horizontal side
of the rectangle for which the window lets through the most light.
\begin{sol}
 If $k\le 2/\pi$ the ratio is $(2-k\pi)/4$; if $k\ge 2/\pi$,
the ratio is zero: the window should be semicircular with no
rectangular part.
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 You are designing a poster to contain a fixed amount $A$ of
printing (measured in square centimeters) and have margins of $a$
centimeters at the top and bottom and $b$ centimeters at the sides.
Find the ratio of vertical dimension to horizontal dimension of the
printed area on the poster if you want to minimize the amount of
posterboard needed.
\begin{sol}
 $a/b$
\end{sol}
\end{ex}

%%%%%%%%%%%%
%\begin{ex}
%
%%The strength of a rectangular beam is proportional to the product of its
%%width $w$ times the square of its depth $d$.
%%Find the dimensions of the strongest
%%beam that can be cut from a cylindrical log of radius $r$.
%%\begin{sol}
% $\ds w=2r/\sqrt3$, $\ds h=2\sqrt2r/\sqrt3$
%%\end{sol}
%\end{ex}
%%
%%\figure
%%\vbox{\beginpicture
%%\normalgraphs
%%\setcoordinatesystem units <1.5truecm,1.5truecm>
%%\setplotarea x from -1 to 1, y from -1 to 1
%%\circulararc 360 degrees from 1 0 center at 0 0
%%\setlinear
%%\plot 0.5 0.866 -0.5 0.866 -0.5 -0.866 0.5 -0.866 0.5 0.866 /
%%\betweenarrows {$d$} <-4pt,0pt> from 0.5 -0.866 to 0.5 0.866
%%\betweenarrows {$w$} <0pt,6pt> from -0.5 -0.866 to 0.5 -0.866
%%\endpicture}
%%\figrdef{fig:beam strength}
%%\endfigure{Cutting a beam.}

%%%%%%%%%%
\begin{ex}
What fraction of the volume of a sphere is taken up by the largest cylinder
that can be fit inside the sphere?
\begin{sol}
 $\ds 1/\sqrt3\approx 58\%$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
The U.S.~post office will accept a box for shipment only if the sum of the
length and girth (distance around) is at most 108 in.  Find the dimensions
of the largest acceptable box with square front and back.
\begin{sol}
 $18\times18\times36$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
Find the dimensions of the lightest cylindrical can containing 0.25 liter
(=250 cm${}^3$) if the top and bottom are made of a material that is twice
as heavy (per unit area) as the material used for the side.
\begin{sol}
 $\ds r=5/(2\pi)^{1/3}\approx 2.7\hbox{ cm}$,\hfill\break
$\ds h=5\cdot2^{5/3}/\pi^{1/3}=4r\approx 10.8 \hbox{ cm}$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 A conical paper cup is to hold $1/4$ of a liter. Find the
height and radius of the cone which minimizes
the amount of paper needed to make the cup.  Use the formula $\ds \pi
r\sqrt{r^2+h^2}$ for the area of the side of a cone.
\begin{sol}
 $\ds h={750\over\pi}\left({2\pi^2\over 750^2}\right)^{1/3}$,
$\ds r=\left({750^2\over 2\pi^2}\right)^{1/6}$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
 A conical paper cup is to hold a fixed volume of water.
Find the ratio of height to base radius of the cone which minimizes
the amount of paper needed to make the cup.  Use the formula $\ds \pi
r\sqrt{r^2+h^2}$ for the area of the side of a cone, called the
\dfont{lateral area} of the cone.
\begin{sol}
 $\ds h/r=\sqrt2$
\end{sol}
\end{ex}

%% Maple only?
%%%%%%%%%%%
%\begin{ex}
%If you fit the cone with the largest possible surface area (lateral area
%plus area of base) into a sphere, what percent of the volume of the
%sphere is occupied by the cone?
%\begin{sol}
% The ratio of the volume of the sphere to the volume of the
%cone is $\ds 1033/4096+33/4096\sqrt{17}\approx 0.2854$, so the cone
%occupies approximately $28.54\%$ of the sphere.
%\end{sol}
%\end{ex}
%
%% Maple only?
%%%%%%%%%%%
%\begin{ex}
%Two electrical charges, one a positive charge A of magnitude $a$ and the
%other a negative charge B of magnitude $b$, are located a distance $c$
%apart.  A positively charged particle $P$ is situated on the line between A
%and B.  Find where $P$ should be put so that the pull away from $A$ towards
%$B$ is minimal.  Here assume that the force from each charge is
%proportional to the strength of the source and inversely proportional to
%the square of the distance from the source.
%\begin{sol}
% $P$ should be at distance $\ds c\root 3\of {a} /
%(\root 3\of {a} + \root 3\of {b})$ from charge $A$.
%\end{sol}
%\end{ex}

%%%%%%%%%%
\begin{ex}
Find the fraction of the area of a triangle that is occupied by the largest
rectangle that can be drawn in the triangle (with one of its sides along a
side of the triangle).  Show that this fraction does not depend on the
dimensions of the given triangle.
\begin{sol}
 $1/2$
\end{sol}
\end{ex}

%%%%%%%%%%
\begin{ex}
How are your answers to Problem~\xrefn{ex:manufacturing}
 affected if the cost per item for the $x$
items, instead of being simply \$2, decreases below \$2 in proportion to
$x$ (because of economy of scale and volume discounts) by 1 cent for each
25 items produced?
\begin{sol}
 \$7000
\end{sol}
\end{ex}

%%%%%%%%%%%%
%\begin{ex}
%%You are standing near the side of a large wading pool of uniform depth when
%%you see a child in trouble.  You can run at a speed $\ds v_1$ on land and at a
%%slower speed $\ds v_2$ in the water.  Your perpendicular distance from the side
%%of the pool is $a$, the child's perpendicular distance is $b$, and the
%%distance along the side of the pool between the closest point to you and
%%the closest point to the child is $c$ (see the figure below).
%%Without stopping to do any calculus, you instinctively choose the
%%quickest route (shown in the figure) and save the child.  Our
%%purpose is to derive a relation between the angle $\ds \theta_1$ your path
%%makes with the perpendicular to the side of the pool when you're on land,
%%and the angle $\ds \theta_2$ your path makes with the perpendicular when you're
%%in the water.  To do this, let $x$ be the distance between the closest
%%point to you at the side of the pool and the point where you enter the
%%water.  Write the total time you run (on land and in the water) in
%%terms of $x$ (and also the constants $\ds a,b,c,v_1,v_2$).  Then set the
%%derivative equal to zero.  The result, called ``Snell's law'' or the ``law
%%of refraction,'' also governs the bending of light when it goes into water.
%%\begin{sol}
% There is a critical point when
%%$\ds \sin\theta_1/v_1=\sin\theta_2/v_2$, and the second derivative is
%%positive, so there is a minimum at the critical point.
%%\end{sol}
%\end{ex}
%%
%%\figure
%%\vbox{\beginpicture
%%\normalgraphs
%%\setcoordinatesystem units <.75truecm,.75truecm>
%%\setplotarea x from 0 to 6, y from -3 to 3
%%\axis bottom shiftedto y=0 /
%%\circulararc 53.13 degrees from 2.667 -1 center at 4 0
%%\put {$\theta_1$} [tr] <-3pt,-3pt> at 3.6 -1.4
%%\circulararc 33.69 degrees from 5 1.5 center at 4 0
%%\put {$\theta_2$} at 4.6 2
%%\setlinear
%%\plot 0 -3 4 0 6 3 /
%%\setdashes
%%\putrule from 4 -3 to 4 3
%%\putrule from 6 0 to 6 3
%%\putrule from 0 -3 to 0 0
%%\put {$x$} [b] <0pt,4pt> at 2 0
%%\put {$c-x$} [b] <0pt,4pt> at 5 0
%%\put {$a$} [l] <4pt,0pt> at 0 -1.5
%%\put {$b$} [l] <4pt,0pt> at 6 1.5
%%\endpicture}
%%\figrdef{fig:rescue}
%%\endfigure{Wading pool rescue.}
%
%
%

\end{enumialphparenastyle}

max_stars_repo_name: TimAlderson/OpenCalc

max_issues_repo_name: TimAlderson/OpenCalc

max_forks_repo_name: TimAlderson/OpenCalc


text:
\input{core_introduction}

\chapter{core. The Core Functionality}
\renewcommand{\curModule}{core}
\input{core_basic_structures}
\input{core_array_operations}
\input{core_dynamic_structures}
\input{core_drawing_functions}
\input{core_persistence}
\input{core_clustering_search}
\input{core_utilities_system_functions}

\chapter{imgproc. Image Processing}
\renewcommand{\curModule}{imgproc}
\input{imgproc_histograms}
\input{imgproc_image_filtering}
\input{imgproc_image_warping}
\input{imgproc_image_transform}
\input{imgproc_struct_shape_analysis}
\input{imgproc_planar_subdivisions}
\input{imgproc_motion_tracking}
\input{imgproc_feature_detection}
\input{imgproc_object_detection}

\chapter{features2d. Feature Detection and Descriptor Extraction}
\renewcommand{\curModule}{features2d}
\input{features2d_detection_description}
\input{features2d_common_detection_description}
\input{features2d_object_categorization}

\chapter{flann. Clustering and Search in Multi-Dimensional Spaces}
\renewcommand{\curModule}{flann}
\input{flann}

\chapter{objdetect. Object Detection}
\renewcommand{\curModule}{objdetect}
\input{objdetect}

\chapter{video. Video Analysis}
\renewcommand{\curModule}{video}
\input{video_motion_tracking}

\chapter{highgui. High-level GUI and Media I/O}
\renewcommand{\curModule}{highgui}
\input{highgui}
\ifPy     %Qt is for C and Cpp, so do nothing
\else
\input{highgui_qt}
\fi

\chapter{calib3d. Camera Calibration, Pose Estimation and Stereo}
\renewcommand{\curModule}{calib3d}
\input{calib3d}

\chapter{ml. Machine Learning}
\renewcommand{\curModule}{ml}
\input{ml}