Tag Info

New answers tagged

1

You can cite a standard nonlinear programming textbook such as Nocedal and Wright, Bertsekas or Bazaraa, Sherali and Shetty. I think all of them have references to the projected gradient method. You should of course go over and make sure you're citing the right section. ps: You might also want to search to see if someone has applied the projected gradient ...


2

If you're willing to use my toolbox CVX, then it's as simple as this: cvx_begin variable w(d) minimize(0.5*norm(w,1)) subject to diag(y) * X * w >= 1; cvx_end But yes, fabee's comment is a valid option as well; he should promote it to an answer so it can be voted up.


1

Do A and B have the same unit, like monetary unit, manpower or volume ? If it is like this, then you can just optimize $f(\vec x)=A(\vec x)+B( \vec x)$.


1

Both your objective functions seem convex in the decision variable. So most problems that arise from multiobjective paradigms should be convex quadratic optimization problem, for which efficient solvers exist. If your problem is in 1 dimension with explicit bounds, you can use simple iterations such as gradient descent or Newton's like littleO mentioned. I ...


2

$\theta f(x,y)+(1-\theta)f(x,y) = (1-\theta+\theta)f(x,y) = f(x,y)$ This is trivial if I understood your question correct.


4

M. Slater, "Lagrange Multipliers Revisited," Cowles Commission Discussion Paper No. 403, November, 1950


0

assuming $P$ to be positive semi-definite, your problem is simply a standard QP with linear constraints. Unless it shows some peculiarities in the linear constraints, the structure of $P$ or a huge dimension, I would just pick up any established QP solver (MOSEK, CPLEX, Gurobi...) or even just quadprog in MATLAB. The papers you refer to deals to some ...


0

Following the above, $f(x_0) \geq \frac{B}{\lambda}$ and $f(x_0) \geq B$. For $\lambda > 0$. If $f(x_0) < 0$, then $\frac{B}{\lambda}$ could be greater than $f(x_0)$ for some $\lambda$, which is a contradiction. Hence, $f(x_0) \geq 0$. For $\lambda \leq 0$. If $f(x_0) \leq 0$, then $\lambda f(x_0) \geq 0 \geq B$ holds. Hence, $f(x_0) \leq 0$. As ...


1

As I said above in my comment, this is not a convex problem; your objective is the difference between two concave functions. However, you might consider a successive convex approximation approach. Here's what I mean. I'm going to assume that $W$ is strictly positive definite. It must be, actually, or else your model is infeasible. First set $X_0=W$, and ...


0

I've tried to recreate the code you were describing and got this below: X = zeros(1,512); positions = randi(512,[1,30]); X(positions) = 1; dctX = dct(X); B = binornd(1,0.5,150,length(X)); y = B*X'; x0 = B'*y; xhat = l1eq_pd(x0, B, [], y, 1e-3); This generates a vector with 30 random spikes, then applies a dct and a random beroulli(0.5) matrix before ...


2

CVX (MATLAB) or CVXPY (Python) would allow you to solve that really easily, as long as your problem isn't too large. The CVX code would be just: cvx_begin variable x(n) minimize( 1/2*quad_form(x,A) + b'*x + lambda*norm(x,1) ) cvx_end


0

What was the issue in the end? I'm having a similar problem. I'm trying to use l1 magic to reconstruct an image from a single pixel camera I've developed. The test functions used are random binary patterns projected onto the object scene, so each pattern is represented as a row vector of 0's and 1's and form the rows of the test function matrix A. (To later ...


4

Oh, absolutely, there are lots of tools. Do a search for proximal gradient methods in your favorite search engine; these are generalizations of projected gradient methods. For specific tools, search for TFOCS (disclosure below), FISTA, NESTA, SPGL1, GPSR, SpaRSA, L1LS... and the bibliographies for these will lead to even more options. Even better, see this ...


1

First we can assume $x_i<0,\forall i$. We can write $f(p) = \frac{1}{N} \sum_i^N ( p^2+\max\{0, -p^2-x_i\} )= \frac{1}{2}\sum_i^n \phi(p)_i,$ Then it is easy to see that $\phi(p)_i = -x_i$ for $p\in [-\sqrt x_i,\sqrt x_i]$, while $\phi(p)_i= p^2 $ otherwise. This is strictly convex. Each $\phi(p)_i$ is known as Huber penalty function (see ...


0

The complex structure does not come into play in optimization problems. As Michael Grant said, we can only minimize real-valued functions. A real-valued function cannot be complex-differentiable unless it is constant. So we must use real-variable notion of derivatives (replacing $z$ with $x+iy$, as copper.hat remarked). At this point, you are just doing ...


0

Let take a simple positive definite matrix A=[1 0 ; 0 1] x=[x1 x2] Now compute the x'Ax =x1*x1+x2*x2; the square term is a convex function and sum of two convex is convex. You can verify by plotting the above function


1

In general I think you can't, this is a typical combinatorial problem. But You can solve it efficiently I guess. Take any direction $m$ and compute $m^T x_i$ for each $x_i \in S$. This induces an ordering along the direction $m$. Then just take the $\alpha|S|-$th point and compute $d$ such that $m^Tx+d=0$. Do the same for the $\alpha|S|+1$ obtaining a ...


1

This is exactly equivalent (in all the respects that matter to us here) to $$\begin{array}{ll}\text{minimize} & x^T P x + p^T x + \alpha \| A x - b \|^2\end{array}$$ Now, this is actually a well-studied approach to solving constrained problems. The term $\|Ax-b\|_2^2$ is a penalty function. I encourage you to do a literature search to learn about the ...


0

Yes, it's true. Plane $\pi_{*}$ is minimizing the following functional: $$ I(a, b, c, d) = \sum \limits_{i = 1}^{n}\frac{(a x_{i} + b y_{i} + c z_{i} + d)^{2}}{a^{2} + b^{2} + c^{2}} \to inf $$ thus $$ \frac{\partial I}{\partial d} = \sum \limits_{i = 1}^{n}\frac{2 (a x_{i} + b y_{i} + c z_{i} + d)}{a^{2} + b^{2} + c^{2}} = \frac{2}{\sqrt{a^{2} + b^{2} + ...


2

No, there is no guarantee that you will converge to $x_1$. This also depends on the choice of your step size. Let us recall that the gradient descent algorithm is defined by $$ \vec x^{k+1} = \vec x^k -\gamma_k \nabla f(\vec x^k)$$ where $\gamma_k$ is the step size. First let us show that if you choose a constant step size then you can always find a counter ...


0

You just need to run a good QP solver on that problem (MOSEK, GUROBI,CPLEX....). If you want, you can transform in conic form: $$ \min t$$ $$ s.t. $$ $$ t\geq ||y||_2 $$ $$ y= Fx $$ $$ x_i\geq 1\quad i=1,\ldots,n$$ where $F$ is a Cholesky factorization of $A$. Then you can restate the first constraint as $(t,f)\in Q$, i.e. they must belong to a ...


1

I think 1) is just a misprint. Indeed, it should read $(f^*, x^*)$. Ad 2): Assume $s = 0$. Then, we have $\lambda^\top \, x \ge c$ for all $x \in E^n$. This yields $\lambda = 0$ which contradicts $(s, \lambda) \ne 0$. Now Assume $s < 0$. But then $s \, r + \lambda^\top \, x \le c$ is violated, since $r$ could be arbitrarily small. This yields $s > ...


2

Unfortunately the set described by your constraint is not convex, which prevents both SDP and SOCP formulations. To see this, you can for example intersect it with hyperplanes x1=1 and x2=2: the resulting set x3*x4 <= 1 is clearly not convex, which implies that the original set was not either. The "det(A)>=0" argument invoked above does not work because ...


0

No slater's condition, KKT is a sufficient condition. With slater's condition, KKT is a necessary and sufficient condition. Reference: page 537 in book: Lectures on Modern Convex Optimization. This is a very good reference book.


3

$$\|\frac{1}{2}(1,0)+\frac{1}{2}(0,1)\|_0=2 > 1=\frac{1}{2}\|(1,0)\|_0+\frac{1}{2}\|(0,1)\|_0$$


0

Here one idea of solution. Any corrections, additional steps, alternative solutions and suggestion are welcome. Admitting that there is a solution for the optimisation problem, fact that still must be proved, we have: $$ \int_0^1 \nu(t)~h(t) ~dt = - \frac{1}{2} \int_0^1\int_0^1 \phi(s,t) ~[\nu(s)~h(t)+\nu(t)~h(s)] ~ds~dt$$ where $\phi$ is symmetric so it ...


1

I would like to clarify my final question as descibed by the discussion with @Joel above (see the comments). Let $\mathbf{w}=(w_1,\ldots,w_n)^T$, $\mathbf{x}_i=(x_{i1},\ldots,x_{in})^T\in\mathbb{R}^n$, $i=1,\ldots,m$, and $A=\big(a_{ij}\big)_{i,j=1}^{n}$ an $n\times n$ symmetric positive definite real matrix. Let's suppose that we would like to minimize ...


2

If the values are sorted $x_1 \le x_2 \ldots \le x_n$, then the value $m^*$ is the unique solution on the interval $[x_{n/2},x_{n/2+1}]$ to the following equation: $$ (m^* - x_1)(m^*-x_2)\ldots(m^*-x_{n/2})=(x_{n/2+1}-m^*)(x_{n/2+2}-m^*)\ldots(x_{n}-m^*). $$ When $n=2$, it's just the mean, and when $n=4$, $m^* = (x_3x_4-x_1x_2)/(x_3+x_4-x_1-x_2)$, which in ...


1

Unfortunately, this approach is not compatible with convex optimization in practice. The reason is that in an optimization context, a convex function and its epigraph are assumed interchangeable. That is to say: consider the following two problems: $$\begin{array}{ll} \text{minimize} & f(x) \end{array}$$ $$\begin{array}{ll} \text{minimize} & y \\ ...


2

To get a true statement, I think we need to add the assumption that $\text{dom} f$ has a non-empty interior. Let $y \in \text{int}(\text{dom} f )$ and suppose (for a contradiction) that $f(x) = -\infty$ for some $x \in \mathbb R^n$. Convexity implies that $f(z) =- \infty$ for all points $z$ between $x$ and $y$. But some of the points between $x$ and $y$ ...


0

The definition is surely explained in the book or lecture note you're reading. A stochastic function is a function from $\Omega$ to a function space. Here is an example : let $X : \Omega \to \mathbb{R}$ be a random variable. Then the following defines a random function : $$ F : \omega \longrightarrow \Big( f_{\omega} : x \to X(\omega) + x \Big)$$ A ...


0

Because it's not differentiable when any row of $W$ is zero. $$\|W\|_{2,1} = \sum_i \left( \sum_j w_{ij}^2 \right)^{1/2}$$ When it is defined, the partial derivative with respect to an individual element of $W$ is $$\frac{\partial}{\partial w_{ij}} \|W\|_{2,1} = w_{ij} \left( \sum_k w_{ik}^2 \right)^{-1/2}$$


2

I would say it is fallacious to say, as you have, that "most optimizer [sic] can perform better if the Hessian is given." Only optimizers designed to accept second-order information would benefit from the computation of a Hessian, assuming one was available. And because such optimizers will typically assume that a function is differentiable, $f$ would not be ...



Top 50 recent answers are included