How to solve this quadratic program using the penalty method?

Question

example: $$\min\frac{1}{2}((x_1-3)^2+(x_2-2)^2)$$ s.t.$$-x_1+x_2{\le}0$$ $$x_1+x_2{\le}1$$ $$-x_2{\le}0$$ and we start with $~x^0=[3,2]^T~$ its violate the condition : $$q(x,c)=\frac{1}{2}((x_1-3)^2+(x_2-2)^2)+\frac{c}{2}((x_1+x_2-1)^2)$$ and what is next?

calculate $~x_1~$and$~x_2~$ with BFGS, newtons method,....

$\nabla_x q(x,c)=0~$,$~c=~$ a very large number starting with $~10,100,1000,\cdots~$ until the solution has very small difference?

Answer 1

Here are my comments on the method.

1. The youtube video you mentioned does not describe the example completely. Formally, the $q$-function there is incorrect in the sense that $\nabla_x q(x,c)=0$ does not solve the problem in general. What it does solve is the first iteration minimization only starting from the given initial point. The complete auxiliary function should look as e.g. \begin{align} q(x,c)=&\frac{1}{2}((x_1-3)^2+(x_2-2)^2)+\\ &+\frac{c}{2}(\max\{0,-x_1+x_2\}^2+\max\{0,x_1+x_2-1\}^2+\max\{0,-x_2\}^2). \end{align} For the given initial point $x^0$ it takes the form as you stated, but at other points of the plane it is (or may be) different.
2. A solution to $\nabla_x q(x,c)=0$ is the global minimizer in the problem $$ \min_x q(x,c) $$ because the function $q(x,c)$ is convex in $x$. It is the known theoretical fact for convex functions. It gives an analytical solution (for lecture's sake). In practice, this step is replaced by Newton/quasi-Newton methods. Moreover, it is often enough to take one iteration of the chosen numerical method to get the next iteration, since it is only one step of the penalty method and to make the exact minimization is too expensive and unnecessary.

Normally the method works like this: for an iteration point $x^k$ do the following

1. Take $x^k$ and the penalty level $c_k$ and calculate $q_k(x,c_k)$ above for $x$ nearby $x^k$. Depending on where $x^k$ is (what constraints are violated) $\max$-penalties become different, some will disappear if $\max=0$ (i.e. the corresponding constraint is satisfied at $x^k$).
2. Calculate the next iteration $x^{k+1}$ by taking one step of a Newton-related method for $q_k(x,c^k)$, starting from $x^k$.
3. If $|x^{k+1}-x^k|$ is small enough then STOP, otherwise update $x^k=x^{k+1}$, $c^k=10*c^k$ and continue with the Step 1.

Answer 2

Show that $$\frac{1}{2}((x_1-3)^2+(x_2-2)^2)\geq 4$$ the equal sign holds if $x_1=1,x_2=0$