Calculus Optimization Methods/Constrained Optimization

Presentation edit

There are two main ways to present a subset of  explicitly and implicitly.

An explicit presentation expresses a set as the image of a function,   most often the image of a function from another Euclidean space or cube,   or   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,   most often the pre-image of a function to another Euclidean space   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 edit

Circle:

  •   is an implicit presentation.
  •   for   is an explicit presentation.
  •   for   is an explicit presentation.

Disk:

  •   is an implicit presentation
  •   for   is an explicit presentation.
  •   for   is an explicit presentation.

Different presentations may be more or less useful.

Caveats: Imperfect parametrizations edit

Note that explicit presentations sometimes hit the same point more than once (in the first presentation of the circle,   and   map to the same point, and in the presentation of the disk, all points with   map to the same point, the origin,  ), or miss a point (in the second presentation, the point   is not hit by any finite t – if one extends the domain to include   then it can be hit by some input). This is often simply a minor technicality to deal with, such as by excluding   or including   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 ( )-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 edit

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 edit

  • Equality constraints
  • Inequality constraints


Explicit solution edit

Implicit solution edit

Discussion edit

When finding the extreme values of   subject to a constraint  , the stationary points found above will not work. This new problem can be thought of as finding extreme values of   when the point   is restricted to lie on the surface  . The value of   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,

 

The number   in the equation is known as the Lagrange multiplier.