The Pheromone Kid
  • Member for 7 years, 7 months
  • Last seen more than a month ago
4 answers
6 votes
7k views
Definition of Global Convergence
6 votes

See the definition in http://papers.nips.cc/paper/3646-on-the-convergence-of-the-concave-convex-procedure.pdf. The points generated by an algorithm with this property converge for any initial point....

View answer
1 answers
3 votes
1k views
Least squares with a quadratic inequality constraint
Accepted answer
4 votes

It depends. Consider the unconstrained least squares problem $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2. $$ This problem has the solution $\mathbf{x}^\star = - (\mathbf{B}^H\mathbf{B})^{-1}\mathbf{B}^H\...

View answer
1 answers
4 votes
1k views
Maximize the largest eigenvalue of a Hermitian matrix constrained by quadratic polynomials
Accepted answer
4 votes

As noticed in the comments, your optimization problem can be formulated as $${\rm max}_{\mathbf{x},\mathbf{y}} \mathbf{x}^T S(\mathbf{y}) \mathbf{x} ~~~{\rm s.t.} \|\mathbf{y}\|_{2} = 1,\|\mathbf{x}\|...

View answer
3 answers
2 votes
433 views
Line with minimum average distance to a set of points in $\mathbb{R}^2$
2 votes

The difficulty of your problem is that you try to minimize with respect to a sum of absolute values. If your problem was "just" to minimize with respect to the sum of squared values it would be much ...

View answer
2 answers
2 votes
81 views
Where am I wrong in my understanding about the activeness of the constraints?
2 votes

Your reasoning is right. However, you have overseen that you can choose $y$ arbitrarily small when $x$ approaches 0. Therefore, the constraints will not be met with equality. For example, you may ...

View answer
1 answers
2 votes
63 views
Finding a solution to matrix equation occurring inside an optimization problem
Accepted answer
2 votes

The answer to your question is yes! You can do this with the help of the Kroecker product, see http://en.wikipedia.org/wiki/Vectorization_(mathematics). Your equality has the form $$ P A R + S A = Q, ...

View answer
1 answers
1 votes
101 views
Optimization problems on the circle
2 votes

"I am wondering if for $\lambda$ sufficiently large the optimal solution of the second problem approximates arbitrarily close the optimal solution of the first one." In general, the answer is no. ...

View answer
2 answers
1 votes
2k views
Optimization problem: Maximize the sum of minimum.
2 votes

If $c$ is an integer, it is worth noting that full search is maybe the fastest way to solve your problem. Trying out all possible values $c=1,\dots,4L$ is not critical in your case as the problem is ...

View answer
1 answers
1 votes
179 views
Optimization of a convex target function with inequality constraints
Accepted answer
2 votes

there is a solution to your problem: Use the cvx interface for convex programming together with Matlab, see http://cvxr.com/cvx/. You have to download some software and read the user's guide. It's ...

View answer
1 answers
1 votes
311 views
May I know that there is a special structure or solution on this linear fractional optimization?
Accepted answer
2 votes

The solution $\mathbf{x}^\star$ to your optimization problem is given by $0 < x_j^\star \leq c $ for $j = \arg \max_i \frac{a_i}{b_i}$, $x_i^\star = 0$ for $i\neq j$. How can we proof this? ...

View answer
2 answers
4 votes
2k views
How to maximize an entropy function?
2 votes

There is a quick solution to your problem. If you use cvx, you can directly apply the entropy function to formulate your target function $\sum_{i,k}-p_{k,i}*\log{p_{k,i}}$ as sum(entr( p )), where p ...

View answer
2 answers
4 votes
2k views
Regularization versus inequality constraint
Accepted answer
1 votes

Let us consider equivalence of both problems in the sense that the minimum values are achieved with the same variable vector i.e. both problems have the same minimizer. It is hard to determine the ...

View answer
1 answers
2 votes
101 views
Find the Dual of a Primal Linear Programming Problem
Accepted answer
1 votes

Let me help you with your problem for the case that $|\cdot|$ is the Euclidean norm. Regarding $ g(u,v)=g(v)=\inf_{z,x} L(z,v),$ we have to minimize $\lVert z\rVert+ v^T (z+b-Ax)$ with respect to $...

View answer
2 answers
1 votes
369 views
Solve KKT conditions of the following problem
Accepted answer
1 votes

It may be hard to find the values for $x,y,z,$ and $\lambda$ analytically. To my best knowledge, this is generally not possible for optimization problems with quadratic cost functions with a quadratic ...

View answer
2 answers
1 votes
113 views
How reliable is the linear problems like $ \min \|Ax - b\|^2$?
1 votes

Your problem has been discussed in the book "Matrix Computations" by Golub and van Loan (http://web.mit.edu/ehliu/Public/sclark/Golub%20G.H.,%20Van%20Loan%20C.F.-%20Matrix%20Computations.pdf). Let ...

View answer
1 answers
2 votes
260 views
Minimize Energy using Gauss-Seidel method with successive over- relaxation.
1 votes

Lets get this done. First, to simplify the probem, let me introduce the following vector notations. I will assume that we have to find $n$ vectors $\mathbf N_i, i = 1,\dots, n.$ We stack all the $\...

View answer
1 answers
2 votes
46 views
Where can I find an algorithm to compute $\min_{x \in \Delta_n} \langle g , x - y \rangle_1 + c\lvert x - y\rvert_1^2$?
Accepted answer
1 votes

Assuming that $c \geq 0$, you can reformulate your problem as a convex optimization problem, introducing a dummy variable $t$. It is equivalent to $$\min_{x \in \Delta_n,t \in \mathbb{R}} \langle g , ...

View answer
2 answers
0 votes
200 views
How to solve the function $\max \sum_{i=1}^n \log(x_i \cdot \mu)$ with $\sum _{j=1}^b \mu_j = 1$
1 votes

There is a closed form solution for your problem under the following assumption: $x_i > 0, \mu_i > 0 $, for all $i$. You can rewrite $\sum_{i=1}^N \log(x_i \mu_i) = \log(\prod_{i=1}^N x_i \mu_i)...

View answer
2 answers
5 votes
132 views
When is $\min_{x\in X,y\in Y}f(x,y)=\min_{x\in X}(\min_{y\in Y}f(x,y))$?
1 votes

This equation is always true. You proof this by contradiction: 1) It is clear that $$\min_{x\in X,y\in Y}f(x,y)>\min_{x\in X}(\min_{y\in Y}f(x,y))$$ cannot hold true. 2) Let us assume $$\min_{x\...

View answer
1 answers
0 votes
79 views
Quadratic Problem with 2 constraints
Accepted answer
1 votes

The stated problem is finding the minimum norm point in an underdetermined set of equations, see http://www.math.usm.edu/lambers/mat419/lecture15.pdf This problem is a special case of the least ...

View answer
2 answers
1 votes
351 views
On a constrained trace minimisation problem
1 votes

I have devided my answer in two parts. First I introduce the formulation. Second, I consider the optimization. 1) Formulation: For simplicity let me rewrite your problem in vector form and formulate ...

View answer
1 answers
0 votes
36 views
Can one determine optimal parameters of a matrix to design the matrix kernel? (with specific example)
Accepted answer
1 votes

Let me summarize your problem: You want to design $A=\text{diag}(\{a_i\}_{i=1}^n)$ and find $\lambda$ such that $(AB-I)\lambda = 0$ and $|\lambda_i| = 1 \forall i\in \{1,...,n\}$. It is clear that $\...

View answer
2 answers
2 votes
152 views
Solving programmatically a least squares problem with one constrain
1 votes

There is a solution to your problem: http://inst.eecs.berkeley.edu/~ee127a/book/login/l_ols_variants.html To bring your problem to the form they are using, replace $Dy$ by some vector.

View answer
2 answers
2 votes
1k views
How to verify whether a solution to an optimization problem is correct.
1 votes

The difficulty to determine wheather some point $x^\ast$ is optimal depends on the structure of the optimization problem. Non-convex optimization problems: Generally, for non-convex problems, proving ...

View answer
1 answers
2 votes
179 views
Software to optimize a quadratic program with quadratic constraints
1 votes

As $A$ is not positive semidefinite and you have (convex) linear equality and inequality constraints, your problem seems to be NP-hard. There is unfortunatly no quick and easy way to solve your ...

View answer
1 answers
0 votes
518 views
Homogeneous non-negative least-squares
Accepted answer
1 votes

Following Rahuls comment, let us consider the convex optimization problem \begin{equation} \min_{\mathbf{x}} \|\mathbf{Ax}\|_2 ~~~\text{subject to } \mathbf{x} \geq 0, ~~\mathbf 1^T\mathbf x =\...

View answer
1 answers
0 votes
117 views
Given an SPD matrix, any diagonal submatrix of full rank must be SPD.
0 votes

An $n \times n$ matrix $Q$ is SPD if $x^T Q x> 0$ for every vector $x$. This is also true the vector $x$ contains zeros. Let now $P= Q_{i:j,i:j}$ some submatrix around the matrix diagonal with $i&...

View answer
1 answers
2 votes
55 views
Show root using Banach Fixpoint
0 votes

You have to reformulate the requirement $f(x^\star) = e^{x^\star} -4x^\star = 0$ for a root such that the root $x^\star$ is a fixpoint of a function $g(x)$, that is $g(x^\star) = x^\star $. This is ...

View answer
4 answers
2 votes
212 views
Why do we need approximation methods when we have algorithms to find exact roots?
0 votes

See also the answers to my question: For which applications are iterative methods particularly suitable to solve linear systems of equations?. Reason for iterative methods are Applications with ...

View answer
1 answers
2 votes
80 views
Newton step for ${\min}_{x \in \mathbb{R}^n} \ \sum_{i=1}^n -\ln(1 + \eta_i x_i) \ $ s.t. $A x \leq b$; $-x \leq 0$ to be used in primal-dual
0 votes

My answer maybe off-topic as you ask explicitly for a primal-dual interior point algorithm. If you are open for another solver you could try CVX which should work for your problem: http://cvxr.com/cvx/...

View answer