0
votes
0answers
24 views

how to prove this sparse coding equation

How can I prove the following? $\sum_i \frac{1}{2} \|\mathbf{x}_i - D\mathbf{\alpha_i}\|^2 = \frac{1}{2}Tr(D^TDA_t) - Tr(D^TB_t)$ where, $A_t = \sum_{i=1}^T \mathbf{\alpha}_i\mathbf{\alpha}_i^T\\ ...
0
votes
1answer
114 views

Gradient descent (with line search) for convex functions viewed as alternation

I have fundamental confusion about gradient descent (with line search) and the reason it works. I try to explain my view here, and please tell me where it goes wrong. Let $f: \mathbb{R}^n \to ...
0
votes
1answer
44 views

Reference for gradient descent with unit norm constraint

I faced a non-convex optimization problem with unit norm constraint. I can solve the problem using the gradient descent method and the projection of the gradient onto the tangent plane as in @joriki ...
0
votes
1answer
54 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
0
votes
1answer
71 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
0
votes
0answers
30 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 ...
0
votes
0answers
35 views

Linear least squares with sparse inequality constraints for support function estimation

The initial problem is the following: $$ ||h - h^{0}|| \to min \; \; s.t. Qh \leq 0 $$ where $h^{0} \in \mathbb{R}^{n}$ is known vector and $Q$ is a $m \times n$ matrix. The problem arises in specific ...
1
vote
1answer
47 views

How to verify correctness of a Fenchel conjugate derivation

Suppose I derived Fenchel conjugate of a function. My goal is to check if my solution is right. Suppose the steps are not available any more and only the final solution is present. Is there any ...
0
votes
0answers
45 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
8
votes
1answer
221 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
1
vote
0answers
193 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
0answers
44 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
0
votes
1answer
62 views

How to re-parametrize for quadratic minimization?

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
0
votes
1answer
200 views

Infeasible start Newton's method

I am implementing infeasible start Newton's method from the information in the slides (slide 11 of the link) posted here. It requires us to calculate primal and dual Newton steps, denoted by, $\Delta ...
2
votes
0answers
156 views

Optimization problem about large matrices

I'd like to solve the following optimization problem: Find non-negative scalar $a$, $b$, $c$ to minimize $\| (D-(aA+bB+cC+D^{-1})^{-1})y\|^2+2\operatorname{trace}((aA+bB+cC+D^{-1})^{-1})$ where ...
0
votes
0answers
33 views

How can I reformulate my problem to make it convex?

I would like to find the symmetric positive definite matrix $S\in \mathcal{M}_{m,m}$ that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex ...
1
vote
0answers
24 views

Can we express a SPD matrix $S$ in terms of $S^{2}$ in a different manner to solve a convex problem?

I have to find the Symmetric Positive Definite matrix $S\in \mathcal{M}_{m,m}$ that minimizes the function $f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ which has been proven to be convex in the ...
0
votes
0answers
240 views

Gradient Descent with nonlinear constraint on Symmetric positive definite matrix space

I would like to find the stationary point $S_*$ (global minimum) that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex in Convexity of ...
2
votes
1answer
60 views

Possibility of Unboundedness in Least Squares Minimization

Suppose we have the quadratic minimization problem \begin{equation} \min_x \frac{1}{2} x^TPx + q^Tx +r \end{equation} We know that when $P$ is symmetric positive semi-definite, but the optimality ...
0
votes
2answers
419 views

What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
0
votes
2answers
308 views

Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1
vote
1answer
1k views

what are Smooth and Non Smooth Problem in optimization?

I am trying to understand the difference between the optimization problem types which are basically smooth and non smooth. I also found this question what does a smooth curve mean? I understand that ...
5
votes
1answer
559 views

Solving a set of 3 nonlinear equations with constraints

Problem statement: I am given 3 sets of equations that govern the force $P$, and also the neutral axis, defined by two variables, the radius from the center $r$ and also the rotation degree in ...