1
$\begingroup$

I have a optimization problem with the conventional form:

$\arg \min f(X)$

$s.t.:$

"some specific elements of X are zero" Ex: $X(1,2)=X(3,4)=...=0$

"some specific elements of X are one" Ex: $X(4,1)=X(5,6)=...=1$

Where $X$ is a $n \times m$ matrix and $f$ is differentiable. My problem is that i do not know how to put the constrains in the form of $g(X)=0$ or $h(X)=1$ where $h$ and $g$ are differentiable!

not to mention that $X$ dimensions are considerably large!

$\endgroup$
1
  • 1
    $\begingroup$ These are linear constraints, hence diferentiable. Alternatively, you can use a combination of lower and upper bounds to impose these constraints. Which way is best depends on the optimizer you are using. You need an optimizer which can accept linear constraints, or alternatively, at least bound constraints. $\endgroup$ Sep 22, 2015 at 11:06

1 Answer 1

0
$\begingroup$

I think best is to leave those elements out and don't define them as variables. Depending on your $f$ this may be eary or hard.

If you want the whole $X$ as variable, and add equality constraints, then you can define one $K$ (of same dimension as $X$) for each equality constraint, eg $K=0\cdot X$ everywhere except $K(1,2)=1$. Then $g(X) = trace(K^\top X)=0$

$\endgroup$
2
  • $\begingroup$ Can you please give a $2\times 2$ example? cause i think it doesn't work that way! Assuming $X$ is $2\times 2$ and $X(1,1)=X(1,2)=X(2,1)=0$ then using the above formula: $g(X) = trace(K^\top X)=0$ wouldn't give the desired constraints. $\endgroup$
    – Bob
    Sep 23, 2015 at 12:34
  • $\begingroup$ For $K$ s.t. $K=0$ everywhere except $K(i,j)=1$, $trace(K^\top X)=X(i,j)$. Maybe I should make it more clear that you have one $K$ for each constraint. So in your example, 3 $K$'s $\endgroup$
    – jf328
    Sep 23, 2015 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.