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 (1)

1
vote
1answer
16 views

Compactness, Convexity, Convex Hull of Sets including sequences

Is the following set compact, is it convex and what is the convex hull? $V = \{(x_1, x_2,...,x_n) \in \mathbb{R}^n :\frac{1}{1 + i} \leq x_i \leq \frac{1}{i}, i=1,2,...,n\}$ My thoughts: I was ...
1
vote
1answer
40 views

Consider the problem minimize $f(x_1,x_2) = (x_2 −x_1^2)(x_2 −2x_1^2)$

(i) Show that the first- and second-order necessary conditions for optimality are satisfied at $(0,0)^T$. (ii) Show that the origin is a local minimizer of f along any line passing through the origin ...
0
votes
0answers
10 views

Expressing a convex set as an intersection of halfspaces

The question is as follows: Express the closed convex set {x $\epsilon$ $R^2_+$ | $x_1x_2$ >= 1} as an intersection of halfspaces. Here is what I have: $\bigcap$ {x $\epsilon$ $R^2_+$| $x^2$ >= 1} ...
-1
votes
1answer
28 views

Showing $\ln(1+e^x)$ is convex [on hold]

I'd like to show that $\ln(1+e^x)$ is convex. Any help would be greatly appreciated!
2
votes
1answer
30 views

Quasiconcavity of incomplete gaussian integral

From visual experiments , it appears that the set $$ S_r = \left\{ (x,y) \text{ s.t. } \int_x^y e^{-t^2} dt \geq r \right\} $$ is convex for $r \geq 0$. Or equivalently, the function $$ f(x,y) = ...
2
votes
3answers
163 views

Why doesn't the definition of the interior of a set depend on the dimension of the set

I have just started with a course on convex optimization and have been introduced to the concept of the interior of a set. I have a fairly basic question. I am still trying to understand this topic, ...
1
vote
2answers
63 views

Is every convex function on an open interval continuous?

Let $f:(a,b)\rightarrow \mathbb{R}$. $f$ satisfied the following property: If $\forall x_{1},x_{0},x_{2}\in(a,b)$ and $x_{1}<x_{0}<x_{2};$then$\frac{f(x_{0})-f(x_{1})}{x_{0}-x_{1}}\geq ...
1
vote
1answer
41 views

Dual of concave function is convex

If $U(x)$ is strictly increasing and strictly concave and $lim_{x \rightarrow \infty}$ U'(x) = 0, prove that its dual: $$U^{*}(y) = max_x \{U(x) - xy\}$$ is convex. Does anyone know how to prove ...
1
vote
0answers
11 views

On Convex Interpolation and distances

Let $C$ denote the class of all real-valued convex functions on $[0, 1]^2$. Fix $n \geq 2$ and points $x_1, \dots, x_n$ in $[0, 1]^2$. Let $S \subset R^n$ be defined by \begin{equation*} S := ...
0
votes
0answers
19 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
14 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
0
votes
0answers
34 views

weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
2
votes
1answer
16 views

Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
0
votes
0answers
6 views

Verification of the Approach to a given non-convex integer programming problem

I need to verify my approach to a non-convex integer programming problem. It would be interesting to see other approaches as well. Let $\mathbf{C}_1,\dots,\mathbf{C}_R$ be $N\times N$ hermitian ...
0
votes
1answer
51 views

Show that this function is convex?

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm ...
0
votes
0answers
10 views

Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
0
votes
1answer
80 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
1
vote
2answers
37 views

How to prove that $H(S_1\cap S_2)\subset H(S_1) \cap H(S_2)$ and $H(S_1 \cup S_2) \supset H(S_1) \cup H(S_2)$

I'm studying convex analysis and my task is to prove the following inclusions: $S_1, S_2$ are non-empty sets in $\mathbb{R}^n$, and $H(S) $ defined as the convex hull of set $S$. Show that ...
0
votes
0answers
11 views

extension of semilinear functional in cone.

I'm studying Nigel Kalton's work in extrapolation Banach space theory (paper: Differentials of complex interpolation processes for Kothe function spaces). My question is: Let $T$ be a cone contained ...
0
votes
1answer
24 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
2
votes
1answer
38 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
0
votes
0answers
16 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
2
votes
2answers
24 views

Under what conditions does local concavity imply global concavity?

I have the following result: Assume $U:\mathbb{R}^+\to\mathbb{R}^+$ is continuous and strictly increasing. Further, for every $a>0$ there exists a neighborhood (interval) $S$ of $a$ such that $U$ ...
7
votes
1answer
141 views

Characterization convex function.

Let be $f:[0,1]\rightarrow\mathbb{R}$ a continuous function such that far all $a,b\in [0,1]$ with $a<b$ $$f\left(\frac{a+b}{2}\right)\leq\frac{1}{b-a}\int_a^b f(x)\,dx.$$ How to prove that $f$ is ...
0
votes
1answer
20 views

Proving that $\lambda_1\textbf{x}_1+\lambda_2\textbf{x}_2\in C$, for convex cone $C$

I'm doing convex analysis studies and I have the following problem to prove: Show that, if $C$ is a convex cone, then $\lambda_1\textbf{x}_1+\lambda_2\textbf{x}_2\in C$, with ...
0
votes
0answers
13 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
19 views

Convex function and its epigraph PROOF

Can someone help prove this statement. Consider a function $f:R^{n} \to R$ and epi $f$ = {$(x,t) \in R^{n+1}$: $x \in R^{n}$, $t \geq f(x)$} A function is convex if and only if its epigraph is a ...
0
votes
1answer
14 views

Questions on conditions for convexity of a real function

We have a function $f:[0,1] \rightarrow \mathbb{R}$. We know it is continuous on $[0,1]$. Aside from a set $S$ of measure $0$, we can compute its right derivative, and can show that this right ...
0
votes
2answers
30 views

Identity regarding convexity of the logistic loss function

I found the following identity regarding the logistic loss function in these lecture notes (slide 16) from Berkeley university: $$\log(1 + e^{-z}) = \max_{0 \leq v \leq 1} -zv + v\log(v) + ...
5
votes
1answer
92 views

Non-empty intersection of convex sets

Assume that $X_1,\ldots,X_n$ are open, convex subsets of $\Bbb R^d$ such that for any $i,j,k$ with $1\le i,j,k\le n$, we have $X_i\cap X_j\cap X_k\neq\emptyset$. Is it possible for $\bigcap_{i=1}^n ...
0
votes
0answers
18 views

Maximum intersection of slabs in $\mathbb{R}^n$

Let $K \in \mathbb{R}^n$ be a compact convex set containing the origin and symmetric with respect to the origin. Let $S_i(t_i)$ be a finite set of slabs of various widths and orientations, translated ...
6
votes
0answers
196 views

Closest fixed point to a convex set

Consider the compact convex sets $Y \subset X \subset \mathbb{R}^n$, and a Lipschitz continuous function $f : X \rightarrow X$. Assume that $f$ has multiple fixed points. (From Brouwer's theorem, $f$ ...
0
votes
1answer
30 views

Minimizing a non-convex rational function of two variables

I need to minimize the following function $$f(x,y)= \frac{a}{x}+\frac{bx}{y}+\frac{cy}{x}+dy+\frac{e}{y}$$ where $a,b,c,d$, and $e$ are positive constants, and $x$ and $y$ are both strictly positive. ...
0
votes
1answer
23 views

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities.

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities. The convex hull of $x_1, \ldots, x_n \in \mathbb R^n$ is defined ...
3
votes
1answer
57 views

Strictly increasing and strictly convex function that does not go to negative infinity

Let $f : \mathbb{R} \to \mathbb{R}$ be continuous, strictly increasing, and strictly convex for all $x$. What are necessary and sufficient conditions for $f$ to be bounded below? Strong convexity is ...
0
votes
0answers
19 views

Some good reference on convex functions

I want some good reference on convex functions i.e. all of their properties along with their proofs.
0
votes
1answer
28 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
0
votes
0answers
19 views

Does $\mu\coth(\mu)=A\mu^{2}+B$ have at most two positive solutions $\mu$?

Is it true that $$ \frac{\mu\cosh(\mu)}{\sinh(\mu)} = A\mu^{2} + B $$ has at most two solutions $\mu > 0$ for any choice of $A$, $B$? I believe this is true; it looks true when I ...
2
votes
0answers
14 views

Convexity of sigmoid-based squared error loss

Assume $w, a_1,a_2 \in \mathbb{R}^d$ and $\sigma = \dfrac{1}{1+e^{-x}}$ the sigmoid function. Is the following squared difference a convex function? $$J(w)= (\sigma(w^Ta_1)\times \sigma(w^T ...
0
votes
0answers
28 views

The convexity of the range of concave function

Given a concave function $f: X \rightarrow \mathbb{R}^n $ with a convex domain $X \in \mathbb{R}^n$, is the range of $f$ a convex set also?
1
vote
1answer
29 views

Directions of sublevel sets ofa convex function

Let $f:\mathbb R^n \rightarrow \mathbb R$ be a convex (continuous ) function. Let's assume that some sublevel set $L_a:=\{x\in \mathbb R^n : f(x) \leq a\}$, where $a \in \mathbb R$, contains a ...
1
vote
0answers
15 views

Existence criterion for solution in quadratic programming

I have the problem $$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}$$ with $D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}$, $A,Q\in \mathbb{R}^{n\times n}$ and $b,c \in ...
0
votes
0answers
33 views

Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
0
votes
1answer
32 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
0
votes
0answers
33 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
3
votes
3answers
133 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
2
votes
0answers
23 views

Convex interpolation between two points with given derivatives

Let's say I have two real values $x_1$ and $x_2$, to each of which I associate $y_i$ and $y'_i$ satisfying $$ (y_2-y_1)(y'_2 - y'_1) \geq 0. \tag{1} $$ I would like to find a polynomial ...
0
votes
0answers
20 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
14 views

What is the nature of this one dimensional function?

Let $\mathcal{S}$ be a 2-D convex set whose elements can be represented as $(x,y)\in\mathcal{S}$. Let $p_L$ and $p_U$ be two real constants such that $p_L\leq p_U$. For $p\in[p_L,p_U]$, I define the ...
1
vote
1answer
35 views

Convex Combination of 3 point in R2 and Triangle

I am new to convex combination, and I am quite amazed by some easy result. I know that convex combination of 2 points($P_1P_2$) in $R^2$ is all points in the line segment $P_1P_2$. And then I see a ...