Interior-point method: Difference between revisions

Revision as of 11:07, 30 November 2023

Revision as of 11:13, 30 November 2023

Line 60:

=== Details ===

We are given a convex optimization problem (P) in "standard form", :<blockquote>'''minimize ''c''^T''x'' s.t. ''x'' in ''G''''', </blockquote>where ''G'' is convex and closed. We can also assume that ''G'' is bounded (otherwise, we can add a constraint |''x''|≤''R'' for some sufficiently large ''R'').<ref name=":0" />{{Rp|___location=Sec.4}}

To use the interior-point method, we need a [[self-concordant barrier]] for ''G''. Let ''b'' be an ''M''-self-concordant barrier for ''G'', where ''M''≥1 is the self-concordance parameter. We assume that we can compute efficiently the value of ''b'', its gradient, and its [[Hessian matrix|Hessian]], for every point x in the interior of ''G''.

Line 81:

== Potential-reduction methods ==

{{Expand section|date=November 2023}}

Potential-reduction methods are elaborated in.<ref name=":0" />{{Rp|___location=Sec.5}} For potential-reduction methods, the problem is presented in the ''conic form'':<blockquote>'''minimize ''c''^T''x'' s.t. ''x'' in ''{b+L} ᚢ K''''', </blockquote>where ''b'' is a vector in R^''n'', L is a [[linear subspace]] in R^''n'' (so ''b''+''L'' is an [[affine plane]]), and ''K'' is a closed pointed [[convex cone]] with a nonempty interior. Every convex program can be converted to the conic form.

Potential reduction methods are elaborated in.<ref name=":0" />{{Rp|___location=Sec.5}}

==Primal-dual methods==