Calculus Optimization Methods/Constrained Optimization

Presentation

There are two main ways to present a subset of $\mathbf {R} ^{n}$ – explicitly and implicitly.

An explicit presentation expresses a set as the image of a function, $X\to \mathbf {R} ^{n},$ most often the image of a function from another Euclidean space or cube, $\mathbf {R} ^{k}\to \mathbf {R} ^{n}$ or $[0,1]^{k}\to \mathbf {R} ^{n}.$ This function can be interpreted as a vector-valued function with k inputs and n outputs.

An implicit presentation expresses a set as the pre-image of a function or functions, $\mathbf {R} ^{n}\to Y,$ most often the pre-image of a function to another Euclidean space $\mathbf {R} ^{n}\to \mathbf {R} ^{k},$ which can be interpreted as k separate real-valued functions (each with n inputs), or as a single vector-valued function in n inputs. Implicit presentations generally present subsets as level sets or sublevel sets: via equalities or inequalities that elements of a subset must satisfy.

Briefly, explicit presentations list points, while implicit presentations test points: in an explicit presentation, as one ranges over the input, one obtains all the output, while in an implicit presentation, one can test possible points to see if they fall in the set: if the satisfy the constraints or not.

One can sometimes convert between these presentations, but in general this can be quite difficult.

Example: circle and disk

Circle:

• $x^{2}+y^{2}=1$ is an implicit presentation.
• $(\cos \theta ,\sin \theta )$ for $\theta \in [0,1]\times [0,2\pi ]$ is an explicit presentation.
• $\left({\frac {1-t^{2}}{1+t^{2}}},{\frac {t}{1+t^{2}}}\right)$ for $t\in \mathbf {R}$ is an explicit presentation.

Disk:

• $x^{2}+y^{2}\leq 1$ is an implicit presentation
• $(r\cos \theta ,r\sin \theta )$ for $(r,\theta )\in [0,1]\times [0,2\pi ]$ is an explicit presentation.
• $\left(u{\frac {1-t^{2}}{1+t^{2}}},u{\frac {t}{1+t^{2}}}\right)$ for $t\in \mathbf {R} ,u\in [0,1]$ is an explicit presentation.

Different presentations may be more or less useful.

Caveats: Imperfect parametrizations

Note that explicit presentations sometimes hit the same point more than once (in the first presentation of the circle, $\theta =0$ and $\theta =2\pi$ map to the same point, and in the presentation of the disk, all points with $r=0$ map to the same point, the origin, $(0,0)$), or miss a point (in the second presentation, the point $(-1,0)$ is not hit by any finite t – if one extends the domain to include $\infty ,$ then it can be hit by some input). This is often simply a minor technicality to deal with, such as by excluding $\theta =2\pi$ or including $t=\infty ,$ or by checking points that are not hit or hit multiply separately and with care. The underlying mathematical issue is that the space being parametrized may not be homeomorphic or diffeomorphic to the space being used to parameterize: one says that there is a "topological obstruction" to giving a parametrization without these imperfections.

One need not in general concern oneself with the details of the topology, and topology is a major field of mathematics, but, as with the boundedness principle and the maximum principle, topological theories underlie much of why calculus optimization methods work.

One topological, or more precisely geometric, observation that is worth mentioning, however, is that in many applications, the subset being considered is a convex set – it bulges out, not in, and, further, is connected (in one piece) and does not have holes in the middle. In these settings, the shape is topologically a disk or in higher dimensions a ball, and one can thus talk about the interior of a shape (the open n-ball), and a single boundary, which will topologically be a simple sphere (the ($n-1$)-sphere) rather than something more complicated. Thus there is little loss in generality of bearing the disk in mind as the archetypal example of a subset in thinking about these problems.

Explicit: parametrization

A set may be given explicitly by a parametrization, such as by a parametric equation in 1 parameter for a curve, or a parametric surface (parametric equation in 2 parameters).

Implicit: constraints

• Equality constraints
• Inequality constraints

Discussion

When finding the extreme values of $f(x_{1},x_{2},\cdots ,x_{n})$ subject to a constraint $g(x_{1},x_{2},\cdots ,x_{n})=k$, the stationary points found above will not work. This new problem can be thought of as finding extreme values of $f(x_{1},x_{2},\dots ,x_{n})$ when the point $(x_{1},x_{2},\dots ,x_{n})$ is restricted to lie on the surface $g(x_{1},x_{2},\dots ,x_{n})=k$. The value of $f(x_{1},x_{2},\dots ,x_{n})$ is maximized(minimized) when the surfaces touch each other,i.e , they have a common tangent line. This means that the surfaces gradient vectors at that point are parallel, hence,

$\nabla f(x_{1},x_{2},\cdots ,x_{n})=\lambda \nabla g(x_{1},x_{2},\cdots ,x_{n}).$

The number $\lambda$ in the equation is known as the Lagrange multiplier.