Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [convex-analysis]

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.

1
vote
0answers
12 views

Proof that makes use of the differentiability of a function and of its convex conjugate

I would like your help to understand what are the crucial assumptions driving the claim reported below. Let me start with the notation $\mathcal{Y}\equiv \{1,2,...,M\}$. $S$ is a random vector with ...
0
votes
1answer
34 views

What is the derivative of $\operatorname{trace}(XCP(XC)^T)$?

I am really stuck at calculating $\frac{d\operatorname{trace}(XCP(XC)^T)}{dC}$ where $P \in R^{r\times r}$, $X \in R^{m\times n}$ and $C \in R^{n\times r}$ . Do I need to recall $A=XC$ and then apply ...
1
vote
0answers
27 views

Show that a function is strictly convex, differentiable, continuous

Consider the vector $\theta\equiv (\theta_1,...,\Theta_M)$. Let $\Theta\subseteq \mathbb{R}^M$. Consider the random vector $\epsilon\equiv (\epsilon_1,..., \epsilon_M)$. (A1) We assume that the ...
1
vote
0answers
37 views

Using Jensen's inequality prove: (1) $~n!<n^n<(n!)^2$ for $n>1$ and (2) $~e^n\geqslant \frac{n^n}{n!}.$

Using Jensen's inequality, prove: $$~(1) ~~n!<n^n<(n!)^2~~~~~ and ~~~(2)~~~ e^n\geqslant \frac{n^n}{n!}.$$ Attempt. For (1), since $\log$ is strictly concave, using Jensen: $$\log\frac{1+2+\...
0
votes
1answer
24 views

Inequality constraints and the max function

Let $g_i(x):\mathbb{R}^{n} \to \mathbb{R}$, for $i=1,\ldots,n$, be continuous convex functions. Define $g_{\rm max}$ as $g_{\rm max}(x) \triangleq \mbox{max}_{i=1,\ldots,n}\{g_i(x)\}$. Define also the ...
1
vote
0answers
52 views

Continuous $f:(a,b)\to \mathbb{R}$ is convex iff $x \mapsto f(x)+\gamma x+\delta$ does not attain max for all $\gamma,~\delta\in \mathbb{R}$

Let $f:(a,b)\to \mathbb{R}$ continuous. Prove that $f$ is convex iff for all $\gamma,~\delta\in \mathbb{R}$ function $x \mapsto f(x)+\gamma x+\delta$ does not attain its maximum value on $(a,b)$. ...
0
votes
1answer
32 views

Proof $C$= {$(x, y) \in \mathbb{R}^2 | x+y=b $} is convex

In an optimization problem, I have constraints of the form $x+y=b$. In order to prove that the solution is unique, I proved that the criterion is strictly convex and now I need to show that the set of ...
4
votes
0answers
26 views

When does a convex sequence $S_n$ satisfy $S_{a+b+c} - (S_{a+b}+S_{a+c}+S_{b+c})+S_a+S_b+S_c\geq 0$

Let $S_n$ be a sequence of integers with $n\geq 0$ such that $S_0=S_1=S_2=0$ (also assume $S_n$ to not be completely zero) and $$ S_{n-1}+S_{n+1}\geq 2S_n $$ i.e. $S_n$ is convex. Now consider the ...
1
vote
1answer
46 views

Without use of derivatives, prove that function $(1+x^p)^{1/p}$ is convex for $p\geq 1$

Without use of derivatives, prove that function $(1+x^p)^{1/p}$ is convex for $p\geq 1.$ Attempt. The result is obvious for $p=1$, since function $x+1$ is affine. For $p>1$, functions $1,~x^p$ are ...
2
votes
2answers
46 views

If $f$ is convex and concave on interval $I$, then $f$ is affine on $I$

Prove that if $f$ is convex and concave on interval $I$, then $f$ is affine on $I$. Attempt. Although this topic has been discussed before, i would like to point out some technique issues. 1) Let $I=...
8
votes
2answers
198 views
+50

Proof (without use of differential calculus) that $e^{\sqrt{x}}$ is convex on $[1,+\infty)$.

Prove (without use of differentiation) that $f(x)=e^{\sqrt{x}}$ is convex on $[1,+\infty)$. Attempt. Function $x\mapsto e^x$ is convex and increasing, but $x\mapsto \sqrt{x}$ is concave, so we ...
0
votes
1answer
55 views

Show that the function is convex

Show that the function $f: S \to \mathbb R$ given by $$f(x,s,t):=-\ln(st - ||x||^2)$$ is convex on $$S := \left\{(x,s,t) \in \mathbb R^n \times \mathbb R \times \mathbb R: \frac{\|x\|^2}{s}<t, s&...
1
vote
2answers
59 views

Prove or disprove: convex function $f:[a,b] \to \mathbb{R}$ attains a minimum value on $[a,b]$

Let $f:[a,b] \to \mathbb{R}$ be a convex function. Prove or disprove: $f$ attains a minimum value on $[a,b].$ Attempt. I believe the answer is yes. We know: If $f:I\to \mathbb{R}$ is convex and ...
0
votes
0answers
18 views

Sufficient conditions for minimum to exist in non-compact subset of normed vector space

Let $X$ be a non-compact subset of a normed vector space. Let $f : X \to \mathbb{R}$ be a differentiable convex function that is bounded from below. Given that $X$ is not compact: 1) Is there a ...
1
vote
1answer
34 views

Prove two convex sets are equal

Prove that following two sets are equal: $$ \operatorname{conv}\left\{\, xx^T \,\middle|\, x\in\Bbb R^n, \|x\|=1 \,\right\} = \left\{ A \in S_n^+ \,\middle|\, \operatorname{Tr}(A)=1 \,\right\}, $$ ...
1
vote
2answers
49 views

If $f:I\to \mathbb{R}$ is convex and interval $I$ is bounded, prove that $f$ is bounded below.

Let $I$ be a bounded interval and $f:I\to \mathbb{R}$ be a convex function. Prove that $f$ is bounded below in $I.$ Attempt. Let $a,~b\in I$, by convexity of $f$ on $[a,b]:$ $$f(x)\leq g(x):=f(a)+\...
-1
votes
0answers
61 views

How to find subdifferential of $sin(x)$ [on hold]

I want to compute the subdifferential of $f(x) = sin(x)$, where $domf = (0, \frac{3}{4}\pi)$. How do I do this?
0
votes
2answers
43 views

Is ‎$‎f‎$‎ ‎monotone ‎when ‎$‎f‎$ ‎is ‎concave?‎

‎Let ‎$‎f:[1, +‎\infty‎)‎‎‎\rightarrow‎‎\mathbb{R}$ ‎be a‎ ‎concave ‎function. Suppose‎ $‎F:[1, +‎\infty‎)‎‎\rightarrow‎‎\mathbb{R}‎$ is a primitive function of ‎$‎f‎$‎. My ‎questions ‎are‎:‎ ‎‎ ‎(a) ...
0
votes
0answers
23 views

I am trying to prove the minimax convex optimization [on hold]

I am trying to prove that this following function is convex, min(max(a)+b). Are there any useful resources that I can use or Do you know how to start with it?
3
votes
1answer
48 views

Problem about the difference of two power

Let $a>b>0$ such that $a+b=2$ and $\alpha\geq 1$ then we have : $$a^{ab}-b^{ab}\leq \alpha(a^{\frac{ab}{\alpha}}-b^{\frac{ab}{\alpha}})$$ My try : The problem is equivalent to : $$\frac{a^{...
0
votes
0answers
24 views

How to prove that the affine hull of a set is a closed set.

I am asked to prove that $\text{aff}(X)$ is closed in the topological sense. I found some posts where people show that it is closed under affine combinations (what it's quite obvious because the ...
0
votes
1answer
18 views

The boundness of a polyhedral set implies that $y \in \mathbb{R}^n $ is equal to zero

I'm solving a problem of nonlinear programming. The problem says: Let $S_1=\{x:A_1 x\le b_1\}$ and $S_2=\{x:A_2 x\le b_2\}$ be nonempty. Define $S=S_1\cup S_2$ and $S'=\{x: x=y+z, A_1y\le b_1\...
1
vote
0answers
38 views

How to prove that the subgradient of a dual function contains the equality constraint for closed and convex function?

Apologies for the fundamental question. But I am am just trying to understand the pieces. Let us consider a minimization problem \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & f(x) \\ ...
0
votes
1answer
32 views

Does the convex hull of a sphere contain every point on its surface?

Sorry if this is an obvious question but I have not been able to find a straightforward answer for it. My intuition tells me this is correct, and have confirmed that the scipy convex hull algorithm ...
1
vote
1answer
45 views

Prove that $x\log x$ is midpoint convex.

Prove that negative entropy function $f(x)=x\log x$ is midpoint convex on $(0,+\infty)$. Attempt. Let $0<x<y$, so: $$f\left(\frac{x+y}{2}\right)\leq \frac{f(x)+f(y)}{2}$$ is equivalent to: $$\...
2
votes
1answer
47 views

Isotonic regression with a linear constraint

I'm trying to find a direct approach to solving (for some fixed vector $y$): $$ \begin{aligned} \min & \; \|x - y \|^2 \\ \mbox{s.t. } & \alpha^\top x \leq 0 \\ & x_i \...
1
vote
1answer
26 views

Partitioning $\mathbb{R}^3$ into two convex sets.

I know that there are $4$ partitions of $\mathbb{R}^3$ into two convex sets, up to affine transformation. One of the partitions is the trivial $\{\emptyset,\mathbb{R}^3\}$ (note that by partition, I ...
0
votes
1answer
23 views

Why is the epigraph of Moreau-Yosida Regularization a projection of a convex set?

The Moreau-Yosida Regularization is given by \begin{equation} f_\mu(x) = \inf_y \left( f(y) + \frac{1}{2\mu} \| x - y \|^2 \right). \end{equation} We know that $L(x, y) = f(y) + \frac{1}{2\mu} \| x -...
2
votes
1answer
49 views

Problems about the convex hull.

I'm stuck in two problems concerning about convex hull. Let $A,B,C \not= \emptyset$, compact sets in $\mathbb{R^n}$. Show that if $A+B=A+C$ then $\text{conv}(B)=\text{conv}(C)$ Let $B\not= \emptyset$...
0
votes
1answer
44 views

Is $\overline {conv}(T(M))\subset T(\overline {conv}(M))$?

Let $(E,\left \| . \right \| )$ be a Banach space $T:E\rightarrow E$ is a continuous and bounded mapping. Let $x_0\in E$, we define a sequence $(x_n)_{n\in\mathbb N}$ as follows: $$x_{n+1}=T(x_n) \...
1
vote
0answers
25 views

Does subdifferential function with non-convex dom exist?

In this question it was proved that, if $f:X \to \mathbb{R}$ and $\partial f(x)\neq \emptyset$ for all $x \in X$, then $f$ is convex. But in the proof we used the fact, that $x = \lambda x_1 + (1 - \...
0
votes
1answer
7 views

Does Lipschitz continuity of a convex imply boundedness of the domain of its Fenchel conjugate

Let $g:\mathcal{H} \to \mathbb{R}$ be a convex and $L_{g}$-Lipschitz continuous function on a Hilbert space $\mathcal{H}$. Is the domain of its Fenchel conjugate $g^*$, where $$ g^*(y) := \sup_{x \in \...
2
votes
0answers
41 views

Minimizing the lower bound of a convex function

Suppose $\bf{A}$ is an $m \times n$ matrix of rank $n$ having entries 0s and 1s. I found that the minimizer of \begin{align*} {\bf Q}^* = \text{min}_{\bf Q} \ \text{tr}({\bf AQQ}^{T}{\bf A}^{T}) \ \ ...
3
votes
1answer
19 views

Does the concept of Minkowski Sums generalise naturally in infinite dimensional settings?

I would like to use the concept of Minkowski Sums to study some convex analysis problems in an infinite dimensional setting, but all the papers and books I can find are referring to finite dimensional ...
1
vote
1answer
13 views

Difficulty Proving First-Order Convexity Condition

I'm independently working through Boyd and Vandenberghe's "Convex Optimization" and am stuck on the following step in their proof of the first-order convexity condition on page $70$. If we divide ...
0
votes
1answer
21 views

Example of convex and injective $f:I \to \mathbb{R}$ such that $f^{-1}$ is not concave

Example of a convex and injective function $f:I \to \mathbb{R}$ on an interval $I$, such that $f(I)$ is an interval and $f^{-1}:f(I)\to \mathbb{R}$ is not concave. Attempt. Our function $f$ cannot be ...
2
votes
0answers
24 views

Lipschitz constant of L2 reg. logistic regression $\sum_i \log \left(1 + \exp\left\{ -t_i \left(w^T x_i\right)\right\} \right) + \mu \|w \|_2^2$

Let the L2 regularized logistic regression function is given by, \begin{align} f(w) &= \frac{1}{N} \sum_i \log \left(1 + \exp\left\{ -t_i \left(w^T x_i\right)\right\} \right) + \mu \|w \|_2^2 \ = \...
0
votes
2answers
63 views

How can we prove this integral inequality?

There is the first inequality that I should solve: For all $R>0$ $$\int_0^{\pi/2}e^{-R\sin(\varphi)}d\varphi < \frac\pi{2R}(1 - e^{-R})$$ But in the next exercise, there is a more general case: ...
0
votes
1answer
28 views

How can the following non-convex problem be converted to a convex one? [closed]

Minimize: $x^2+xy+3y^2-x-4y+1$ Subject to: $(x-1)\log(1+\exp(x))\leq 0, x+y\geq0$
0
votes
1answer
29 views

Prove that the inverse of trace of inverse is convex.

This is B.17 from Fundamentals of Convex Analysis by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Let $f: S^{++}(\mathbb{R}^n) \to \mathbb{R}$ be $$f(M) := \frac{-1}{tr(M^{-1})}$$ Then show $f$ ...
0
votes
1answer
28 views

About subgradient of matrix norm

I am reading Characterization of the Subdifferential of Some Matrix Norms by G.A. Watson. And in the first page the subgradient of $\|A\|$ is defined:$$\partial\|A\| := \{G\in \mathbb{R}^{m \times n}:\...
0
votes
1answer
26 views

Convex subset of $\mathbb{R}^{m \times n}$

Let $S$ be a convex subset of $\mathbb{R}^{m \times n}$ with $0 \in S$. Is it true that if $a,b \in S$ and $0 \leq a_{ij}\leq b_{ij}$ for all $1 \leq i \leq m$ and $1 \leq j \leq n$, then $b-a \in S\,\...
3
votes
1answer
33 views

A convex function's epigraph is convex. What property has that of an increasing function?

In some sense, convex functions are the second-order version of increasing functions: under suitable hypotheses (for instance if the function is $C^2$), an analytic characterization of convexity is ...
6
votes
0answers
53 views

Inequality for convex function $f:(0,\infty)\to\mathbb{R}$ [duplicate]

I have been working through the Exercises at the end of Chapter $1$ of Bollobas' Linear Analysis. Chapter $1$ is on inequalities, and the text is fairly brief. I have found the problems unexpectedly ...
0
votes
0answers
13 views

Does a maximal cyclically monotone correspondence have convex range?

More specifically, if $\Gamma$ is a $K \times J$ matrix whose columns are linearly independent probability vectors, and $S(x)= \ln (\Gamma ^\intercal \ln \Gamma x)$ is a function $\mathbb R^J_+ \...
0
votes
0answers
35 views

optimization problem with square root and quadratic

Consider the optimization problem \begin{align} \max_{\mathbf{y\in\mathbb{R}^N}}~~\mathbf{y}^T\mathbf{b}+\beta\sqrt{c-\mathbf{y}^T\mathbf{Ay}} \\s.t.~~\mathbf{0}\leq\mathbf{y}\leq \mathbf{1} \end{...
1
vote
2answers
36 views

Silly question on lower semi-continuity

Suppose that $X_n\rightarrow X$ in a complete separable metric space $(\mathcal{X},d)$. Let $f:\mathcal{X}\rightarrow (-\infty,\infty]$ be a proper, convex, lower semi-continuous function, such that $...
2
votes
0answers
70 views

Is $f(x,y)=\left(\frac{x^a(1-y)}{(1-x)}-\frac{y^{a}(1-x)}{(1-y)}\right)\frac{1}{x-y}$ convex?

Is it possible to prove that, $$f(x,y)=\left(\frac{x^a(1-y)}{(1-x)}-\frac{y^{a}(1-x)}{(1-y)}\right)\frac{1}{x-y}$$ is convex in the following range: $0<y<x<1$, where $a\ge2$ is an integer ...
1
vote
0answers
30 views

How does minimax equality fail for non-convex sets of distribution?

Minimax theorem states that $$ \sup_{P_X \in P}\inf_{\eta} mse(P_X,\eta) = \inf_{\eta} \sup_{P_X \in P} mse(P_X,\eta) $$ where $\eta$ is an estimator of X and $P$ is a convex set of distributions ...
0
votes
1answer
18 views

What is the relationship between convexity as a whole and convexity in respect to each parameter?

What, if any, is the relationship between the convexity of a function $f:\mathbb{R}^N\rightarrow \mathbb{R}$ and the convexity of the same function with all parameters held constant except for a ...