MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Made a crucial mistake in the problem formulation; please delete.

share|cite|improve this question
${\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. – Robert Israel Apr 26 '12 at 20:52
Thanks for pointing out that mistake. Your other point led me to more correctly define the problem; I hope it makes more sense now. – xipsi Apr 26 '12 at 21:10
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$? – Brian Borchers Apr 27 '12 at 1:12

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.

share|cite|improve this answer
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. – xipsi Apr 27 '12 at 19:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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