0
$\begingroup$

Assume that we have the following class of primal QCQP problems

$$ \begin{array}{ll} \text{minimize}_\alpha & f(\alpha) \\ \text{subject to} & h(\alpha)\leq t, \end{array} $$ that are solvable (strictly convex objective) and satisfy Slater's condition for all $t\in(a,b)$, for which no closed form solutions has been found.

Also consider the corresponding class of dual problems $$ \begin{array}{ll} \text{maximize}_\alpha & g_t(\alpha) \\ \text{subject to} & \lambda \geq 0, \end{array} $$ where $g_t(\lambda) = \inf_{\alpha}\{ f(\alpha)+\lambda [h(\alpha)-t] \}$ for any $\lambda \geq 0$ and $t\in(a,b)$.

For any fixed $t\in(a,b)$, we let $\alpha^\star(t)$ denote the solution to the primal problem with constraint bound $t$. By strong duality, there exists a unique $\lambda^*(t)$ for which $$p^\star(t) := f(\alpha^\star(t)) = g_t(\lambda^\star(t))=:d^\star(t)$$

So far I have been able to prove that $\alpha^\star(t)$ is also the unique solution to the minimization problem $$ \text{minimize}_\alpha \quad f(\alpha) + \lambda^\star(t) h(\alpha). $$ In my setup this minimization problem has an easily derived closed form solution, hence instead of solving the primal problem, I would like to simply solve this latter optimization problem.

However, in order to do this, we need to find $\lambda^\star(t)$.

My question: is there any way to find $\lambda^\star(t)$ for all $t\in(a,b)$? That is, to find the relationship/map $ t\mapsto \lambda^\star(t)$, between the constraint bound $t$ and the corresponding dual solution $\lambda^\star(t)$.

$\endgroup$
4
  • 1
    $\begingroup$ You know $\lambda^*(t)$ is an optimal solution to the dual problem, right? Therefore, the question is if you can solve the dual problem efficiently. Just for clarity, $h$ is scalar-valued, right? $\endgroup$
    – LinAlg
    Oct 25, 2019 at 1:26
  • $\begingroup$ I actually haven't explored this, I will have a look into that. Yes both $f$ and $h$ are scalar valued. $\endgroup$
    – John
    Oct 25, 2019 at 9:03
  • 1
    $\begingroup$ was the exploration helpful at all? $\endgroup$
    – LinAlg
    Oct 29, 2019 at 13:28
  • $\begingroup$ @LinAlg I have not had time to look at it yet. But I doubt I will get any other useful answer. So I suggest you post your comment as an answer and I will award you the bounty if no-one has another smart way to look at it. $\endgroup$
    – John
    Oct 29, 2019 at 21:18

1 Answer 1

1
$\begingroup$

Your convex optimization problem satisfies Slater's condition, and hence strong duality holds. By strong duality, $\alpha^\star(t)$ must be an optimal point that minimizes $f(\alpha) + \lambda^\star(t)\left(h(\alpha) - t\right)$. Similarly, $\lambda^\star(t)$ must be an optimal point that maximizes $f(\alpha^*(t)) + \lambda\left(h(\alpha^*(t)) - t\right)$.

You seem to say that you can easily find a closed-form solution for the following problem: $$ \text{minimize}_\alpha \quad f(\alpha) + \lambda^*(t)(h(\alpha)-t). $$ Let your closed-form solution be denoted by $$ \alpha^*(t) = q(\lambda^*(t)).$$

Scenario one:

You further have a closed-form solution to the following optimization problem (or you can generalized your current closed-form solution to): $$ \text{minimize}_\alpha \quad f(\alpha) + \lambda(h(\alpha)-t). $$ Then you have access to $g_t(\lambda)=f(q(\lambda)) + \lambda(h(q(\lambda))-t)$, and you can simply try to take the first order derivative to find $\lambda^*(t)$.

Scenario two:

Your ability of getting a closed-form solution for minimizing the Langrangian is limited to $\lambda^*(t)$. Then you can try the following iterative process. That is, for any $t$,

  • start with arbitrary guess of $\lambda_0$;
  • from $\lambda_n$, take derivative of $g_t(\lambda)=f(q(\lambda)) + \lambda_n(h(q(\lambda))-t)$ to find a better approximation $\lambda_{n+1}$ where $q(\cdot)$ is the closed-form solution equation you derived;
  • repeat the above step until the dual gap disappears.
$\endgroup$
1
  • $\begingroup$ Hi @Xiaohai, For some reason I can't award you the bounty? $\endgroup$
    – John
    Nov 2, 2019 at 18:16

You must log in to answer this question.

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