# Relationship between QCQP constraint bound and dual solution.

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)$$.

• 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? Oct 25, 2019 at 1:26
• I actually haven't explored this, I will have a look into that. Yes both $f$ and $h$ are scalar valued.
– John
Oct 25, 2019 at 9:03
• was the exploration helpful at all? Oct 29, 2019 at 13:28
• @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.
– John
Oct 29, 2019 at 21:18

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.
• Hi @Xiaohai, For some reason I can't award you the bounty?
– John
Nov 2, 2019 at 18:16