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
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
0
votes
0answers
34 views

How can the ADMM algorithm be distributed?

I am reading Boyd's tutorial paper on ADMM. One question I had after I reached the formulation of the algorithm on pp.14 is: how can the alternating or sequential fashion of x-minimization step and ...
1
vote
3answers
39 views

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$?

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$ is the statement correct? Can I prove like this: $sup_x [ f(x)+sup_x g(x)] = sup_x[f(x)] + sup_x[g(x)] = sup[f(x)+g(x)]$.
0
votes
1answer
17 views

Showing that $ye^{x/y} = \max_{\alpha>0} \left[ \alpha(x+y) - y\alpha \log(\alpha) \right]$

In my optimization textbook, the author states without proof that $$ ye^{x/y} = \max_{\alpha>0} \left[ \alpha(x+y) - y\alpha \log(\alpha) \right]. $$ To be honest, this does not seem very obvious ...
0
votes
0answers
20 views

convex envelop on a unit ball

What does that exactly mean by "the function $g$ (continuous) is the convex envelop of the function $f$ (discrete) on a unit $\ell_\infty$ ball". I understand the part of "a function being the convex ...
8
votes
2answers
122 views

Opening and closing convex sets

It seems true that, given $K \subseteq \mathbb{R}^n$ a convex set with $K^\circ \neq \emptyset$, then $\overline{K^{\circ}} = \overline{K}$ and $\left ( \overline{K} \right )^\circ = K^\circ$. I am ...
1
vote
2answers
31 views

Tangents of a Strictly Convex Fuction

Let $f:\mathbb R \rightarrow \mathbb R$ be differentiable and strictly convex. Is it true that $x,y \in \mathbb R$ and $x \neq y$ imply \begin{equation} f'(x)(y-x) <f(y) - f(x) \end{equation} If ...
0
votes
1answer
35 views

Smallest convex body inscribed in $n$-cube with all its symmetries? [closed]

Consider the cube $[-1,1]^n$ and convex bodies inscribed in it, such that all these bodies have the symmetries of the cube. Is there a lower bound on the volume? Which shapes attain it?
0
votes
0answers
20 views

Smallest volume of a centrally symmetric convex body inscribed in $n$-cube

We consider several centrally symmetric convex bodies inscribed (intersecting all its facets) in an $n$-cube , $[-1,1]^n$, with volume $2^n$. For instance, such a crosspolytope (its polar dual) has ...
2
votes
2answers
30 views

Strictly Convex Implies Invertible Gradient?

If $f:\mathbb R^n \rightarrow \mathbb R$ is strictly convex and continuously differentiable, does this imply that $\nabla f$ is a one-to-one mapping? To be precise, can we say that $x, y \in \mathbb ...
0
votes
0answers
20 views

Applying homogeneity for a norm to prove triangle inequality

I am hoping to have someone help explain to me the steps of this proof of the triangle inequality for $L^p$ spaces, $p\ge 1$. Specifically the first two applications of the homogeneity property don't ...
0
votes
0answers
50 views

Computing Direction of Descent for General Fermat Problem

Suppose that $k \geq 3$, and let $X_1, \dots , X_k$ be $k$ points in $\mathbb{R}^2$, and let $w_1, \dots , w_k$ be $k$ positive real-valued constant weights. Given this, consider the function $g(p) = ...
1
vote
0answers
48 views

Show Direction of Steepest Descent is Unique

If f is a proper convex function and x is in the interior domain(f), how would one go about proving that the direction of steepest descent at x is unique? I intuitively get it, but don't get how one ...
0
votes
1answer
20 views

Functions with convex/concave potential

A function $f:A\to A$ has convex/concave potential if there is $F:\mathbb{R}^n\to \mathbb{R}$ such that $\nabla F=f$, and $F$ is convex/concave. Let $A\subset \mathbb{R}^n$ be a compact set. Are ...
0
votes
0answers
30 views

Supremum of a Sequence of convex and closed functions {f_i} is also closed [closed]

I feel like this is an obvious question, but I am having difficulty formally proving it. Given a set of convex and closed functions {f_i(x)} and f(x) is defined as the sup f_i(x), then how does one ...
1
vote
0answers
29 views

Conflict with definition of “face”

I am given this definition of face from Convexity: An analytic viewpoint: Definition: A face of a convex set $P$ is a set $F\subsetneq \overline{P}$ such that for every $x,y\in\overline{P}$ and for ...
0
votes
0answers
15 views

Convexity of Maximum Inscribed Ellipsoid Problem

I am confused about the problem of finding the ellipsoid of maximum volume inscribed in a polyhedron as discussed in section 8.4.2 of Convex Optimization by Boyd and Vandenberghe. I've followed the ...
3
votes
2answers
33 views

A caracterization of convexity in $\mathbb R^n$

Let $C$ be a closed subset of $\mathbb R^n$ such that $$\forall x,y \in C, (x,y)\cap C \neq \emptyset$$ where $(x,y)=\{(1-t)x+ty, t\in (0,1)\}$ Prove that C is convex A quick drawing shows ...
1
vote
1answer
16 views

Convex and Symmetric subset of a Banach space

Let X be a Banach space and A be a convex and symmetric subset of X. Is it true then that the closure of A will be a subset of 2A=A+A? I doubt that this always holds, but can't seem to find a ...
0
votes
1answer
37 views

Is there a geometric interpretation for a function's $\alpha$-sublevel set?

In Boyd and Vandenberghe's "Convex Optimization": The $\alpha$-sublevel set set of a function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is defined as $$C_\alpha=\{x \in \mathbf{dom} ...
3
votes
1answer
51 views

Jensen's inequality in measure theory

Here cites its original claim from http://www.math.tau.ac.il/~ostrover/Teaching/18125.pdf. Theorem 3.1 Jensen's Inequality Let $(X,\mathcal{M},\mu)$ be a probability space (a measure space ...
0
votes
1answer
40 views

Prove an inequality through convexity

I'm trying to prove $-hp + ln(1 - p + pe^h) \le (1/8)h^2$ for all $h > 0$ and $0 \le p \le 1$. After moving the term $-hp$ to the RHS and exponentiating we get $1 - p + pe^h \le e^{(1/8)h^2 + ...
0
votes
1answer
18 views

Proving inequality from convexity of function

I am having trouble proving the following inequality for all $x,y>0$ from "The Mathematics of Nonlinear Programming" by Pressini, Uhl. The book states that it follows from the convexity of an ...
0
votes
0answers
32 views

What algorithms are applicable to solve a inequality constraint Quadratic Optimization?

Suppose that we have a quadratic optimization problem $$(QP) \qquad \min \lbrace\frac{1}{2}x^TQX+ q^TX\rbrace $$ s.t. $$AX=a;$$ $$BX\le b;$$ $$X \ge 0;$$ where $Q \in \mathbb{R}^{n \times n}$ ...
3
votes
1answer
42 views

A convex real function is continuous - can we generalize?

There is a well-known theorem $\newcommand{\RR}{\mathbb{R}}$ Let $f: (a,b) \rightarrow \RR$ be a convex function. Then $f$ is continuous on $(a,b)$ The proof I know makes use of the fact that ...
2
votes
1answer
39 views

Convolution of convex function and Gaussian is convex

Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function, i. e., for all $x_1, x_2 \in \mathbb{R}$ and $t \in [0, 1]$, $$ \qquad f(tx_1+(1-t)x_2)\leq t f(x_1)+(1-t)f(x_2).$$ I want to prove that the ...
4
votes
1answer
36 views

Classification of boundary points of convex sets in $R^n$

I'm trying to prove the following: Let $P\neq R^n$ be a convex set containing an $R^n$ neighborhood of $0$. Then $x\in\partial P\iff (\lbrace tx: 0\leq t < 1\rbrace\subset P^\circ)\wedge(x\not\in ...
0
votes
1answer
56 views

Given a convex function $f(x)$, is $xf'(x)$ also convex?

Given a convex function $f(x)$, I'm trying to proof that $g(x) = xf'(x)$ is also convex. I have found neither a proof nor a counterexample so far. A function $g(x)$ is convex iff $g''(x) \ge 0$. ...
0
votes
0answers
33 views

Question regarding “distance function” in convex spaces.

Assume that we have a convex space $K < \mathbb{R}^n$ and a point $a \not\in K$. I need to show that there is a function in the dual, $f\in \mathbb{R}^n$ such that $f(a)\geq f(x)$ for all $x\in K$. ...
1
vote
0answers
41 views

non negativity of an sequence alternating series

Assume we have the positive real number $a_1,...,a_n$, and variable $x \in \Bbb R^+$, I am trying to prove the following to be positive (or at least non negative): $$ \frac{1}{x^3} - \sum_{i=1}^{n} ...
0
votes
0answers
15 views

The $d$-skeleton of a polytope is strongly connected

A polytope is the convex hull of a finite set of points in $\mathbb R^n$. The $d$-skeleton of a polytope is the set consisting of faces of dimension at most $d$. I would like to show that every ...
0
votes
0answers
40 views

hyperbolic constraint in SOCP

I learned that any hyperbolic constraint can be transformed as second order cone constraints. Such as if the constraint is, $x^2\leq w$ the second order constraint would be $$ ||[2x,w-1]||_2 \leq w+1 ...
0
votes
0answers
12 views

Decomposition of convex functions

Under what conditions is it possible to decompose a convex real-valued function $f$ and write it as an integral of the simple functions $g(x;w)=\max(x-w,0)$ and $h(x;v)=\max(v-x,0)$, where the ...
1
vote
0answers
49 views

why dual of $l_1$ norm is $l_\infty$ and vice versa

This might be a very dumb question but I am having a hard time to understand why dual of $l_1$ norm is $l_\infty$ and vice versa. The dual of a norm is denoted $\lVert\cdot\rVert_*$, defined as $$ ...
1
vote
0answers
29 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
1
vote
0answers
51 views

Proof or disproof of convexity for $f(x,y)=x^2y^2$

I'm trying to prove or disprove the convexity of $f(x,y)=x^2y^2$. This is part of a larger function but I think I proved that the rest of the function is convex using Hessian's. The other term in the ...
2
votes
0answers
34 views

shrinking a convex hull around a set of polygons

I'm trying to find (Or design) an algorithm that will let me, after I have a convex hull, progressively shrink the hull towards the polygon set via increasing some parameter. I.e., if we use the ...
3
votes
1answer
62 views

Subadditivity of the $n$th root of the volume of $r$-neighborhoods of a set

Let $A$ be a closed subset of $\mathbb{R}^n$. For $r>0$, let $A_r$ be the $r$-neighborhood of $A$, namely the set $\{x:\operatorname{dist}(x,A)\le r\}$. Let $f(r) = \mu(A_r)^{1/n}$ where $\mu$ is ...
2
votes
3answers
48 views

Convexity of a non linear optimization problem

I have a non linear optimization problem, namely: $$\min {\sqrt{(x-u)^2 + (y-v)^2 + (z-w)^2)}}$$ How can i show that the above function is convex. Doing via Hessian is a difficult task.
-1
votes
2answers
51 views

Is the function $\frac{f(x)}x$ increasing, if $f(x)$ is convex? [closed]

Suppose $x$ is real and positive. $f''(x) > 0$ (f is convex) is the function $h(x) = \frac{f(x)}x$ increasing? If so, is it strictly increasing? If yes, why? Thank you.
0
votes
1answer
17 views

Collecting terms in an example of checking concavity/convexity

$z=x_1^2+x_2^2$ $u=(u_1,u_2)$ $v=(v_1,v_2)$ Height of arc: $f[\theta u+(1-\theta )v]= f[\theta u_1+(1-\theta)v_1,\theta u_2 + (1-\theta)v_2 ]$ $= [\theta u_1+(1-\theta)v_1]^2 + [\theta u_2 + ...
5
votes
2answers
221 views

Set is Convex regardless of b

Let the function $f$ be convex, $f :\Bbb R^n \rightarrow \Bbb R$ and let $$S = \{x : f(x) \le b\}$$ The proposition states that the set $S$ is convex regardless of $b$. Can someone explain to me how ...
0
votes
3answers
48 views

What is the solution for this optimization problem?

I have an optimization problem in the form: $$\max (a-\bar{a})(b-\bar{b}) \qquad \text{subject to} \qquad a+b=1.$$ Here $\bar{a}$ and $\bar{b}$ are known values and both of them are positive. Let ...
1
vote
1answer
42 views

Continous family of $n$-gons

The statement of this problem asks to show that if $A$ and $B$ are two distinct convex $n$-gons there is a continous family of convex $n$-gons such that the first in that family is $A$ and the last is ...
4
votes
1answer
29 views

Which functions are the composition of convex functions?

The composition of convex functions is not necessarily convex or concave: For example, composing $f_1(x) = x^2-1$ and $f_2(y) = y^2$ gives $f_2(f_1(x)) = (x^2-1)^2$. Or consider $f_1(x) = x^2$ and ...
4
votes
1answer
37 views

What class of functions is characterized by the property $f[\operatorname{conv} A] \subseteq \operatorname{conv} f[A]$

It is well-known that the inclusion $f[\overline A] \subseteq \overline{f[A]}$ (for every subset $A$) characterizes continuous functions.1 Asking similar questions for other closure operators seems ...
0
votes
0answers
29 views

Convex optimization of a fractional objective function involving matrix determinants

I am interested in convex representation of the following fractional optimization problem. I have also described my approach in the following. However, as I am new to convex optimization, I am not ...
0
votes
2answers
30 views

SVD with Sparisty Penalties

I am trying to solve a problem like $$\min_{u,v} \Vert X-uv^T \Vert_F^2 + \beta \Vert v \Vert_1 \mbox{ s.t. } \Vert u \Vert_2 \le 1$$ where $X \in \mathbb{R}^{N\times N}$, $u, v \in ...
0
votes
4answers
57 views

for $I = [0,1]$, is $I\times I$ convex in $\mathbb{R} \times \mathbb{R}$?

for $I = [0,1]$, is $I \times I$ convex in $\mathbb{R} \times \mathbb{R}$? The definition of convex seems to be that $Y \subset X$ is convex in $X$ if $\forall a < b $ in $Y$ whole of $(a,b)$ ...
0
votes
0answers
21 views

Negative eigenvalue of a hessian matrix entails a local decrease in function value?

I was reading up on non-convex optimization, and I can across this sentence: "Since Hessian(f(w)) has a negative eigenvalue, there is always a point that is near w which has smaller function value" ...