Tag Info

New answers tagged

2

One option is to check directly that the definition of a convex function is satisfied. It's useful to know that any norm on $\mathbb R^n$ is a convex function. Proof: If $x,y \in \mathbb R^n$ and $0 \leq \theta \leq 1$, then \begin{align*} \| \theta x + (1 - \theta) y \| & \leq \| \theta x \| + \| (1 - \theta) y \| \\ &= \theta \| x \| + (1 - ...


1

It suffices to write $f$ as the pointwise supremum of some family of affine functions, here $f=\sup\{g,h\}$ with $g:x\mapsto x$ and $h:x\mapsto-x$, since every such supremum defines a convex function and every convex function can be written as such a supremum.


1

Here are some useful facts: If $f$ is convex and $T$ is affine, then $g(x) = f(T(x))$ is convex. Any norm is a convex function, including the $\infty$-norm. The function $f(x) = \|x\|^2$ is convex. (Here $\|x\|$ is the $2$-norm of $x$.) If $f$ is convex and $c$ is a real number, then $\{x \mid f(x) \leq c \}$ is a convex set. These facts show that your ...


3

You can rewrite the infinity norm constraints as a set of linear inequalities. $$ \text{max}_i (| (y + Ax)_i |) \leq \beta \ || y ||_{\infty} $$ Therefore, $$ (y + Ax)_i \leq \beta \ || y ||_{\infty} \quad i = 1,\dots,\mathbb{K}.$$ and $$ -(y + Ax)_i \leq \beta \ || y ||_{\infty} \quad i = 1,\dots,\mathbb{K}.$$


1

The $\|.\|_{\infty}$, like any other norm, is a convex function (because of the triangle inequality). The constraint using the infinity norm describes a set of $n$ second-order cones: $$ \|(y + Ax)_i\|_2 \leq \beta \|y\|_{\infty},\ \text{for } i = 1,..,k $$ or $$ \lvert(y + Ax)_i\rvert \leq \beta \|y\|_{\infty},\ \text{for } i = 1,..,k $$ The quadratic ...


1

What a great question! The term "log-log convexity" is indeed used to refer to the property you have described. It pops up in literature on polynomial optimization, and also in a bit of a disguised manner in geometric programming. Let's look at the latter case, because to be honest that's what I'm personally familiar with. Consider an expression of the form ...


0

If you care about the computational complexity of QP, not the absolute runtime for a specific instance of the problem, you might want to take a look at the ellipsoid algorithm.


1

The objective function is a quadratic function of $w$, as can be seen using FOIL. The graph of this quadratic function is a parabola that opens upwards. The maximum value of this quadratic function over $[0,1]$ must occur either at $w = 0$ or $w = 1$. So just check those two possibilities.


3

Since $X,Y \in \mathbb{R}$, we can restate your problem as $$w^* :=\arg \max_{0\leq w\leq 1} (a+bw)^2$$ where $a = X$ and $b = -(X+Y)$. Now, with $f(w) = (a+bw)^2$, we now that this convex parabola has a zero at $-\frac{a}{b}$ (where the minimum is reached). So we want to go the further as possible from the minimum. Therefore we have $$ w^* = 1 \quad \text{ ...


0

Yes this can happen. Let $K_1 = \{(x,y,z) : x^2+y^2\leq z^2 \}$ be the second order cone in $\mathbb{R}^3$, and let $K_2 = \{ t(1,0,-1) : t \geq 0\}$. Then $(0,1,0)$ is not an element of $K_1 + K_2$. But $(0,1,0) = \lim_{t \to \infty} [t(1,0,-1) + (-t,1+1/t,\sqrt{t^2+(1+1/t)^2})]$.


1

Believe me, if it could be relaxed, it would have been. But no, you cannot relax the strict inequality in the first LMI. While there are other formulations of the SDP Farkas Lemma, in all of them one of the inequalities is strict. Note also that strong duality does not always hold for semidefinite programs, either (these facts are, of course, related). For ...


0

I don't think you read the proof right. Not sure how to address your specific question so I'll just explain the proof instead. The first step is to simply show that $(A \cap B)^* \supseteq A^* + B^*$ from first principles. The rest of the proof is to show the reverse inclusion. He shows that $(A^* + B^*)^* \subseteq A^{**} + B^{**}$ by utilizing F2 and ...


2

"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. Consider the problem $$ \min_{x \in \mathbb{R}^2} x^{\top} P x + q^{\top} x ~~~~{\rm s.t.}~~ A x = b, \ x \in X. $$ If $x^\star$ is the solution and ...


1

This is not just strictly convex, it's strongly convex. A strictly convex function has at most one unique minimizer on any open interval. But that does not guarantee that a minimizer exists. For instance, $f(x)=e^x$ is strictly convex, but it does not have a minimizer on any open interval. Strong convexity is a stronger condition; it guarantees the ...


0

The enclosed paper developed a constrained LASSO for portfolio optimisation: Sparse and stable Markowitz portfolios (2009). Proceedings of the National Academy of Science, Vol. 106, No. 30, pages 12267-12272. http://www.pnas.org/content/106/30/12267.full


1

As I understand it, the confusion is that the problem is convex in terms of $x$, but not (understood to be) convex in terms of the step size $\alpha$ (given the statement about not jointly convex). However, when we do a line search, we restrict $f$ to another convex set (the line). This, then, is also a convex problem, for which we find the minimum (to give ...


0

If you solved the dual and have optimal values for the dual variables, then plug those optimal dual values back into the Lagrange equation. Now you have an equation with only x as unknown. Minimize, and you've recovered the value for x.


0

If there were two different minima $x$ and $y$ then $y-x$ is a feasible direction and $c\cdot(y-x) = c\cdot y - c\cdot x = 0$ since the value of $c\cdot x$ is the same in all minima.


0

Take a look at dlib - it has some decent routines for general nonlinear optimization that you might be able to adapt to your problem (though on second glance, I'm not sure it handles integer programs directly). I played with it some a while back but it ended up being faster to write my own system. The best part: it's extremely well documented and written.


3

From a quick look, your problem is LINEAR. This makes a huge difference, since nonlinear mixed integer programming is much more difficult than mixed integer linear programming. If you are a student you can get academic licenses for GUROBI or CPLEX. Those are pretty much the best commercial solvers for MILPs. If you want something open source, you can try ...


0

The class of problems you refer to is called "nonsmooth optimization problems" in the field. Specifically, nonsmoothness refers to the presence of functions for which either the second or the first derivatives do not exist or may not be computable/available. Techniques to solve them vary based on problem class, but there are extensions of first order ...


1

Coordinate-wise equality constraints are trivial. Just fix $x_i=c_i$ and skip that coordinate during the search. More complex equality constraints are likely not possible here. After all, it's unlikely that you will be able to hold all of the other coordinates fixed and maintain feasibility. Coordinate-wise bounds are not difficult to deal with, either. ...


1

The $0$-sublevel set of a function $g$ is the set $\{x: g(x)\le 0\}$. Generally, the $t$-sublevel set of a function $g$ is the set $\{x: g(x)\le t\}$. A function $g$ is called quasiconvex if for every $t$, the set $\{x: g(x)\le t\}$ is convex.


1

Here are some useful facts: Any norm is convex. If $f$ is convex and $T$ is affine then $g(x) = f(T(x))$ is convex. A conic combination of convex functions is convex. A maximum of convex functions is convex. These rules can be used to prove the functions in your question are convex.


1

Hints: 1) Notice that $(1-t)x_{1}+tx_{2}-y=(1-t)(x_{1}-y)+t(x_{2}-y)$ and that norms are convex. 2) $x_{1}^{2}+3x_{2}^{4}-2x_{1}-6x_{2}=(x_{1}-1)^{2}-1+(3x_{2}^{4}-6x_{2})$ is a convex function and $\max\{f(x),0\}=\frac{f(x)+\lvert f(x)\rvert}{2}$.


0

Checking whether second order partial derivative of f(a,b,c,d,e) with respect to 'b' is greater or less than zero at maxima-minima point (By taking the derivative of 'f' over 'b', setting it to zero, I can solve 'b' = 'b0') will help us judge whether function is minimum or maximum at that combination of a,c,d,e. Since you said you are trying to find maximum ...


0

$\newcommand{\prox}{\operatorname{prox}}$ No, there is no closed form solution unless F is semi-orthogonal or orthogonal. The way to solve it is to notice that this problem is actually a generalized Lasso problem. Recall, that the general form of generalized Lasso is: $\min$ $\lambda\|Fx\| + (1/2)\|Ax-b\|^2_2$ We can then introduce a new variable $z$ and ...


0

Consider the cost function $f(x_1,x_2)= x_1^2 + \alpha\cdot x_2^2$, which has minimum at $x_1=x_2=0$. Consider the problem constrained to lie on the line $a\cdot x_1 + b\cdot x_2 + c=0$. The projection of the previous solution onto this line is the closest point to the origin, in the Euclidean sense, and thus minimizes $x_1^2+x_2^2$. This point is fixed by ...


3

Take $f(x) = \|x\|_\infty$ on $\mathbb{R}^2$ and the feasible set $F= \{ \lambda 2 e_1 + (1-\lambda) e_2 \}_\lambda$. Note that $f(\lambda 2 e_1 + (1-\lambda) e_2) = \max(2|\lambda|, |1-\lambda|)$ has a unique minimum at $\lambda= {1 \over 3}$ corresponding to the point ${1 \over 3} (2,2)$, whereas the Euclidean projection of $0$ onto $F$ gives the point ${1 ...


1

It may be the case that your columns aren't normalized. In order for basis pursuit to work, the columns need to all be roughly the same length ($\ell_2$ norm). The columns of the inverse DFT are usually of magnitude $1/\sqrt{n}$, whereas the columns of identity matrix are of unit magnitude. So if $n$ is large, then this could prevent finding the sparse ...


2

Collect the accessory parameters $a$, $c$, $d$, $e$ into a parameter point ${\bf p}:=(a,c,d,e)$. For given ${\bf p}$ we then have to study the function $$f_{{\bf p}}:\quad [0,1]\to{\mathbb R},\qquad b\mapsto f(a,b,c,d,e)$$of the single variable $b$. If this function is continuous on $[0,1]$ and differentiable in the interior of this interval it assumes a ...


0

If your function $f(a,b,c,d,e)$ is continuous, differentiable and has only the point $b=g(a,c,d,e)$ inside [0,1] where the first derivative is zero, then one of the points $b=g(a,c,d,e), b= 0$ or $b=1$ has to be your global maximum. We consider the three different cases: $b=g(a,c,d,e)$ is a maximium, a minimum or a saddle point. Case 1: $b=g(a,c,d,e)$ is ...


1

Q1) Any true norm will do here. The Frobenius norm is a bit easier to work with, because of course the squared norm is easily differentiated. I don't believe the spectral norm is differentiable. Q2) A more general class of functions that can be used instead of the squared norm are Bregman divergences, or Bregman distances. I believe the key properties that ...


0

Question 1: No, if you find $g^*(y)$, all you've done is evaluated $g^*(y)$. You have not yet evaluated the prox operator of $g^*$. If you were able to evaluate the prox operator of $g^*$, then the Moreau decomposition would then allow you to evaluate the prox operator of $g$. Questions 2 and 3: No, I'm pretty sure there is no known analytical expression ...


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


0

Just for completion here is the code I used to implement fabees solution: f = [zeros(d,1); ones(d,1)]; A = [diag(-y)*X zeros(n,d) [eye(d) -eye(d); -eye(d) -eye(d)]]; b = [-ones(n,1); 1*ones(2*d,1)]; p = linprog(f, A, b); w = p(1:length(p)/2);


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


3

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.



Top 50 recent answers are included