Karmarkar's canonical form for convex quadratic programs??

173 Views Asked by At

I'm working through this paper A Simple Polynomial-Time Algorithm for Convex Quadratic Programming which gives an interior point algorithm for convex quadratic programming. I've reached the end of the paper where I should be learning how to initialize the algorithm.

On page 8 the author states "Suppose that [the problem] is in the canonical form considered by Karmarkar", which I thought was something for linear programming only? However the author says that I can refer to section 5 (beginning on page 385) of A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR PROGRAMMING in order to learn how to "transform general convex quadratic programs into this canonical form". However the referenced paper appears to be Karmarkar's 1984 paper on linear programming. The fifth section of the paper shows how to transform a general linear programming problem into a special canonical form but does not state anything at all concerning quadratic programs.

I've attempted to apply the transformation given in Karmarkar's paper to the variables in the convex quadratic program. Since from the paper I'm looking at on page 8 it seems like this is what the author may have done (the $e$ is a vector of all ones, which corresponds to a strictly interior feasible point of the transformed problem). Let the original problem be given by

\begin{align} \underset{x}{\textrm{min}} \ & \ \frac{1}{2}x^T A x + x^Ta \\ \tag{P} \textrm{s.t.} \ & \ Bx = b \\ \ & \ x \geq 0 \end{align}

Where $A$ is an $n$ by $n$ positive semidefinite matrix, and $B$ is $m$ by $n$ with rank $m \leq n$. We want to map $(P)$ to a new convex quadratic minimization problem

\begin{align} \underset{y}{\textrm{min}} \ & \ \frac{1}{2} y^T C y + y^Tc \\ \tag{Q} \textrm{s.t.} \ & \ Dy = 0 \\ \ & \sum_i y_i = 1 \\ \ & \ y \geq 0 \end{align}

such that we can extract a solution to $(P)$ from any solution to $(Q)$ (the constraints here have the form of those in Karmarkar's canonical form for a linear program).

The projective transform from the positive orthant into a simplex considered in Karmarkar's paper is of the form \begin{align} \forall i \in \{1, 2, \dots, n\} & \quad y_i := \frac{x_i/E_i}{\sum_j(x_j/E_j)+1} \\ &y_{n+1} := 1 - \sum_{j=1}^{n}y_j \end{align} with inverse $$x_i = E_i y_i/y_{n+1}$$ where $E_i > 0$ is the ith entry of the diagonal matrix $E$ satisfying $BEe = b$ and $e$ is the vector of all ones. Substituting $E_i y_i/y_{n+1}$ for $x_i$ in $(P)$ gives

\begin{align} \underset{y}{\textrm{min}} \ & \ \frac{y^T C y}{2y_{n+1}^{2}} \\ \tag{R} \textrm{s.t.} \ & \ Dy = 0 \\ \ & \sum_i y_i = 1 \\ \ & \ y \geq 0 \end{align}

where

$$C = \begin{bmatrix} E^T A E & a \\ a^T & 0 \end{bmatrix}$$ and $$D = \begin{bmatrix}BE & -b\end{bmatrix}$$

There are a few problems with this which means that I must have interpreted the author of the paper I'm working through incorrectly.

Does anyone know anything about some sort of Karmarkar canonical form for convex quadratic programs or know what the author is talking about on page 8 of the first linked paper?

Any help or information is much appreciated. Thank you for your time and consideration.