User:ZeroVector/sandbox

The Central Curve

The central curve(or central path) is an algebraic curve arising from the use of an interior point method to solve an optimization problem. One particular algorithm of the interior point method is the barrier method. This method modifies the objective function of an optimization problem by adding a barrier function. The purpose of this barrier function is to incorporate the inequality constraints into the objective function, thus reducing the size of the feasible region. A side effect of using a barrier function is the introduction of a new variable, $0<\mu \leq 1$, into the objective function. As $\mu$ varies, the central path is formed by the optimal solutions $x^{*}(\mu )$ of our barrier function. the $\lim _{\mu \to o}x^{*}(\mu ),\,$ also exists, and is equal to the optimal solution $x^{*}$ of our original objective function (before the barrier function was introduced). These curves can be expressed by polynomial equations and studied through the use of algebraic geometry.

The Barrier Function

Perhaps the most basic example one could look at to understand the construction of the central curve is the linear programming case. Here, the objective function and all of the constraints are linear. Let us observe the following general linear program

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}&&c'x\\&\operatorname {subject\;to} &&Ax=b,\\&&&x\geq 0,\quad i=1,\dots ,n.\end{aligned}}$

Here $c,x\in \mathbb {R} ^{n}$ and $A$ is a $p\times n$ matrix. Depending on how large $n$ is, the constraints $x\geq 0$ can make the feasible region of this problem very large. The larger the feasible region, the harder it becomes to locate an optimal solution. Eliminating these inequality constraints in order to reduce the size of the feasible region is the motivation behind the barrier function. The idea is to modify the objective function in such a way that the inequality constraints are implied, thus erasing the need for them. This is achieved by adding terms $-logx_{j}$ to the objective function . As $x_{j}\rightarrow 0$, the objective function value increases to $\infty$. To counteract this, a new vairable $\mu$ is also introduced. We let $0<\mu \leq 1$ and define the following logarithmic barrier function $B_{\mu }(x)=c'x-\mu \sum _{j=1}^{n}logx_{j}\qquad j=1,\dots ,n$.

When $x_{j}\leq 0,B_{\mu }(x_{j})=\infty .$ This effectively erases the need for the inequality constraints $x\geq 0$, since in a standard feasible minimization optimization problem solutions that yield an objective function value of $\infty$ will not be optimal.

The Central Path and the Analytic Center

Using the barrier function we just constructed and our original optimization problem, we can construct a new optimization problem known as a barrier problem parameterized by $\mu >0$

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}&&B_{\mu }(x)\\&\operatorname {subject\;to} &&Ax=b,\\\end{aligned}}$.

Since $B_{u}(x)$ implies $x\geq 0$, we have no need for the inequality constraints on $x$. For every choice of $\mu >0$, we can find an optimal solution for $B_{u}(x)$, which we will call $x^{*}(\mu )$. As $\mu$ varies, a path is formed in the feasible region passing through the optimal solutions to the barrier function for every choice of $\mu$. This path is called the central curve (or central path). The $\lim _{\mu \to o}x^{*}(\mu )$ also exists and is equal to $x^{*}$, the optimal solution to the original linear optimization problem. The logic behind this fact is that when $\mu$ is very small,

$\mu \sum _{j=1}^{n}logx_{j}\qquad j=1,\dots ,n$

becomes very small as well, making $B_{u}(x)=c'x$, the objective function of the original optimization problem.

Example Computing the Central Path

Let us consider the following linear optimization problem,

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}&&x_{2}\\&\operatorname {subject\;to} &&x_{1}+x_{2}+x_{3}=1,\\&&&xx_{1},x_{2},x_{3}\geq 0.\end{aligned}}$

Our first step will first look at our barrier function $B_{\mu }(x)$. Here,

$B_{\mu }(x)=x_{2}-\mu \sum _{j=1}^{3}\log x_{j}\qquad j=1,\dots ,3$

$B_{\mu }(x)=x_{2}-\mu \log x_{1}-\mu \log x_{2}-\mu \log x_{3}$.

Now in order to compute the central path we have to solve the following optimization problem,

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}&&x_{2}-\mu \log x_{1}-\mu \log x_{2}-\mu \log x_{3}\\&\operatorname {subject\;to} &&x_{1}+x_{2}+x_{3}=1,\\\end{aligned}}$.

In the spirit of eliminating constraints, we can further modify our objective function by performing the substitution $x_{3}=1-x_{1}-x_{2}$. This gives us the following unconstrained optimization problem.

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}&&x_{2}-\mu \log x_{1}-\mu \log x_{2}-\mu \log(1-x_{1}-x_{2})\\\end{aligned}}$.

(Note that this problem is no longer linear). By taking derivatives and setting them equal to zero we find that the central path is given by

$x_{1}(\mu )={\frac {1-x_{2}(\mu )}{2}}$

$x_{2}(\mu )={\frac {1+3\mu -{\sqrt {1+9\mu ^{2}+2\mu }}}{2}}$

$x_{3}(\mu )={\frac {1-x_{2}(\mu )}{2}}$

The analytic center of the central curve can be computed by letting $\mu \rightarrow \infty$. Since $\lim _{\mu \to \infty }x_{2}(\mu )={\frac {1}{3}}$, then the analytic center is the point $(1/3,1/3,1/3)$.

Looking back at our original optimization problem, we wanted to minimize $x_{2}$ with the constraint that $x_{1}+x_{2}+x_{3}=1$ and $x_{2}$ was nonnegative. Clearly this is achieved by letting $x_{2}=0$ and making $x_{1},x_{3}$ such that $x_{1}+x_{3}=1$. If we construct a set $Q$ of all optimal solutions of this particular linear program

$Q=\{x|x=(x_{1},0,x_{3}),x_{1}+x_{3}=1,x\geq 0\}$

then the analytic center of the polyhedron $Q$ is the point $(1/2,0,1/2)$. Notice we can obtain the point $(1/2,0,1/2)$ by letting $\mu =0$, showing that the central path locates an optimal solution as $\mu \rightarrow 0$.

See also

optimization problem

convex optimization

linear programming

interior point method

algebraic curve

References

• Bertsekas,Dimitris, Tsitsiklis, John N. (1997). Introduction to Linear Optimization. Athena Scientific.{{cite book}}: CS1 maint: multiple names: authors list (link)

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved February, 2013. {{cite book}}: Check date values in: |accessdate= (help)

• {Jes´us A. De Loera, Bernd Sturmfels, and Cynthia Vinzant, The central curve in linear programming, Found. Comput. Math. 12 (2012), no. 4, 509–540. MR 2946462)