Hot answers tagged

3

Read the last line: (for any choice of $X\succ0,V$) So, somewhere in the lecture notes the author must have assumed that $X$ is positive definite and $V$ is symmetric. Now, when $X$ is positive definite, the usual convention is that $X^{1/2}$ denotes not an arbitrary square root of $X$ but the unique positive definite square root of $X$. Hence $X^{-1/2}...


3

CVX can't solve your problem because it's not a convex optimization problem (because you are maximizing, rather than minimizing, a convex function).


2

This can be done in $O(N log(N))$ time, where $N$ is the number of rows in $A$. The matrix inequality $Ax \leq b$ is equivalent to half-plane inequalities: $(a_i, x) \leq b_i, i = 1, \ldots, N$. We can obtain the vertices of polygon that is the intersection of these half-planes by the following procedure: Transform lines $\{(a_i, x) = b_i\} \mapsto d_i$ ...


2

I think it depends on how you choose $\gamma$. If you choose it using line search, then fine (see this proof), otherwise I think in general, it does not. Consider the case $f(x) = x^2$ with $D = [-1,1]$. Starting from $x_0=1/2$ and using the rule $\gamma = \frac{2}{k+2}$ (fron the wikipedia page you linked), we have: $$ \begin{array}{rcccc} k: & 0 &...


2

A solution to your original problem probably has some components equal to $\pm 1$, but hyperbolic tangent is never equal to $\pm 1$. Thus, the reformulated problem probably has no minimizer. Also, $g $ is probably not convex, so convexity has been lost. You mentioned the projected gradient method. You might also consider FISTA or the TFOCS software package.


2

Boyd uses $\prec$ and $\preceq$ to denote component-wise inequality when comparing vectors ($v \prec w$ denotes $v_i < w_i$ for all $i$), and positive [semi]definiteness when comparing matrices ($A \prec B$ is defined to be $B-A \succ 0$). So everything you've written above are matrix inequalities (statements about positive semidefiniteness). I believe ...


2

Taking the second derivative, we find that $f_n$ (for $n > 0$) is convex when $$ (n-1) t^{2n}-c (n-1)t^n +c^2 n \ge 0$$ The left side is a quadratic $Q(s)$ in $s = t^n$. If $n > 1$, the minimum of the quadratic occurs at $s = c/2$, with $Q(c/2) = (3n+1) c^2/4 > 0$. Thus it is indeed convex. On the other hand, if $0 < n < 1$, the left side ...


2

Hint: as the function is $C^\infty$ you can check if the second derivative is always positive or not. Now, the second derivative is given by $$f_n''(x)=e^{c x^{-n}} n x^{-2-n} (c^2 n-c (-1+n) x^n+(-1+n) x^{2 n}),$$ and as the first terms are positive you only need to check if the expression in the parenthesis is always positive


1

Write $y = 12 - x$. From $x,y \geq 0$, we get $0 \leq x \leq 12$. The objective function becomes $$3 x^2 + 5 (12 - x)^2 = 720 - 2 x^2$$ Hence, the maximum is $720$, which is attained at $(x,y) = (0,12)$.


1

You have not seen many mentions of approach 2 in the literature (in fact, have you seen any ?) because it is rather ad-hoc and unprincipled. Also, the phrase "... We can then use any convex optimization procedure to solve the unconstrained problem ..." makes little sense since $\tanh$ is all but convex... Short and simple, forget approach 2. It's probably ...


1

I think the line "Let $G$ be a function such that ..." should continue with "... $\text{epi} G = \overline{\text{epi} F}$". Take this $G$. Its epigraph is the closure of $\text{epi} F$, i.e. the smallest closed set to contain $\text{epi} F$. Thus there cannot be any l.s.c. function $\bar{F} \leq F$ with $G(v) < \bar{F}(v)$ in some point $v$. Therefore $...


1

A quadratic function of one variable fails to be quasiconcave on an interval if and only if it has an interior minimum point there. It follows that a quadratic form $W$ fails to be quasiconcave on a convex domain $\Omega\subset \mathbb{R}^n$ if and only if there exist $x\in \Omega$ and $h\in \mathbb{R}^n$ such that the first derivative of $W$ in direction $...


1

Let $C = \{(x, t) | z^Tz \le t^2 | t \ge 0\}$ and $K := \{x|x^TPx \le (c^Tx)^2, c^Tx \ge 0\}$. It's straightforward to see that $C$ has the representation $C = \{(z, t) | \|z\|_2 \le t, t \ge 0\} = \text{epi}(\|.\|_2) \cap (\mathbb R^n \times \mathbb R_+)$, and is thus convex. It should be clear that $f$ is affine, and it's a rather straightforward exercise ...


1

If variables $x_i$ are independent, all you need is $f$ to be a strictly increasing function. Generally, for any function $f = g \circ h$, if $g$ is strictly increasing, then $f$ and $h$ have the same variations. In particular, $f$ and $g$ have the same optimums. To understand where this comes from (this is not a proof), consider the mono-variable case. ...


1

We know that a convex function is also quasiconvex and therefore has lower level sets that are convex sets. Thus if $g_i$ is convex then the set of $x$ such that $g_i(x)\leq 0$ is a convex set. The set $\mathcal{C}$ is the intersection of these sets over $i$. Since the intersection of convex sets is convex, $\mathcal{C}$ is convex. See https://en.wikipedia....


1

Assuming that the numbers $w_{ij} $ are not variables, each term in the objective function is a linear function of $M $. That's true even if $w_{ij} < 0$ for some $i,j $. So the objective function is convex.


1

$$\begin{array}{ll} \text{maximize} & x^T A x\\ \text{subject to} & x^T x = 1\end{array}$$ where $A \in \mathbb{R}^{n \times n}$ is symmetric and, thus, has real eigenvalues. We define the Lagrangian $$\mathcal{L} (x,\lambda) := x^T A x - \lambda (x^T x - 1)$$ Taking the partial derivatives of $\mathcal{L}$ and finding where they vanish, $$(A - \...


1

One easy and effective option is to solve this problem using the proximal gradient method or FISTA (which is an accelerated version of the proximal gradient method). The proximal gradient method minimizes $f(x) + g(x) $ where $f $ and $g$ are convex and $f $ is smooth and $g$ is "simple", in the sense that the proximal operator of $g $ can be evaluated ...


1

Consider the problem $\min f(x) + \lambda \| x \|_{q}$ where $\lambda \geq 0$ and $f(x)$ is strictly convex. Also consider the related problem $\min f(x) $ subject to $\| x \|_{q} \leq \delta$. A common technique used in compressive sensing and other regularization schemes is to switch back in forth between these problems. This is most commonly ...


1

The notation is quite fine. Let $X$ be a set and $f:X\rightarrow D$ a function defined on $X$. Then \begin{equation} f(X):=\{f(x)\in D: x\in X\}. \end{equation} To the proof: Suppose $f:D\rightarrow \mathbb{R}$. The epigraph for $f$ is defined as \begin{equation} \operatorname{Epi}(f):=\{(x,a)\in D\times\mathbb{R}: f(x)\leq a\}. \end{equation} Therefore, for ...


1

The $2$ in the subscript means that it's the two-norm or euclidean norm, meaning that if we have, for example, an $x=(x_1,x_2,\ldots,x_n)$, then: $$\| x \|_2^2=\sqrt{\sum^n_{i=1} |x_i|^2}^2$$ The two norm is a special case of the $p$-norm so $\| x\|_p^2$ becomes $$\| x\|_p^2 = \sqrt[p]{\sum_{i=1}^n |x_i|^p }^2.$$


1

This is probably referring to the case $p=2$ of a $p$-norm.


1

$f(x)=x^2$ is convex and $g(x)=\sqrt{x}-x^2$ is decreasing on $[1,\infty)$, but $f(x)+g(x)=\sqrt{x}$, which is concave.


1

Two comments: When you find the KKT point for the Lagrangian minimization - how do you know that it is actually the minimizer? A KKT point is a generalization of a stationary point in unconstrained minimization, and those as we know can be minima, maxima or saddle points. (Hint: the problem is convex). When you are done maximizing the dual function - how ...


1

The property you stated is equivalent to $f$ being strongly monotone and Lipschitz continuous; searching for this combination of terms will bring up a number of papers. It doesn't have a single-word name, since "Lipschitz strongly monotone" is short enough, and self-descriptive. Here's a justification. If $f$ is $L$-Lipschitz and $m$-strongly monotone, ...


1

The cone $C=\{y\colon Ax=y,x\ge 0\}$ is finitely generated (by finitely many columns of $A$) and convex. By Minkowsky-Weyl theorem (en easy proof via Fourier-Motzkin eliminations can be found here, Theorem 1) it is a polyhedral cone, that is, $C=\{y\colon By\le 0\}$. From the last representation it is clear that $C$ is closed as an intersection of closed ...


1

Online optimization usually means that the function evaluations or measurements become available sequentially in time and that the algorithm works with the data as it arrives before all data has been collected. I.e., the data collection and optimization occurs simultaneously. For example, think of optimization occurring in a car engine. The performance is ...


1

The obvious guess is going to be that the optimal solution will take the form $x_1=x_2=\dots=x_N$ for some $N$. Thus, this suggests solving the following optimization problem: $$\begin{align*} \text{maximize } \; &N\\ \text{subject to } \; &N f(x) \le a, N g(x) \le b, Nx \le c \end{align*}$$ where $x$ ranges over $\mathbb{R}$ and $N$ ranges over $\...



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