Beni Bogoşel's blog

Putnam 2018 – Problem B4

February 8, 2019 beni22sof Leave a comment

B4. Given a real number ${a}$ , we define a sequence by ${x_0=1}$ , ${x_1=x_2=a}$ and ${x_{n+1} = 2x_nx_{n-1}-x_{n-2}}$ for ${n \geq 2}$ . Prove that if ${x_n =0 }$ for some ${n}$ , then the sequence is periodic.

Putnam 2018, Problem B4

Solution: The path to the solution for this problem is really interesting. The first question that pops in mind when seeing the problem is: How do I prove that a sequence is periodic?. It’s not obvious from the given recurrence relation that this should happen, and what’s with the condition ${x_n = 0}$ ?

Categories: Algebra, Analysis, Olympiad, Problem Solving Tags: olympiad, periodic, putnam, sequence, trigonometry

Putnam 2018 – Problem B2

February 7, 2019 beni22sof Leave a comment

B2. Let ${n}$ be a positive integer and let ${f_n(z) = n+(n-1)z+(n-2)z^2+...+z^{n-1}}$ . Prove that ${f_n}$ has no roots in the closed unit disk ${\{z \in \Bbb{C}: |z| \leq 1\}}$ .

Putnam 2018, Problem B2

Solution: This is a cute problem and the path to the solution is quite straightforward once you notice some obvious things. First note that ${f_n(0)=n}$ , so ${0}$ is not a solution.

Some angle chasing

February 4, 2019 beni22sof Leave a comment

I recently stumbled upon the following question on Math Stackexchange: link

The idea is to find the missing angles in the figure:

Geom1

I tried various methods and was able to find one of the angles using some auxiliary constructions, however the method didn’t seem natural, so I tried the suggestion given in one of the answers, that is to include the figure in a regular polygon with 18 sides. It did not work for the whole configuration, but it worked like a charm if we consider quadrilaterals PDBC and ABDE separately.

Below you can see the Geogebra configuration for PDBC.

After you’ve found the angle PBD you can construct a similar configuration for the quadrilateral ABDE.

I leave the details to the interested reader. It seems interesting that this problem is completely solvable by using regular 18 sides polygons.

Categories: Geometry, Olympiad Tags: angle chasing, Geometry, polygon, regular polygons

p-Laplace equation – Fixed point approach

January 25, 2019 beni22sof Leave a comment

The ${p}$ -Laplace problem is the generalization of the usual Laplace problem and is defined for ${p \geq 2}$ in the following way

$\displaystyle \left\{ \begin{array}{rcll} -\text{div} ((1+|\nabla u|^{p-2})\nabla u) & = & f & \text{ in }\Omega \\ u & = & 0 & \text{ on }\partial \Omega \end{array} \right.$

We are not going into details regarding the functional spaces corresponding to ${f}$ and ${u}$ since in the end we are interested in showing a way to solve this equation numerically.

Lagrangians – derivation under constraints

December 21, 2018 beni22sof Leave a comment

In this post I will describe a formal technique which can help in finding derivatives of functions under certain constraints. In order to see what I mean, take the following two examples:

1. If you differentiate the function ${x \mapsto f}$ with respect to ${x}$ , you get zero, obviously.

2. If you differentiate the function ${x \mapsto f}$ under the constraint that ${f^2=x}$ (supposing that ${x>0}$ ) then it is not hard to see that ${f = \sqrt{x}}$ and the derivative will be ${1/(2\sqrt{x})}$ .

This shows that adding certain constraints will change the derivative and when dealing with more sophisticated constraints, like PDE or differential equations, things get less clear.

The question of the existence of derivatives with respect to some variables, when dealing with constraints, is usually dealt with by using the implicit function theorem: this basically says that if some variables are linked by some smooth equations and that you can locally invert the dependence, then you can infer differentiability.

The method presented below skips this step and goes directly for the computation of the derivative. This is a common used technique in control theory or shape optimization, where computing derivatives is essential in numerical simulations. I will come back to derivatives linked to shape optimization in some further posts. For now, let’s see how one can use the Lagrangian method for computing derivatives in some simple cases.

Example 1. Let’s compute the derivative of ${x \mapsto f}$ under the constraint ${f^2 = x}$ . In order to do this we introduce a Lagrangian, which has the following form

$\displaystyle \text{(objective function) } + \text{ (penalization of the constraints)}.$

Example of optimization under constraints – using Lagrange multipliers

November 27, 2018 beni22sof Leave a comment

Consider the functional ${J : (0,\infty)^2 \rightarrow\Bbb{R}}$ defined by

$\displaystyle J(x,y) = \cosh(3x+2y)$

and the set ${K}$ defined by ${K = \{(x,y) \in (0,\infty)^2 : xy \geq 1\}}$ .

Prove that ${J}$ admits a minimizer on ${K}$ and find it.
Let ${K_2}$ be the set ${K_2 = \{ (x,y) \in (0,\infty)^2 : y \leq 2+x,\ y \geq -x+5\}}$ . Does ${J}$ admit minimizers on ${K_2}$ ? If yes determine all points in which the maximum is attained.

Proof: This is a problem which illustrates well concepts related to optimality conditions for constrained problems. It is possible to solve these problems by two methods: one using only basic ideas and a second one using results from optimization theory. One can also see by examining the basic method how to recover naturally the optimality condition given by the Lagrange multipliers.

Categories: Analysis, Optimization Tags: lagrange, optimization

Optimizing a quadratic functional under affine constraints

November 2, 2018 beni22sof Leave a comment

Consider the quadratic functional ${J : \Bbb{R}^n \rightarrow \Bbb{R}}$ defined by

$\displaystyle J(v) = \frac{1}{2} Av\cdot v-b\cdot v$

for a ${n\times n}$ real matrix ${A}$ which is symmetric positive definite and a vector ${b \in \Bbb{R}^n}$ . Consider also the application ${F : \Bbb{R}^n \rightarrow \Bbb{R}^m}$ defined by ${F(v) = Cv-d}$ where ${C}$ is a ${m\times n}$ real matrix and ${d \in \Bbb{R}^m}$ . Furthermore suppose that ${m<n}$ and that ${C}$ is of maximal rank. The objective is to study the following optimization problem under equality constraints:

$\displaystyle \min_{v \in K} J(v)$

where ${K}$ is defined by ${K = \{ v \in \Bbb{R}^n : F(v) = d\}}$ .

Show that ${J}$ has a unique minimizer on ${K}$ .
Prove that if ${u}$ is the minimizer of ${J}$ on ${K}$ then there exists a unique vector ${\lambda \in \Bbb{R}^m}$ such that ${(u,\lambda) \in \Bbb{R}^n\times \Bbb{R}^m}$ solves the linear system
$\displaystyle \begin{pmatrix} A & C^t \\ C & 0 \end{pmatrix} \begin{pmatrix} u \\ \lambda \end{pmatrix} = \begin{pmatrix} b \\ d \end{pmatrix}$
Show that the matrix of the above system is invertible.

Categories: Analysis, Optimization, Uncategorized Tags: Analysis, lagrange, optimization, teaching

Older Entries

Beni Bogoşel's blog

Putnam 2018 – Problem B4

Putnam 2018 – Problem B2

Some angle chasing

p-Laplace equation – Fixed point approach

Lagrangians – derivation under constraints

Example of optimization under constraints – using Lagrange multipliers

Optimizing a quadratic functional under affine constraints

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll