Tag Info

Hot answers tagged

5

Note that $|\sum_{i=1}^{n}z_iw_i| \leq \sum_{i=1}^{n}|z_iw_i| \leq (max_{i}|z_i|) \sum_{i=1}^{n}|w_i|=(max_{i}|z_i|)$. So you maximum is less than or equal to $(max_{i}|z_i|) $. Now can you find a seq of $w_i$'s which achieve the maximum?


4

I think this plot descripes very well whats's meant here. If you are at the green point, it seems like it gets worse no matter what way you go, however there are better points, like the red point, you just have to pass over a bump.


3

Since you already have linprog, let's start there. Your challenge is to reformulate into an LP that is as compact as possible. Enumerating the vertices as you are doing is not the way to go about it. Instead, you want to define vector variables $p$, $q$, and do this: $$\begin{array}{ll} \text{maximize} & g^T f \\ \text{subject to} & \vec{1}^T f = 1 ...


3

If you fix $\beta$ as a constant, the function is jointly concave in $(\mu, \alpha)$. That is because $\log(\mu + \alpha c)$ is jointly concave in $(\mu, \alpha)$. So you could fix $\delta>0$ and consider $\beta \in \{\delta, 2\delta, 3\delta, \ldots, K\delta\}$ for some value $K>0$. Then for each $k \in \{1, \ldots,K\}$ do: (i) Fix $\beta = ...


3

Do you know Schur's Inequality,i.e. If $x,y,z\geqslant 0$, then $$x(x-y)(x-z)+y(y-x)(y-z)+z(z-x)(z-y)\geqslant 0.$$ Proof: Without loss of generality, we can assume that $x\geqslant y\geqslant z$. Then $$x(x-y)(x-z)+y(y-x)(y-z)\geqslant x(x-y)(x-z)+x(y-x)(y-z)=x(x-y)^2\geqslant 0$$ and $$z(z-x)(z-y)\geqslant ...


2

Yes, this particular function is definitely nonconvex. For me, the dead giveaway is the product $B\alpha_j$, which is itself nonconvex, and the further squaring of these terms in the first summation. (Consider the function $f(x,y)=xy$, for instance, with no sign restrictions on either variable; and then consider $g(x,y)=(1-xy)^2$.) Convexity is the ...


2

I would start from a classic: Bertsekas, Dimitri P., and John N. Tsitsiklis. Parallel and distributed computation: numerical methods. Prentice-Hall, Inc., 1989.


2

Another approach is this: If you assume each index $i \in \{1, \ldots, N\}$ is a node of a connected graph, you can define local variables $y_i$ for each $i \in \{1, \ldots, N\}$, and then enforce the constraint $y_i=y_j$ whenever $i$ and $j$ are neighbors. If you want, you can do the same thing for the $x_i$ variables: Define $x_i^{(k)}$ as the node $i$ ...


2

There is a whole field devoted to this problem. Look up material on semidefinite relaxations, sum-of-squares and moment methods. Papers by Jean Bernard Lasserre, such as "Global optimization with polynomials and the problem of moments" SIAM J. Optimization 11, pp 796--817. " might be a good start. There is software for the problem too, such as the MATLAB ...


2

If you can find closed-form expression to solve your optimization problem go for it! But it is a very rare situation, that's way iterative methods has been developed.


2

Voldemort's answer is right and I've upvoted it... however... This is not actually convex as written. To make it so you must write it this way: $$\begin{array}{ll} \text{maximize} & \sum_i z_i w_i \\ \text{subject to} & \sum_i |w_i| \leq 1 \end{array}$$ Fortunately, you can prove this is equivalent. To see why, suppose that you have found an optimal ...


2

In convex analysis, the convex conjugate of a function $f$ is usually defined to be \begin{equation*} f^*(y) = \sup_x \, \langle y, x \rangle - f(x). \end{equation*} With this definition, $f^*$ is convex because a supremeum of convex functions is convex. (And for each $x$, the function $y \mapsto \langle y, x \rangle - f(x)$ is convex.) The function $U^*$ ...


2

In this case, it's probably easier just to avoid Matrix notation and just consider it a function of $n$ variables. To simplify, let's write $a_i$ rather $a_{ii}$. Also, write $x_{ij}$ for the $i$th component of $x_j$. Then in summation notation, the objective is: $$ \begin{aligned} E &= \sum_j \sum_i (a_{i} x_{ij} - B_i)^2 + \mu \sum_i a_{i}^2\\ ...


2

With a little knowledge about proximal operators, it's easy to see this is equivalent to projection onto the $l_2$ ball, which has a closed form solution. Let $y = x-u$, $w=v-u$, $f(y) = \frac{1}{2C} \|y\|$. Then the problem is equivalent to: $$ \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator{\prox}{prox} x^*-u = y^* = \argmin_y f(y) + ...


1

I do not see an "hideous fourth-order quartic" anywhere. If $$S(x) = \sqrt{h^2+x^2} + \sqrt{(p-x)^2 + q^2}$$ $$S'(x)=\frac{x}{\sqrt{h^2+x^2}}-\frac{p-x}{\sqrt{(p-x)^2+q^2}}$$ So, for $S'(x)=0$,$$\frac{x}{p-x}=\frac{\sqrt{h^2+x^2}}{\sqrt{(p-x)^2+q^2}}$$ Square both sides, reduce to same denominator, expand and simplify; you should arrive to $$-h^2 p^2+2 h^2 p ...


1

Regarding your general question: it's entirely reasonable to minimize convex functions involving the sum of the root of the sum of squares :-) It is convex, but as you rightly point out, it's often not differentiable. Don't get hung up on the need for an analytic solution. Within the set of useful, practical optimization problems, the subset that admit ...


1

The Frobenius norm gives a trace of the product of matrices. You can then use the chain rule and the following formula: $$ \frac{\partial{\mathrm{tr}(BD)}}{\partial{B}} = D $$


1

Taiben is on the right track. You will also benefit from two additional facts: $\|X\|_F^2=\langle X, X\rangle = \mathop{\textrm{Tr}} X^TX$ and $\mathop{\textrm{Tr}} AB=\mathop{\textrm{Tr}} BA$ whenever both products are well-posed. One trick I use in many cases a variational approach. I replace the variable, in this case $B$, with $B+\delta B$. Then I ...


1

I believe the problem is with the naming convection which has not been made concrete over the years. Most authors (and readers) seem not to highlight on the distinction between a "convex function" and a "convex problem". A more appealing distinct convention is as follows: A function f need not be defined over a convex domain for f to be called a convex ...


1

Given an arbitrary line $L = \{ x_0 + tv \in R^n \ | \ t \in R \}$, we know that the set $C = \{ x \in R^n \ | \ x^TAx + b^Tx + c \le 0 \}$ is convex if and only if the intersection with this line is convex. For convexity, we want to prove that $L$ intersects $C$ as a continuous line segment where $t$ is continuous in a bounded range (e.g, stretching $v$ in ...


1

I find it easier to first work with $f(x) = \log \phi(x)$. This gives ${\partial f(x) \over \partial x} = {1 \over \phi(x)} {\partial \phi(x) \over \partial x} $, and continuing, we get ${\partial^2 f(x) \over \partial x^2} = {1 \over \phi(x)^2}\left( \phi(x) {\partial^2 \phi(x) \over \partial x^2} - {\partial \phi(x) \over \partial x}^T {\partial \phi(x) ...


1

$$f(D)=\mathop{\textrm{Tr}}(DD^TF)=\mathop{\textrm{Tr}}(D^TFD)=\sum_{i=1}^n d_i^TFd_i.$$ Each term in the summation a simple quadratic form with $F$ as the quadratic coefficient matrix. So $f$ is convex if $F$ is positive semidefinite. There are a couple of ways to see this. One is to define $g(v)=v^TFv$, so that $f(D)=\sum_i g(d_i)$. Because $f$ is ...


1

To answer this, you must write down the optimality condition, given an optimization problem as: $\mathbf{x^*}= \operatorname{argmin}_{\mathbf{x} \in \mathcal{K}} f(\mathbf{x}) $ The optimality condition asserts that for all $\mathbf{x} \in \mathcal{K}$ $\nabla f(\mathbf{x}^*)^\top(\mathbf{x}-\mathbf{x^*}) \ge 0 $ Writing this condition for the optimal ...


1

I was a bit too pessimistic in my comment regarding the relaxation. If the second constraint is tight at optimality, the two models are equivalent. Solve the relaxation, and if the original constraints are satisfied, the original problem has been solved. Hence, in some cases, the problem can be solved somewhat easily as it is a convex quadratically ...


1

This is not, actually, a linear program, because you haven't specified S in LP form (and you haven't even said that it is polyhedral). It's convex though. First, some preparation: let's define $x\triangleq (x_0,\bar{x})$, where $\bar{x}=(x_1,x_2,\dots,x_N)$, and let $I_\mathcal{S}$ be the indicator function for $\mathcal{S}$. That is: ...


1

I think you are right. Here it is my explanation. Both objective function and constraints are separable and thus you can just think in terms of a single pair $x,z\in R$. Given that, $D(x,z)$ is strictly convex and we have that $$D'(x,z) = log(x)-log(z)$$ and therefore it attains its minimum for $x=z$. It follows that either $z\in [0,1]$ and thus ...


1

I'll assume $f$ is convex. (I should probably also assume $f$ is closed and proper.) As you said, the Lagrangian is $L(x,y) = f(x) + \langle y, Ax - b \rangle$. The dual function is \begin{align*} g(y) &= \inf_x \, L(x,y) \\ &= \inf_x \, f(x) - \langle -A^Ty, x \rangle - \langle y, b \rangle \\ &= - \sup_x \, \langle -A^Ty, x \rangle - f(x) + ...


1

If $P$ is bounded the solution must be achieved on the boundary. The solution exists because $P$ is compact and $c^Tx$ is continuous. The solution must be on the boundary because of linearity of $c^TX$. This is trivial. Let me skip the proof. If $P$ is unbounded and exists such $x\in P $ such that $c^Tx < 0$ and $kx\in P$ for all $k>1$ then of course ...


1

You can use this nice result for the differential of the trace $$ \eqalign { d\,\mathrm{tr}(f(A)) &= f'(A^T):dA \cr } $$ to write $$ \eqalign { d\,\mathrm{tr}((x^Tx)^{\frac {1} {2}}) &= \frac {1} {2} (x^Tx)^{-\frac {1} {2}}:d(x^Tx) \cr &= \frac {1} {2} (x^Tx)^{-\frac {1} {2}}:(dx^T x + x^T dx) \cr &= x(x^Tx)^{-\frac {1} {2}}: dx ...


1

Your $y$ term is a big problem for parallelizing your problem, since it makes every $x_i$ affect every $f_i$. You will need all-to-all communication regarding $h(\vec{x}) = \sum_{i=1}^{N}\!\frac{\partial f_i(x_i,y)}{\partial y}$ at the current value of $\vec{x}$. Then you can use $g_i(x,\cdot) = x \left( h(\vec x) - \frac{\partial f_i(x_i,y)}{\partial y} ...



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