Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (3)

2
votes
1answer
47 views

Why is this matrix symmetric?

There is an example in the Convex Optimization lecture notes, Boyd. He just said in the lecture that the matrix which is underlined in red color is symmetric! How can we claim that when there is no ...
0
votes
0answers
12 views

how to calculate infimum of Augmented Lagrangian?

should any body explain that how do we calculate these step? \begin{align*} L(x,y) &= f(x) + y^T(Ax-b)\\ g(y) &= \inf_x \, L(x,y) \\ &= \inf_x \, f(x) - \langle -A^Ty, x \rangle - \langle ...
0
votes
0answers
6 views

Nesterov's bound between quadratic and strongly convex cases?

Are there some examples of simple & strongly convex functions for which the convergence bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s bound for strongly convex case $\...
2
votes
1answer
28 views

Why isn't $\ell^p$ locally convex for $0<p<1$?

I believe we have to distinguish the finite-dimensional from the infinite dimensional case. Regardless, if $0<p<1$, $\|x\|_p := (\sum |x_i|^p)^{\frac 1 p}$ is not a norm as it fails to satisfy ...
1
vote
2answers
29 views

How to check whether a given inequality is convex? [on hold]

I have the inequality $$x_1^2+x_2^2\geqslant1$$ How do I check its convexity analytically?
0
votes
0answers
19 views

Basis of convex and concave functions

Let $g(t)$ be a positive function. I'm trying to show that the set $\{ |t|^ne^{\frac{g(t)}{t^n}}\}_{n\in \mathbb{N}}$ is linearly independent in the space of measurable functions on $\mathbb{R}$ (ie: ...
3
votes
1answer
25 views

minimum of sum of strictly convex functions

Is the following statement true? If so, how can I find a proof? Suppose that $f_1$ and $f_2$ are strictly convex functions on a convex set $X \subseteq \mathbb{R}^n$. If $f_1$ and $f_2$ have minimum,...
1
vote
2answers
27 views

Convexity of Certain Functions

Consider the set of functions: \begin{equation} f_n(t) := t^n e^{(\frac{c}{t^n})}, \end{equation} where $c$ is a non-zero real constant. I know that for $n=1$ $f_1(t)$ is convex on $(0,\infty)$ and ...
0
votes
0answers
17 views

Equality case in the Prékopa-Leindler inequality.

in the paper 'Remarks on the conjectured log-Brunn-Minkowski inequality' by C. Saraoglou, the author uses the result (Lemma A. 3.) about the equality case in the Prékopa-Leindler inequality. For the ...
0
votes
1answer
20 views

Definitions of intrinsic core of convex set

Let $C$ be a convex subset of a vector space $V$. We consider two definitions of the intrinsic core of $C$. Definition 1. The intrinsic core of $C$ consists all points $c\in C$ such that for every $c^...
5
votes
1answer
90 views

Is the smallest ellipsoid enclosing a convex set unique?

Let $S \subset \mathbb{R}^n$ be a convex set. Assume that it is bounded. We want to find an ellipsoid $E$ of smallest volume such that $S \subset E$. Is $E$ unique?
0
votes
0answers
11 views

Prove that a nest of sets has an empty intersection

Let $f$ be a real convex function and $S$ an arbitrary closed bounded subset of the relative interior of the effective domain of $f$. Let $B$ be a closed Euclidean unit ball. The nest of sets $$(S + \...
-1
votes
0answers
24 views

Definition of space by convex function [on hold]

It is well know that it is possible to define a space by norm, e.g. lets say that the norm we are concentrating on is L3 norm, thus $C = \{\theta \in \Re^d \mid \| \theta \|_3 \leq 1\}$ where $d \in \...
0
votes
1answer
19 views

Helly theorem application

Let $X$ be a normed space, $dim(X)=d$, let $r>0, A$ and $\subset X$ . Show that if every $d+1$ points of $A$ are contained in a closed ball of radius $r$, then $A$ is contained in a closed ball of ...
0
votes
1answer
20 views

Convex set equals convex functions within optimization?

Can optimizing a convex function subject to convex constraints be written as optimizing the function subject to a convex set? Does the intersection of convex nonlinear ineualities necessarily describe ...
0
votes
1answer
20 views

Convexity versus Strict Convexity

Let $u,v,w\in\mathbb{R}^n$ be three points that are not collinear. We define $$ \triangle(u,v,w):=\{\alpha u+\beta v+\gamma w:\alpha+\beta+\gamma=1, \alpha,\beta,\gamma\geq 0\}, $$ $$ [u,v]=:= \{tu+(...
1
vote
0answers
48 views

Analytical, numerical and graphical approaches to solve convex optimization problems?

I'm wondering if there are analytical approaches to solve these problems(I found these problems in a book by Stephen Boyd): minimize $f_0(x_1,x_2)$ subject to $2x_1+x_2\ge1$ $x_1+3x_2\ge1$ $x_1\...
0
votes
0answers
18 views

Why are generalized inequalities defined over proper cone?

Why generalized inequality is defined over a proper cone? What property does not hold if we define it over non-convex cone? Same with `pointed'. For example, generalized inequality makes sense in a ...
0
votes
1answer
23 views

Convexity of the composite of convex function by exponential function

Let $\exp : \mathbb{R}^2 \to \mathbb{R}^2$ be the function given by $\exp(x_1,x_2) := (e^{x_1}, e^{x_2})$. Suppose that $f : \mathbb{R}^2 \to \mathbb{R}$ is a smooth (i.e. $\mathcal{C}^2$) convex ...
0
votes
0answers
10 views

Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given submodular ...
1
vote
0answers
14 views

Measure induced by subgradient of convex functional

I am trying to understand why the following defines a measure. Let $\phi : \mathbb{R}^d \to \mathbb{R}$ be a convex function. Define a measure $\mu$ on $\mathcal{B}(\mathbb{R}^d)$ by $$\mu(E) = \...
0
votes
0answers
11 views

random pursuit without function evaluations

Assume we want to minimize a convex function $f(x)$ with $x\in \mathbb{R}^n$. Function $f(x)$ represents cost of a system which we cannot compute directly but can observe if system is at state $x$. My ...
0
votes
0answers
26 views

Interior of a solid self dual cone

Let $X$ be a real Hilbert space with a solid self dual positive cone $K$, that is, $\mathrm{int}(K)$ is non-empty and $K^{*}=K$. If $X$ is finite dimensional, I know that the $\mathrm{int}(K)$ = $\...
2
votes
0answers
15 views

convexity of a multivariable function

I have a function of the following type: $f(x_1,x_2,...,x_n)$ Each $x_i$ has domain $[0,\infty)$. The function is continuous and differentiable in each variable (It is an expectation of several ...
0
votes
2answers
73 views

Easy interpretation of matrix multiplication with a set

I have just started learning convex optimization. I am having little bit difficulties in some notations. Currently I just encountered the following equation: $$ \boldsymbol{epi}(wf) = \left[ \begin{...
1
vote
1answer
28 views

Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex $\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ Why adding the proximal ...
1
vote
2answers
53 views

Optimization with box constraints - via nonlinear function

I have the following convex optimization problem over $\mathbb{R}^n$ with box constraints: $$\begin{align}\text{minimize }&\;f(x)\\ \text{subject to }&\;x \in [-1,1]^n\end{align}$$ I can see ...
1
vote
1answer
63 views

Corollary 2.1 in Ekeland and Temam on lower semicontinuity

Why in Corollary 2.1 on page 10 (see the picture) from Ekeland and Temam book Convex Analysis and Variational Problems there is equality in (2.11), i.e why $$\forall u\in V,\quad \overline F(u)=\...
3
votes
1answer
39 views

Is there a way to measure how (non)convex a function is, maybe analogous to condition number?

Consider the functions $f(x) = \sin x$ and $g(x) = (x+1)^2 (x-1)^2$. We know that $f$ has an infinite number of local minimizers and is nonconvex on a non-compact subset of $R$. We know that $g$ has ...
1
vote
1answer
76 views

Prove that $u$ is upper semicontinuous on $\Delta(0,\rho)$.

Let $u:\Delta(0,\rho)\rightarrow \mathbb{R}$ be a function such that $u(x+iy)$ is convex in $x$ for each fixed $y$, and convex in $y$ for each fixed $x$. Prove that $u$ is subharmonic on $\Delta(0,\...
2
votes
1answer
20 views

Dual polyhedron & dual cone

From Wiki: Def. of dual of polyhedral (polytope): polyhedra are associated into pairs called duals, where the vertices of one correspond to the faces of the other. EX: 2. Def. of dual ...
0
votes
0answers
27 views

Concave optimization on closed unit ball, using penalty function

Background: I want to solve an optimization problem like $$\begin{align*}\text{minimize }&f(x)\\ \text{subject to }&\|x\| \le 1.\end{align*}$$ where $x \in \mathbb{R}^d$, $\|\cdot\|$ is the $...
0
votes
0answers
28 views

Is sum (convex combination) of quadratic function/aggregator quadratic?

We know convex combination of concave/convex functions are concave/convex. While convex combination of two quasi-convex/quasi-concave functions necessarily quasi-convex/quasi-concave. Common ...
0
votes
2answers
43 views

Poof- A function is convex iff it is convex when restricted to a any line that intersects its domain.

When I read the Convex Optimization, Boyd I noticed a statement about determining a function to be convex or not. It is: "A function is convex iff it is convex when restricted to a any line that ...
1
vote
1answer
61 views

show the quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$ is quasi-concave

I have a quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$, with $x_i$ nonnegative and $A \in[0,1)$. And w.l.o.g. we can normalize $x_i's$ to between 0 and 1. In ...
1
vote
1answer
39 views

How Do I Check Convexity Using The Actual Definition?

Suppose $f:\mathbb{R}^{+}\rightarrow\mathbb{R}$ is defined as follows: \begin{eqnarray} f(u)=\text{sgn}(\rho)\left(u^{\rho+1}-1\right),~u\geq 0, \end{eqnarray} where $\rho\in (-1,\infty)$, $\rho\neq 0$...
0
votes
0answers
20 views

The convex (bi)conjugate and the Fourier transform

In the context of convex optimization, I am looking to find a formula for the convex biconjugate of a function $f: X \rightarrow \mathbb{R}$ where $X$ is a real normed vector space, in terms of its ...
0
votes
1answer
25 views

Find minimal point of convex set

I'm having some convex set $P \subset \mathbb{R}^n_+$ and a linear-time indicator procedure $I_P(x)$ that allows for each given point $x \in \mathbb{R}^n_+$ to say whether it lies inside $P$ or not. ...
1
vote
1answer
46 views

How many times can strictly convex functions intersect?

Some time ago, I saw a post related to the number of times that two convex (and continuous) functions' graphs can meet. In general, infinitely many times: one can think, for instance, of $g(x):=x^{2}$ ...
1
vote
0answers
33 views

A set is affine if and only if its intersection with any line is affine. [duplicate]

How can we prove that the a set is affine if and only if its intersection with any line is affine? In fact, I want to know if there is such theorem that the intersection of two affine set is affine?
4
votes
1answer
56 views

My proof for “$\Gamma =\{X\in \mathbf{R}^{n\times n} \mid X \succeq 0, \text{Tr}(X)=1\}$ is compact”

This problem comes from: How to prove the compactness of the set of Hermitian positive semidefinite matrices In short, we want to prove $$\Gamma =\{X\in \mathbf{R}^{n\times n} \mid X \...
0
votes
1answer
27 views

$\{X \mid \text{trace}(X)=c\}$ is a hyperplane?

A hyperplane is a set of the form: $$\{x\in \mathbf{R}^n \ \ \mid \ \ a^Tx=b, a\in \mathbf{R}^n\}$$ This definition is quite intuitive. However, I am reading some books or paper and they ...
0
votes
1answer
39 views

Convex compact set must have extreme points

I am reading a paper and there is such description as title. Why? I have an example: $(0,1)$. This is a convex set but not closed, so I cannot find an extreme point. However if convex and compact,...
1
vote
1answer
27 views

How to give a formula of the perimeter of a $r$-neighborhood of a smooth set in $2D$?

Let $A$ be a simply connected open set in $\mathbb{R}^2$ with smooth boundary. Define $$A^r := \{x \in \mathbb{R}^2: d(x, A) \le r \},$$ where $d$ is the distance function. Let $P$ denote the ...
1
vote
0answers
41 views

Proof of the rotation matrix is an extreme point of $\text{conv } SO(n)$

Define the set of rotation matrices: \begin{equation} \begin{aligned} SO(n) := \{X\in \textbf{R}^{n\times n}: X^TX=I, \text{det}(X)=1\} \end{aligned} \end{equation} I want to prove that if $X\in SO(...
0
votes
0answers
9 views

Is $ \frac{F}{A}+c_p D K \sqrt{A}+c_g \Theta^2+c_e a D + t e (1-\Theta) D+ \frac{t a}{A}$ quasiconvex?

I am trying to check if the following function is jointly quasiconvex in $A>0,a,\theta \geq 0$. $$ \frac{F}{A}+c_p D K \sqrt{A}+c_g \Theta^2+c_e a D + t e (1-\Theta) D+ \frac{t a}{A}$$ The ...
1
vote
0answers
27 views

Width of a cone

Let $V=\{v_k\}$ be a collection of vectors of $\Bbb{R}^n$, and define their cone to be the set of all their non-negative linear combinations: $$ C(V):=\Big\{ \sum_k a_k\,v_k; \; a_k\ge 0 \Big\}\;. $$ ...
1
vote
1answer
69 views

Probability that the convex hull of random points is a triangle

Question: Consider a fixed number $k > 3$ of random points in the plane, each independently distributed according to a 2D standard normal distribution. What is the probability that the convex hull ...
2
votes
1answer
94 views

Continuously differentiable function injective on convex set

Can you help me solve the following exercise: (a) Let $n\in \mathbb N$ and $G \subset \mathbb R^n$ a convex set, $f:G\to \mathbb R^n$ continuously differentiable with $$det\left(\begin{matrix} \...
7
votes
2answers
139 views

Mean value theorem for a gradient of convex function

This is from an article, page 19. Let $J(u)=\sum \sqrt {u_i^2+\epsilon}$, and $p^{k+1}=\nabla J(u^{k+1})$, $p^{k}=\nabla J(u^{k})$. Since $J$ is convex, the mean value theorem tells us that $$p^{k+...