Re: Optimization for a positive definite constraint
- From: borchers@xxxxxxx (Brian Borchers)
- Date: Thu, 16 Feb 2006 23:36:47 +0000 (UTC)
From antispam@xxxxxxxxxxxx Thu Feb 16 16:13:30 MST 2006Article: 70349 of sci.math.num-analysis
Path: border1.nntp.dca.giganews.com!nntp.giganews.com!newscon06.news.prodigy.com!prodigy.net!newsfeed-00.mathworks.com!bigboote.WPI.EDU!news.tufts.edu!elk.ncren.net!nntp.upenn.edu!news.msu.edu!not-for-mail
Hiu Chung Law wrote:
Let X be a n by n matrix.
The goal is to minimize a real-value function f(X)
subject to the constraint that X is symmetric, and X is positive definite.
(The function f is not defined for X that is not positive definite).
If f(X) is linear in the elements of X, then you have a semidefinite
programming problem. The SDP formulation can also include linear
equality and inequality constraints on the elements of X. Also, many
problems that don't appear at first to be SDP's can be reformulated as
SDP's. For example, many eigenvalue optimization problems can be
rewritten as SDP's. Quite a bit of work has been done on solving
SDP's, and there are several open source and non-free software
packages for solving such problems. You should certainly make use
of the work on SDP's if possible.
If f(X) is a more general non-linear function, then you have a nonlinear
semidefinite programming problem. Much less research has been done on
such problems, but there are certainly some ways to approach these
problems.
For example, if f(X) is convex, then one approach is to construct an
outer approximation to f(X) using linear constraints derived from the
gradient of f(X). You start with a solution X0, find the gradient of
f at X0, and use it to construct a linear function f0(x) that
underestimates f(X). Solve a linear SDP with this constraint and
obtain a solution X1. Repeat.
One important issue concerns the nature of the function f(X). Is your
function convex or nonconvex? Is it differentiable? Does it have
some particular structure, such as being a function of the eigenvalues
of X? Can X be easily expressed in terms of a smaller number of
parameters? The answers to these questions could help in selecting an
appropriate approach to solving the problem.
Another important question has to do with the size of the problem. How
big is n?
I am now treating this as an optimization problem with n^2 variables,
and the gradient and the Hessian can be computed.
The symmetric constraint can be handled easily because it is linear.
However, the constraint that X should be positive-definite is more difficult
to handle. Right now, I simply force my line-search procedure to reject
any X that is not positive definite. However, this does not seem to be
robust.
This is not a good way to go for any constrained optimization
problem.
I have also re-parameterized X by X = F * F', but the Hessian with
respect to F is much more nasty than the Hessian with respect to X.
This is a well know approach, but it doesn't seem like a good choice
in your case.
I thought something related to how to handle bound constraint may
help, but I cannot find anything similar. Also, this is quite
different from semi-definite programming.... Do you have any advice
on how to tackle this type of problem?
I would suggest that you start by reading up on "nonlinear
semidefinite programming." A search on google scholar gives 53 hits,
including several that look quite likely to be useful. For example,
there's
A Global Algorithm for Nonlinear Semidefinite Programming
SIAM Journal on Optimization
Volume 15 , Issue 1 2005
Pages: 303 - 318
Authors: Rafael Correa and Hector C. Ramirez
You might also tell us more about your particular problem so that we
could suggest methods appropriate to your f(X).
--
Brian Borchers borchers@xxxxxxx
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: 505-835-5813
Socorro, NM 87801 FAX: 505-835-5366
.
- References:
- Optimization for a positive definite constraint
- From: Hiu Chung Law
- Optimization for a positive definite constraint
- Prev by Date: Re: Numerical determination of error convergence
- Next by Date: Higher-order root solving. Newton. Halley, Householder, Bernoulli
- Previous by thread: Re: Optimization for a positive definite constraint
- Next by thread: Method to Solve 2 unknowns 2 Equations
- Index(es):
Relevant Pages
|
