0
$\begingroup$

I would like to find a numerical solution to the following quadratic matrix programming problem. Square matrix A has thousands of rows, so I need a algorithm which works fast. I looked into Python but couldnt find much there. Is there something in Matlab, Mathematica, or elsewhere.

$A$ is an $n\times n$ matrix of coefficients represented by $a_{ij}$. I know the zero entries (see constraint 4). The optimization problem is to compute the coefficients of matrix A.

\begin{aligned} \underset{\{a_{ij}\}}{\text{minimize}} & & \sum_{i=1}^n \sum_{j=1}^n (a_{ij})^2 \\\\ & \text{constraint 1} & & Ax = x \\\\ & \text{constraint 2} & & a_{ij} \geq 0 \text{ } \forall i,j \\\\ & \text{constraint 3} & & \sum_{j=1}^n a_{ij} = 1 \text{ } \forall i \\\\ & \text{constraint 4} & & a_{ij} = 0 \text{ } \forall a_{ij} \in B \end{aligned}

Where B is a collection of tuples indicating which elements of A is zero. For example, $B=[a_{01}, a_{02}, a_{31} ]$, means $a_{01}, a_{02}, a_{31}$ are zeros in $A$.

And x is fixed vector.

the problem in latex

$\endgroup$
  • $\begingroup$ Is $x$ some fixed vector? Then you can look at quadratic programming (QP) or second-order cone programming (SOCP). Both Matlab and Pyton/Scipy have solvers for QPs but there is also tons of other software for those problems. $\endgroup$ – Michal Adamaszek Aug 30 '18 at 12:13
  • $\begingroup$ yes x is a fixed vector $\endgroup$ – user58925 Aug 30 '18 at 12:22
  • $\begingroup$ Then your formulation is a straightforward QP or SOCP with the $a_{ij}$ as variables. $\endgroup$ – Michal Adamaszek Aug 30 '18 at 12:37
  • $\begingroup$ In the case SOCP is expensive for you ($A$ seems to be big), you can formulate your problem as a convex-concave saddle point and apply simpler and cheaper first-order methods. $\endgroup$ – cheyp Sep 3 '18 at 15:53

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.