8
$\begingroup$

At the moment I'm studying constrained optimization. Recently we had a lecture concerning dual problems. I have a few questions regarding this.

The primal problem is given as \begin{align} \min_x \quad & \frac{1}{2} x^THx+g^Tx \\ \text{s.t.} \quad & A^Tx = b . \end{align} The Lagrange dual program of the equality constrained QP is given as \begin{align} \max_{x,\lambda} & \qquad - \frac{1}{2} x^THx+b^T \lambda, \\ \text{s.t} & \qquad Hx+g-A\lambda = 0. \\ \end{align} It's assumed that the matrix H is positive definite.

My questions are as follows.

  1. How is this maximization problem derived?
  2. What are the optimality conditions for the dual problem and how are they related to the primal problem?
  3. When does the primal and dual problem have the same solution?
  4. Can one use KKT for the solution of this problem?
  5. How are the variables in the primal and dual problem related in general?
  6. What are the advantage of solving the dual instead of the primal problem?

I have a few suggestions myself.

Q1: I've read that we define the dual objective as the infimum of the Lagrange, that is $q(\lambda) = \inf_x L(x, \lambda)$. The dual problem is then the maximization of q. However I'm in doubt about the constraints in the dual problem.

Q2: Don't know.

Q3: Is it when the primal problem is strictly convex (meaning a positive definite hessian in the primal objective function)?

Q4: Don't know. Guess it depends on the optimality conditions somehow.

Q5: Don't know.

Q6: Don't know.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

I'll assume that $H$ is symmetric positive definite (as stated in the question).

The Lagrangian is \begin{align} L(x,\lambda) &= \frac12 x^T Hx + g^T x + \lambda^T (A^Tx - b) \\ &= \frac12 x^T H x+ x^T (A \lambda + g) - \lambda^T b. \end{align} The dual function is \begin{align} g(\lambda) &= \inf_x \, L(x,\lambda) \\ &= -\frac12 (A \lambda + g)^T H^{-1} (A \lambda + g) - \lambda^T b. \end{align}

The dual problem is to maximize $g(\lambda)$ (with no constraints on $\lambda$). Is this equivalent to the dual problem given in the question? From the constraint $Hx + g - A \lambda = 0$, it follows that $x = H^{-1}(A \lambda - g)$. Plugging into the objective function, the stated dual problem reduces to \begin{align} \text{maximize} & \quad -\frac12 (A \lambda - g)^T H^{-1}(A \lambda - g) + b^T \lambda \\ \text{subject to} & \quad \lambda \geq 0. \end{align} This is similar to the dual problem I derived, except that we have $-g$ in place of $g$ and we have an extra constraint $\lambda \geq 0$.

It seems like the dual problem given in the question is wrong.

$\endgroup$
5
  • $\begingroup$ You are right. The constraint on lambda is not correct. I'll delete it. Further I've come up with some answers for some of the question myself. Thanks for your reply though :) $\endgroup$
    – ANYN11
    Mar 29, 2016 at 16:12
  • $\begingroup$ @littleO I'm working on a problem similar to this, where I have posted a question here: math.stackexchange.com/questions/2571031/… Would you be willing and/or able to take a look and possibly help me out? Thanks so much! :) $\endgroup$
    – user100463
    Dec 17, 2017 at 21:53
  • $\begingroup$ @littleO: why is $\lambda\geq0$ needed? $\endgroup$
    – jjjjjj
    Jul 25, 2021 at 22:27
  • $\begingroup$ @jjjjjj What I was writing down there was the dual problem which was stated in a previous version of the question [the question has since been edited], and I was commenting that the "stated" dual problem seems to be wrong, because indeed the constraint $\lambda \geq 0$ should not be there. This answer I posted only made sense in response to a previous version of the question. $\endgroup$
    – littleO
    Jul 25, 2021 at 23:23
  • $\begingroup$ gotcha, thanks! $\endgroup$
    – jjjjjj
    Jul 25, 2021 at 23:24
0
$\begingroup$

I searched some literature. It appears this duality is from the paper Duality in Quadratic Programming by W. S. Dorn. Here is a link to that paper: https://www.ams.org/journals/qam/1960-18-02/S0033-569X-1960-0112751-2/S0033-569X-1960-0112751-2.pdf.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .