English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

This study examines two different barrier functions and their use in both path-following and potential-reduction interior-point algorithms for solving a linear program of the form: minimize c T x subject to Ax = b and l (le) x (le) u , where components of l and u can be nonfinite, so the variables x j , can have 0-, 1-, or 2-sided bounds, j = 1, ..., n . The barrier functions that we study include an extension of the standard logarithmic barrier function and an extension of a barrier function introduced by Nesterov. In the case when both l and u have all of then components finite, these barrier functions are $$\Psi(x)=\sum_j\left\{-\ln(u_j - x_j) -\ln (x_j - l_j)\right\}$$ and $$\Psi(x)=\sum_j\left\{-\ln\left(\min\{u_j - x_j, x_j - l_j\}\right)+\min \{u_j - x_j, x_j - l_j\} / ((u_j - l_j)/2)\right\}.$$ Each of these barrier functions gives rise to suitable primal and dual metrics that are used to develop both path-following and potential-reduction interior-point algorithms for solving such linear programming problems. The resulting complexity bounds on the algorithms depend only on the number of bounded variables, rather than on the number of finite inequalities in the system 1 (le) x (le) u , in contrast to the standard complexity bounds for interior-point algorithms. These enhanced complexity bounds stem directly from the choice of a “natural” metric induced by the barrier function. This study also demonstrates the inter-connection between the notion of self-concordance (introduced by Nesterov and Nemirovsky) and properties of the two barrier functions that drive the results contained herein.

Barrier Functions and Interior-Point Algorithms for Linear Programming with Zero-, One-, or Two-Sided Bounds on the Variables