Made a crucial mistake in the problem formulation; please delete.
3
-
$\begingroup$ ${\mathbb R}^n \times {\mathbb R}^n = {\mathbb R}^{2n}$, not ${\mathbb R}^{n \times n}$. And there is no reason for $A$ to be full rank. For example, $A = c (1 \ldots 1)^T$ would satisfy the constraint. $\endgroup$– Robert IsraelCommented Apr 26, 2012 at 20:52
-
$\begingroup$ Thanks for pointing out that mistake. Your other point led me to more correctly define the problem; I hope it makes more sense now. $\endgroup$– xipsiCommented Apr 26, 2012 at 21:10
-
$\begingroup$ The set of full rank matrices is not convex, and I'm not aware of any work on optimizing over the set of full rank matrices. I think you're better off staying with the original formulation. For reasonably small values of $n$, the original formulation can readily be attacked by branch and bound methods. How big is your $n$? $\endgroup$– Brian BorchersCommented Apr 27, 2012 at 1:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Are these really all the constraints? Let $u$ be the vector of all $1$'s. Consider solutions of the following form: $p$ is an arbitrary vector with $u^T p = 1$,
$A = B + c u^T$ where $B p = 0$. If your problem has an optimal solution, $f(B)^T p$ must be $0$ for all $B$ such that $B p = 0$.
By scaling and continuity, $f(B)^T x = 0$ for all matrices $B$ and vectors $x$ such that $B x = 0$. This can only happen if $f(B)^T$ is in the span of the rows of $B$, i.e. $f(B) = B^T q$
for some vector $q$. At first sight it appears that $q$ could depend on $B$, but in fact it's not hard to see that if $f$ is linear $q$ must be constant. But then for any $A$ and $p$ with $A p = c$, $f(A)^T p = q^T A p = q^T c$. So the objective is constant on the set of feasible solutions.
answered Apr 27, 2012 at 8:19
-
$\begingroup$ Good catch. At the risk of something like this happening, I did leave off some details of the problem in order to provide minimum details in conveying my question. I've updated the original post. $\endgroup$– xipsiCommented Apr 27, 2012 at 19:40