0
votes
1answer
16 views

making a function non-linear using a Lagrangian function

How Is this formula a Lagrangian function ? And how can a non-linear element be added to a function using this "Lagrangian function" This is where i got this In order to improve the performance ...
4
votes
1answer
32 views

Maximizing the trace

Say i have the following maximization. $ max_R$ trace $(RZ): R^TR = I_n$ where $R$ is an $n$ x $n$ orthogonal transformational vector. Also, the SVD of $Z = USV^T$. I'm trying to find the optimal ...
0
votes
0answers
12 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
2
votes
0answers
19 views

Quadratic minimization with real output

Let $A$ be a $n\times n$ hermitian matrix. My goal is to minimize the following hermitian form with an additionnal "real constraint": $$\min_f f^\ast A f$$ $$\text{subject to }f \in \mathbb{R}^n$$ ...
0
votes
1answer
18 views

Expanding variance

Could someone please expand on line 2 and 3 of: Thank you.
2
votes
2answers
50 views

Minimum of a quadratic form

If $\bf{A}$ is a real symmetric matrix, we know that it has orthogonal eigenvectors. Now, say we want to find a unit vector $\bf{n}$ that minimizes the form: $${\bf{n}}^T{\bf{A}}\ {\bf{n}}$$ How can ...
2
votes
0answers
36 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 ...
1
vote
2answers
40 views

steepest descent with quadratic form converge in 1 iteration

Well I'm stuck on an exercise given: The steepest descent method is applied to the quadratic form $$Q(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^TA\mathbf{x} - \mathbf{b}^T\mathbf{x} + c$$ where $A$, ...
3
votes
0answers
33 views

Find closest vector to a given vector from a particular set of vector

Let $x=\left(x_t\right)_{t=1}^n$ be a vector such that $$ x_t = \prod_{i=1}^t u_i, \tag{1} $$ where each parameters $u_i$ can take any of two value $$ u_i \in \left\{a,b \right\} = \left\{ 1.3, 0.8 ...
0
votes
1answer
37 views

$|\langle a_i, a_j\rangle|$ for $p$ points on a unit circle.

Is it true that given any $p$ points $a_1, .., a_p$ on a unit [euclidean] circle, there is always a pair $i \ne j$ such that $|\langle a_i, a_j\rangle| \ge \cos{\pi/p}$?
0
votes
0answers
47 views

Solve the system of inequalities. Optimization problem.

I have a set of linear inequalities as follow: ...
2
votes
1answer
55 views

using the kronecker product and vec operators to write the following least squares problem in standard matrix form

I have a least squares problem with the following form: $$ \min_\mathbf{X} ~ \left\| \sum_{i=1}^n \mathbf{u}_i^\top \mathbf{X} \mathbf{v}_i - b_i \right\|^2 $$ where $\{\mathbf{u}_i\}_{i=1}^n$ and ...
1
vote
1answer
33 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
41 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 ...
0
votes
1answer
56 views

Semi-positive definite Hessian matrix and local minimum

Suppose we have a function $F(x)$ defined as \begin{equation} F(x) = \frac{1}{2}x^TAx + b^Tx +c, \end{equation} where \begin{equation} A = \begin{bmatrix} 4 & 2 \\ 2 & 1 \\ ...
0
votes
0answers
16 views

Sparse coding with local sparseness of dictionary

The title is probably pretty unclear, I hope I am able to explain it better here. I am currently working on a problem in the field of sparse coding, that is Principal Component Analysis, Non-negative ...
1
vote
1answer
38 views

Finding $\max_{||x||_2=1} \min_i |(Ax)_i|$

Let us define for $x \in \mathbb{R}^n$ $$M(x)=\min_i|x_i|$$ Is there a way to solve the following optimization problem: $$\max_{||x||_2=1}M(Ax)$$ for a given $A$?
2
votes
1answer
39 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
1answer
57 views

Explain the convexity by looking the hessian matrix of a function

The hessian matrix of a function is given by, $$ H = \begin{bmatrix} a & b & c \\[0.3em] b & b & 0\\[0.3em] c & 0 & c \end{bmatrix} $$ where, ...
0
votes
0answers
30 views

Vectors on a Sphere

Let $S$ be a sphere centered at origin in $\Bbb R^{2n}$ of radius $\sqrt{2n}$. Let $D$ be a diagonal matrix. Let $U$ be unitary matrix. Let $r\in\Bbb Z_+$ be a fixed integer. $(1)$ For a vector $v$ ...
0
votes
0answers
20 views

Sum of two polyhedra is a polyhedron

I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows: Let $P$ and $Q$ be polyhedra in ...
-1
votes
1answer
42 views

value of x when equation reach maximum?

how can i find the value for $x$ when $y$ reach to $maximum$ value or go to $infinity$ $$ y=\frac{1}{2}A(1+\cosh{(x \sqrt[2]{\frac{B}{A}})} )$$ where $A,B$ are constant $x$ range from $0$ to ...
3
votes
2answers
49 views

Finding minimum $\alpha > 0$ so that $\det(A - \alpha B) = 0$ for positive definite $A,B$

Given two positive definite symmetric matrices $A,B$, I'd like to find the minimum $\alpha > 0$ such that $A - \alpha B$ is singular, i.e., the threshold where $A - \alpha B$ is no longer positive ...
1
vote
0answers
40 views

mathematics of chemical stoichiometry

I would like to better understand the mathematical description of chemical stoichiometry and thermodynamic chemical equilibrium. This problem has many features and I know my description might be too ...
0
votes
1answer
49 views

Solution to a Quadratic Minimization with Norm Constraint

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ ...
2
votes
1answer
56 views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
1
vote
0answers
33 views

analytic solution to structured algebraic Riccati equation

In solving a model I have written down for a research paper, I am left with two Algebraic Riccati Equations, that is I need to solve for $X$ in the equation \begin{align*} X = A^\top (X + XB(R + ...
1
vote
1answer
54 views

least squares minimization problem

It's easy to show that the solution to a least squares problem such as minimizing $||Ax+b||$ is $(A^tA)^{-1}A^tb$. But how can one minimize $\sum_{i}||A_ix+b_i||$? In one of the passages of the ...
1
vote
1answer
55 views

Relation between softmax and max

For two vectors $X$ and $Y$ in $\mathbf{R}^n$, does the inequality below hold? $\left| \text{softmax} X - \text{softmax} Y \right| \leq \text{max} | X - Y |$ Softmax is the same as log-sum-exp: ...
1
vote
1answer
47 views

Minimum Eigenvalue of the Rank One update to a Positive Semi-Definite matrix

Let $\mathbf{A}$ be a $N\times N$ positive semi-definite hermitian matrix. Let $\mathbf{b}$ be a $N\times 1$ complex vector. For any given constant $t$, I interested in the minimum eigenvalue of the ...
3
votes
2answers
205 views

Adding Elements to Diagonal of Symmetric Matrix to Ensure Positive Definiteness.

I have a symmetric matrix $A$, which has zeroes all along the diagonal i.e. $A_{ii}=0$. I cannot change the off diagonal elements of this matrix, I can only change the diagonal elements. I need this ...
0
votes
1answer
33 views

Sample Variance in Principle Components Analysis

I was reading this Why is the eigenvector of a covariance matrix equal to a principal component?. And in the top answer, the poster mentions that if the covariance matrix of the original data points ...
0
votes
1answer
41 views

Partial Differentiation Question. Solving when there is many variables

In one of my computer science classes we were given a homework problem that deals with partial differentiation. I never learned this in my math classes and have been trying to teach myself this but ...
2
votes
1answer
164 views

Testing critical points using newton-raphson method

I'm working on a homework assignment for my artificial intelligence course and I became a bit stuck on one part. The problem asks to retrieve the optima of the function and then to tell for each ...
0
votes
0answers
34 views

Approximation of largest eigenvalue

What is an approximation for the largest eigenvalue of a matrix $A $? I mean, I am looking for some expressions that can be used as approximation for largest eigenvalue
0
votes
1answer
41 views

Relation between arg min of two functions

When is $u_F(x) = \underset{u}{\text{argmin}}(F_1(x),\cdots,F_u(x),\cdots,F_U(x))$ $\le$ $\underset{u}{\text{argmin}}(G_1(x),\cdots,G_u(x),\cdots,G_U(x)) = u_G(x)$ where $u \in \{1,2,\cdots,U\}, x \in ...
2
votes
0answers
55 views

Find the following transformation $G$

I'm not sure if I'm writing this problem properly, so any suggestions or modifications are much appreciated, but here is what I have: Let $\mathbf{y=Gx}$, where $\mathbf{G} \in \mathbb{C}^{N\times ...
6
votes
1answer
159 views

Gradient Descent on Non-Convex Function Works But How?

For Netflix Prize competition on recommendations one method used a stochastic gradient descent, popularized by Simon Funk who used it to solve an SVD approximately. The math is better explained here ...
0
votes
2answers
53 views

Optimization of electricity costs

I have to solve this exercise for the school and I do not really understand why the teacher solved it like this. Here is the exercise: I want to replace the 60 watt bulbs with 8 watt LED lamps. The ...
3
votes
1answer
48 views

Does having a zero eigenvalue preclude a matrix from being indefinite?

If a $3\times3$ matrix has a positive eigenvalue, a negative eigenvalue, and a zero eigenvalue, is it then, by definition, indefinite? I think so, since the matrix has both a positive and a negative ...
0
votes
0answers
64 views

Minimizing the Kullber-Leibler divergence between two multivariate normal distributions

Take two zero-mean multivariate normal distributions: $p=\mathcal{N}(\mathbf{0},\boldsymbol\Sigma)$ and $q=\mathcal{N}\left(\mathbf{0},\left(\mathbf{A}^{T} \boldsymbol\Omega ...
0
votes
0answers
26 views

MinMax Tree data structure problem

Let vector (x,y,z) be a "Tree Node" where x,y,z are integers. Each node (x,y,z) has 3 parents which are (x-1,y,z), ...
1
vote
1answer
73 views

Finding minimum of the trace of the matrix equals finding maximum of the trace of the inverse matrix?

Let $K$ be a positive definite, symmetric matrix. Let $C$ be a nondegenerate matrix of the same order. Elements of $K$ and $C$ depend on some parameter $a.$ Is it true to say that $$ ...
1
vote
1answer
55 views

Direction of steepest descent and minimization?

I have the following linear function: $min$ 1/2 $<x, x>$ + $r^Tx$ for every x belonging to $R^n$, $r^Tx$ belongs to $R^n$ Now, = $x^TAy$ and A is symmetric positive definite. = $x^TAy$ is ...
2
votes
0answers
43 views

What (if anything) can I say about the inverse of the matrix product B'AB if B is not square?

Suppose I have: a matrix $A$ with dimension $n \times n$ a matrix $B$ with dimension $n \times m$. $C = B^{T}AB$. I'm interested in finding an expression for $C^{-1}$ when $m < n$. The ...
0
votes
1answer
45 views

Strictly positive solution of linear equations

Suppose $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$, and $b\in \mathcal{R}(A)$. Show that there exists an $x$ satisfying $x \succcurlyeq 0$, $Ax = b$ if and only if there exists no ...
1
vote
0answers
44 views

find conditions on input data such that a linear system has (no) feasible points

As a result of the apllication of Farkas' lemma I obtained the following problem: Let $ m,n,q \in \mathbb{N} $, $ b \in \mathbb{N}^m, l \in \mathbb{N}^m $ with $ l_i \mid q$ for all $ i=1,\ldots,m $. ...
2
votes
0answers
27 views

Monotononically Increasing Water Filling Solution?

$\mathbf{I}$ is the $K\times K$ identity matrix. $\mathbf{h}_i\in\mathbb{C}^{M\times1}\quad\forall1\leq i\leq K$ are column vectors. Consider the solution of the convex optimisation problem over ...
2
votes
0answers
80 views

Optimization - show that linearized feasible set is empty.

I need help in the following problem: Consider the following optimization problem $$ \min_{x_1,x_2}-x_1-x_2\quad\text{s.t.}\quad x_1^2+x_ 2^2-1=0,\quad x_1,x_2\geqslant 0.$$ Show that the ...
3
votes
2answers
62 views

Matrix which when multiplied, gives a maximal minimum of elements of result.

I'm working on an optimization problem and am stuck at this particular step. Let $\bf{A}$ be a matrix with 4 columns and a finite number of rows, consisting of elements which are either 0 or 1. Let ...