2
votes
1answer
43 views

QR transformation with Householder transformation

It's a task i do to understand minimizing the error including the QR transformation with the help of Householder transformation. I think i really do something wrong but i dont get it running i hope ...
1
vote
2answers
131 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 $$ ...
3
votes
1answer
51 views

Linear Algebra quesion

$A^{-1} - \lambda A = B^{-1} - \lambda B - \alpha v v^T$ $A, B \in S^n_+$; $v \in R^n$; $\lambda, \alpha \in R_+$. Can we solve A in term of other variables?
0
votes
1answer
32 views

Estimating rates of convergence

If I have a set of data points obtained from a numerical approximation say 15.3828 15.2458 15.2095 15.2003 how can I estimate the rate of convergence?
1
vote
0answers
25 views

Simultaneous iteration of Symmetric Matrices

Given a Matrix $A$ we can use Simultaneous iteration(Using power iteration on all columns simultaneously) to compute the d biggest eigenvalues. Now this method will give you the biggest eigenvalues, ...
0
votes
1answer
37 views

Reference request: nonlinear systems, optimization, ode/pde

Could someone suggest me one or more good books on the following topics: Nonlinear systems: fixed point and Newton's method Optimization: steepest descent and Newton's-quasi newton methods ODE ...
0
votes
1answer
60 views

Can a 6-arm star be convex

Please help me with the following question. Suppose that the constant level contours of some function $V:\mathbb{R}^{2} \rightarrow \mathbb{R}$ have the shape of a symmetric 6-arm star. Can such a ...
1
vote
1answer
92 views

Does a Convex Function need to be Continuous

I have been trying the following problem and I am very confused. If possible the problem should be solved with derivatives. If the derivative exists for all the points on the graph then it is ...
0
votes
2answers
171 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 ...
1
vote
1answer
71 views

a conjugate gradients result for eigenvalue estimates

Consider the not preconditioned CG-method for a linear system $Ax=b$. Define $\beta_j = \frac{(r_{j+1},r_{j+1})}{(r_j,r_j)}$ and $\alpha_j=\frac{(r_j,r_j)}{(Ap_j,p_j)}$, where $(x,y) = y^Tx$ denotes ...
1
vote
0answers
91 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
39 views

Constrained non-linear optimisation algorithm making use of problem structure

I have a problem that in some ways is quite simple and in other ways is quite hard. I feel that there is probably an algorithm out there that is better suited to solving my problem than the one I am ...
2
votes
1answer
155 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 ...
2
votes
0answers
50 views

Customising force-directed graph layout

I would like to implement a variant of the force-directed graph layout where some nodes are constrained to moving only along a predefined curve (e. g. circle). I looked at some implementations using ...
3
votes
1answer
93 views

least square problem

Let $1<p<\infty $.We define the space: $L_{V}^{p}(-1,1)=\left \{ f:(-1,1)\rightarrow \mathbb{R}:\int_{-1}^{1}\left | f(x) \right |^{p}V(x)dx<\infty \right \}$ We define the norm: $\left \| ...
3
votes
1answer
111 views

What does “overdetermined” mean

When we say a problem is an overdetermined system, what do we mean by that in a rigorous fashion? Thanks.
2
votes
2answers
494 views

Why does the standard BFGS update rule preserve positive definiteness?

My class has recently learnt the BFGS method for unconstrained optimisation. In this procedure, we have a rank-1 update to a positive definite matrix at each step. This is specified as: $H_{k+1} = ...
0
votes
0answers
73 views

relative error relation

Let $x$ be a non-null quantity. Let $\hat{x}$ be its approximation. I am trying to find the relation between: $\frac{\left | x-\hat{x} \right |}{\left | x \right |}$ and $ \frac{\left | x-\hat{x} ...
0
votes
0answers
279 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...
1
vote
1answer
320 views

Minimization of function expressed with vectors and matrices

I need to find vector $\bf{p}$ in the following system: $$\bf{0} \approx \bf{W} \left[ \bf{C}^2 \bf{p} - \bf{d} \right]$$ $$\bf{0} \approx \varepsilon \bf{p}$$ In the above, $\bf{0}$ is a vector, ...
0
votes
2answers
129 views

Superlinear convergence of conjugate gradients

The global convergence bounds of conjugate gradients are too pessimistic, how can the super-linear convergence, experienced in practice, be explained?
4
votes
1answer
457 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 ...
4
votes
1answer
2k views

Linear least squares with inequality constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. ...