4
votes
0answers
135 views

Are there some numerical test to check if a map is a contraction?

Let's say I have a multivariate function $$ f:D \to D, D \subset \mathbb R ^n, D \text{ compact}, $$ for which there is no closed form. That is the only way to evaluate the function is to do it ...
2
votes
0answers
122 views

minimize a cost function with matrix traces

Hi, I have a cost function of the form $$F(X) = \operatorname{tr}(X'AX)+\operatorname{tr}(X'B),\quad\textrm{ s.t. }X'X=I.$$ $X$ is a $m\times n$ matrix, ($m>n$), with orthonormal columns. $A$ is ...
2
votes
0answers
60 views

Approximating solutions to minima of the discrete Lagrangian

I have been stuck on this problem for a week and I'm not sure whether or not it is hard or I'm just missing something obvious. General gist of the problem I have a variational problem on a ...
0
votes
1answer
76 views

Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$. $(x = 0 \wedge y = 1) \vee (x \neq 0 ...
5
votes
0answers
131 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
2
votes
1answer
197 views

Best constant in a convex polynomial inequality.

Let $\phi(x)$ be a convex polynomial of degree $m$ at least two. Note that for $x,q \in \mathbb{R}$ $$\phi(x) + \phi(q) - 2\phi(\frac{x+q}{2}) = ...
5
votes
3answers
445 views

solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
2
votes
2answers
305 views

My overdetermined linear system gives both bad and good estimates. Why ?

Hello to everyone. What the question means is that different ways of expressing the same relation between the data and unknown variables produce really weird fit results: The problem: I have the ...
1
vote
1answer
128 views

Nonlinearly constrained optimization (quadratic)

Hi all -- what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, where some constraints are non-linear ...
0
votes
3answers
756 views

Solving a non-convex quadratically constrained quadratic program

I have the following quadratic optimization problem: $\min_{\vec{x}} |\vec{x}|^2$ subject to $\vec{x}^T G_j \vec{x} \geq 1$, $j = 1 \ldots m$, where the $G_j$ are positive semidefinite. $|\vec{x}|$ is ...
1
vote
1answer
248 views

Projection onto a quadratic cone?

Consider a constraint of the form $$ f(x) := x^T A x = 0 $$ where $A \in \mathbb{R}^n$ is symmetric but may be singular and indefinite. The constraint set $C$ is a (nonconvex) cone, since for any ...
2
votes
1answer
122 views

Relations between a set of inner products of vectors

Suppose we have n normalized vectors on an arbitrarily large Hilbert space $|A_1\rangle,\dots,|A_n\rangle$, $\langle A_i|A_i\rangle=1$ for every i. And there're $\frac{n(n-1)}{2}$ inner products ...
2
votes
1answer
241 views

Optimization of a Specific Polynomial

I have a polynomial: $$f(x_1 \dots x_n) = \prod_{i=1}^n (c_ix_i + 1) - \frac{1}{2}c_0\sum_{i=1}^nx_i^2$$ Given some values for $c_0 \dots c_n$, I'd like to choose the maximizing values for $x_1 ...
2
votes
0answers
79 views

Minimum time planar paths under a bound on magnitude of acceleration

On a plane, given initial position (x1,y1), initial velocity (u1,v1), final position (x2,y2), and final velocity (u2,v2), compute the solution to x''= cos(z), y''=sin(z) that has these endpoint ...
2
votes
1answer
371 views

minimizing functions over simple matrix inequalities

I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example: $min \Sigma x_i ln ...
0
votes
0answers
385 views

Decomposing max-convolution of sum of functions ?

Hello. $R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. $R$ is a linear combination of $F_1, F_2, F_3$. Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where ...
2
votes
1answer
609 views

How do I optimize over (or take derivative wrt) a square diagonal matrix?

Hello. I'd like to solve the following optimization problem. $P_i$ is a 6x6 matrix $X$, $Y$ is a 6xk matrix $w_i$ is a kx1 vector $diag(w_i)$ is a square diagonal matrix with diagonal entries equal ...
13
votes
2answers
907 views

Seeking proof for linear algebra constraint problem.

Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...
5
votes
1answer
318 views

Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently

What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$? Do we have to calculate $A^{-1}b$, or is this not necessary? edit: I forgot to mention that A is symmetric and ...
1
vote
2answers
460 views

Problems finding feasible points with respect to linear matrix inequalty constraints

Hi! I'm a trying to learn the basics of semidefinite programming and how to solve problems with linear matrix inequalities. Inspired by the book "Convex Optimization" by Boyd and Vandenberghe (can be ...
3
votes
1answer
621 views

An optimization problem in numerical linear algebra

Provided two diagonal real matrix which has positive entries, $V$ and $U$. Find a real matrix $A$, satisfying $A^TA=a^2I$ for some scalar $a$, to minimise $\left|A^TVA-U\right|\quad\quad(*)$ ...
2
votes
2answers
1k views

Second order Taylor expansion to solve system of equations

Suppose you need to solve $f(\mathbf{x})=\mathbf{0}$ where $f:\mathbb{R}^n \to \mathbb{R}^m$, $m,n>1$. Newton's method relies on first order Taylor expansion of f. Where can I find details of ...
3
votes
2answers
645 views

Optimizing over matrices with spectral radius <1?

Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so ...
6
votes
1answer
683 views

Random, Linear, Homogeneous Difference Equations and Time Integration Methods for ODEs

Most methods (that I know of) of numerically approximating the solution of ODEs are "general linear methods". For this type of method, the so-called 'linear stability' is examined by applying the ...
-1
votes
1answer
687 views

Determine noise distribution [closed]

I'm trying to solve the following least squares problem: $\underset{x}{\text{min}} ||Ax - \tilde{b}||_2$ where $Ax = b$ and $\tilde{b} = b + w$ Question: How do I determine which probability ...
2
votes
1answer
614 views

Condition number for Ellipsoid method matrix

Hello, When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$. ...
9
votes
2answers
2k views

An optimization problem for points on the sphere (master's dissertation)

First, by means of a disclaimer, some background. I am entering the fourth and final year of an undergraduate master's degree in maths, and a quarter of the maximum credit for this year will be for a ...
3
votes
1answer
701 views

Maximize the multiplicity of an eigenvalue

Hi, We have a real, non-singular and symmetric matrix M of size n by n, with diagonal elements 0's. Its eigenvalues and eigenvectors are computed. Now we wish to change its diagonal elements ...
1
vote
1answer
531 views

Recommendations for a large scale bounded variable least squares (BVLS) solver for sparse matrices

I'm trying to solve the BVLS problem for huge (2e6x2e6) matrices which are very sparse (4 elements per row). Does anybody have a recommendation for a free solver (preferably a library of routines)? ...
6
votes
3answers
1k views

minimize the sum of absolute eigenvalues

Hi, We have a real symmetric matrix M with diagonal elements 0's, the eigenvalues and eigenvectors of M are computed. Now we wish to change its diagonal elements arbitrarily to minimize the sum of ...
3
votes
0answers
309 views

Convergence to a (unique?) fixed point?

Consider a given $N\times P$ matrix $X$ (full rank with columns ${\bf x}_p$, $p=1,\ldots,P$), a given vector ${\bf y}\in R^N$ and a thresholding function $\eta_\lambda(|x|)=(|x|-\lambda)_+$ with ...
3
votes
0answers
230 views

Nonlinear conjugate gradient update strategy by Dai and Yuan

In Nocedal and Wright book "Numerical Optimization", they describe on page 123 (formula 5.49) an update strategy for the beta parameter in the nonlinear conjugate gradient optimization, which was ...
0
votes
2answers
1k views

Finding the local/global minima of Shubert function

Consider the 2D Shubert function. As given in that page, the function has 18 global minima and several local minima. How can I find the (x,y) of all these minima? Any help appreciated. If it was a ...
2
votes
3answers
348 views

Which method to apply to this problem?

I'm a programmer and I came a across an interesting problem. I'm sure there is a mathematical method or an algorithm to solve it, but I don't know where to start with the search nor which literature ...
4
votes
2answers
948 views

Minimizing a function containing an integral

I am trying to optimize a function of the following form: $L = \int_{t=0}^{T}(AR-x)dt$, where A is a system parameter i.e. I am trying to find the optimum x(t) that minimizes L over all admissible ...
3
votes
1answer
1k views

Maximizing Sparsity in l1 Minimization?

Consider the optimization problem $$\min_x ||Ax||_1 + \lambda||x-b||^2,$$ where $A \in \mathbb{R}^{n \times n}$, $x,b \in \mathbb{R}^n$ and $\lambda$ is strictly greater than 0. (This problem is ...
7
votes
4answers
1k views

Is there a name for the matrix equation A X B + B X A + C X C = D?

I happen to be working on a problem that reduces to solving the following equation: $$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$ where A through D are known matrices ( A, B, D ...