Interior-point method: Difference between revisions

Revision as of 15:42, 25 October 2024

Revision as of 16:09, 30 October 2024

Line 63:

* The solver is Newton's method, and a ''single'' step of Newton is done for each single step in ''t''.

They proved that, in this case, the difference ''x_i'' - ''x''*(''t_i'') remains at most 0.01, and f(''x_i'') - f* is at most 2*''m''/''t_i''. Thus, the solution accuracy is proportional to 1/''t_i'', so to add a single accuracy-digit, it is suffiicentsufficient to multiply ''t_i'' by 2 (or any other constant factor), which requires O(sqrt(''m'')) Newton steps. Since each Newton step takes O(''m n''²) operations, the total complexity is O(''m^3/2 n''²) operations for accuracy digit.

[[Yurii Nesterov|Yuri Nesterov]] extended the idea from linear to non-linear programs. He noted that the main property of the logarithmic barrier, used in the above proofs, is that it is [[self-concordant]] with a finite barrier parameter. Therefore, many other classes of convex programs can be solved in polytime using a path-following method, if we can find a suitable self-concordant barrier function for their feasible region.<ref name=":0" />{{Rp|___location=Sec.1}}