# Tag Info

4

Why are these models equivalent? What does it mean for two models to be equivalent? Here's my answer: two models are "equivalent" if the solution to one model readily leads to the solution of the other, and vice versa. Suppose you have a solution to (1) above: that is, you have an $(a,b)$ pair that satisfies $$a^Tx_i+b>0 ~~ \forall i=1,\dots, M, \quad ... 4 A simple example would be f(x) = x, g(x) = -x:$$ (f\Box g) (z) = \inf_{x \in \mathbb R} (f(x) + g(z-x)) = \inf_{x \in \mathbb R} (2x - z) = - \infty \, . $$f(x) = e^x, g(x) = e^{-x} is an example where the infimum is finite:$$ (f\Box g) (z) = \inf_{x \in \mathbb R} (f(x) + g(z-x)) = \inf_{x \in \mathbb R} e^x (1 + e^{-z}) = 0 $$and the infimum ... 3 The function f can be written as \max\{1, x^2\}. Minimising a maximum of two functions is equivalent to minimising an upper bound z to both functions. The modified problem reads: Minimise g(x)+z subject to the additional constraints$$z\ge 1,\quad z\ge x^2.$$3 Just compute the second derivative, we have, by the chain rule$$\def\norm#1{\left|#1\right|} Df(x)h = \frac 1{(1 + \norm{x}^2)^{1/2}} \cdot \def\<#1>{\left<#1\right>}\<x, h> $$Hence,$$ D^2f(x)[h,k] = -\frac 1{(1 + \norm x^2)^{3/2}}\<x,h>\<x,k> + \frac{1}{(1 + \norm x^2)^{1/2}}\<h,k> So, we have \begin{align*} D^2 ... 2 (Note that in the derivation below I make multiple uses of the trace identity \mathop{\textrm{Tr}}(AB)=\mathop{\textrm{Tr}}(BA), which is valid whenever both matrix multiplications AB and BA are well-posed.) Since A is symmetric, we know that it can be diagonalized by a unitary matrix Q: that is,A=Q\Lambda Q^T, \quad Q^TQ=QQ^T=I, \quad ...

2

It helps to look at the Taylor expansions of $f$ and $\tilde{f}$: $$f(z+\Delta z) \approx f(z) + \langle \nabla f(z), \Delta z \rangle + \tfrac{1}{2}\langle \nabla^2 f(z) \Delta z, \Delta z \rangle$$ $$\tilde{f}(y+\Delta y) \approx \tilde{f}(y) + \langle \nabla \tilde{f}(y), \Delta y \rangle + \tfrac{1}{2}\langle \nabla^2 \tilde{f}(y) \Delta y, \Delta y ... 2 One of your conditions is (x-2)^2+(y-3)^2\le 4. This leaves two cases: either (x-2)^2+(y-3)^2=4 or (x-2)^2+(y-3)^2<4. (That is, the point (x,y) is either in the interior or at the boundary of the disc. Treat these separately.) In the first case you have two conditions for two variables. Therefore there is no need to use Lagrange's method. ... 2 Your're almost there... Recall the definition of convex conjugates. Recall that the convex conjugate of a norm \|.\| is the indicator function of the unit ball of the dual norm \|.\|_*. Now, \begin{split} g(\nu) &:= \underset{x}{\inf }L(x,\nu) = \underset{x}{\inf }\|x\| + \nu^T Ax - \nu^T b = \nu^Tb -\underset{x}{\sup }x^T(-A^T\nu) ... 2 There are two relevant geometric observations. Consider the following drawing of a quadrilateral with \theta_1, \theta_2 \geq \frac{\pi}{2}: Then |w_2 - w_1| \leq |z_2 - z_1|. In order to prove it algebraically, we have$$ \left< w_2 - w_1, w_2 - w_1 \right> = \left< (z_1 - w_1) + (z_2 - z_1) + (w_2 - z_2), w_2 - w_1 \right> = \\ ...

2

Actually, the Lagrange multiplier method is used to find critical points, so you can use the same sign for both. The distinction between minima, maxima and saddle points is given by the Hessian matrix.

2

Think of what $S$ represents graphically: the lines of a square with corners at (-1,0), (0,1), (1,0), (0,-1), so you can write $S$ as follows: $$S=\{y= 1-x, 0\le x \le 1,0\le y \le 1 \}\cup\{y= x+1,-1\le x \le 0,0\le y \le 1\}\cup\{y= -1+x,0\le x \le 1,-1\le y \le 0 \}\cup \{ y= -x-1,-1\le x \le 0,-1\le y \le 0 \}$$ Now introduce boolean variables to ...

2

I don´t see from this single constraint, that it is a MILP or can be transformed into one. But you can remove the absolute value signs. Let´s define $x=x^+-x^-$, where $x^+,x^- \geq 0$ Then $|x|=x^++x^-$ Similar transformation for $y$. In total you get $x^++x^- + y^++y^- = 1$ $x^+,x^- , y^+,y^- \geq 0$ This could be a part of the standard form of a ...

2

If you want to find the proximal operator of $\|x\|_{\infty}$, you don't want to compute the subgradient directly. Rather, as the previous answer mentioned, we can use Moreau decomposition: $$v = \textrm{prox}_{f}(v) + \textrm{prox}_{f^*}(v)$$ where $f^*$ is the convex conjugate, given by: $$f^*(x) = \underset{y}{\sup}\;(x^Ty - f(y))$$ In the case of ...

2

I'll just write down the solution and hope that you catch some tricks from the manipulations :) Define $\mathbb{R}^n_+ := \{x \in \mathbb{R}^n | x \ge 0\}$ (the nonnegative $n$th orthant), and $\mathbb{R}^n_- := \{x \in \mathbb{R}^n | x \le 0\}$ (the nonpositive $n$th orthant). From these definitions, it's clear that $-\mathbb{R}^n_+ = \mathbb{R}^n_-$. Now, ...

2

Let $X$ and $Y$ be euclidean spaces (for simplicity of the exposition), $g: X \rightarrow (-\infty, +\infty]$ be convex and $A : Y \rightarrow X$ be affine, say $Ax \equiv Lx + \text{cte}$, where $L : Y \rightarrow X$ is linear. Finally, let $x \in Y$. We'll show that $\partial (g \circ A)(x) \supseteq L^* \partial g(A(x))$. Indeed, let $v \in \partial ... 2 Recall the definition of strict convexity: $$f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda) f(y) \quad \forall x,y\in\mathop{\textrm{dom}}(f), ~ x\neq y, ~\lambda\in(0,1)$$ The strictly convex functions$f(x)=e^x$and$f(x)=x^2$have exactly zero and one minimizers, respectively. Now suppose we claim that a strictly convex function$f$has two ... 1 Kuifje is on the right track, but it's not quite there. It's true that$|x|+|y|=1$can be expressed as$|x|+|y|\leq 1$and$|x|+|y|\geq 1$. The first of these is convex so we don't need to do anything special convert it to linear inequalities. There are a variety of ways to do this but let's do it this way: $$x+y\leq 1, \quad -x+y\leq 1, \quad x-y\leq 1, ... 1 Assume that \mathcal{X} is a vector space. Your condition easily implies \nabla f(x^*) = 0 (in \mathcal{X}^*). Indeed, for any x \in \mathcal{X}, you have x + x^* \in \mathcal{X}. Hence,$$\langle \nabla f(x^*), x\rangle = \langle \nabla f(x^*), (x + x^*) - x^* \rangle \ge 0.$$Similarly, you can show$$\langle \nabla f(x^*), -x\rangle \ge 0.$$... 1 In fact, the convex hull \mathrm{conv}\{x_1,\ldots,x_k\} := \{\sum_{1 \le j \le k}t_kx_k | t \in \mathbb{R}^n, t \ge 0, \sum_{1 \le j \le n}t_j = 1\} is compact (in the usual euclidean topology)! Step 1: The simplex \Delta_n := \{t \in \mathbb{R}^k | t \ge 0, \sum_{1 \le j \le k}t_j = 1\} is compact. Indeed it closed, being the intersection of closed ... 1 In general, there is a decomposition of square matrices into a symmetric part and anti-symmetric part:$$A=M+N$$where M is symmetric and N is anti-symmetric. This is a very general result, and this decomposition is in fact a Hilbert space decomposition so that M is the "closest" symmetric matrix to A. It is easy to derive the forms of M,N: ... 1 Steepest descent as is works only for unconditional problems in general. The (minus) gradient direction points at the steepest direction of the function with no respect for the constraints. That's why you come to the boundary, and the algorithm wants to continue further since there are smaller values of the function outside. This point of the boundary is ... 1 Your feeling is right. Try to figure out a counterexample. Think of something simple like one-dimensional parabolic. True, but explanation is unclear to me. How do you know that the KKT is a local minimum? The sufficiency of KKT for convex problems is typically proved via Lagrangian L, which turns out to be convex too, so KKT point is a stationary point ... 1 \sigma_C=\iota_{C^\perp} where C^\perp is the orthogonal of C and \iota_K is the indicator function of K 1 If x \in C^\perp, then x^Tv = 0 for all v \in C and so i_C^*(x) = 0. If x \not \in C^\perp, then x^Tv_0 \not = 0 for some v_0 \in C\setminus\{0\}. Now, it is clear that v \mapsto x^Tv is unbounded on the line L := \{tv_0 | t \in \mathbb{R}\} \subseteq C. Thus i_C^*(x) = +\infty. Putting things together, we have i_C^* = i_{C^\perp}, as ... 1 Here is a pdf of a very good clear book on an introductory level: Operations Research by Wayne L. Winston. Another, more advanced source, would be Chvatal's Linear Programming (Amazon link) 1 Pseudo Code for Steepest Descent using Armijo's Rule: Given x_k, maxiter, other conditions Compute \nabla F(x_k) objold \leftarrow 0 Define \sigma \ \& \beta [between (0,1)] while (iter < maxiter) && (other conditions) flag \leftarrow 0 s_k \leftarrow 1 while flag \neq 1 ... 1 It depends on whether v\ge0 or v<0. First, note$$f^*(v)=\sup_x \langle x,v\rangle -f(x)=\sup_{x>0} \langle x,v\rangle +\ln(x)$$as \langle x,v\rangle -f(x) equals -\infty when x\leq 0. Second, indeed, when v\ge 0, \ln(-1/v) is not defined. But in that case, note, for x>0,$$ \frac{d}{dx}[\langle x,v\rangle+\ln ... 1 let$s_2\in S_2$, we have to show if$x+s_2=s_1\in S_1, y+s_2=s'_1\in S_1$, then$tx+(1-t)y+s_2\in S_1$. We have:$tx+ts_2+(1-t)y+(1-t)s_2=tx+(1-t)y+s_2=ts_1+(1-t)s_1'$.$ts_1+(1-t)s_1'\in S_1$since$S_1\$ is convex

1

Your set equals $$\bigcap_{s\in S_2}(S_1-s)$$ ans is convex as translates and intersections of convex sets are convex.

1