Tag Info

Hot answers tagged

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


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

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


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


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


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


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


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


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


1

Again, the answer to "how to solve the problem" depends in large part on what $X$ is, what software you intend to use, etc. But as I said in the comment, at least the objective function can be expressed in second-order-cone or semidefinite form. To see how, create new variables $y\in\mathbb{R}^p$ and write the problem as follows: \begin{array}{ll} ...


1

Do you want to do it efficiently or exactly? Technically you have a mixed-integer convex MAXDET problem, so it can be solved using branch-and-bound applied on a convex semidefinite MAXDET problems. This is the model in the MATLAB Toolbox YALMIP (disclaimer, developed by me), which has a rudimentary mixed-integer SDP solver. To solve the relaxations, the ...


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) &= ...


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


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


1

$$\lambda_1(0,0)+\lambda_2(0,4)+\lambda_3(2,4)=(3,1), \text{ given that } \lambda_1+\lambda_2+\lambda_3=1 \text{ and } \lambda_1,\lambda_2,\lambda_3 \in [0,1].$$ $$\implies \big(2\lambda_3,4(\lambda_2+\lambda_3)\big)=(3,1)$$ $$\lambda_3=3/2, \ \lambda_2=-5/4, \ \lambda_1=3/4$$ But this is not the convex combination because it violates the conditions that- ...


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


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

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


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

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

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

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


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


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


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



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