1
vote
0answers
9 views

LU decomposition of a $n\times n$ matrix

I would like to find the LU decomposition of the following matrix: $$\begin{equation} a_{i,j}=\left\{ \begin{split} 1\quad \mbox{if}\qquad i=j \quad\mbox{or}\quad j=n\\ ...
0
votes
0answers
23 views

A problem on positive semi-definite quadratic forms/matrices

Suppose $a+b+c=0$ and (without loss of generality) $a^2+b^2+c^2=1$, is the following quadratic form positive semi-definite? Thank you very much. \begin{equation*} \begin{split} ...
0
votes
1answer
17 views

Finding the minimum distance between two lines

I really don't know how to tackle this optimization problem: We consider the two lines $$a(x) = x \begin{pmatrix}1\\2\\3\end{pmatrix}, b(y) = ...
0
votes
0answers
16 views

How to describe contours of a function

$$f(x) = 0.5x^TAx-b^Tx$$ $$A = 2I$$ $$b = (-1, -1, -1,...,-1)^T$$ How can I use this information (or in the general case, just $A$ and $b$) to describe the contours of $f$? I get the feeling that ...
1
vote
1answer
26 views

Taking the dual of this non-standard linear program

I am just beginning to learn linear programming have a question about taking the dual of a non-standard LP specifically the one below: $\min M\\ 2x_1 + 3x_2 + 4x_3 \leq M \\ 2x_1 - x_2 + x_3 \leq M\\ ...
0
votes
1answer
42 views

Why does SVD provide the least squares solution to $Ax=b$?

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, ...
1
vote
2answers
42 views

Is the set of all projection matrices a convex set?

The set $\phi=\{P| P^2=P\}$ contains all projection matrix. Is this set $\phi$ convex?
3
votes
3answers
69 views

Orthogonal Vectors in a 2D Lattice with minimum area

I came across an interesting problem in my research (not a mathematician). Here it goes: Suppose, there is a 2D lattice $\Lambda$ in the X-Y plane with basis vectors $\vec{a}$ and $\vec{b}$, which ...
0
votes
1answer
20 views

Convergence of Steepest Descent: Proving Orthogonality of Exact Line Search Steps

For the following assume that $f(x) = 0.5x^TQx - b^Tx$, where Q is symmetric, positive definite $n$ x $n$ matrix, and $b$ belong to $R^n$. Assume that $x^*$ is the unique local minimizer of $f(x)$ and ...
1
vote
1answer
28 views

By minimizing the function $\phi(s,t) = \frac{1}{2} \mid\mid \textbf{b} - (s\textbf{a}_1 + t\textbf{a}_2) \mid\mid^2$, find a for

Suppose $\textbf{a}_1$ and $\textbf{a}_2$ are linearly independent vectors, $L = \text{span} \ \{{\textbf{a}_1, \textbf{a}_2}\}$, and $\textbf{b}$ is a vector not in $L$. By minimizing the function ...
0
votes
0answers
26 views

Saddle point problem (KKT) with block-diagonal matrix

Consider the following saddle point problem originating from an interior-point method algorithm: $$ \begin{bmatrix}\mathbf{H} & \mathbf{A}^{T}\\ \mathbf{A} & \mathbf{0} ...
0
votes
1answer
63 views

Give example of a set which has No Extreme Point !!..

Give example of a set in R^2 , which has no extreme point ?? We were given this question for assignment !!..I thought of a simple line but doing some research i stumbled upon this solution which ...
0
votes
0answers
10 views

BFGS update formula

In this pdf : http://www.ing.unitn.it/~bertolaz/2-teaching/2011-2012/AA-2011-2012-OPTIM/lezioni/slides-mQN.pdf, in slide 46, the BFGS updata rule is given and is simplified to a second form. How did ...
0
votes
1answer
25 views

How to apply Sherman Morrison formula for rank 2 update?

For obtaining the inverse update in BFGS, Sherman-Morrison needs to be applied twice since it is a rank 2 update. But what does it mean to apply it twice?
0
votes
0answers
25 views

optimisation problem with linear constraint

optimisation problem with linear constraint I have an optimisation problem. I wish to maximise a function subject to a constraint. It is the constraint that is causing me problems. I am using an ...
1
vote
1answer
24 views

Properties determining boundedness of function

The function I am looking at is $$f(x) = \frac{1}{2}x^TAx + b^Tx + c$$ where $A$ is a symmetric matrix in $\mathbb{R}^{n\times n}$ and $b,c$ belong to $\mathbb{R}^n$ I want to determine what ...
0
votes
1answer
34 views

The relation between two different definitions of Affine sets

I am following a presentation, which says that for an affine set $L \subseteq \mathbb{R}^n$ it is: $$L=\left\{x|Ax=b \right\}$$ for some $A,b$. The first definition of $L$ as an affine set is given ...
0
votes
0answers
39 views

How to Extract the dual feasible search directions for the primal-dual potential reduction algorithm?

I am trying to implement the 4.4 Primal-dual potential reduction algorithm introduced in M.S Lobo et al.. Here is a screenshot depicts the algorithm flow: As ...
1
vote
0answers
18 views

Condition that multiplied hermitian matrix stays hermitian

Suppose we are given a hermitian matrix $E \in \mathbb{C}^{n\times n}$. I want to find sufficient conditions on the entries of a real symmetric matrix $M$ (depending on the entries of the given ...
1
vote
1answer
38 views

Minimize the Frobenius norm of the difference of two matrices with respect to matrix: $\underset{B} {\mathrm{argmin}} \left\| A- B \right\|_F$

The following question is similar to this one, but I think that it is not straightforward to move from one to the other, so please take a look. Otherwise, please let me know and I will delete it. ...
1
vote
0answers
30 views

Derivation of Steepest Descent Direction used in Line Search Methods

In the numerical optimization text I am reading, the Steepest Descent Direction was derived by considering $$ \min_{||p||_2\leq 1} p^T\nabla f(x_k) $$ This resulted in $$ p_k=-\frac{\nabla ...
1
vote
0answers
56 views

How to stop iteration in inverse problem using nonlinear least square problem?

I am having a real trouble with stopping criterion in iteration of Generalized Nonlinear Least Square. My problem is that I do not know exactly how to stop my iteration. First, I will give a short ...
1
vote
4answers
54 views

optimization of coefficients with constant sum of inverses

Does anybody knows if there is an easy solution to the following problem: Given $A = [a_1, a_2, ... a_n]$ and K, find B = $[b_1, b_2,...b_n]$ that minimizes $AB^T$ such that ...
1
vote
0answers
39 views

Does this formula take constant value?

Now, $x_i, \xi, f \in R^n(i= 1, 2, \cdots , k)$, and \begin{align} \sum_{i=1}^k x_ix_i^T\xi=f \end{align} holds. If the above equation is solvable about $\xi$, the value of $f^T\xi$ doesn't depend on ...
0
votes
0answers
21 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
1
vote
1answer
27 views

Show that a matrix A may have all leading principal minors greater or equal to zero, yet not be positive semi-definite.

Title says it all, but I'll rephrase it to be clear. A is an $n\times n$ matrix whose leading principal minors are all greater than or equal to zero. A leading principal minor is the determinant ...
1
vote
1answer
36 views

How to show that these two versions of Farkas lemma are equal?

One version of Farkas lemma is that Let $A$ be a real $m\times n$ matrix and $b$ an $m$-dimensional real vector. Then, exactly one of the following statements are true. There exists an ...
0
votes
1answer
53 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
0
votes
0answers
35 views

Vertices of Polyhedral

Suppose there are matrix $A\in\mathbb{R}^{n \times m}$ and vector $b\in\mathbb{R}^n$. Consider a non-empty polyhedron $P = \{Ax \leq b\} $. Then, there exists a vector $\bar{x}\in P $ such that ...
1
vote
0answers
21 views

Reconstruct a vector with a known vector and residual

I observe $\vec y \in \mathcal R^n$ and know $\vec x$. I assume that $\vec y$ mostly consists of $\vec x$, with some added residual $\vec r$. This gives me the problem $\vec y = a\vec x + \vec r$, ...
2
votes
2answers
66 views

The minimum of $x^2+y^2$ under the constraints $x+y=a$ and $xy=a+3$

I solved the following problem: If $x,y,a \in \mathbb{R}$ such that $x+y=a$ and $xy=a+3$, find the minimum of $x^2+y^2$ Here is my solution. $x^2+y^2=(x+y)^2 -2xy= a^2-2a-6$. The minimum value is ...
0
votes
0answers
26 views

Simple Optimization Problem with linear Algebra

I'm asked to find that the solution of $\displaystyle S(\mathbf{c})=\max_{\mathbf{c}}\frac{\mathbf{X' Z c}}{||\mathbf{X}||\cdot||\mathbf{Z c}||}$, where $\mathbf{X}$ is a $n\times1$ vector, and ...
0
votes
0answers
24 views

How to find a separating hyperplane?

I know about support vector machine, and it's quadratic programming approach which delivers the best separating hyperplane. My question is: is there a relatively simple algorithm to find a ...
2
votes
0answers
28 views

Constrained Quadratic Optimization(Reproducing Kernel)

I am attempting to use a constrained quadratic optimization to find the coefficients of a reproducing kernel. The problem is as follows: $y(t)=\sum_{i=0}^J\alpha_iK(t, t_i)$ $Q(\alpha)= ...
0
votes
1answer
34 views

Why is alternative sign in Hessian subdeterminant a necessary and sufficient condition for multivariable maxmization

The necessary and sufficient condition for a maximal point in a multivariable function is the following $$\text{i. } x \text{ must satisfy first order condition}$$ $$\text{ii. } |H|_1 < 0 \text{ ...
0
votes
1answer
108 views

Closed form solution

I have the following optimization problem: $$\min_{\mathbf{G}} \|\mathbf{B(A+G)\|_F^2} \quad{} \\\text{subject to} \quad{} \mathbf{\|C^T(A+G)\|_F^2\leq \gamma \|A^T(A+G)\|_F^2 } \quad{}, \\ ...
0
votes
1answer
30 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 b$$ Where Q is square ($n$x$n$), positive semi ...
0
votes
0answers
21 views

How to attack solving for similarity transformed quantities

I'm interested in solving equations of the form: $$ R\mathbf{x}R^{T}=\alpha\mathbf{x}+k $$ where $R$ is a orthonormal matrix (rotation), $\alpha$ is a scalar multiplier (non-zero), ...
0
votes
0answers
19 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
69 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
33 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
31 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
16 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
50 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
69 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
35 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
81 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
58 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
56 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 ...