0
votes
0answers
14 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
3
votes
2answers
46 views

finding the closest matrix of a given form

let's say I have a vector $(a_1\dots a_n)$, where each component is between $-1$ and $1$. Now from this vector I define a $n\times n$ matrix $M$ such that $$M_{ij} = \begin{cases} 1&\,& i = ...
0
votes
0answers
12 views

“Rank-K Correction” of a matrix and significance?

Today my studies led me to read about the matrix inversion lemma, which Wikipedia introduces as follows: In mathematics (specifically linear algebra), the Woodbury matrix identity, named after Max ...
3
votes
2answers
19 views

Smallest linear combination of a set of vectors

I'm searching for an algorithm to accomplish a (hopefully) simple task. If I have a set of vetors, (e.g. $\left( ...
0
votes
0answers
10 views

Dual discordance [closed]

Problem: minimize h(z,x,y) with h>=0 with a constraint being t=0 , where t decision variable not appearing in the objective . The 't' affects the objective however through some constraints. The ...
0
votes
0answers
15 views

Dual problem of SDP

Suppose we have the following optimization problem: \begin{array}{l} \mathop {\min }\limits_{{\bf{X}},{\bf{x}}} \,\mathrm{Tr}\left( {{\bf{XA}}} \right) + 2{{\bf{a}}^H}{\bf{x}} + b\\ ...
0
votes
1answer
47 views

minimizing sum of different least squares?

Can we write the minimization problem: $$\operatorname{min}\limits_{x\in\mathbb{R}^n}\sum_{i=1}^{n}\|C_i x-b_i\|_2^2$$ as a least square problem?
2
votes
2answers
64 views

Why does this vector derivation hold?

I have the following variables/matrices: $$A \in \mathbb{R}^{m \times n} , \quad p \in \mathbb{R}^{n}, \quad \Sigma \in \mathbb{R}^{m \times m}, \quad w \in \mathbb{R}^{m}$$ where $\Sigma$ is a ...
2
votes
0answers
34 views

Finding gradient of an objective as a PDE

I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me? Assume that we have an optimization ...
1
vote
1answer
77 views

Maximum determinant of a $m\times m$ - matrix with entries $1..n$

I want to find the maximal possible determinant of a $ m\times m$ - matrix A with entries $1..n$. Conjecture 1 : The maximum possible determinant can be achieved by a matrix only ...
1
vote
0answers
55 views

Proving boundedness of a function .

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,\; ...
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,\; ...
0
votes
1answer
25 views

Volume of a polytope cut off by a hyperplane

Given a maximization problem with constraints, and adding a few more constraints using the Gomory cuts and solving the relaxed maximization problem, we can arrive at integer solutions. I am looking to ...
0
votes
4answers
45 views

Given a satisfactory real number = [any integer]/(2b) where a and b are integers, how would one find the minimum value of b?

For instance, 0.625 = 5/(2*4). Given 0.625, how would one find 4? 0.75 = 1/(2*2). Given 0.75, how would one find 2? I should ...
1
vote
1answer
30 views

Linear Algebra Question concerning the trace of a symmetric positive definite matrix.

The objective is to minimize the diagonal elements of a symmetric positive definite matrix. The expression of this matrix is a little bit nasty and its inverse is much easier to deal with. Can I claim ...
2
votes
0answers
25 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
3
votes
2answers
82 views

Minimum of $|\det(X+iC)|$

Let $C$ be a fixed real $n\times n$ matrix, $X$ be an arbitrary real $n\times n$ matrix. Find the minimum value of: $$|\det(X+iC)|=\sqrt{\det(X+iC)\det(X-iC)}$$ When $n=1$ it's clear that the ...
1
vote
1answer
58 views

Find max and min subject to constraint ||x|| = 4

$Q(x,y)=7x^{2}+12xy+12y^{2}$ I only know how to do this is $\|(x,y)\|=1$ If $\|(x,y)\|=1$, the eigenvalues are $16$ and $3$. So obviously $\min=3,\max=16$. I don't know what to do if ...
0
votes
0answers
20 views

Minimization problem with amplitude constraint

I have the following minimization problem: $$\left\| \bf{A}x - y\right\|^2 \to min $$ $$s.t. \left|x_i\right| < 1, \forall i,$$ where $\bf{A}$ is the complex matrix with size of $(n\times m)$, ...
0
votes
0answers
24 views

Differentiation of cost function in adaptive CFO estimator

I'me trying to simulate the steepest descent algorithm for CFO estimation using null subcarriers (OFDM wireless). And some mathematic difficulties have arised. In the core of algorithm lies cost ...
1
vote
0answers
34 views

Is there any available method to solve $A^TAA^TA+A^TAPA^TA-Q=0$

Let $P, Q\in \mathbb{R}^{m\times m}$ are symmetric matrixes. $A$ is an unknown matrix $\mathbb{R}^{m\times m}$ which satisfies the following equality and $A$ is not sure to be unique, ...
0
votes
1answer
20 views

How to maximize this function

We are in an euclidian space, and we have to maximize the quadratic form : $x\in B\rightarrow (x|u) (x|v) $where $u$ and $v$ are two given vectors, and $B=\{x:||x||\leq1\}$ I don't find where i have ...
2
votes
0answers
25 views

Random Rotation of Points using Householder matrices

I have $N$ points in $D$ dimensions, were $D$ is big, for sure more than $100$. $N$ is also big. The goal is to produce an algorithm in my code, that will take as input this dataset and will give ...
0
votes
1answer
21 views

Rank degenerate non negative least squares

I'm following an algorithm in the book "Solving Least Squares Problems" by Lawson and Hanson (#15 in Siam's Classics in Applied Mathematics) for solving non negative least squares. That is, minimize ...
0
votes
1answer
24 views

Closest points on two line segments

I am looking for a general formulation to find the closest points on two line segments. What I was thinking about is to define our lines as: $$ P1 + s (P2-P1)$$ $$ Q1 + t (Q2-Q1)$$ Where $P1 , ...
0
votes
0answers
17 views

How to find iso function value points without exploring all points in 2D space

Consider a 2D graph with dim1 and dim2 represented as X and Y respectively. The range of X and Y are 1 to 100. Hence there are 10000 points in the 2D space. Each point in the space is some function of ...
1
vote
0answers
24 views

How to solve Bellman's optimal equation from the first principle

How to solve the following set (finite) of equations $$ v_*(s) = \max_{a\in A(s)} \sum_{s'} p(s'|s,a) [r(s,a,s') + \gamma v_*(s')]$$ $p$ and $r$ functions are given.
2
votes
0answers
50 views

How to find out the closed form of a function from its parametric form?

In general suppose that we have a parametric curve given by: $$ x = \phi(t) \\ y = \psi(t) $$ Then if $\phi^{-1}$ exists it is easy to get $y$ as a function of $x$ in closed form: $$ y = ...
1
vote
0answers
23 views

Optimal VCV matrix solution of multivariate loglikelhood

I asked a related question yesterday and got a brilliant answer from Ross B. However I still have difficulties. I have the following analog of multivariate loglikehood function (minus 2*log-likehood ...
1
vote
1answer
28 views

Minimize Energy using Gauss-Seidel method with successive over- relaxation.

I have an energy function to minimize $$E = \sum_i \|I_i - \mathbf N_i^T\mathbf L\|^2 + \lambda\sum_{i,j}\|\mathbf N_i - \mathbf N_j\|^2$$ where $I$ is a known scalar, $N$ is an unknown $n\times3$ ...
1
vote
2answers
127 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 $$ ...
0
votes
0answers
32 views

The eigenvector does not minimize the error

Consider the cost function J: $J=|P_1-\beta P_2|^2+\lambda(\pmb{q}^H\pmb{q}-E)$ where $P_1, P_2$ and $\beta$ are complex scalars, $\lambda$ is the Lagrange multiplier and E is the constraint applied ...
0
votes
1answer
74 views

Weighted Singular Value Decomposition

Lemma: $\forall A\in R^{n\times n}$ and a diagonal matrix $\forall W\in R^{n\times n}$ with $ w_{11}\geq w_{22}\geq ...\geq w_{_{nn}} >0$. The singular value decomposition of A denoted by: $A=XM ...
0
votes
1answer
23 views

Can one determine optimal parameters of a matrix to design the matrix kernel? (with specific example)

Suppose we are given a matrix $B\in \mathbb{R}^{n\times n}$. I would like to find $n$ real values $\{a_i\}_{i=1}^n$ that form a diagonal matrix $A=\text{diag}(\{a_i\}_{i=1}^n)$ to design the kernel of ...
0
votes
0answers
87 views

Maximize the maximum Eigenvalue under a diagonally constrained matrix

Suppose we have $N\times N$ Hermitian matrix $\mathbf{A}$ I want to find the real $N\times N$ diagonal matrix $\mathbf{D}$ that maximizes the sum of the maximum Eigenvalues : $\mathbf{D}=\arg\max ...
0
votes
1answer
36 views

Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?

I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions... Let $P$ =$\{x\in \mathbb{R}^n ...
2
votes
1answer
76 views

Linear Algebra 101 - Optimizing inequalities

I am considering the region contained in $\mathbb{R}^2$ consisting of all the points that satisfy all the following inequality: $-4 \leq y < 4 \\ -9 \leq 2x + y \leq 9 \\ -9 \leq x + 2y \leq 9 \\ ...
1
vote
2answers
35 views

How to verify whether a solution to an optimization problem is correct.

Consider a general optimization problem min f(x) subject to g(x) <=0 h(x)=0, where x denotes a vector and the functions are $R^n$ -> $R^n$. suppose ...
3
votes
1answer
60 views

Rank one plus diagonal matrix approximation

Given $A \in R^{n \times n}$, $A$ symmetric. I'm trying to solve the following minimization problem: $\underset{u \in R^n, d \in R^n} \min \, \frac{1}{2} \|X - A\|_F^2$ subject to $X = u u^T + ...
1
vote
1answer
14 views

the differences and relationship between linear independent and affinely independent

When learning optimization, I heard the two related concepts on linear algebra: linearly independent and affinely independent. ...
1
vote
1answer
23 views

Linear Optimization Study Material

I've recently enrolled in a linear optimization course, and it's been a while since I've taken linear algebra. I do not yet have access to the book for the course or I would skim it to see what I need ...
1
vote
0answers
16 views

Sufficient condition for Lagrange function to be maximum or minimum

In optimization by Lagrange method, what is the sufficient condition for the Lagrange function to be minimum or maximum? Of course , I do know that in direct replacement method, Hessian matrix being ...
0
votes
1answer
49 views

Shortest distance between parallel line and plane

I've been doing questions regarding the shortest distance between lines/planes and points , and I've come across a question asking to find the shortest distance between a line and a plane which are ...
0
votes
1answer
44 views

Homogeneous non-negative least-squares

I would like to least-squares-"solve" a set of linear equations ($\underset{\mathbf{x}}{\mathrm{argmin}}\; \|\mathbf{Ax-b}\|_2$). In my case, $\mathbf{b=0}$, e.g. the system is homogeneous. I also ...
0
votes
1answer
24 views

Solve this system of linear equations and also prove sth. else

Solve this systems of linear equations with variables $a$, $b$, $c$ and $d$, others are constant. That is, how to solve for $a$, $b$, $c$ and $d$ with a closed form, using the other constant. (To ...
1
vote
1answer
30 views

Relation between rank of a symmetric positive semi-definite matrix and its number of non-zero eigen values (or singular values)

Is there any relation between the rank of a symmetric positive semi-definite matrix and its number of non-zero eigenvalues (or singular values)? For a matrix $\mathbb{P}$ Can we find the ...
0
votes
0answers
31 views

Mixed Interprogramm remodeling

for example i have the following problem min z 5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z -3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z x_1a + x_1b = 1 (Constraint say of this group only one variable ...
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
22 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
37 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 ...