Barrier and primal dual interior point methods — Examples

For every admissible $\mathrm{\Delta }$, [F1] gives $\mathrm{\parallel }(A+\mathrm{\Delta })x-b{\mathrm{\parallel }}_2\le \mathrm{\parallel }Ax-b{\mathrm{\parallel }}_2+\rho \mathrm{\parallel }x{\mathrm{\parallel }}_2$. If $x\mathrm{\ne }0$ and $r=Ax-b\mathrm{\ne }0$, choose $u=r\mathrm{/}\mathrm{\parallel }r{\mathrm{\parallel }}_2$ and $\mathrm{\Delta }=\rho u{x}^T\mathrm{/}\mathrm{\parallel }x{\mathrm{\parallel }}_2$; then $\mathrm{\parallel }\mathrm{\Delta }{\mathrm{\parallel }}_F=\rho$ and $\mathrm{\Delta }x=\rho \mathrm{\parallel }x{\mathrm{\parallel }}_{2}u$, attaining the upper bound. If $r=0$, any unit $u$ gives the same supremum; if $x=0$, the perturbation term vanishes.

Therefore the robust objective equals $\mathrm{\parallel }Ax-b{\mathrm{\parallel }}_2+\rho \mathrm{\parallel }x{\mathrm{\parallel }}_2$. Introducing epigraph variables $t,u$ gives $\min t+\rho u$ subject to $(t,Ax-b)\in {\mathcal{L}}_{m+1}$ and $(u,x)\in {\mathcal{L}}_{n+1}$ by [F2], which is an SOCP.

The closed feasible triangle $\{x_1\ge 0,x_2\ge 0,x_1+x_2\le 1\}$ is compact, and $x_1,x_2,q$ lie in $[0,1]$. On its strict interior, each barrier term is nonnegative; as any boundary point is approached, at least one of $x_1,x_2,q$ tends to zero and its negative logarithm tends to $+\mathrm{\infty }$, while $t{x}_1$ is bounded. Fix any strict-interior point. Its objective sublevel set is therefore separated from the boundary, closed in the compact triangle by continuity, and compact; the objective attains a strict-interior minimizer. Direct differentiation gives $H_t=\left(\begin{array}{cc}{x}_1^{-2}+q^{-2}& q^{-2}\\ q^{-2}& x_2^{-2}+q^{-2}\end{array}\right)$, whose quadratic form is $h_1^2\mathrm{/}{x}_1^2+h_2^2\mathrm{/}{x}_2^2+(h_1+h_2{)}^2\mathrm{/}{q}^2>0$ for every nonzero $h$, so the minimizer is unique. At the central point, the $x_2$ derivative is $-1\mathrm{/}{x}_2+1\mathrm{/}q=0$, hence $q=x_2$ and $x_1+2x_2=1$. The $x_1$ derivative is $t-1\mathrm{/}{x}_1+1\mathrm{/}q=0$, so $1\mathrm{/}{x}_1=t+1\mathrm{/}{x}_2>t$ and $0<x_1<1\mathrm{/}t$. Consequently $x_1\to 0$ and $x_2=q\to 1\mathrm{/}2$ as $t\to \mathrm{\infty }$.

For $t\ge 4$, step 1.1 gives $x_1<1\mathrm{/}4$ and $x_2=q=(1-x_1)\mathrm{/}2>3\mathrm{/}8$. By [F2] applied to the coordinate unit vectors, ${\lambda }_{\max }(H_t)\ge (H_t{)}_{11}>x_1^{-2}>t^2$ and $0<{\lambda }_{\min }(H_t)\le (H_t{)}_{22}=x_2^{-2}+q^{-2}<2(8\mathrm{/}3{)}^2=128\mathrm{/}9$. With ${\kappa }_2(H_t):={\lambda }_{\max }(H_t)\mathrm{/}{\lambda }_{\min }(H_t)$ for this positive-definite Hessian, ${\kappa }_2(H_t)>9t^2\mathrm{/}128$, exhibiting growing conditioning as the central path approaches the boundary.

The slice $X_{11}=1$, $X_{22}=0$ is feasible at $X=\mathrm{diag}(1,0)$ but has no positive-definite point: a symmetric matrix in the slice is $X(a)=\left(\begin{array}{cc}1& a\\ a& 0\end{array}\right)$. If $a\mathrm{\ne }0$, the vector $(-a,1)$ gives $(-a,1)X(a)(-a,1{)}^T=-a^2<0$, so $X(a)$ is not positive semidefinite; if $a=0$, it is singular. Its Phase-I margin with $e=I$ is $0$, since $X(0)+\tau I=\mathrm{diag}(1+\tau ,\tau )⪰0$ for $\tau \ge 0$ and is impossible for $\tau <0$ by testing the second coordinate.

Every matrix in the slice $X_{22}=0$, $X_{12}=1$ has form $X(t)=\left(\begin{array}{cc}t& 1\\ 1& 0\end{array}\right)$. If $t>0$, the vector $(-1\mathrm{/}t,1)$ gives quadratic form $-1\mathrm{/}t<0$; if $t=0$, vector $(-1,1)$ gives $-2<0$; if $t<0$, vector $(1,0)$ gives $t<0$. Thus the slice is infeasible. For $t>0$, the matrix $Y(t)=\left(\begin{array}{cc}t& 1\\ 1& 1\mathrm{/}t\end{array}\right)$ is positive semidefinite because its quadratic form is $t(u+v\mathrm{/}t{)}^2$; its Frobenius distance from $X(t)$ is $1\mathrm{/}t\to 0$. For any $\tau >0$, choose $t=1\mathrm{/}\tau$. Then $X(t)+\tau I$ has quadratic form $(\frac{1}{\tau }+\tau )u^2+2uv+\tau v^2=(\frac{1}{\tau }+\tau ){(u+\frac{\tau v}{1+{\tau }^2})}^2+\frac{{\tau }^3}{1+{\tau }^2}{v}^2$, which is positive for every nonzero $(u,v)$, so it is positive definite and $\tau$ is Phase-I feasible. If $\tau <0$, the lower-right diagonal entry of $X(t)+\tau I$ is $\tau <0$, so it cannot be positive semidefinite. Hence the Phase-I infimum is zero and is not attained.

Substituting $x_2=1-x_1$, stationarity of the barrier objective gives $-t-1\mathrm{/}{x}_1+1\mathrm{/}{x}_2=0$, or $1\mathrm{/}{x}_2-1\mathrm{/}{x}_1=t$. Multiplying by $x_1{x}_2>0$ and using $x_1+x_2=1$ yields $t{x}_1^2+(2-t)x_1-1=0$. Its roots are $(t-2\pm \sqrt{t^2+4})\mathrm{/}(2t)$; because $\sqrt{t^2+4}>\mathrm{\mid }t-2\mathrm{\mid }$, only the plus root is positive. Thus $x_1=(t-2+\sqrt{t^2+4})\mathrm{/}(2t)$, and rationalizing $1-x_1$ gives $x_2=2\mathrm{/}(t+2+\sqrt{t^2+4})>0$. These coordinates sum to one and satisfy stationarity. The restricted second derivative is $1\mathrm{/}{x}_1^2+1\mathrm{/}{x}_2^2>0$, so the stationary point is the unique exact central point. At $t_0=1$ these become the values in Given, whose reciprocal difference is $1$; hence the supplied start is exact and its decrement is zero.

The central inequality multipliers are ${\lambda }_i=1\mathrm{/}(t{x}_i)>0$. Their difference is ${\lambda }_2-{\lambda }_1=(1\mathrm{/}t)(1\mathrm{/}{x}_2-1\mathrm{/}{x}_1)=1$, so the equality multiplier $y=1-{\lambda }_1=2-{\lambda }_2$ satisfies both dual stationarity equations. Every primal feasible vector has objective $x_1+2x_2=1+x_2\ge 1$, while $(1,0)$ attains $1$, so $p^{\ast }=1$ and the objective excess is $x_2$. The primal-dual gap is $x_1{\lambda }_1+x_2{\lambda }_2=2\mathrm{/}t$; hence $x_2\le 2\mathrm{/}t$ by [F1]. By [F3], $\nu =2$. For $0<\epsilon <3$, put $K=\lceil \log (3\mathrm{/}\epsilon )\mathrm{/}\log (1+1\mathrm{/}(8\sqrt{2}))\rceil$, supply exact solves of the scalar restricted Newton equations, and choose $N_{out}\ge K$ and $N_{in}\ge 2$. Their scalar Hessian is positive by step 1.1. With the exact $t_0=1$ start from that step and $p^{\ast }=1$, all hypotheses of [F2] hold, so at most $K$ path updates suffice, with at most two corrections each.

The primal residual is $(1,1)\cdot (3\mathrm{/}5,2\mathrm{/}5)-1=0$. The dual stationarity residual is $c-A^{T}y-s=(1,2)-(1,1)-(0,1)=(0,0)$, and $x\ge 0$, $s\ge 0$, so the candidate pair is exactly feasible.

The primal objective is $3\mathrm{/}5+2(2\mathrm{/}5)=7\mathrm{/}5$, the dual value is $by=1$, and the gap is $x^{T}s=2\mathrm{/}5$. Every primal feasible vector has $x_1+x_2=1$, $x_i\ge 0$, and objective $x_1+2x_2=1+x_2\ge 1$; the feasible point $(1,0)$ attains $1$, so $p^{\ast }=1$. Thus the objective error is exactly $7\mathrm{/}5-1=2\mathrm{/}5=x^{T}s$, and [F2] gives the same certified upper bound.

Write the minimization objective as $C\bullet X=-X_{12}$ with $C=\left(\begin{array}{cc}0& -1\mathrm{/}2\\ -1\mathrm{/}2& 0\end{array}\right)$. For any feasible $X$, [F1] applied to $e_1-e_2$ gives $2-2X_{12}\ge 0$, hence $-X_{12}\ge -1$. The feasible matrix $X_{\ast }=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ attains $-1$.

The dual multiplier $y=(-1\mathrm{/}2,-1\mathrm{/}2)$ and slack $S=\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$ satisfy $v^{T}Sv=\frac{1}{2}(v_1-v_2{)}^2\ge 0$ for every $v$, hence $S⪰0$. Direct addition gives $\mathrm{diag}(y)+S=C$. Their dual value is $y_1+y_2=-1$, and $X_{\ast }\bullet S=0$. Thus the displayed primal and dual values match and certify the relaxation optimum.