The LP-Newton Method and Conic Optimization

Authors Francesco Silvestri, Gerhard Reinelt

Publication date 28 November 2016

Linear programming (90C05) Semidefinite programming (90C22) Methods of quasi-Newton type (90C53)

Abstract: We propose that the LP-Newton method can be used to solve conic LPs over a conic box, whenever linear optimization over an otherwise unconstrained conic box is easy. In particular, if

l e q_{m} a t h c a l K

is the partial order induced by a proper convex cone

m a t h c a l K

, then optimizing a linear function over the intersection of

[l, u]_{m} a t h c a l K = l l e q_{m} a t h c a l K x l e q_{m} a t h c a l K u

and an affine subspace can be done with this method whenever optimizing a linear function over

[l, u]_{m a t h c a l K}

is efficient. This generalizes the result for the case of

m a t h c a l K = m a t h b b R_{+}^{n}

that was originally proposed for using the method. Specifically, we show how to adapt this method for both SOCP and SDP problems and illustrate the method with a few experiments. While the approach is promising due to the low amount of Newton steps needed, solving the minimum-norm-point problem involved in the Newton step with a Frank-Wolfe algorithm is not advisable.

This page was built for publication: The LP-Newton Method and Conic Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280233)