Convex Optimization: Dual Function Definition

[Master1022]

Homework Statement

Given the following problem: find the dual and the dual solution.

Relevant Equations

Lagrange dual

Hi,

I was working through the following problem and I am getting confused with the solution's definition of the dual.

Problem:
Given the optimization problem:
minimize $x^2 + 1$
s.t. $(x - 2) (x - 4) \leq 0$

Attempt:
I can define the Lagrangian as:
$$L(x, \lambda) = (x^2 + 1) + \lambda (x^2 - 6x + 8)$$
where $\lambda \geq 0$ (this is where the question arises in a later part of the question)

Now we can define the primal problem as: $min_{x} \left( max_{\lambda} \left[ L(x, \lambda) \right] \right)$
and thus the dual problem is: $max_{\lambda} \left( min_{x} \left[ L(x, \lambda) \right] \right)$

if we follow the algebra through, we see that the minimum of $L(x, \lambda)$ occurs at $x_{min} = \frac{3 \lambda}{\lambda + 1}$ and therefore the dual function $g(\lambda)$ is defined as :
$$g(\lambda) = L(x_{min}, \lambda) = \frac{1 + 9\lambda - \lambda^2}{1 + \lambda}$$

The answer now specifies that the dual function as:
$$g(\lambda) = \begin{cases} \frac{1 + 9\lambda - \lambda^2}{1 + \lambda} & \text{if } \lambda > -1 \\ -\infty & \text{if } x \leq - \infty \end{cases}$$

Question: Why are we concerned with $\lambda \leq -1$ when we have restricted $\lambda \geq 0$?
- Is this because we are dealing with $g(\lambda)$, which is inside the maximum function and thus the restriction isn't applied yet?

Thanks in advance.

[EDIT]: Also, I don't fully understand where the $-\infty$ comes from. We can substitute values $\lambda < -1$ and get finite numbers, so am slightly confused...

 

[Mark44]

Homework Statement:: Given the following problem: find the dual and the dual solution.
Relevant Equations:: Lagrange dual

Hi,

I was working through the following problem and I am getting confused with the solution's definition of the dual.

Problem:
Given the optimization problem:
minimize $x^2 + 1$
s.t. $(x - 2) (x - 4) \leq 0$

Attempt:
I can define the Lagrangian as:
$$L(x, \lambda) = (x^2 + 1) + \lambda (x^2 - 6x + 8)$$
where $\lambda \geq 0$ (this is where the question arises in a later part of the question)

Now we can define the primal problem as: $min_{x} \left( max_{\lambda} \left[ L(x, \lambda) \right] \right)$
and thus the dual problem is: $max_{\lambda} \left( min_{x} \left[ L(x, \lambda) \right] \right)$

if we follow the algebra through, we see that the minimum of $L(x, \lambda)$ occurs at $x_{min} = \frac{3 \lambda}{\lambda + 1}$ and therefore the dual function $g(\lambda)$ is defined as :
$$g(\lambda) = L(x_{min}, \lambda) = \frac{1 + 9\lambda - \lambda^2}{1 + \lambda}$$

The answer now specifies that the dual function as:
$$g(\lambda) = \begin{cases} \frac{1 + 9\lambda - \lambda^2}{1 + \lambda} & \text{if } \lambda > -1 \\ -\infty & \text{if } x \leq - \infty \end{cases}$$

Question: Why are we concerned with $\lambda \leq -1$ when we have restricted $\lambda \geq 0$?
- Is this because we are dealing with $g(\lambda)$, which is inside the maximum function and thus the restriction isn't applied yet?

Thanks in advance.

[EDIT]: Also, I don't fully understand where the $-\infty$ comes from. We can substitute values $\lambda < -1$ and get finite numbers, so am slightly confused...

Quick sanity check. $(x - 2)(x - 4) \le 0 \Leftrightarrow 2 \le x \le 4$, so the minimal value of $x^2 + 1$ is attained when x = 2, thus $x^2 + 1 \ge 5$ is the minimum value on the interval I listed.

$$g(\lambda) = \begin{cases} \frac{1 + 9\lambda - \lambda^2}{1 + \lambda} & \text{if } \lambda > -1 \\ -\infty & \text{if } x \leq - \infty \end{cases}$$

Part of this makes no sense to me. How can $x \le -\infty$? Was this a typo, but should say $\lambda \le -1$?

 

[Master1022]

Part of this makes no sense to me. How can $x \le -\infty$? Was this a typo, but should say $\lambda \le -1$?

Yes, apologies. This was a typo. It should read:

$$g(\lambda) = \begin{cases} \frac{1 + 9\lambda - \lambda^2}{1 + \lambda} & \text{if } \lambda > -1 \\ -\infty & \text{if } \lambda \leq - 1 \end{cases}$$

 

[Mark44]

What about the other part of what I said, about the maximal value being 5? If my understanding is correct, any work you do should agree with that.

 

[Master1022]

Thanks for the response @Mark44 !

What about the other part of what I said, about the maximal value being 5? If my understanding is correct, any work you do should agree with that.

Yeh that makes sense - I understood that part of the problem. We can differentiate that expression for $g(\lambda)$ and then the optimal lambda (which is 2) leads us to dual problem optimal of 5. The strong duality makes sense because Slater's condition holds.

The parts that confused me were:
1. The definition of $g(\lambda)$ : I was unsure why we needed to define it over all $\lambda$ when we are optimizing over $\lambda \geq 0$. The only reason I have is that the maximization (and hence restriction on $\lambda$) is applied after defining $g (\lambda)$ and therefore we need to define it over the whole range
2. Where did the $- \infty$ come from in the case of $\lambda \leq -1$. I can understand for the case of -1, but not for numbers less than that.