Re: ? analytic constraint optimization


"Robert Israel" <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:rbisrael.20070520072202$0cb0@xxxxxxxxxxxxxxxxxxx
"Cheng Cosine" <acosine@xxxxxxxxxx> writes:

Hi:

Usually when searching for the optimal soln of a constrained
optimization,

we use iterative method to do that and need to be aware of whether the
obtained

soln is global or only local. It'd be good if we can transform the
problem
to

other form that has better analytical property.

For example, A and B are both semi-positive definite Hermitian matrices.

We want to find the maximal of f(u) = u*A*u subjected to the constraint

g(u) = u*B*u <= c (the constraint), u is complex.

I assume you mean u^* A u and u^* B u (where ^* is Hermitian transpose).
It's easy to see that if a maximum exists, we must have Ker(B) contained
in Ker(A), and then we can restrict to the orthogonal complement of
Ker(B), where B is positive definite and not just semidefinite.
So suppose B is positive definite.

I heard that this can be transformed to an eigenvalue problem but don't
see

how. Anyone knows how to do this?

Let B^(1/2) be the unique positive definite square root of B,
v = B^(1/2) u and C = B^(-1/2) A B^(-1/2). Then you want to
maximize v^T C v subject to the constraint v^T v <= c. Rayleigh's
Principle says this is maximized when v is an eigenvector of C for
the largest eigenvalue.

Hmm, so the ineq constraint only affects the scaling. Then will the
following

approach gives the same optimal soln, except a scaling?

max h(u), where h(u) = f(u)/g(u) = u'*A*u/( u'*B*u )?

Since now it is unconstrined, the extreme can be obtained by 1st derivative.

dh/du = 0 => ( u'*B*u )*A*u-( u'*A*u )*B*u = 0
=> A*u= g*B*u, g = real scalar = ( u'*A*u )/( u'*B*u )

The maximal is the 1st e-vector of the above generalized e-problem.

Will this 1st e-vector the same as what you obtained above or the scalar

g could change it, since the value of g depends on f(u) and g(u)?

Thanks,
by Cheng Cosine
May/20/2k7 NC





.

Relevant Pages

  • Re: ? analytic constraint optimization
    ... Usually when searching for the optimal soln of a constrained optimization, ... A and B are both semi-positive definite Hermitian matrices. ... We want to find the maximal of f= u*A*u subjected to the constraint ... Principle says this is maximized when v is an eigenvector of C for ...
    (sci.math.num-analysis)
  • Re: ? analytic constraint optimization
    ... Find the maximal eigenvector of A*u = lambda*u based on ... Then determine the scaling according to the original constraint ... The e-vector maximizes A is not the same as the one maximizes ...
    (sci.math.num-analysis)