0
$\begingroup$

I have a qudratic programming problem

$$J_{min} : \frac {1}{2}x^TQx + c^Tx \\ S.T \\ Ax \leq b \\ x \geq 0$$

But I have only a solver for linear programming using simplex method.

$$J_{max} : c^Tx \\ S.T \\ Ax \leq b \\ x \geq 0$$

I have heard that if I change simplex method so it will minimize $J_{max}$ instead of maximize it. That is called the Dual method. It's is an easy change with some transposes of the objective function.

But if I combine the Dual method with KKT conditions. Then I can solve qudratic programming problems?

If yes: How can I rewrite KKT conditions so they work with the Dual method?

If no: What have I missed? I know that it's possible to use linear programming to solve for qudratic programming.

$\endgroup$
1
$\begingroup$

Still me. It is possible to solve the quadratic programming with simplex method.

Method 1

The Lagrangian function of original problem is \begin{equation} L(x; \lambda_1, \lambda2) = \frac{1}{2}x^TQx + c^Tx + \lambda_1^T(Ax-b) - \lambda_2^T x, \quad \lambda_1, \lambda_2 \ge 0. \end{equation} And the KKT conditions are \begin{equation} \begin{array}{c} {\nabla_x L(x;\lambda_1,\lambda_2) = Qx+c+A\lambda_1-\lambda_2 = 0.} \\ {Ax-b \leq 0, \quad x \ge 0.} \\ {\lambda_1 \ge 0, \quad \lambda_2 \ge 0.} \\ {\lambda_1^T(Ax-b)=0, \quad \lambda_2^T x= 0.} \end{array} \end{equation} Except the last complementary slack condition, All of them are linear. We temperately drop this condition, and add one slack variable $y$, then can obtain \begin{equation} \begin{array}{c} {Qx+c+A\lambda_1-\lambda_2 = 0} \\ {Ax-b+y = 0} \\ {x \ge 0, \lambda_1 \ge 0, \lambda_2 \ge 0, y \ge 0} \end{array} \end{equation} And we can use simplex method to search feasible solution of the above constraints. However, to satisfied the complementary slack condition, we must take one of ${\lambda_1}_i$ and $y_i$ as zero. Similarly, we also must take one of ${\lambda_2}_i$ and $x_i$ as zero. In other words, we need to keep ${\lambda_1}_i$ and $y_i$, ${\lambda_2}_i$ and $x_i$ could not be basis variables at the same time.

Method 2

But now I guess what you want is another method which is called Frank-Wolfe algorithm. For the iterative point $x_k$ at $k$ step, we can compute the gradient \begin{equation} \nabla_x J(x_k) = Qx_k + c \end{equation} And we try to solve the following approximated problem: \begin{equation} \begin{array}{cl} {\min_{x}} & J(x_k)+ \nabla_{x}J(x_k)^T(x-x_k) \\ {} & {Ax -b \leq 0} \\ {} & {x \ge 0} \end{array} \end{equation} This is a linear programming in terms of $x$, and you can solve it directly by the Simplex method.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Is this the same method? I just use KKT conditions with simplex? Do you have Matlab? Can you show how to solve a QP-problem with the function linprog? :) researchgate.net/publication/… $\endgroup$ – Daniel Mårtensson Mar 29 at 11:47
  • $\begingroup$ I took a brief look at this paper, and it seems that it is the same method. And I found that this answer may be will helpful to you. In this answer, it says that the 'quadprog' function in Matlab actually reproduce this active set method. $\endgroup$ – Ze-Nan Li Mar 29 at 15:46
  • $\begingroup$ So I can just follow this paper and I don't need to change anything on my Simplex solver? I wrote it by my self in C code. Don't want to change it again hehe. $\endgroup$ – Daniel Mårtensson Mar 29 at 18:24
  • $\begingroup$ @Royi, thanks a lot. Here are two different approaches. The first one is called Wolfe's modified simplex method (I guess), which is actually an active set method. And the second one is Frank-Wolfe algorithm. $\endgroup$ – Ze-Nan Li Mar 30 at 1:49
  • $\begingroup$ @DanielMårtensson, I think you still need to modify your simplex method, especially the selection of the basis variable. In this paper, they just drop the complementary slack condition because they can choose the optimal solution from the table. If you don't want to change anything in your code, I guess you can consider the second method. $\endgroup$ – Ze-Nan Li Mar 30 at 1:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.