0
$\begingroup$

How to solve the following optimzation by lagrange multiplier method?

$$\begin{array}{ll} \text{minimize(P)}& \| \mathbf{B} - \mathbf{P}\mathbf{A} \|_F^2\\ \text{subject to} & {\mathbf{P}}^T\mathbb{1} = \mathbb{1}\\ & \mathbf{P} \geq 0\end{array}$$

where $A$ and $B$ are given and $\mathbb{1}$ is a vector containing only $1$'s, can we solve ot by lagrange multiplier method ? Thanks so much.

Let says if $\mathbf{P} \geq 0$ are ignored now. Can we solve it by largrange multiple method?

design a largrange function: $L(P,\lambda) = \| \mathbf{B} - \mathbf{P}\mathbf{A} \|_F^2 + \lambda({\mathbf{P}}^T\mathbb{1} - \mathbb{1})$ And then use KKT complementary condition to solve it. Can we do that? I am total new about optimization. thanks.

$\endgroup$
  • $\begingroup$ I believe you cannot, at least not in a finite amount of years of computation. You need to check all possibilities of $P_{ij} = 0$ vs $P_{ij} > 0$, which might take forever. $\endgroup$ – Alex Shtof Oct 24 '17 at 8:44
  • $\begingroup$ This is expressible as a quadratic program, so there are a wide variety of solvers available for it. $\endgroup$ – Michael Grant Oct 24 '17 at 13:52
  • $\begingroup$ By $P \geq 0$, do you mean that $P$ has nonnegative elements, or that $P$ is positive semidefinite? $\endgroup$ – Brian Borchers Oct 25 '17 at 21:00
  • $\begingroup$ Yes P has not nonegative element. I hope P is a stochastic matrix $\endgroup$ – jason Oct 26 '17 at 15:49
  • $\begingroup$ @Alex what if we just remove the constraint P>=0. can we solve it by lagrange method? $\endgroup$ – jason Oct 26 '17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.