# Tag Info

## New answers tagged convex-optimization

1

Hint for the case $x=1$: $\displaystyle g(z) = \frac{f(z)-f(0)}{z-0}$. What is that the slope of?

1

Hint: As $f$ is concave and differentiable, it should lie below all its tangents, that is: $$f(b)\leq f(a)+f'(a)(b-a)$$ for all $a,b \in[0,1)$. On the other hand, for $g$ (easily seen to be differentiable on $(0,1)$) we have: $$g'(z) = \frac{zxf'(zx)-f(zx)}{z^2}$$ which can be proven (using above observation and $f(0)=0$) to be less than or equal to ...

0

To complete your attempted proof, you just need to apply the Cauchy-Schwartz inequality. Recall that for any vectors $u,v$, we have $|u' v|^2 \le \|u\|_2^2 \|v\|_2^2$. Taking the square root implies $-\|u\|_2 \|v\|_2 \le u'v \le \|u\|_2 \|v\|_2$. In particular: $$u'v \ge -\|u\|_2 \|v\|_2$$ Applying this to your equation with $u=\nabla f(x)$ and $v= y-x$, ...

0

How about this approach? I use @davcha 's idea to convert the matrix to vector m. so we have the following unconstrained optimization problem: $\min_{m} \|b+V\ m\|_2$ where V denotes $(v^{T}*A)$. Now by decomposing matrix $V=\tilde{V}\ T$, where $\tilde{V}^{T}\tilde{V}=I$, leads to $\min_{m} \|b+\tilde{V}\ \tilde{m}\|_2$ where $\tilde{m}=T\ m$. So ...

3

We want to minimize $\|Ma-b\|_2^2 = \displaystyle\sum_{i = 1}^{n}\left[\sum_{j = 1}^{n}(m_{ij}a_j) - b_i \right]^2$ subject to the constraint $\|M\|_{\infty} \le 1$, i.e. $\displaystyle\sum_{j = 1}^{n}|m_{ij}| \le 1$ for all $i$. Let $k = \text{argmax}_{1 \le j \le n}|a_j|$. Split the minimization problem into $n$ problems (one for each $i$). If $|b_i| ... 1 You have $$f(y) \geq f(x) + \nabla f(x)'(y-x) + \frac{m}{2} \| y-x \|^2_2, \: \forall x,y \in S.$$ In particular, for$x=x^*,$it is $$f(y) \geq f(x^*) + \nabla f(x^*)'(y-x^*) + \frac{m}{2} \| y-x^* \|^2_2, \: \forall y \in S.$$ Since$x^*$is a global minimum of$f$it is$\nabla f(x^*)=0.$That ... 1 Definition : A set$C ⊆ \mathbb R^n$n is affine if the line through any two distinct points in$C$lies in$C$, i.e., if for any$x_1$,$x_2 ∈ C$and$θ ∈ \mathbb R$, we have$θx_1 +(1−θ)x_2 ∈ C$This is the definition given in the book of S. Boyd and L. Vandenberghe, the answer of your question is as @Nameless clarified before. all vector spaces ... 2 This$\theta$is the maximum of$2n$numbers hence finite. By convexity, for every$i$, $$(f(x^*+\delta'e_i)-f(x^*))+(f(x^*-\delta'e_i)-f(x^*))\geqslant0,$$ hence$f(x^*+\delta'e_i)-f(x^*)\geqslant0$or$f(x^*-\delta'e_i)-f(x^*)\geqslant0$, in particular, $$\max(f(x^*+\delta'e_i)-f(x^*),f(x^*-\delta'e_i)-f(x^*))\geqslant0.$$ Thus$\theta\geqslant0$. 0 That's one of the reasons that the gradient decent is not the best method. This issue is resoved by the Newton method. Let$H_k(x)=\nabla^2f_k(x)$be the Hessian of$f_k(x)$, then by the Newton method your updates will be: $$x_{t+1}=x_t-\lambda H_k(x_t)^{-1}\nabla f_k(x_t)$$ Now for example, if$f_k(x)=kf(x)$, then$\nabla f_k(x)=k\nabla f(x)$, and ... 1 You should see the optimization algorithm as a black box that gives you the optimal solution for a fixed objective. If the solving time of the optimization algorithm is slower than the change-rate of the objective function (for example in a real-time application) -- This issue usually happens with non-convex optimization problems that are usually NP-hard ... 2 If$u, v \in U$, then$c_1u+ c_2v \in U$where$c_1,c_2 \in \Bbb R$. This is by the closure of subspace. Thus if we replace them with familiar constants this is simply,$c_1u+ (1-c_1)v \in U$where we have chosen$c_2 = 1 - c_2.$1 If your step size$\lambda$is small enough, then when you update $$x_{t+1} = x_t - \lambda \nabla f_k(x)$$ you can ensure that$f_k(x_t) \geq f_k(x_{t+1})$. At least for the function you performed a gradient descent step on. So, if$\lambda$is small enough for$f_1$, maybe it's not small enough for$f_2$. The normalization you're talking about is ... 0 If performance is not a big concern, just cast your problem in this form:$ min_q \sum_{i=1}^n t_i\\ \quad t\geq ||A_i q - b_i||_2,\quad i=i,\ldots,n\\ \quad q_j \in [0,1] \quad j=1,\ldots,k$then make one more transformation and cast the problem as$ min_q \sum_{i=1}^n t_i\\ \quad (t, A_i q - b_i) \in Q,\quad i=i,\ldots,n\\ \quad q_j \in [0,1] \quad ...

1

The optimization variable is $y \in \mathbb R^N$. Without a regularization term, the solution to the optimization problem written is the vector that agrees with $x$ except in the $c$th component, which is equal to $a$. You can add a regularization term involving a (discrete) gradient of $y$ as you have mentioned. One popular choice for a regularization ...

0

The constraints aren't sufficient to imply that $(I-X)$ is nonsingular. So the objective isn't continuous on the feasible set, let alone convex. (Maybe there is supposed to be an additional constraint such as being negative semidefinite?) But if you want to form the Lagrangian and differentiate it would be this: $$L(X,\lambda) = a^T (I-X)^{-1}b + ... 2 Technically, D is not the dual of P. P has no constraints, so its true dual is$$\begin{array}{ll} \text{maximize} & p^* \end{array}$$where p^*\triangleq \inf_x f(x)+g(Lx) is a (possibly infinite) constant. That's right: the dual has no variables. Needless to say it's somewhat useless. D is actually the dual of$$\begin{array}{ll} ...

2

The function $f(x,y) = x^2 + y^2$ is convex and especially convex on the line $y = a x$ $f(x,ax) = (1+a^2)x^2$. So what they mean is that $\Rightarrow$ if the function is convex, it is convex on any such line and $\Leftarrow$ if the function is convex on any line, it is convex on the entire domain. They are using the word line here because convexity ...

1

Hint: In $\mathbb R^2$, consider projection onto the two basis vectors $P_1(x_1,x_2)=(x_1,0),P_2(x_1,x_2)=(0,x_2)$, then $P_1/2+P_2/2=I/2$.

1

Hint: consider $$A=\left( \begin{array}{ccc} 1/2 & 1/2 \\ 1/2 & 1/2 \end{array} \right)\\ B=\left( \begin{array}{ccc} 1 & 0 \\ 0 & 0 \end{array} \right)\\ C = 1/2A + 1/2B$$

1

This is the beginning of your problem study. I believe you can finish it using this approach, but there are many cases to study... Please check my algebra. Let the answer include $M$ points such that $1-y_i=\frac{x_i}{\theta}$, $K-M$ points such that to $1-x_i=\frac{y_i}{\theta}$. We will compute the answer for each $M\in\{0,1,\dots,K\}$, then pick $M$ ...

1

If the convex set $C$ is closed, then $C$ is an intersection of half spaces $H_u^c=\{x\mid \langle x,u\rangle\leqslant c\}$ for some family $\mathcal H$ of pairs $(u,c)$ in $\mathbb R^n\times\mathbb R$. For every such pair $(u,c)$ in $\mathcal H$, $\langle X,u\rangle\leqslant c$ almost surely and $\langle E(X\mid \mathcal F_0),u\rangle=E(\langle ... 2 Many iterative methods for solving the$z$problem will actually recover$X$as a natural consequence. For instance, if you were to convert these problems to semidefinite programs and solve them using a symmetric primal-dual method, then both problems are solved simultaneously, and the primal and dual solutions will typically converge to optimality at the ... 1 Here,$\mathbb{S}^n$is a vector space, and we're asked to check that the subset$\mathbb{S}^n_+ \subset \mathbb{S}^n$has some special properties: (1)$\mathbb{S}^n_+$is a cone, that is, for every$\textbf{X} \in \mathbb{S}^n_+ - \{\mathbf{0}\}$, the entire ray with vertex$\bf 0$passing through$\bf X$is also contained in$\mathbb{S}^n_+$. ... 0 Let$\lambda_l^+,\lambda_l^-$for$l=1,\ldots,n$be a feasible solution such that there exists$l$such that$\lambda_l^->0$. Setting $$\lambda_l^+ \leftarrow \lambda_l^ + + \lambda_l^-,\\ \lambda_l^- \leftarrow 0,$$ we obtain a new feasible solution. It is easy to see that the objective function cannot decrease. 1 Hints: For$x,y \in \mathbb{R}^n$, $$\nabla_{x} |x^Ty|= \text{sign}(|x^Ty|)y,\qquad \nabla_{x}\|x\|_2 = \dfrac{ x }{ \|x\|_2 },$$ So $$\nabla_x \left(\dfrac{|x^Ty|}{\|x\|_2\|y\|_2}\right) = \dfrac{\|x\|_2\nabla_{x}|x^Ty|+|x^Ty|\nabla_{x}\|x\|_2}{\|x\|_2^2\|y\|_2}=\ldots$$ 0 Definition : An extreme point$x_e$of a convex set$\mathcal{C}$is a point, belonging to its closure$\overline{\mathcal{C}}$, that is not expressible as a convex combination of points in$\overline{\mathcal{C}}$distinct from$x_e$; i.e, for$x_e\in \overline{\mathcal{C}}$and all$x_1 , x_2 \in \mathcal{C} \setminus \{x_e\}$... 1 For any real-valued function$h$,$\alpha\in[0,1]$and$x,y$in the (convex) domain, let $$D(h,\alpha,x,y)=\alpha h(x)+(1-\alpha)h(y)-h[\alpha x+(1-\alpha)y].$$ Convexity for$h$means$D(h,\alpha,x,y)\geq 0$for all$\alpha,x,y$. For your situation, one sufficient condition for$f-g$to be convex is that $$D(f,\alpha,x,y)\geq D(g,\alpha,x,y)\tag{i}$$ ... 1$f\ge g$is not sufficient: for example, take$f(x)=\sqrt{x^2+1}$and$g(x)=|x|$(with$X=\mathbb R$); for another, take$f(x)=|x|$and$g(x)=\max\ \{0,|x|-1\}$. 1 For the last term, you can use a matrix$M$(dimension$d\times d$) constructed as follows: The principal diagonal of$M$is$(1,1,\ldots,1,0)$($1$everywhere except for the last entry). The entries immediately to the right of the principal diagonal are all$-1$. (There are$d-1$such entries.) The remaining entries are all$0$'s. Then $$... 2 The constraints of optimization problems are typically written as a system of equations and inequalities. In order to ensure that the feasible region is convex, one assumes that the g_i are convex, and the equation constraints are affine linear. That said, linear affine equations always yield a convex feasible set. Nonlinear equations as constraints might ... 1 \textbf{hint}$$ \log(\sigma_j(\textbf{z};\theta)) = \theta_{i}^{T}\textbf{z} -\log\left(C(\textbf{z},\theta)\right) $$where$$ C(\textbf{z},\theta) = \sum_{j=1}^{c}\mathrm{e}^{\theta_{i}^{T}\textbf{z}} $$and$$ \bigtriangledown_{\theta_j}\log\left(C(\textbf{z},\theta)\right) = \dfrac{\bigtriangledown_{\theta_j} ... 1 Edited to add: I guess this answer doesn't really address the OP's question, since it sounds like he wants to write this code from the ground up. First (perhaps this is assumed) you should check that$u_1$and$u_2$are vertices of$P$. (Eg, this can be done by checking that the convex hull of$F\setminus\{u_i\}\$ is different from the convex hull of ...

2

This is an over-kill, but you can use the software Polymake to compute all edges of a polytope, which is given as a convex hull of a finite set.

Top 50 recent answers are included