1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting problem, I'll try to have a look at it later (ping me if I don't). Have you tried other ways of combining the primal and the dual and arriving at a simplex-like feasible region? Could you share the primal/dual formulation before you apply the transformation? $\endgroup$ – LinAlg Nov 1 '18 at 12:41
  • $\begingroup$ The dual will be the lagrangian dual. If helpful replace the original problem with the primal minus the dual so the optimal value will be zero. Although unsure if necessary. I wonder if the author got his references mixed up. $\endgroup$ – DAS Nov 2 '18 at 11:01
  • $\begingroup$ oh my good god. The author in the paper said to check the fifth section of his reference labeled [1] which is the Karmarkar paper. So on a whim I went and decided to check the fifth section (if it existed) of his reference labeled 10 instead of [1]. And I think this may address it still don't know why he was talking about Karmarkar though, doubly confusing. bit too tired to check now. we'll see tomorrow. $\endgroup$ – DAS Nov 2 '18 at 11:18
  • $\begingroup$ Good find! That seems to address the question with a completely different solution. $\endgroup$ – LinAlg Nov 2 '18 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.