Tag Info

Hot answers tagged convex-optimization

3

Given that an arbitrary regular curve $\gamma$ can be parametrized by arc length, there's no hope of deducing convexity of the arc length function $$s(t) = \int_{a}^{t} \|\gamma'\|$$ from the shape of the curve. Convexity of the arc length function depends entirely on the parametrization. In particular, convexity of a curve can have no bearing on ...

3

A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.

2

No. For example take n=1, C = [0,1]. Then f(x) = 0 if x<0; f(x) = x for x in [0,1] and f(x) = 1 for x>1. And this function is not convex.

2

This is absolutely the case, and it is straight out of the seminal text, Interior Point Polynomial Algorithms in Convex Programming by Yurii Nesterov and Arkadii Nemirovskii. See Section 2.4.3, "Legendre transformation of a self-concordant logarithmically homogeneous barrier." (Or don't. The book is rather... uh... thick. :-)) I don't think this exact ...

2

The point of lower semicontinuity (or something like it) is that were it to fail, there's no guarantee that $f(x^\ast)$ has the right value. For example think about what goes wrong in the following: consider $X=[-2,2]$ and the function $f$ which takes $x$ to $-x$ for $x<0$ and takes $x$ to $x+1$ to $x\geq 0$. Take a minimizing sequence $x_n\in[-2,2]$ ...

2

This is just the soft thresholding operation. The subgradient of $|w|$, where $w$ is a scalar, is $$\partial |w| \triangleq \begin{cases}\{1\} & w > 0 \\ [-1,1] & w = 0 \\ \{-1\} & w < 0 \end{cases}$$ Therefore, to minimize $|x+y|$, we need to choose the value of $x$ closest to $-y$, but not exceeding $1$: ...

2

The answer is no. The reason for that is that the matrix $J^HJ$ is not the Hessian, but an approximation of it. Look at the following one-dimensional example: given constant $y$, solve $\min f(x)$ where $$f(x)=\left\|\left[\matrix{y_1\\y_2}\right]-\left[\matrix{\cos(x)\\ \sin(x)}\right]\right\|^2.$$ Here $$J=\left[\matrix{\sin(x)\\ -\cos(x)}\right],\qquad ... 2 It is not a convex set. I have the following counterexample for n=2 (calculated by hand, so it might be wrong): Take a=(\ln(\frac{1}{4}),\ln(\frac{2}{5})),b=(\ln(\frac{2}{5}), \ln(\frac{1}{4})). This gives us \frac{1}{2}(a+b) = (\frac{1}{2}\ln(\frac{1}{10}),\frac{1}{2}\ln(\frac{1}{10})) We have a,b \in S but \frac{1}{2}(a+b) \notin S 2 The go-to method for attacking your problem is the ADMM (Alternating Directions Method of Multipliers). Your can learn ADMM here. For a more in-dept theory, see Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55 (1992) Glowinski, R., Marroco, ... 2 It seems that you can. Take \|\cdot\| to be the 1-norm, A = I, and c = (1,\dots,1)^T. In particular, we have$$ x \in \Bbb R^n_+ \iff |x_1| + \cdots + |x_n| \leq x_1 + \cdots + x_n $$1 Let t \in [0, 1]. We can construct a sequence of intervals such that t is the only point in their intersection. C_0 = [0, 1], t \in X_0 Let X_{i} = [a, b]. If t \in [a, \frac{a+b}{2}], then X_{i+1} = [a, \frac{a+b}{2}] If t \in (\frac{a+b}{2}, b], then X_{i+1} = [\frac{a+b}{2}, b] Obviously, it is a sequence of nested intervals, ... 1 Since you seem to be unclear about the f part of the energy / cost-function, I'll ignore it (f \equiv 0) in what follows. Also, since I imagine you're going to implement this on an actual computer, let's forget the integral, etc., and consider the discretization. The TV semi-norm can then be written as \begin{eqnarray} \begin{split} TV(x) &:= ... 1 (Because the question changed ( \frac{e^x}{1-e^x} became \frac{e^x}{1+e^x}), i decided to write another answer) It is still not convex. Your calculations for n=2 are correct, but e.g. for n=3 it is not correct, here is another counterexample (again, calculated by hand): Take a=(\ln(\frac{1}{2}),\ln(\frac{1}{5}),0),b=(\ln(\frac{1}{5}), ... 1 This should help. It is always a good idea to plot. Note : 1-dimensional convex sets are subsets of lines. You don't expect something having to do with exponentials to be a line segment (a priori it could have been, but your first guess should be no). 1 If h\colon \Bbb R^k \to \Bbb R and g\colon \Bbb R^n \to \Bbb R^k, then their composition is given by$$f(x)=h(g(x)) \qquad \qquad \operatorname{dom}(f)=\{x\in\operatorname{dom}(g)\mid g(x)\in \operatorname{dom}(h)\}.$$We denote by \tilde h the extended-value extension of h, which assigns the value \infty (-\infty) to points not in ... 1 By relaxation the feasible set stays equal or becomes larger. Thus, the global minimum might decrease (depending on the objective function). However, since you have a non convex problem, gradient projection method computes a stationary point, a local minimum at best. So it may give you the same, a larger, or a smaller value. You can't really predict what ... 1 Short answer: No. I general, you wouldn't expect the subgradient to vanish in the neighborhood of a minimum point x^*. All you can say is 0∈∂f(x^*). Indeed, consider the abolute-value function f:x↦|x|. A simple calculation reveals that ∂f(x)=sign(x) if x≠0 and ∂f(0)=[−1,1]. Also, we know (from purely algebraic considerations) that f attains a global ... 1 Checkout my answer to a similar question. It explains what prox operators are, and how they're used in modern convex optimization. It also gives useful references for further reading on the subject. If you still have questions, then we can look at those. 1 Consider f(x) = \frac12 x^2 for x\in\mathbb R, q=0, p=1, w = -1. Then, we have (w-q)(w-p) = -1(-2) = 2 \ge 0 and f'(1)(-2) = -2 < 0. 1 With the Lagrangian$$ L(x,\lambda) = -c^Tx + \lambda \frac12 (x^TQx -1) $$one finds the KKT conditions$$ -c + \lambda Qx = 0, \ \lambda\ge0 , \ \lambda(x^TQx -1)=0, \ x^TQx\le 1. $$If x^TQx<1 then \lambda=0, and necessarily c=0. Hence \lambda>0, x^TQx=1,$$ x = \frac1\lambda Q^{-1}c, \ x^TQx = \frac1{\lambda^2}c^TQ^{-1}c = 1, $$this ... 1 I'm going to assume that we may consider matrix norms. Then in fact, the answer is precisely analogous to the answer given for \mathbb{R}^n_+ in your other question. Let \|X\|_* be the nuclear norm of X\in\mathbb{S}^n; that is,$$\|X\|_*=\sum_{i=1}^n \sigma_i(X) = \sum_{i=1}^n|\lambda_i(X)|$$Then we have$$X\in\mathbb{S}^n_+ \quad\Longrightarrow\quad ...

1

For the first equation $(A - xc^t) x = 0$: If $x$ is a solution of that equation, then we have $$Ax = x (c^t x).$$ Apart from the trivial solution $x=0$, $x$ needs to be an eigenvector of $A$ and $c^t x$ the corresponding eigenvalue. Let $v$ be an eigenvector to eigenvalue $\lambda$. Then, we have $$Av = \lambda v = (c^t v) v.$$ So \$x = ...

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