9
votes
Accepted
Is a piecewise linear function always a sum of concave and convex functions?
Let me assume that you are talking about a real-valued function $f : [a,b] \to \mathbb{R}$. A characterization of which such functions may be written as $f=g-h$ with $g$ and $h$ convex (so $-h$ ...
- 3,341
9
votes
Accepted
The set of inner products of two convex sets convex?
It is true, and it suffices that $X,Y\subset \mathbb{R}^n$ are connected. (This is more general since all convex sets in $\Bbb R^n$ are connected.)
Then $X \times Y$ is also connected (see e.g. here) ...
- 113k
8
votes
Sum of squared maximization with a norm constraint
In the sequel, we assume that the matrices and vectors are real and the norm is Euclidean. If the field is complex, let $L=A+iB,\,\mathbf x=\mathbf p+i\mathbf q$ and $\mathbf y=\mathbf a+i\mathbf b$. ...
- 139k
7
votes
When do two functions have the same subdifferentials?
You need some extra assumptions on $f$ and $g$. If $f,g \colon X \to \bar{\mathbb R}$ are convex and lower semicontinuous and if $X$ is a Banach space, then $\partial f = \partial g$ imply that $f$ ...
- 31.4k
7
votes
Accepted
Sublinear function $f$ with $f(x)+f(-x)=0$ for some $x \neq 0$ is linear.
This will not hold as it is:
$f$ sublinear and $f(x_0)+f(-x_0)=0$ at some point $x_0 \neq 0$ means that $f$ is linear.
Let $f:\mathbb{R}^2 \rightarrow \mathbb{R}$ defined as $f(x) = |x_1|$. This ...
- 303
5
votes
Accepted
Proving convexity of a bivariate function
The feasible region of all the constraints in the model is the following red-shaded region:
In order for a model to be convex, both the objective function and the feasible region of the model must be ...
- 1,586
5
votes
Accepted
Property of twice of a vector minus its orthogonal projection
For the original (unedited question), let $y = (0,0)$, $y \not\in C$, and use what you've already found to disprove the statement.
If $C$ contains the zero vector (that is, $0\in C$), then by the arg ...
- 98.5k
5
votes
Minimize $\frac{1}{2}\sum_{k=1}^m (x_{k+1}-x_{k})^2$
Not yet the solution, but I found
The closed form expression of $(x_k)_k$
The minimum and the $m$ values of $x$ such that $A$ reaches its minimum
It is not necessary to find the miminum for $\color{...
- 16k
4
votes
Accepted
Why is gradient symmetric at optimal point for convex functions on the positive semidefinite cone?
Let $A= \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ and $f(X) = {1 \over 2} \| X-A\|_F^2$. Then $\nabla f(X) = X-A$.
A straightforward computation shows that $\min_{X \ge 0 } f(X) $ is ...
- 173k
4
votes
Accepted
Directional derivative of proximal mapping of a convex function
You must be careful, in your reference, the directional differentiability of the projection onto $C$ is only established for points $x \in C$. In fact, the projection might fail to be directionally ...
- 31.4k
4
votes
Accepted
When is $\exp(f(x))$ concave?
In general, if $u:[0, 1]\to (-\infty, 0)$ is a continuous function, the function $f$ that fullfils
$$(\exp(f(t)))''=u(t)$$
is concave. We know that such an ODE has a solution, for each $u$, and ...
- 368
4
votes
Accepted
Is this an example of an SOCP optimization problem?
Introduce nonnegative variables $y$ and $z$ to represent the square roots, and impose
\begin{align}
y + z &\le 1 \\
y^2 &\ge \sum_{i=0}^n x_i^2 \\
z^2 &\ge \sum_{i=n+1}^{2n} x_i^2
\end{...
- 45.7k
4
votes
Accepted
Bound $\|\mathbb{E} [ \boldsymbol{H} (x-y)]\|^2$ for $\mu \preccurlyeq \boldsymbol{H} \preccurlyeq L$
Counterexample to stated claim.
Consider the function $f(x) = x \tan^{-1}(x) - (1/2) \log(1+x^2)$, which is convex and has $f''(x) = 1/(1+x^2)$. On any bounded domain $[-M, M]$, then
$$
\frac{1}{1 + M^...
- 3,690
4
votes
Accepted
Tractable formulation of a mixed integer program
You can linearize the problem as follows. Introduce nonnegative decision variables $y_i$ to represent $|c_i A_1 x_i|$, change the objective to minimizing $\sum_i y_i$, let $M_i$ be a small constant ...
- 45.7k
3
votes
Newton's method intuition
Boyd's Convex optimization Chapter 9.5 gives an intuitive way to think about the Newton step in $\mathbb{R}^n$ as the steepest descent direction in the norm of the Hessian.
You can also think of it ...
- 141
3
votes
construction Lyapunov function for global asymptotic stable systems
Let's attempt to find a suitable Lyapunov function in the form:
\begin{equation}
V(x) = ax_1^2 + bx_2^2 + cx_3^2
\end{equation}
Now, calculate the time derivative of V(x) along the trajectories of the ...
- 946
3
votes
Given convexity, $\lim_{\|x\| \xrightarrow{} \infty} f(x) = \infty$ is equivalent to $\liminf_{\|x\|\xrightarrow{} \infty} \frac{f(x)}{\|x\|} > 0$?
Here is a proof of (ii) implies (i).
Take $x_0$ with $f(x_0)<+\infty$. Due to (i), for $M:=f(x_0)+1$ there is $R$ such that $f(x)>M$ for all $x$ with $\|x\|\ge R$.
Fix $x$ with $\|x\|= R$.
Then ...
- 49.2k
3
votes
Accepted
Listing vs. counting perfect matchings in a graph
The complexity of counting and of listing is evaluated differently. An algorithm listing all the possibilities is usually called an enumeration algorithm. (This can be confusing because outside ...
- 143k
3
votes
Find the Minimum of: $\sum_{i=1}^n a_i^2+\sum_{1\leq i<j\leq n}g_{j-i}a_i a_j+\sum_{i=1}^n q_i a_i$
*Please see the discussion under the actual question. There, a closed-form solution for the question without nonnegativity restrictions on the $\{a_i\}$ was asked for, which is given here. *
I would ...
- 15.2k
3
votes
Find the Minimum of: $\sum_{i=1}^n a_i^2+\sum_{1\leq i<j\leq n}g_{j-i}a_i a_j+\sum_{i=1}^n q_i a_i$
Relaxing the condition $a_i \ge 0$ as suggested in the question discussion, with
$$
M = \left(\matrix{
1&g_1&g_2&g_3&\cdots&g_n\\
0&1&g_1&g_2& \cdots&g_{n-1}\\
\...
- 33.4k
3
votes
Least squares with an equality constraint
We can express x as a combination of two matrices:
$$x = q_1 + Q_2 z
$$
where $z$ is a (n-1)-dimensional vector. We can substitute this expression for x into the constraint $q_1^T x = 1$:
$$
q_1^T (...
- 196
3
votes
Optimization problem involving the inverse matrix
Let me expand on my earlier comment and @RodrigodeAzevedo 's reference.
Your original problem is
\begin{align*}
\min_{s_1, \dots, s_\ell, \lambda, \mathbf{K}} & \quad \mathbf{y}^T \mathbf{K}^{-1} \...
- 1,056
3
votes
Accepted
$\forall P \succ 0, \langle X,P \rangle = \langle Y,P \rangle$, implies $X=Y$?
Here is a perspective on this problem that you might find helpful. If we let $M = X - Y$, then the following statements are equivalent:
$$
\forall P \succ 0, \langle X,P\rangle = \langle Y,P\rangle\\
\...
- 226k
3
votes
Accepted
Lower bound on the sum of square roots of probabilities that are upper and lower bounded
If $n$ is even:
From the given condition, we have
$$\sqrt{\frac{1}{n}\left(\frac{1}{n}-\epsilon\right)}\le \sqrt{\frac{p_i}{n}}\le \sqrt{\frac{1}{n}\left(\frac{1}{n}+\epsilon\right)} \hspace{1cm} \...
- 16k
3
votes
Lower bound on the sum of square roots of probabilities that are upper and lower bounded
For odd $n$:
Problem: Let $n\ge 3$ be a fixed odd number. Let $0 < \epsilon\le \frac{1}{n}$ be fixed. Let $p_i\ge 0, i = 1, 2, \cdots, n$
with $\sum_{i=1}^n p_i = 1$ and
$\frac{1}{n} - \epsilon \le ...
- 37.8k
3
votes
Property of twice of a vector minus its orthogonal projection
Let $C=\{-1\}, y = 0$ then $x_* = -1$, but $x_*(2y-x_*) = (-1)(0-(-1)) = -1 < 0$.
- 173k
3
votes
How to solve the primal problem via Lagrangian directly?
This is a counterexample. Set
\begin{align*}
f(x) &:= x^2 \exp(-x^2) - (x-1) \exp(x)\\
g(x) &:= f_1(x) := (x-1) \exp(x).
\end{align*}
For the primal problem, the feasible set is $(-\infty, 1]$ ...
- 31.4k
3
votes
Accepted
ADMM (Alternating direction method of multipliers) for an optimization problem with non-separable term (multiplication of two variables)?
Choose $z = b$ and choose $x$ so that $x + a = -1$. Then the objective function value is $0$, so the optimization problem has been solved.
- 52k
3
votes
Accepted
Finding convex optimization books for beginners.
Perhaps you can try this classic book by Bubeck: https://arxiv.org/abs/1405.4980
- 1,182
3
votes
Accepted
Intuition behind the Euclidean orthogonal projection
If we consider the closed square in $\mathbb{R}^2$ defined by the four corners $(\pm 1, \pm 1)$ and $x_0 = (2,2)$ we see a tangent plane may not be well defined. However the convexity ensure a ...
- 11k
Only top scored, non community-wiki answers of a minimum length are eligible