# Questions tagged [convex-optimization]

Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

**0**

votes

**0**answers

36 views

### Concavity of a function after binomial transform and maximization

Suppose $f(x)$ is a one-dimensional discrete concave function, and $X(n,p)$ is Binomial random variable. Is the function $g(x)= \max_n \mathbb{E} f(x+X(n,p))$ also discrete concave?

**3**

votes

**0**answers

54 views

### Optimizing a multivariate symmetric (permutation-invariant) function

Let $\ell$ and $d$ be two integers such that $\ell \le d$.
I would like to find the global maxima of the following symmetric function $f\colon (0,1]^n \to \mathbb{R}$,
$$f(x_1, \ldots, x_n) := \sum_{\...

**1**

vote

**0**answers

20 views

### Second order necessary and sufficient conditions for convex nonsmooth optimization

For convex smooth optimization, first and second order necessary and sufficient conditions are well known. Does such standard second order necessary and sufficient conditions exist for convex ...

**0**

votes

**0**answers

9 views

### How to Create Point-Optimal Objective Functions

Here is a problem that has originated from some IP research i'm working on.
You are given a polyhedron $P$ in standard matrix inequality form of $Ax \le b$, $x \in \mathbb{R}^n$ as well as a point $...

**0**

votes

**0**answers

59 views

### Is dynamic programming suitable for a specific optimization problem?

Let $c,\,\mathcal{P}_0,\,\mathcal{P}_1,\,\mathcal{P}_2,\ldots$ be a sequence of positive real numbers.
Let $N\in\{1,\,2,\,3,\ldots\}$ and let $t\in\{0,\,1,\,2,\ldots\}$, with $N$ and $t$ fixed.
...

**0**

votes

**0**answers

33 views

### optimisation problem for unknown function

I have two variables function $z=f_{a,b}(x,y)$ ($a,b$ - some parameters), however I don't know its formula (I can compute its value for given $x,y$ and $a,b$). I would like to find minimum of this ...

**-1**

votes

**0**answers

43 views

### Maximum or minimum value

I appologize if the question is too elementary to MathOverFlow, but there was no answer or comment when I posted it to MathStackExchange. I just deleted the question on MathStackExchange and turned to ...

**0**

votes

**0**answers

26 views

### Convergence of a fixed-point algorithm for a concave objective function

Let's suppose we have an objective function $\max_\limits{x} \sum_\limits{i} f_i(x_i)$ with the constraint that $\ x_i \geq 0, \sum_\limits{i} x_i = 1$.
Each function $f_i$ is continuous and ...

**0**

votes

**1**answer

69 views

### Closed form solutions for maximal subsets of convex polytopes

I'm looking for any known exact results about inscribing simple convex bodies inside a convex polytope. The most famous is the Löwner-John ellipsoid, but as far as I understood in general there is no ...

**1**

vote

**0**answers

71 views

### Matrix completion in $2\times2$ case by nuclear norm minimization to guarantee rank $1$?

Does fixing diagonal entries and minimizing nuclear norm under weighted sum of entries conditions produce a rank $1$ matrix? I think the answer for this is no.
At least could it be true in $2\times2$ ...

**2**

votes

**1**answer

101 views

### Polygon of convex arcs

Convex polygons in the plane $R^2$ arise in linear programming where the constraints are linear. The objective linear function attains its maximum at a vertex of the feasible region(if exists).
Assume ...

**0**

votes

**0**answers

21 views

### A question related to parametric linear programming

Consider the following parametric linear problem:
\begin{align}
\min z(t)=c^T x\\
Ax=b(t)\\
0\leq x\leq u.
\end{align}
We know $z(t)$ is a piecewise linear function. Let $x(t_1)$ and $x(t_2)$ be the ...

**0**

votes

**2**answers

136 views

### Is it possible to “solve” iterative (convex/non-convex) optimization problems via learning (one-shot)?

I posted a following question in MSE, but I think it should be posted here in MO. Since I don't know how to transfer the post from MSE to MO, I have pasted the question below. Thank you in advance and ...

**1**

vote

**2**answers

55 views

### Alternative characterization of epi-convergence

I am struggling with the proof of a property of epi-convergence.
We need the following definitions:
For a sequence of sets $(C^\nu)_\nu$ in $\mathbb R^n$, the outer limit is the set $\limsup_\nu C^\...

**1**

vote

**0**answers

117 views

### The perturbation of a convex function can also be convex?

$ W^{1,\infty}(D)\ni f:D\to\mathbb R, (x,y)\mapsto f(x,y)$, is a strictly increasing on both dimensions (i.e. if $x_1>x_2$ then $f(x_1,y)>f(x_2,y)$), lipschitz continuous function defined on a ...

**3**

votes

**0**answers

56 views

### Legendre transform on signed measure space

Let $X$ be an open set in $\mathbb{R}^n$ and $M(X)$ be the space of finite signed measures defined on $X$. $L(p)$ is a lower-semicontinuous convex functional defined on $M(X)$. My question is: (1) ...

**1**

vote

**1**answer

52 views

### Efficient way to compute eigenvalue decomposition for following problem

I have an optimization problem
$$\begin{array}{ll} \text{minimize} & Tr(X^TAX) \\ \text{subject to} & X^TX=I
\end{array}$$
where $A\in R^{n \times n}$ and it is symmetric positive definite, ...

**2**

votes

**1**answer

51 views

### Given the following two assumptions, How to conclude $\lim_{k \rightarrow \infty}|\nabla g_r(y^{k})|=0 \ $?

Please refer attached 6-page short paper for details.
Let $M(y)=y+2r\nabla g_r(y)$.
Given $\ g_r(M(y^k))>g_r(y^k)+r|\nabla g_r(y^k)|^2, \forall k. \ $ (equation 36 in the paper)
and $ \ \lim_{k ...

**0**

votes

**0**answers

23 views

### Projecting a polyhedral cone onto its intersection with the infinity-norm ball

For a point in a convex polyhedral cone, $x\in \mathcal{C} = \{\sum_{i=1}^m \alpha_i r_i \vert \alpha_i \geq 0, r_i \in \mathbb{R}^n \}$, is there an efficient algorithm to project $x$ onto the ...

**1**

vote

**0**answers

58 views

### Solve simple stochastic variational inequality

Let $Z$ be a random variable with finite mean $\mathbb E[Z]$ and let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a convex l.s.c function which is differentiable at $z=1$ with gradient $\...

**1**

vote

**0**answers

26 views

### Dual representation of problems involving $f$-divergences

Studying some problems arising in decision-making under model uncertainty, I'm led to consider the following problems.
Let $\mathbb E_P$ and $\mathbb V_P$ denote the expectation and variance ...

**0**

votes

**1**answer

112 views

### How to solve this optimization problem efficiently? [closed]

Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...

**3**

votes

**1**answer

61 views

### Echange of Infimum Integral with Pointwise Infimum

Setup
Suppose that $U$ is a subset of $L^{\infty}_{\mu}(\mathscr{F})\cap L^1_{\mu}(\mathscr{F})$ defined by
$$
f\in U \Leftrightarrow g(f(x))\leq M \mbox{ and } f \in L^{\infty}_{\mu}(\mathscr{F})\...

**3**

votes

**1**answer

151 views

### it's convex sequence inequality

A sequence $a_0,a_1,\dots,a_n$ of real numbers is called concave if $a_{0}=0$, and for each $0<i<n$, we have $a_i\geq\dfrac{a_{i-1}+a_{i+1}}{2}$.
Find the largest $c(n)$ such that for every ...

**2**

votes

**1**answer

116 views

### Advantages of hyperbolic programming over semidefinite programming?

What are the advantages of a hyperbolic program over a semi definite program? SDPs can be used to represent a wide variety of algebraic constraints. Are there constraints that can be represented in a ...

**2**

votes

**0**answers

63 views

### convex approximation for a non convex function

Consider the function
$f\left( {{x_1},...,{x_M},{y_1},...,{y_N}} \right) = \left( {\sum\limits_{j = 1}^M {{\alpha _j}{x_j}} } \right)\left( {{e^{ - \sum\limits_{i = 1}^N {{\beta _i}{y_i}} }}} \right)$...

**2**

votes

**1**answer

92 views

### Convergence of a stochastic sequence?

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...

**0**

votes

**1**answer

68 views

### maximization of a log norm function

Considering the following optimization program:
$$
maximize \ \ \ \log \left( \|x\|_\infty \right)
$$
$$
subject \ to \ \ Ax\leq b, \ x \geq 0
$$
can we rewrite this program as a convex ...

**1**

vote

**1**answer

69 views

### LASSO problem but with a maximization instead of minimization

I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):
$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...

**0**

votes

**1**answer

49 views

### Quasiconvexity property of quasinorms

Schatten $p$ norm is convex when $p\geq1$ holds and if $p\in(0,1)$ it is quasinorm.
If $p\in(0,1)$ then is Schatten $p$ norm quasi convex? I am interested in definition of quasi convexity here https:...

**3**

votes

**0**answers

35 views

### Level sets of strongly convex and smooth functions

Let $f: \mathbb{R}^N \to \mathbb{R}$ be a $\alpha$-strongly convex and $\beta$-strongly smooth function, i.e.,
$$ f(x) + \langle\nabla f(x), y- x\rangle + \frac{\alpha}{2}\|y-x\|^2
\leq f(y) \leq f(x) ...

**4**

votes

**2**answers

235 views

### Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...

**1**

vote

**0**answers

36 views

### Minimum Preserving Transformations [closed]

If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then
$$
\operatorname{argmin}_{x \in X} f(x)
=
\operatorname{argmin}_{x \in X} g\circ f(x) .
$$
X and Y ...

**2**

votes

**1**answer

77 views

### Why the convexity condition on the definition of a face of a convex set?

A face of a closed convex set $X\subseteq\mathbb{R}^n$ is defined to be a set $F\subseteq X$ such that:
$F$ is convex.
Every line segment from $X$ whose interior meets $F$ is contained in $F$.
Is ...

**1**

vote

**2**answers

172 views

### Maximizing a function that is sum of gaussians

Let $\mathbf{x}_1,\dots,\mathbf{x}_n$ be given $n$ vectors in $\mathbb{R}^d$. Define the function
\begin{align}
\mathcal{K}(\mathbf{x},\mathbf{y})=
\alpha\exp(-\frac{||\mathbf{x}-\mathbf{y}||^2}{2\...

**5**

votes

**2**answers

157 views

### Is there any efficient solution of the matrix equation AXB + (AXB)' + cX = D

I am trying to find the symmetric solution $X\in \mathbb{R}^{p\times p}$ of following matrix equation:
$AXB + (AXB)^T + cX = D$
where $A,B\in \mathbb{R}^{p\times p}$ are symmetric positive ...

**9**

votes

**1**answer

427 views

### Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...

**0**

votes

**0**answers

65 views

### Iterative methods for minimizing sequences

Let $\mathbb{X}$ be a Banach space equipped with some norm $||\cdot||_\mathbb{X}$ and $F:\mathbb{X}\to\mathbb{R}$ be some linear functional. Suppose we are given a set $A\subseteq\mathbb{X}$ which is ...

**3**

votes

**0**answers

78 views

### Fenchel conjugate on a Hadamard manifold

Let $M$ be a Hadamard manifold and let $F:M\to\mathbb{R}$ be a real-valued convex function on $M$. What would be the Fenchel-Young conjugate of $F$?
In general for a real locally convex vector space $...

**3**

votes

**1**answer

189 views

### concavity of $\log [ (1+\frac{x_0}{1+x_0+x_1/2+x_2/4}) (1+\frac{x_1}{1+x_0/4+x_1+x_2/2}) (1+\frac{x_2}{1+x_0/2+x_1/4+x_2}) ]$

Let $f:~ [0,1]^3 \rightarrow \mathbb{R}$ be
$$
f(x_0,x_1,x_2)= \log \left[ \left(1+\frac{x_0}{1+x_0+\frac{x_1}{2}+\frac{x_2}{4}}\right) \left(1+\frac{x_1}{1+x_1+\frac{x_2}{2}+\frac{x_0}{4}}\right) \...

**4**

votes

**3**answers

142 views

### Quasi-concavity of $f(x)=\frac{1}{x+1} \int_0^x \log \left(1+\frac{1}{x+1+t} \right)~dt$

I want to prove that function
\begin{equation}
f(x)=\frac{1}{x+1} \int\limits_0^x \log \left(1+\frac{1}{x+1+t} \right)~dt
\end{equation}
is quasi-concave. One approach is to obtain the closed form ...

**1**

vote

**0**answers

36 views

### Lower semicontinuity of proximal gradient descent sequence

I'm using an alternate optimization scheme to minimize a function $F(a,b,c) = G(a,b,c) + H(c)$ where $G$ is continuous and differentiable, $H$ is not differentiable but lower semi-continuous and ...

**0**

votes

**1**answer

139 views

### Strict complementary slackness for semidefinite programs with strong duality

By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary ...

**3**

votes

**1**answer

107 views

### Strong polynomial algorithm for linear programming

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?

**2**

votes

**1**answer

110 views

### Quasi-concavity of $f(x)=(1-\frac{x}{1000})\log_2(1+2^x)$ on $[0~1000]$

I want to prove that function $f:[0~1000]\rightarrow R$, $$f(x)=(1-\frac{x}{1000})\log_2(1+2^x)$$ is quasi-concave. Any idea how to do the proof? I already tried to prove that any super-level set is ...

**4**

votes

**1**answer

316 views

### Minimize the variance of a Boltzmann distribution

N.B.: Sorry for cross-posting from https://stats.stackexchange.com/posts/347804/edit (I realized it was the wrong venue for the question, but couldn't find an easy way to transfer the question here).
...

**1**

vote

**0**answers

48 views

### Relative interior of a normal cone at a face of a convex polytope?

Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$.
Consider the normal cone of $A$ at $F$:
$C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...

**1**

vote

**1**answer

166 views

### Is this parametrized semidefinite program convex?

I am considering an optimization problem of the form:
\begin{equation}
\begin{split}
f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\
&\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\
&\;\;\;\;\;\;\;\;\;\;\; \...

**0**

votes

**0**answers

44 views

### Is this set of polynomial constraints convex? Can I optimise it?

Basically I want to optimise a problem with a constraint on the (variable dependant) roots of a polynomial, which I would like to be assigned depending on other constraints.
I reduced the problem to ...

**0**

votes

**1**answer

47 views

### Linearly constrained saddle-point optimization

Let $f(x,y)$ be a smooth (twice differentiable) saddle function (convex in $x$ and concave in $y$), where $f \colon X \times Y \rightarrow \mathbb{R}$, and $X \subset \mathbb R^n$, $Y \subset \mathbb ...