Tag Info

Hot answers tagged

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 ...


4

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


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$$


2

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

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.


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.


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 ...


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 ...


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


2

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 ...


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 ...


1

No, there is no way to do this (even if $P$ is invertible), except in some special cases. If we could, it would make it easy to derive very effective methods for a lot of important convex optimization problems. One special case where we can do this is when the matrix $P$ is orthogonal. To evaluate \begin{equation*} \arg \min_x f(Px) + \frac12 \|x - ...


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

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 ...


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

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 > ...


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 ...



Only top voted, non community-wiki answers of a minimum length are eligible