0
votes
1answer
17 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$ \min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge 0$$ Where Q is square ($n$x$n$), positive semi ...
0
votes
0answers
27 views

resources about sparse global constrainted optimization

Please recommend a good resources (books/articles/software) about sparse global constrained optimization?
0
votes
1answer
49 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
2answers
128 views

Trace minimization of a matrix

Suppose $S = \pmatrix{1&1\\ 1&0\\ 0&1}$, $W$ is a $3\times3$ covariance matrix, which could be regarded as fixed. I need to find a $2\times 3$ matrix $Q$ that minimizes $$ ...
5
votes
1answer
28 views

proving a theorem of alternative

I've read the following exercise in my book: Let $A\in\mathbb R^{m\times n},b\in\mathbb R^m,c\in\mathbb R^n$. Then exactly one holds: $Ax=0,c^t\cdot x=1$ with $x\geq0$ has a solution $A^ty\geq c$ ...
1
vote
0answers
23 views

Vector optimization with set constraint

This is a more generalized form of a previous unanswered question, from which I've removed all the content that wasn't relevant to the actual problem. I have a minimization problem of the form $$ ...
0
votes
0answers
38 views

Minimizing a vector constrained to a set

Sorry if this is wordy or over-complicated, I'm not sure how to isolate the problem any more than I have below without losing important context: I'm trying to implement a coordinate block descent ...
2
votes
0answers
47 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
0
votes
1answer
62 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
1
vote
1answer
40 views

How to solve an Optimization problem with linear as well as Quadratic constraints.

I want to solve the following problem, \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x^T}\mathbf{Px} \\ & \text{subject to} & & ...
0
votes
0answers
55 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
2
votes
1answer
62 views

Absolute values in linear programming

Suppose I have an objective function in my LP as follows $max$ $|x|$ Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. $|x|$ = $ x^+ + x^-$ $x ...
0
votes
2answers
149 views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in ...
3
votes
1answer
57 views

Solve Ax = b, but I have a function that implements A

I have an overdetermined linear system $Ax = b$. I need to choose an $x$. $x$ has about 100 elements in it. If I had the matrix $A$, I would set x equal $A^\dagger b$, the pseudoinverse of $A$ ...
1
vote
0answers
84 views

Orthogonal Procrustes Problem

The classical orthogonal Procrustes problem concerns finding the matrix $\Omega$ which minimizes $||A\Omega-B||_{F}$ subject to $\Omega'\Omega=I$, with A and B known matrices. Let A be the identity. I ...
0
votes
1answer
30 views

Expressing a vector as the best linear combination of “random” vectors

Suppose I have something like: $\vec{v} = \langle 1, 2, 3, 4, 5 \rangle$ and I have a set of vectors (these are all just made up numbers): $\vec{w_1} = \langle 3, 7, -2, -4, 8 \rangle$ $\vec{w_2} ...
0
votes
1answer
31 views

Avoid evaluation of a very large matrix in non-negative matrix factorization

This is somewhere in between a math and a programming question, so please send me back to SO if you think it's off-topic. I'm implementing non-negative sparse coding, a regularized variant of ...
3
votes
1answer
271 views

What are non-orthogonal eigenvectors?

Given a symmetric matrix $A$, the maximum of the trace, $Tr(Z^TAZ)$ under the assumption that $Z^TZ=I$ occurs when $Z$ has the eigenvectors of $A$, as $Tr(U^TAU)= \lambda_1 +\lambda_2+...\lambda_ d$ ...
1
vote
0answers
57 views

Reformulating objective function of canonical correlation analysis

Given two column vectors $X = (x_1, \dots, x_n)'$ and $Y = (y_1, \dots, y_m)'$ of random variables with finite second moments, canonical-correlation analysis seeks vectors $a$ and $b$ such that the ...
1
vote
1answer
149 views

Ideas on matrix factorizations and/or transformations for $\ell_1$ minimization

I am starting with a typical $\ell_1$ basis pursuit problem: $$ \min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{ERx} - \mathbf{y} \Vert_2 \leq \epsilon, $$ where ...
1
vote
1answer
64 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
3
votes
1answer
326 views

How to show that the Hessian matrix of $G$ is positive definite?

Let $\{g_i:X\subset\mathbb{R}\rightarrow\mathbb{R};\;i=1,...,m\}$ be a linerly independet set of real functions. Given $n$ points $(x_1,y_1),...,(x_n,y_n)\in X$, consider the following function ...
3
votes
1answer
230 views

Finding the smallest subset of a set of vectors which contains another vector in the span

Consider a set $S=\{ \underline{v_1},\dots , \underline{v_n} \} $ of vectors of dimension $d<n$. Suppose for some vector $\underline{b}$ that the solution space for the matrix equation $\left[ ...
0
votes
1answer
103 views

Solve: This System of equations for $X$ (does a real solution, exist?)

How can I solve $AX + diag(X)[I-c]=0$ for $X$? All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...
2
votes
0answers
40 views

maximal m-elements of the matrix inversion

Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
3
votes
0answers
370 views

Trace Minimization of Covariance Matrix

Given a matrix X whose rows contain observations collected at some locations. Can someone explain how trace minimization of covariance matrix $XX^T$ can lead to orthogonal / mutually independent ...
6
votes
1answer
1k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
2
votes
0answers
76 views

Spectral/ Eigen-Value solution with a linear constraint?

Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...
1
vote
1answer
104 views

trace function, eigen decomposition and optimization!

The equation \begin{align} \min_{X}~trace(CX^{T}MX) \end{align} where $C$ is symmetric and M is symmetric , p.s.d can be minimized by defining $M=F^{T}F$ ($M$ being a psd matrix, you will be able to ...
1
vote
2answers
86 views

Spectral/Eigen-value solution?

Is there a spectral or eigen-value solution to finding $d$ vectors $x_1...x_n$ such that $ \sum_{i,j=1}^{d} C_{i,j} \cdot x_i^\top M x_j $ is minimized, with $C_{i,j}$ being a constant real-scalar ...
4
votes
1answer
262 views

principal “pseudo eigenvector” of a real symmetric positive-semidefinite matrix

Let $A$ be a real symmetric positive-semidefinite matrix and suppose that $c>0$ is a sufficiently small number. I wonder if it is possible to solve the non-convex optimization $$\arg\max_u\ ...
0
votes
0answers
121 views

Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid $$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$ where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively. Given this ...
3
votes
1answer
117 views

Orthogonality, Maximization and Eigen-Solution

I Have read that for a matrix of reals $Y$ and a p.s.d matrix $B$ that the Maximum of $ f(Y)=Tr(Y^TBY)$ subject to $Y^TY = I$ is achieved when $span(Y)$ equals the span of the first $d$ ...
0
votes
0answers
107 views

Efficient principal pivots

Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal pivoting" methods to solve optimization problems (specifically linear ...
1
vote
1answer
23 views

Optimization of closed (ring) transforms

I have a closed set of 4 linear matrix (3x3) transforms. Let's name them (A,B,C,D). Closed set means that $D*C*B*A=E$, where $E=eye(3)$. Their numeric representation is known from experiment and, ...
0
votes
0answers
93 views

Does a single Gauss-Seidel iteration lead to unique coordinates?

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$, and $x,y\in\mathbb{R}^{n\times 2}$ are ...
0
votes
1answer
115 views

Suitable Loss function for Order preserving Factoring of a matrix?

(Old-Question) Given a $n\times n$ symmetric matrix $X$, I would like to factor it using a vector $c$ of size $n \times 1$ such that: $\sum_{i,j} [X_{ij} \cdot c_i\cdot c_j]$ is minimum. How can I ...
10
votes
2answers
924 views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
3
votes
1answer
178 views

Testing constrained linear least squares for optimality

I've written a C# solver for linear least squares problems with inequality constraints. That is, given $A$, $b$, $G$, $h$ $$\min\|Ax-b\|^2\text{ s.t. }Gx\ge h$$ I have a few hand crafted test ...
4
votes
1answer
453 views

Algorithm for solving sparse equality-constrained least squares

I have a diagonal, positive-definite inner product matrix $M$ and want to find a minimizer of $$\min_q \frac{1}{2} \|q-q_0\|_M^2\qquad \text{s.t.}\qquad C^Tq+c_0 = 0,$$ where $q_0, c_0$, and $C$ are ...
5
votes
2answers
800 views

Least square principles with Lagrange multiplier

I have a function to minimize: $$f(a_1,a_2,a_3,a_4)=\sum_{i=1}^n\left(\sum_{k=1}^3 a_k\ p_i^k -a_4\right)^2$$ subjected to this constraint: $$a_1^2+a_2^2+a_3^2=1$$ and $$a_4\geq0$$ I am trying ...