# Can I determine a parameter in the objective function of a convex problem, given the optimal solution?

Considering a convex optimization problem with inequality constraints: \begin{aligned} \min_{x\in\Re^{n}} & ~x^\top H x + f^\top x + \lambda\sqrt{x^\top R x}\\ \text{s.t.} & ~Ax\leq b \end{aligned}, where both matrices $$H$$ and $$R$$ are positive definite. If the optimal solution $$x^*$$ is given and assume that the non-negative scalar $$\lambda$$ is unknown, I am wondering, is it possible to estimate the value of the $$\lambda$$?

Many Thanks!

• The inequality $\ Ax<b\$ typically means that every entry of the column vector on the left side of the inequality is strictly less than the corresponding entry of $\ b\$. Is that the case here? If it is, then the problem with the constraint will have an optimal solution if and only there's an optimal solution of the unconstrained problem which satisfies the constraint. Commented Jun 21, 2021 at 1:45
• Shouldn't $\lambda >0$ be a constraint. Because it seems that otherwise the problem could become unbounded Commented Jun 21, 2021 at 3:48
• @rostader I guess $\ \lambda\$ could be zero, but if it were strictly negative, then I don't believe the objective function would be convex on $\ \mathbb{R}^n\$, although I haven't formally checked that. So yes, $\ \lambda\$ must be restricted to non-negative values. However, I gather it's supposed to be a fixed constant whose value is unknown, rather than a variable to be optimised over, so, strictly speaking, $\ \lambda\ge0\$ isn't a "constraint" of the optimisation problem as such. Commented Jun 21, 2021 at 5:56
• Okay. So I definitely don't understand the problem. Given $x^*$ this reduces to a problem of a function in $\lambda$. So I can choose $\lambda$ to be whatever I want. The constraint doesn't play any role because I already have an $x^*$. So unless I am given some more information on what the optimal value of the objective function is I can't really say anything about $\lambda$. Commented Jun 21, 2021 at 17:49
• $Ax<b$ or $Ax\le b$? Commented Jun 22, 2021 at 8:42

Let $$\gamma = \sqrt{(x^*)^T Rx^*}$$. Notice that $$x^*$$ is a minimizer for the problem \begin{align} \tag{1} \text{minimize} & \quad x^T H x + f^T x \\ \text{subject to} &\quad Ax \leq b, \\ &\quad \sqrt{x^T R x} \leq \gamma. \end{align}

Solve problem (1) using an algorithm such as an interior point method that will compute a Lagrange multiplier $$\lambda$$ for the constraint $$\sqrt{x^T R x} \leq \gamma$$. According to a Lagrange multiplier theorem, which tells us roughly speaking that hard constraints can be replaced with penalty terms in the objective, $$x^*$$ is optimal for your original optimization problem with the value of $$\lambda$$ found by solving problem (1).

The CVX or CVXPY software packages make it easy to solve small instances of problem (1), obtaining Lagrange multipliers for the constraints. That might be an easy way to test out this approach.

• Hi, thank you for your replying. I varied $\lambda$ between 0 and 1, get different optimal solutions $x^*$ and tried to solve problem (1) using MOSEK and get dual variable of the inequality constraint as the estimated $\hat{\lambda}$, however it couldn't give me the correct answer. BTW, what is the problem (2)? Commented Jun 22, 2021 at 6:43
• BTW, solving the problem (1) will get the identical result of the optimal $x^*$ Commented Jun 22, 2021 at 6:59
• Oh, writing (2) was a typo, I meant to write problem (1). I fixed that. Commented Jun 22, 2021 at 7:04
• Yes, the $x^*$ you obtain by solving your original problem is optimal for problem (1). So solving (1) will indeed yield the same solution $x^*$. Commented Jun 22, 2021 at 7:05
• The difference is significant. For example, I use $\lambda = 0.0001$, the optimal value of my original problem is -5.37e5. If I substitude the optimal $x$ that is calculated using estimated $\hat{\lambda} = 3.4795$ into my original problem, I got objective function = -3.6488e5, which is much worse. Commented Jun 22, 2021 at 8:58

Some thoughts:

Let $$\theta$$ denote the Lagrange multiplier. Then, $$(\lambda, x^\ast, \theta)$$ satisfies the system \begin{align*} 2Hx^\ast + f + \lambda\frac{Rx^\ast}{\sqrt{(x^\ast)^\mathsf{T} R x^\ast}} + A^\mathsf{T}\theta &= 0, \\ \theta^\mathsf{T}(Ax^\ast - b) &= 0, \\ \theta &\ge 0, \\ \lambda &\ge 0. \end{align*} Since the system above is linear in $$(\lambda, \theta)$$, we can find a feasible $$(\lambda, \theta)$$ by using convex programming.

I tested some examples (I use cvx + matlab), and it works.

• Thank you, I think your "KKT condition" idea is equivalent to solving littleO's problem (1), but I will try it! Commented Jun 23, 2021 at 5:37
• I think because $A\in\Re^{(2n+2)\times n}$, the feasible solution $(\lambda,\theta)$ will not be unique. Commented Jun 23, 2021 at 6:53
• @StephenGe So, it fails for your examples? I used cvx to minimize $\lambda$ subject to the linear system which return the desired. Commented Jun 23, 2021 at 7:05
• I tried, it works & it is fast, thanks Commented Jun 23, 2021 at 8:31
• @StephenGe Nice. We need to prove that $\lambda$ is unique. Commented Jun 23, 2021 at 9:05