0
votes
1answer
24 views

Is $f(X) = || Y - XX^T ||_F$ convex given fixed $Y$?

In the scene of nonnegative matrix factorization, $f(X_1, X_2) = \| Y - X_1 X_2 \|_F$ is not convex, but both $f(X_1)$ given fixed $X_2$ and $f(X_2)$ given fixed $X_1$ are convex, enabling us to ...
0
votes
0answers
83 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 ...
1
vote
1answer
25 views

Problem understanding dual optimization problem?

I am reading this paper: http://dl.acm.org/citation.cfm?id=1390696 Following optimization problem is defined in section 2: \begin{align} \max_{\mathbf{X}>0} \log ...
0
votes
1answer
33 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
3
votes
1answer
57 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 + ...
0
votes
0answers
27 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
0
votes
1answer
28 views

Is this following SDP problem Convex?

Is the following problem convex function? \begin{eqnarray} \begin{aligned} \underset{\mathbf{X}} {\text{minimize}}\,\,\,\, & \text{Trace}(\mathbf{RX}) \\ \text{subject to} &\\ & ...
0
votes
0answers
18 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
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 ...
1
vote
2answers
62 views

Optimization of Product of Different Objective functions (Ex.: Maximize The Product of projections of a complex vector)

Suppose We have this optimization problem which is convex $\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max f_{i}\left (\mathbf{x} \right )$ But the product of different objective function is ...
0
votes
2answers
68 views

Solution in general for a seemingly simple problem

Let $\mathbb{S}$ be a closed, bounded, convex set in $\mathbb{R}^N$. Let $\mathbb{x}=[x_1,\dots,x_N]$ be any arbitrary vector in $\mathbb{S}$. Then what can we comment on the problem \begin{align} ...
0
votes
0answers
52 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
277 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
24 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 ...
7
votes
2answers
264 views

Derivative of nuclear norm

I'm trying to take the derivative of nuclear norm with respect to its argument. nuclear norm is defined in the following way: $$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$ I'm trying to calculate: ...
0
votes
1answer
76 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, ...
1
vote
1answer
63 views

How to find a positive semi-definite linear combination?

Suppose we are given two explicit symmetric matrices $X$ and $Y$ and we'd like to find a non-zero real linear combination $aX+bY$ that is positive semi-definite (if possible). Is there a way to go ...
0
votes
0answers
13 views

NNLS for under determined system

I have system of equations to solve Ax=B under x>=0. I read that Non Negative least Square(NNlS) algorithm proposed by Lawson and Hanson could solve this system for over determined case( number of ...
0
votes
1answer
47 views

Minimize $L_2$-norm of $x1-b$ where $x \in R, b \in R^n$

Minimize $L_2$-norm of $x1-b$ where $x \in R, b \in R^n$ $||x1-b||_2 \rightarrow ||x1-b||^2_2=||x1-b||^T||x1-b||$ (squaring $L_2$-norm doesn't change outcome and yields quadratic) ...
0
votes
1answer
76 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 }\\ ...
3
votes
2answers
114 views

Singular Values of Matrix as Optimization Problem

Assume that $A$ is a positive semidefinite symmetric matrix. It is known that $$\max_{||y||\leq1} \quad y^TAy$$ Has an analytical solution which is the maximum eigenvalue of $A$. This isn't hard ...
0
votes
1answer
91 views

SDP formulation of noisy low rank matrix completion (2)

Thank you Michael for the answering my previous question, SDP formulation of noisy low rank matrix completion. It seems that I overlooked the problems in my initial question. I didn't recognize the ...
1
vote
1answer
37 views

An equation related to covariance matrix, square root of the matrix, and Euclidean norm.

How can I prove this equation: $${ ({ x }^{ T }\Sigma x) }^{ 1/2 }={ \left\| { \Sigma }^{ 1/2 }x \right\| }_{ 2 }$$ In which $\Sigma $ is a covariance matrix. I tried some numerical examples in ...
0
votes
0answers
30 views

Isomorphisms of Convex Cones

A convex cone $C$ is a subsets $C \subseteq V$ of a vector space which is closed under positive linear combinations, i.e. for $\lambda, \mu > 0$ and $u,v \in C$ it is $\lambda u + \mu v \in C$. An ...
3
votes
2answers
357 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 ...
1
vote
2answers
62 views

Hessian matrix and epigraphs

I'm working on a homework assignment concerning convex optimization and I came across a problem involving the convexity of the function and the convexity of the domain of the function. Consider the ...
0
votes
0answers
42 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
1
vote
0answers
166 views

Minimum L1 norm may not obtain the sparsest solution?

Here is a paper called For Most Large Underdetermined Systems of Equations, the Minimal L1-norm Near-Solution Approximates the Sparsest Near-Solution. However, I did not quite get its definition of ...
1
vote
1answer
85 views

minimum trace norm on the set of matrices with fixed diagonal entries

What is the min nuclear norm (sum of singular values) on all $n \times n$ matrices$A$ whose diagonal is fixed. i.e. $diag(A) = v$ Is it true that the diagonal matrix is a minimizer?
0
votes
1answer
53 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
2answers
160 views

Why the unit circle in $\mathbf{R^2}$ has one dimension?

When I was reading 'Convex Optimization, Stephen Boyd', I was wondering of following steps Consider the unit circle in $\mathbf{R^2}$, $i.e.$, $\{x\in\mathbf{R^2}|x^2_1+x^2_2=1\}$. Its affine hull ...
0
votes
0answers
31 views

Implementing SVM: Help converting equation into form of another

I'm currently programming a simple linear SVM (Support Vector Machine). For the optimization involved, I need to find a way to convert the equation $\sum\limits_{i=1}^L a_i ...
1
vote
0answers
53 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
0
votes
0answers
26 views

Error of the norm of solution in linear least-squares

How can we estimate the solution norm ($\Vert x \Vert$) error, separate from the solution ($x$) error in solving $Ax=y$ (linear least-squares problem)? Is the error of $\Vert x \Vert$ higher or lower ...
1
vote
0answers
55 views

Joint cost function with Lagrangian

How can I formulate joint cost functions if Lagrangians are involved? For example, if I have $J_1 = \|\mathbf{Ax} - \mathbf{b}\|^2_2 + \lambda f$ and $J_2 = \|\mathbf{Cx} - \mathbf{d}\|^2_2$, ...
0
votes
2answers
51 views

Non-elementwise Matrix Derivatives

Let A,B,C,D,X be matrices. I'd like to perform a Gradient Descent minimization to the loss functin $$ tr[(AXBX^TC-D)^T(AXBX^TC-D)] $$ My question is, how to take the gradient efficiently w.r.t. $B$? ...
1
vote
0answers
23 views

Issues related to positive definiteness in a convex optimization problem

I have some issues in a convex optimization problem. My f(X) is a convex function of X where X is a positive definite matrix. X is very sparse and has a handful of non zeros values. Now I only need to ...
0
votes
1answer
56 views

Is this function convex or concave?

I have a function, $f(x_{0},x_{1},......x_{n})=\sum^{n-1}_{i=0}A_{i}r^{-(x_{i}+x_{i+1})}-B$ $A_{i} >0$ for all $i$ and $B>0$ and $1 \leq r \leq 2$ so above function is convex or concave? ...
2
votes
0answers
63 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
0
votes
0answers
29 views

Monotone linear maps on symmetric matrices

I consider linear maps from real symmetric matrices in dimension n to real symmetric matrices in dimension m, monotone which respect to the ordering induced by the positive semidefinite cone (or, ...
0
votes
1answer
71 views

Problem with dot product and outer product of vectors.

I have two column vectors $X$ and $Y$. Now the Equation is $$ \frac{1}{2}(X Y^T)^2 - X^TXY^TY $$ Where $X^T$ is the transpose of $X$. I need to solve the equation basically get something like ...
0
votes
0answers
29 views

A generic 3-D optimization problem

Let $\mathbb{S}_3$ be any general 3-dimensional convex body. Let $(x,y,z)$ denote a 3-D point in it. Consider the following optimization problem \begin{align} ...
0
votes
2answers
87 views

How can I find the center of a region in a linear programming problem?

I have an optimization problem that in most respects can be very elegantly expressed via linear programming. The twist is that I don't actually want to minimize or maximize any of my variables; I ...
1
vote
1answer
72 views

Linear System with constrained solutions

After a model my problem I found a rectangular linear system : $$Ax=b$$ I can easely solve it with a least square with QR/SVD... But the model include constrains for each solution $x_i$, the $\vec{x}$ ...
1
vote
1answer
56 views

Containment of one convex hull in another

This question is related my previous question (Comparing two probability distributions) which are both related to my current research. Suppose we have two bounded convex hulls in $\mathbb{R}^n$ ...
2
votes
0answers
53 views

Proving an optimization problem has a rational optimum.

Consider the function $$ J_\gamma(X) = \det\left( I - \tfrac{1}{\gamma^2} (A+BXC)^\mathsf{T}(A+BXC)\right) $$ where $A$, $B$, $C$, $X$ are matrices of real numbers. Further suppose that ...
1
vote
1answer
55 views

Interpreting a theorem about convex sets

I'm studying about linear programming and I bumped into following theorem (I have added my questions into the image): So in 1st rectangle how did we obtain the resulting equation when $\alpha ...
1
vote
1answer
76 views

Help with a proof of a theorem about convex sets

I'm studying the following theorem: Theorem 1. Let $C$ be a convex set and let $\textbf{y}$ be a point exterior to the closure of $C$. Then there is a vector $\textbf{a}$ such that ...
1
vote
0answers
49 views

Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
1
vote
0answers
105 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...