technical question about iterate update in coneqp/conelp

[bruno durin]

Joachim, Lieven,

I am trying to figure out the details of the implementation of your
conic algorithms as an exercise to check my understanding of the
theory. There is one step I do not understand.
Line 1971 of coneprog.py we have
ds = e + step*ds
dz = e + step*dz
Then line 1990
ds = H(lambda)^-1/2 ds
dz = H(lambda)^-1/2 dz
At this stage ds and dz are the updated iterate in the current
scaling.
But I find a different formula. On the one hand, noting P(x) the
quadratic representation of the Jordan algebra so that P(x) = H(x)^-1,
I get from your lines
dz = P(lambda^1/2)(e+step*ds) = lambda + step * P(lambda^1/2) * ds
where I used P(x) e = x^2
On the other hand starting from the naive step update:
S_n = S + step * DS
where S, DS are unscaled quantities ( (d)s = P(w)^-1/2 (D)S with w
scaling point of s,z P(w)z = s, or in the notation of the code, ds =
W^{-T} DS )
then
P(w)^-1/2 S_n = P(w)^-1/2 S + step * P(w)^-1/2 DS
s_n = lambda + step * ds
because lambda = P(w)^-1/2 S = P(w)^1/2 Z. s_n is the new iterate in
the current scaling.

Where does the P(lambda^1/2) * come from ? Did I make a mistake in my
derivation ?
Thank you for your help and from cvxopt, it works really well !

Sincerely,
Bruno Durin

[bruno durin]

Hi,

The answer and an additional question:

I missed the two far less (I mean, no comment highlighting the
operation as compared to the inverse operation) advertised lines
computing ds = H(lambda)^1/2 ds, lines 1938, 1939
misc.scale2(lmbda, ds, dims)
misc.scale2(lmbda, dz, dims)

One last question :
sigma = (1 - step) ** EXPON
is it an heuristic correction to mu or does it come from a formula (if
yes where can I find it) ?

Thank you,

Bruno

[Lieven Vandenberghe]

Bruno,

That is correct. The purpose of the more complicated update for s and
z is to work with the scaled variables as much as possible, to improve
stability. This is inspired by Jos Sturm's paper in Math. Prog. (vol
95, p 219, 2003).

The rule for sigma is a heuristic. For the conelp algorithm one can
show that the affine scaling direction satisfies

s' * dz + z' * ds = -s' * z
kappa * dtau + tau * dkappa = -tau*kappa
ds'*dz + dkappa*dtau = 0.

The expression for sigma is therefore equal to

sigma = ( new gap / current gap )**EXPON

where
new gap = ( s + step * ds ) ' * (z + step * dz) + (kappa + step *
dkappa ) * (tau + step * dtau)
current gap = s'*z + kappa * tau.

The second expression provides some justification for the choice of
sigma.
Most primal-dual codes use some variation on this heuristic.

Lieven

[bruno durin]

Thanks a lot ! Everything is clear now.

Bruno

On Sep 14, 2:38 am, Lieven Vandenberghe