0
$\begingroup$

Tell me if I have found the right approach to the following optimization problem:

$$ min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2 \\ s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0 $$

$A$ and $\Phi$ represent matrices, $x$, $b$ and $v$ vectors. The final answer for $x$ should have binary {0,1} values only, since the operator $A$ only accepts binary inputs.

Will ADMM and variable splitting solve this?

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you sure about the first constraint? It just gives you the solution for x as $x=\Phi v$. Also, can you specify the dimensions of $A$ and $\Phi$? $\endgroup$
    – Taha
    Commented Jan 14, 2016 at 23:57
  • $\begingroup$ The first constrain can be relaxed by $|\Phi v-x|<\epsilon$, A is has more columns than rows and $\Phi$ is fat (over determined system) $\endgroup$
    – c.Parsi
    Commented Jan 15, 2016 at 0:13
  • $\begingroup$ ADMM would builde the augmented Lagrangian for the problem and then alternatingly minimize between $v$ and $x$ with suitable update for the Lagrange multiplier. You may get intro trouble due to the nonlinear (in fact bilinear) constraint for $x$ (which I interpret componentwise, right?) resulting in a non-convex subproblem for the $x$ minimization (and also no convergence result I knows will be applicable). $\endgroup$
    – Dirk
    Commented Jan 15, 2016 at 10:46
  • $\begingroup$ Will ADMM and variable splitting solve this? I think you have to try this to get an answer. (Implementation seems straightforward and monitoring descent of the objective also. Checking second order sufficient conditions seems also possible…) $\endgroup$
    – Dirk
    Commented Jan 18, 2016 at 7:41

0

Reset to default

You must log in to answer this question.