Tag Info

New answers tagged

1

The term "logarithmic convex hull" is in use for this object, because it can be obtained by convexifying the image of a domain under the logarithm map, and then coming back. It comes up in complex analysis in several variables, due to the following fact: a domain $D\subset\mathbb{C}^n$ is a region of convergence of some power series (centered at $0$) if ...


2

You cannot avoid an exponential blow-up in the number of resulting constraints. As an example, let us look at cross-polytope $P_3$ in $\mathbb{R}^n$. It is the convex hull of all vertices obtained by all permutations of $(\pm1,0,\dots,0)$. Hence, it has $2n$ vertices and $2^n$ facets (see https://en.wikipedia.org/wiki/Cross-polytope) and its ...


2

No, I don't think you will find a guaranteed fast algorithm, as the problem appears intractable in general, if I understand the below paper correctly. A quick search led me to, e.g., On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes, by Hans Raj Tiwary


1

Part 1: Note that $\text{prox}_{t(cf)}(x) = \text{ prox } _ { (tc) f}(x)$. Part 2: Let $ g (x) = f ( cx) $. To evaluate $\text{prox}_{tg}(y)$, we must find a minimizer of \begin{equation} f (cx) + (1/2t) \|x - y \|^2. \end{equation} Make the change of variable $ z = cx $. Our optimization problem is equivalent to minimizing \begin{equation} f(z) + (1/2t) ...


1

I am not sure that my answer answers your question. So, pls. be forgiving. I've made up a game: You choose a number between, say, $-4$ and $0$ and then I choose a function among those you listed. Then we plug your number into my function and the result will be my gain (your loss). The figure below depicts the three functions: The thick line shows the ...


2

Let's go for an explicit analytic construction of the set of all the solutions to your problem. Basic notation: $e_K := \text{ column vector of }K\text{ }1'$s. $\langle x, y \rangle$ denotes the inner product between two vectors $x$ and $y$. For example $\langle e_K, x\rangle$ simply amounts to summing the components of $x$. Recall the following ...


0

You are right; the intersection of two closed half-spaces in $\mathbb{R}^3$ does not have any extreme points. Indeed, let $u,v$ be the normal vectors of these halfspaces. Let $w=u\times v$. The vector $w$ is parallel to the boundary of either halfspace. Hence, for any point $p$ in the intersection, the points $p\pm w$ are also there.


0

Suppose $f$ attains its maximum, $M$, at some point $a$. Since $f$ is convex, the set $\{x:f(x)<M\}$ is convex. This set does not contain $a$; therefore it lies in a closed halfplane with $a$ on its boundary. After some further considerations involving convexity of $f$, it follows that either $f\equiv M$, or $a$ is a boundary point of the domain of $f$.


3

Which is easier? Neither. Both of these models can be solved analytically, and in the exact same way. First, let's knock out the easy cases: If any $a_i=0$ for some $i$, then the optimal value of either model is clearly $0$, as demonstrated by selecting setting $x$ to be the $i$th unit vector (the vector with $1$ at position $i$ and zeros everywhere else). ...


3

Theorem: Let $X,Y$ be real linear spaces and $f\colon X\times Y\to [-\infty,+\infty]$ be convex. Then $$ \phi(x)=\inf_{y\in Y}f(x,y) $$ is convex. Proof: Let $E$ be the image of $\text{epi}(f)$ under the projection $(x,y,\alpha)\to (x,\alpha)$. Then by definition of infimum $$ \text{epi}(\phi)=\{(x,\alpha)\in X\times\mathbb{R}\colon \ (x,\beta)\in E,\ ...


1

It is convex! Your first statement that the minimum of convex functions is in general not convex is true, but here you have a lot more structure! In a sense you are projecting onto $x$. In fact, $g$ is also called the inf-projection of $f$. Let $\lambda \in (0,1)$ and $y_1, y_2 \in J$ arbitrary: $$ \begin{aligned} g(\lambda x_1 + (1-\lambda) x_2) &= ...


2

Yes, and here is why. Begin with some standard facts about convex conjugates: Conjugation reverses inequalities: if $f\le g$ then $f^*\ge g^*$. This is immediate from the definition of conjugate function, where the original function appears with the minus sign. The conjugate function is always convex and lower semicontinuous, being the supremum of some ...


1

The simplest way to prove this is to take advantage of the fact that a function is convex if and only if its epigraph is convex. In this case, the epigraph is $$\left\{(x,Y,z)\in\mathbb{R}^n\times\mathbb{R}^{n\times n}\times\mathbb{R}\,|\,Y\succ 0,~x^TY^{-1}x\leq z\right\}$$ But consider this linear matrix inequality: $$\begin{bmatrix} Y & x \\ x^T & ...


2

The proximal operator for $\|CX\|_1$ does not admit an analytic solution. Therefore, to compute the proximal operator, you're going to have to solve a non-trivial convex optimization problem. So why do that? Why not apply a more general convex optimization approach to the overall problem. This problem is LP-representable, since $$\|CX\|_1 = \max_j \sum_i ...


2

Are you leaving out some assumptions? What if $n=1$ and $Y$ is negative? EDIT: With the new assumptions, we may consider a line segment through $(x,Y)$ space: $x = x_0 + t x_1$, $Y = Y_0 + t Y_1$, where $Y_0$ is positive definite and $Y_1$ is symmetric. It is enough to show that $\left.\dfrac{d^2}{dt^2} (x' Y^{-1} x)\right|_{t=0} \ge 0$. Now if $Z = ...


1

It's actually easy. Let's do it from first principles. First observe that \begin{eqnarray} \underset{\mu \ge 0}{\text{sup }}\mu^T(g(x)-u) = \begin{cases}0, &\mbox{ if }g(x) \le u,\\+\infty, &\mbox{ otherwise.}\end{cases} \end{eqnarray} Now, \begin{eqnarray} \begin{split} \text{LHS of 1.47} &= \underset{u \in \mathbb{R}^r}{\text{inf }}p(u) + P(u) ...


2

Lemma: If $B$ is positive semidefinite then $$ \max_{\|y\|_\infty\le 1,\|z\|_\infty\le 1}y^TBz=\max_{\|z\|_\infty\le 1}z^TBz. $$ Proof: $\fbox{$\le$}$ Since $(y-z)^TB(y-z)\ge 0$ we have for $\|y\|_\infty\le 1$ and $\|z\|_\infty\le 1$ $$ 2y^TBz\le y^TBy+z^TBz\le 2\max_{\|z\|_\infty\le 1}z^TBz\quad \Rightarrow\quad y^TBz\le \max_{\|z\|_\infty\le ...


0

There has in fact been some controversy over the usefulness of invex functions at all. This article is interesting A critical view on invexity As far as I can tell, the criticism is justified and the definition is vacuous. Please can someone prove me wrong by providing a concrete example of a novel, interesting theorem which cannot be easily proven without ...


1

It's good you're learning Fenchel-Rockefellar duality by doing-it-yourself. Question: Does my whole derivation make sense ? Answer: Yes! Qestion: Is the way to form the conjugate function in the second step correct? Answer: Almost there... Indeed, let me recover your results from first principles (without assuming any knowledge of the concept of "dual", ...


0

There are many (but of course closely related!) notions of "duality". By far the most powerful is the Fenchel-Rockafellar. This this 'technology', you can convert rather complicated problems into dual form in just one line of calculation. It some cases, the problem so-obtained is much easier to attack than the original. To get the ball rolling, start with ...


1

As you say, it is a nonlinear program, so you simply use a nonlinear solver. Here is an implementation in YALMIP (disclaimer: developed by me) which is a modelling toolbox in MATLAB. It interfaces various solvers, such as the nonlinear solvers fmincon, ipopt, snopt. Trial data n = 100; alpha = -rand(n,1); g = rand(n,1); sigma = rand(1); q = rand(1); gpu ...


1

Turns out I ran into an open problem. Theoretical properties of these kind of schemes are very poorly understood, but seem to be superior in practice, see arxiv.org/pdf/1202.4184.pdf and http://www.optimization-online.org/DB_FILE/2014/12/4679.pdf for instance. Violating independence wrecks a bunch of assumptions needed to prove convergence, although this ...


1

Boyd and Vandenberghe is a good place to start. It makes the discussion of duality about as simple as possible, and it certainly has many good examples. The book is free online.


1

This is what I'm thinking. Ignore your attempt to use Cauchy Schwarz. Your problem looks like this: \begin{array}{ll} \text{minimize} & \left\| (X^TX-\Phi) - (Y^TY-\Theta) \right\|_F \\ \text{subject to} & 0 \preceq \Phi \preceq X^T X \\ & 0 \preceq \Theta \preceq Y^T Y \\ & \Phi,\Theta~\text{diagonal} ...


3

I'll consider only vector spaces over $\mathbb R^n$ if that's OK. Since $A$ is non-singular, $A^{-1}$ exists and is non-singular. So $x = Au + x_c$ is equivalent to $u = A^{-1}(x - x_c)$, and we can rewrite the second definition as follows: $$ E = \{ x \mid \|A^{-1}(x - x_c)\| \leq 1 \}.$$ But $\|A^{-1}(x - x_c)\| = (x - x_c)^T \left(A^{-1}\right)^T ...


1

The condition that $P$ be positive definite, is equivalent to saying that all of it's eigen values are positive. This means, that if you take the eigendecomposition, $P= U^{-1}DU$, where $D$ is a diagonal matrix and $U$ unitary, $D$ will have only positive values. If you think of the unitary $U$ as a combination of rotation and stretching, you see that your ...


-1

If $g(u)$ is convex, then you problem is convex as well: [EDIT by mcg: the linear/affine case is probably the only useful one for which this is convex.] Other cases can be convex as well. There are several simple rules to be used to detect convexity. You may want to take a look to a classic book: http://stanford.edu/~boyd/cvxbook/ The $|\cdot|_1$ is a ...


1

Typically that problem is not solved by optimization in one step. Normally you hold the matrix $\bf B$ constant and then optimize for the $\alpha_j$ given a particular training example $\bf x$, which is a convex problem. Then once you have the activation vector you can optimize for the basis weights $\bf B$, which is normally done using gradient descent over ...


0

I'd say the easiest way to solve this is with a descent method. The partial derivatives are \begin{aligned} \frac{\partial f}{\partial q_i} &= -p^T(C^TQC)^{-1}C^Te_ie_i^TC(C^TQC)^{-1}p+K^TC^Te_ie_i^TCL+MC^Te_ie_i^TCN \\ &= -(e_i^TC(C^TQC)^{-1}p)^2+(e_i^TCK)(e_i^TCL)+(e_i^TCM)(e_i^TCN) \end{aligned} \begin{aligned} \frac{\partial^2 f}{\partial ...


1

The $l-1$ norm is not differentiable, as it involves absolute values. But luckily you can cast the problem as a linear program. Firstly, you can write $$ \begin{array}{ll} \min &\sum t_i\\ s.t.&\\ & t_i \geq |z_i|,\quad i=1,\ldots\\ &z = Ax -b,\\ &t_i\geq 0,\quad i=1,\ldots, \end{array} $$ then you just split the absolute value in two ...


0

The spaces with Fréchet differentiable norm are usually called Fréchet smooth spaces... which of course is just a name. Šmulian gave a useful characterization of this property: it holds if and only if for every unit vector $x$ and every sequence of unit functionals $f_n$ such that $f_n(x)\to 1$, the sequence $\{f_n\}$ is norm-convergent. The stronger ...



Top 50 recent answers are included