2
$\begingroup$

This is a belated follow up to my question here, because I didn't want to tack questions onto questions.

According to the Mosek documentation here, one possibility for expressing $t \leq log(det(X))$, where $X$ is a symmetric positive semidefinite matrix variable to be optimized, as a semidefinite programming constraint is to reformulate it as

$$\begin{bmatrix}X & Z\\Z^{T} & diag(Z)\end{bmatrix} \succeq 0$$ $$s.t.$$ $$\text{Z is lower triangular} $$ $$t \leq \sum _{i}log(Z_{ii}) $$

The documentation goes on to state that "the optimal value of $det(X)$ is obtained when $Z=LD$ if $X=LDL^{T}$ is the $LDL$ factorization of $X$". The obvious way (to me at least) to express this is to define a new variable $M = \begin{bmatrix}X & Z\\Z^{T} & diag(Z)\end{bmatrix}$ along with constraints that $M \succeq 0$, $X \succeq 0$, and $Z$ being lower triangular. My question is, how do you express the requirement that $Z$ be lower triangular? Would you explicitly requiring that all superdiagonal entries of $Z$ be $0$, or is there a way of implicitly expressing this constraint? At least some of my confusion stems from the statement that $Z$ should be equal to $LD$ from $X$'s $LDL$ factorization, which would be simpler to express except that $X$ is a variable to be optimized and so we don't actually know what the $LDL$ factorization would look like in advance (when constraints have to be set).

The first answer to this question seems to get at similar ideas, but still has the issue that $X$ is not known in advance, so it's unclear to me how to ensure that $LDL^{T}=X$.

EDIT:

The reason for asking this question is that I'm trying to figure out how the constraint matrix that actually gets used in a low level solver is formed for this sort of problem.

$\endgroup$
2
$\begingroup$

You simply put zeros on the required positions, i.e. parameterize $Z$ using the required triangular basis. You never explicitly work with any factorization, that's just for proving that the optimization model yields the desired result at optimality.

Here implemented with YALMIP interfacing Mosek

% Random example (fixed A)
A = randn(5);A = A'*A;
% Define a scalar and a triangular matrix
sdpvar t
Z = tril(sdpvar(5));
% Solve
Model = [[[A Z';Z diag(diag(Z))] >= 0], t <= sum(log(diag(Z)))];
optimize(Model,-t)
% Compare
log(det(A))
value(t)
$\endgroup$
4
  • $\begingroup$ $A$ is a variable to be optimized, it is not an input to the problem. Apologies if the notation was confusing - I will edit it. What I'm trying to figure out, more broadly, is how you actually form the constraint matrix that gets operated on by the solving algorithm (whether that's interior point or ADMM, or whatever). Will elaborate a bit more in my question. $\endgroup$ – nick.schachter Apr 23 at 20:59
  • $\begingroup$ No difference if A depends on decision variables. I just showed a trivial problem where it was easy to check that the logdet operation works as expected. $\endgroup$ – Johan Löfberg Apr 24 at 6:59
  • $\begingroup$ Under the hood, are the constraints on the structure of $Z$ implemented as a combination of $A \vec{z} = b$, where $\vec{z}$ is the vectorization of $Z$ and $A$ and $b$ are a matrix and vector such that the equality only holds if $Z$ is lower triangular? $\endgroup$ – nick.schachter Apr 24 at 20:39
  • $\begingroup$ No, under the hood all variables parameterizing the triangular $Z$, t and possibly $A$ are collected in a variable $y$, and then data representing the conic model $\mathcal{C} - \mathcal{A}^Ty \succeq 0$ are gathered (i.e. this is a problem most likely benefiting from being interpreted as a representation of SDP dual form) $\endgroup$ – Johan Löfberg Apr 24 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.