Solving optimization problem by penalty method

Question

Given this minimization problem:

$$ \text{minimize }\, \, x_1^2 + 2x_2^2 \\ \text{subject to } \, \, x_1 + x_2 = 3 $$

I wish to solve this using the penalty method, what I've done so far:

$$ \text{minimize} \, \, f(x) \\ \text{where} \, \, f(x) = x_1^2 + 2x_2^2 + \gamma(x_1 +x_2 -3)^2 $$

I try to find $x_1, x_2$ using First Order Necessary Condition:

$$ 2(1 + \gamma)x_1 + 2\gamma x_2 - 6\gamma = 0 \\ 2\gamma x_1 + 2(2+ \gamma)x_2 - 6\gamma = 0 \\ $$

What I do next is to use row reduction to solve this problem:

$$ \begin{bmatrix} 2(1+\gamma) & 2\gamma & | \, \, 6 \gamma \\ 2\gamma & 2(2+\gamma)& | \, \, 6 \gamma \end{bmatrix} \\ \downarrow \\ \begin{bmatrix} 1+\gamma & \gamma & | \, \, 3 \gamma \\ \gamma & 2+\gamma& | \, \, 3 \gamma \end{bmatrix} \\ $$

Dividing by $\gamma$ and letting $\gamma \rightarrow \infty$:

$$ \begin{bmatrix} 1 & 1 & | \, \, 3 \\ 1 & 1 & | \, \, 3 \end{bmatrix} \\ $$

Which does not give me an unique solution, according to the textbook the unique solution is to be

$$ x^* = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $$

What am I doing wrong?

Thank you very much

The textbook tells us to use that penalty function, probably because of Courant Beltrami penalty function. I let $\gamma \to \infty$ because that is when the penalty method converges. — Bob Pen, May 01 '21 at 11:53
The mistake is letting $\gamma \to \infty$ before completing the Gaussian elimination. — user1337, May 01 '21 at 11:55
But why don't you use completing square method for this particular problem? — Martund, May 01 '21 at 12:23

score 0 · Accepted Answer · answered May 01 '21 at 12:15

Mistake was to let $\gamma \to \infty$ before completing the elimination, thanks for pointing this out @user1337.

Correction:

$$ \begin{bmatrix} 1+\gamma & \gamma & | \, \, 3 \gamma \\ \gamma & 2+\gamma& | \, \, 3 \gamma \end{bmatrix} \\ \downarrow\\ \begin{bmatrix} 1 & 0 & | \, \, \frac{6 \gamma}{2+3\gamma} \\ 0 & 1 & | \, \, \frac{3 \gamma} {2+3\gamma} \end{bmatrix} \\ $$

Now letting $\gamma \to \infty$ and using L'Hopital:

$$ x^* = \begin{bmatrix} 2 \\ 1 \end{bmatrix} $$

score 0 · Answer 2 · answered May 01 '21 at 13:10

Here is an alternative solution using completing squares method (since OP asked in comments):

We wish to minimize \begin{align} (3-x_2)^2+2x_2^2&=3x_2^2-6x_2+9\\ &=3((x_2-1)^2+2) \end{align} which is clearly minimum when $x_2=1$ and therefore $x_1=2$.

Solving optimization problem by penalty method

2 Answers2