optimization on positive semidefinite matrix

[Ryutaroh Matsumoto]

Hello everyone,

I am solving a convex optimization problem on a convex subset of
positive semidefinite matrices, and Knitro for Matlab is working fine.
Thank you very much.

Although it works fine, I have several questions.

(1) What is the standard way to tell the domain of optimization being
the set of positive semidefinite matrices?? We include the constraint
det M >= 0, provide a strictly feasible start point, and
set "bar_feasible" to "stay". Is it the expected usage?

(2) We plan to include the numerical computation results by Knitro-
Matlab
into our research paper. Is there any recommended way to cite Knitro?

Best regards,

Ryutaroh Matsumoto

[Artelys Knitro support team]

Dear Ryutaroh Matsumoto,

(1) The determinant is not a sufficient condition. Indeed, you need
the determinants of all principal minors to be positive too (cf
http://en.wikipedia.org/wiki/Minor_(linear_algebra) ). In order to
enforce the constraint, you could write it like that: d_i>0 where
A=LDL' is the factorization of A and d_i is the diagonal. It is a
costly constraint because you have to compute L. In a nutshell, if you
have good results, it is fine but KNITRO is not designed to solve SDPs
(Semi-Definite Programming). Therefore, you may also try specialized
solvers like Sedumi, SDP3 or PenSDP.

(2) On http://www.ziena.com/documentation.htm , you will find the
primary reference (Byrd et al., 2006). You may also cite the user
manual.

Best regards.

Nicolas Omont.

[Ryutaroh Matsumoto]

Dear Nicolas,

Thank you very much for your reply.
Please allow me to ask questions on your message.

> (1) The determinant is not a sufficient condition. Indeed, you need
> the determinants of all principal minors to be positive too (cfhttp://en.wikipedia.org/wiki/Minor_(linear_algebra) ).

Yes, I know it.
But the constraints has det M >= 0 and the optimizer stays inside the
strictly
feasible region, is the optimizer supposed to stay inside the set of
positive
definite matrices, and eventually reaches the optimal value??

I believe the above behavior is what an interior point method does in
general.

> In order to
> enforce the constraint, you could write it like that: d_i>0 where
> A=LDL' is the factorization of A and d_i is the diagonal. It is a
> costly constraint because you have to compute L.

But it seems to more difficult to compute the gradient and Hessian
of the constraints. At least the computation of the gradient and
Hessian of det M is relatively easy.

> In a nutshell, if you
> have good results, it is fine but KNITRO is not designed to solve SDPs
> (Semi-Definite Programming). Therefore, you may also try specialized
> solvers like Sedumi, SDP3 or PenSDP.

The problem with SDP solvers is that our objective function is not
linear but convex. It is essentially the sum of x_i log x_i, where
x_i is an eigenvalue of the positive semidefinite matrix M.
I would appreciate it if you could give me a suggestion to solve
such kind of the problem.

Best regards,

Ryutaroh Matsumoto


>
> (2) Onhttp://www.ziena.com/documentation.htm, you will find the

[Artelys Knitro support team]

Dear Ryutaroh Matsumoto

(1) If you set det M >= 0, in feasible mode (bar_feasible=1, which is
only used for inequalities) with a feasible initial point, Knitro will
remain in the feasible domain with the tolerance defined by
bar_feasmodetol. If there is a theorem saying that the det(M)>=0
domain around the initial matrix contains only positive definite
matrices, then the answer is yes : the algorithm will stay in a subset
of positive definite matrices.

(2) PennSDP accepts non-linear objectives. Such solvers enforce the
det M >= 0 condition (with a penalty of the log(det(M)) kind), but,
backtrack if they fall on a non positive definite matrix (KNITRO does
not do that). It may be that backtracking is not needed on your
problem, so that KNITRO works fine.

Nicolas Omont.

> > > Ryutaroh Matsumoto- Hide quoted text -
>
> - Show quoted text -

[Ryutaroh Matsumoto]

Dear Nicolas,

Thank you very much for your help.

Ryutaroh Matsumoto

On 10月30日, 午後8:18, Artelys Knitro support team <support-