Re: ? analytic constraint optimization

"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.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: ? analytic constraint optimization
    ... Usually when searching for the optimal soln of a constrained ... We want to find the maximal of f= u*A*u subjected to the constraint ... so the ineq constraint only affects the scaling. ... The maximal is the 1st e-vector of the above generalized e-problem. ...
    (sci.math.num-analysis)
  • Re: ? analytic constraint optimization
    ... Usually when searching for the optimal soln of a constrained ... and then the constraint epxressed by gis just a scaling problem. ... Why would you think that an eigenvector of A would give you ...
    (sci.math.num-analysis)
  • Re: ? analytic constraint optimization
    ... and then the constraint epxressed by gis just a scaling ... Will the above two approaches give the same soln always? ... Why would you think that an eigenvector of A would give ... Spending money makes a man happy, but a man only has limited money. ...
    (sci.math.num-analysis)
  • Re: lagrange multiplier question / eigenvector question
    ... u is a vector with n componets. ... to be parallel to gradient of constraint function. ... Under the constraint sum a_i^2=1, this is obviously maximized if u has ...
    (sci.math)
  • Re: ? analytic constraint optimization
    ... Given 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 ... larger than Jhat. ... by Cheng Cosine ...
    (sci.math.num-analysis)
Loading