Minimize $\sum_i w_i^2 x_i^2$ subject to $Ax = b$

Question

I have the following problem in an example test for a course in optimization:

$$\begin{array}{ll} \text{minimize} & \sum_{i=1}^n w_i^2 x_i^2\\ \text{subject to} & Ax = b\end{array}$$

where $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$ and $w_i > 0$.

---

A) is the problem convex?

My attempted answer: I think so. The target function is convex as a positive sums of quadratics. The constraints define a convex set (either empty, in case of over-determined, a single point in case of a determined set, or some hyperplane in case of under-determined set of equations).

---

B) What is the condition that the problem has a single global solution?

It might be that $m \le n$ - so that the set is not over-determined? The Hessian is PD for all x, so if there's a stationary point, it will be a global minimum.

---

C) Are all KKT points of the problem are global minima?

Not sure how to even find KKT here.

---

D) Suppose A is of full column row rank - find the optimal solution.

Ditto.

Answer 1

Let's write out the Lagrangian, $$\ \mathcal L(x, \mu) = \sum_{i=1}^n w_i^2x_i^2 + \sum_{j=1}^m \mu_j \left(\sum_{i=1}^n A_{ji}x_i -b_j \right) $$ In matrix form this becomes $$\ \mathcal L(x, \mu) = x^TWx+\mu^T(Ax-b) $$ where $W$ is a diagonal matrix with $W_{ii}=w_i^2$. Taking gradient we get, $$\ \nabla_x \mathcal L(x, \mu) = 2Wx+A^T\mu=0\\ \implies x= -\frac{1}{2}W^{-1}A^T\mu $$ Substitute it back in the constraint to get, $$\ x^*=W^{-1}A^T\left(AW^{-1}A^T \right)^{-1}b $$ $AW^{-1}A^T$ is invertible if $A$ is full row rank. I think you should recheck the question as if $A$ is full column rank i.e. $rank(A) = n$. There may not exist any feasible point.

Answer 2

A) The answer is "yes", but note that the empty set is convex by convention.

Let $A_k'x=b_k$ be the $k$-th row of the equality system. Then you can rewrite it as $A_k'x \ge b_k$ and $A_k'x \le b_k$, giving you $2m$ inequalities. Each inequality corresponds to a closed half-space, which is a convex set. The feasible set is the intersection of all the inequalities, and an intersection of convex sets is convex. It might, however, be empty.

B) The objective function is a strictly convex set and the constraint set is convex, so any critical point of the Lagrangian is a global minimum (if there are no feasible points, there is no critical point). The constraint set here is not guaranteed to be compact, so Weierstrass' Extreme Value Theorem does not apply, but there are existence theorems for finding the weighted distance between a point (zero) and a convex set in Hilbert spaces that do apply; or you could show that the objective function is convex and coercive, so it has a global minimum ($e^{x}$ is not coercive on $\mathbb{R}$ because there exist sequence $x_n$ for which $e^{x_n} \rightarrow 0$ and not $\infty$ as $|x_n| \rightarrow \infty$, but it is strictly convex, so strict convexity is not enough to guarantee existence on non-compact sets; $w x^2$ is strictly convex and coercive).

C) See Shiv Tavker's answer.

D) If $A$ has full rank, it is invertible, and $Ax = b$ has a unique solution, $x^* = A^{-1}b$. There is a unique feasible point, so it is the global minimum. If $\text{rank }(A)>n$, there are no solutions, and if $\text{rank }(A)<n$, there are an infinite number, and that's the set from which you are picking your solutions.