Re: constrained optimization

In article
<dd330b9f-04c1-4255-b157-772c739d3244@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Beliavsky <beliavsky@xxxxxxx> wrote:

I want to maximimize a function of N real variables x(1:N) with the
constraint that the sum of the squared elements equals one. In
Fortran, sum(x**2) == 1 . There are constrained optimization Fortran
codes, but is there a way I could transform the x's so that this
constraint holds automatically?

You have an N-dimensional space, and you are interested in a
solution to some equation on the surface of a unit sphere in that
N-dimensional space.

There are two general approaches. One approach is to transform to a
set of (N-1) "essential" variables that satisfy the constraint by
construction. Having done that, you can either transform your
original problem to this new (N-1) dimensional coordinate system, or
you can use the chain rule to transform the derivatives from your
original coordinates to the new coordinates and use those
derivatives to optimize the new function. There are many general
ways to do this kind of transformation, and the best choice depends
often on the details of the problem (the symmetries involved, the
range of values of input variables, boundary conditions, etc.).

The other approach is to add a lagrange multipier to the original
problem and solve the unconstrained problem in this new (N+1)
dimensional space.

So you can optimize in an (N-1) dimensional space in which the
constraint is automatically satisfied at each optimization step, or
you can optimize within an (N+1) dimensional space in which the
converged solution (and sometimes only at convergence) satisfies the
constraint.


What about the case where, in
addition, all x's are non-negative? In Fortran, sum(x**2) == 1 .and.
all(x >= 0).

These problems are called linear constraint problems. Usually
different approaches are used for these because the constraints only
come into the problem along the borders. Within the allowed space,
you have an N-dimensional problem (you can move infinitesimally in
all directions), but at the borders you can only move in some subset
of this space. In your above specification, you have both kinds of
constraints. You might try to use a lagrange multiplier for the
first constraint, and then use the linear constraint approach for
the other N constraints.

I would have asked these questions in sci.math.num-analysis, but
unfortunately that once useful newsgroup has become overrun by spam.

I've noticed that too. Hopefully you can get some good replies to
your question here in clf.

$.02 -Ron Shepard
.

Relevant Pages

  • Re: how to transform Aruns LDPC code to max-product (Min-sum)?
    ... Advice would be appreciated on how to transform Arun's code given on ... In max-product computation of sum() is replaced by ... constraint node "constraint" is an even parity check i.e. the sum of the ... To transform this to max-sum, we use log likelihoods and actually transmit ...
    (comp.dsp)
  • polynomial coefficient transformation
    ... i've tried a couple google searches, but i don't know how to ... optimize these parameters subject to the *constraint that none of the ... roots of the polynomial are on the positive real axis*. ... i can transform the polynomial to reflect this constraint? ...
    (sci.math)
  • Re: Numerical Recipes (Fortran) Usenet ??
    ... you can shift and scale z in order to fit the constraint range. ... nature of the mapping can be handled. ... and differentiable so that you can transform derivatives. ... Constrained optimization really is much different from unconstrained ...
    (comp.lang.fortran)
  • Re: constrained optimization
    ... constraint that the sum of the squared elements equals one. ... codes, but is there a way I could transform the x's so that this ...
    (comp.lang.fortran)
  • Re: matrix pseudoinverse
    ... want to add the constraint that the padd to 1 ... rows of M and truncate the matrix equation to just ... row where the reduced coefficients are all ...
    (sci.math)