Solution to an optimization problem

199 Views Asked by At

I see optimization problems of the following form a lot in the field I am researching. I want to know more about it and its solution. Would be great if someone could provide a not-too-long explanation.

$$\arg\min_x\quad\mathbf{x}^TW_k\mathbf{x} \quad \text{subject to} \quad y=D\mathbf{x}$$

1

There are 1 best solutions below

4
On

I'm going to assume you want to minimize. This supports a simple Lagrangian approach to solution. The Lagrangian is $$L(x,\lambda) = x^TW_kx - \lambda^T ( y - D x ) = 0$$ where $\lambda$ is the Lagrange multiplier. The optimality conditions are $$W_k x + D^T \lambda = 0, \quad D x = y$$ which can be expressed in block form: $$\begin{bmatrix} W_k & D^T \\ D & 0 \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} 0 \\ y \end{bmatrix}$$ Any optimal point must satisfy these conditions, but this is not a guarantee that such a point exists; additional conditions must be satisfied. The most common requirement is that $W_k$ is positive semidefinite, which guarantees that the objective is nonnegative.