# Questions tagged [convex-optimization]

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

549
questions

**0**

votes

**1**answer

46 views

### Minimum mean over all random variables subject to logarithm constraint

Does the following problem have a solution?
$$
\min_X \mathbb{E} X
\quad\text{subject to}\quad
\mathbb{E} \log X = C.
$$
Here, the minimization is with respect to all integrable random variables $X$ ...

**-1**

votes

**1**answer

57 views

### Minimize a function through its upper approximation

I have some function $f(x) : \mathbb{R}^n \to \mathbb{R}$ (n is about several thousands, say $1000 \leq n \leq 10000$) to minimize over some constraints $g(x) \leq 0$ (by the way, $g$ is quadratic ...

**4**

votes

**1**answer

113 views

### Minimization of a discrete valued function

$$
\min_{f} \sum_{i=1}^n \max \left( 0, 2f(i) - f(i-1) -f(i+1)\right),
$$
where the minimum is taken over all the functions $f$ from $\{0,1,2,\ldots,n+1\}$ to $[0,x]$, $x <1$, such that $f$ is non-...

**0**

votes

**0**answers

9 views

### Constrained maximin optimisation problem

Let
i) $\mu = [\mu_1,\mu_2,\mu_3]\in\mathbb{R}^3$, such that $\mu_2 > \mu_1$, $\mu_2 >\mu_3$ fixed,
ii) $\lambda = [\lambda_1,\lambda_2,\lambda_3] \in \mathbb{R}^3$ such that $\lambda_1 \geq \...

**0**

votes

**0**answers

83 views

### How to solve optimization problem with matrix constraint?

I'm working with the following optimization problem below.
$$\min_{\Pi} \left[
\frac{1}{4 \lambda
}\left((\Pi\vec{1}-s)^T K(\Pi\vec{1}-s) + \left(\Pi^T \vec{1}-t\right)^T K \left(\Pi^T \vec{1}-t\...

**0**

votes

**0**answers

85 views

### A minimax optimization with expectation operator

Let $\mathbf{X}$ be an $m\times n$ random matrix with Gaussian i.i.d entries with zero mean and unit variance. How we can think about the following optimization
\begin{align}
\max_m\mathbb{E}_\mathbf{...

**0**

votes

**1**answer

25 views

### Basis pursuit algorithms for exponentially large matrices?

Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is $\arg\min_x\lVert x \rVert_0$ subject to $y = Ax$, where $A$ is an exponentially large matrix ...

**2**

votes

**1**answer

58 views

### Max-norm projection of a Hermitian matrix onto the set of positive semidefinite matrices

For a given Hermitian matrix $A$ (i.e. complex matrix with $A_{ij}^{\ast}=A_{ji}$) find its max-norm projection onto the set of complex positive semi-definite matrices:
$$\Pi(A)=\mathrm{argmin}_{M\...

**-2**

votes

**0**answers

51 views

### the subdifferential at points of differentiability in infinite dimensional space

Let $ f:X \longrightarrow (-\infty,\infty] $ that $X$ is infinite dimensional space and $f$ be a proper convex function and $ x\in int(dom(f))$.
Is it the case that: if $f$ is differentiable at $x$, ...

**1**

vote

**1**answer

63 views

### $\arg\max$ in the dual norm of the nuclear norm

Given a matrix $X \in \mathbb{R}^{m \times n},$ then the spectral norm is defined by
$$\left \| X\right\| := \max\limits_{i \in \{1, \dots, \min\{m,n\}\} }\sigma_i (X)$$
whereas the nuclear norm is ...

**-1**

votes

**1**answer

37 views

### Compute the proximal of a mapping [closed]

Let $ f: \mathbb{R}\longrightarrow \mathbb{R}$: compute
proximal of following mapping
$$ f(x)= \sqrt {1-x^2} $$
for $ x \geq 0 $
I know that the proximal is given by
$$ \operatorname{prox}_{\!...

**2**

votes

**0**answers

31 views

### First moments of uniform distribution on a curve from (0,0) to (1,1) in two-space

The curve $\Gamma$ in $\mathbb{R}^2$ is defined by a continuous and monotonically increasing function $f(x)\in\text{C}[0,1]$, where $f(0)=0$, $f(1)=1$.
Let $(X,Y)$ is jointly and uniformly ...

**0**

votes

**0**answers

16 views

### Derivation of dual for infinite linear program

I'm reading the section on Linear Programming in Barbu and Precupanu's Convexity and Optimization in Banach Spaces, and had a couple of questions concerning their derivation of the dual problem for ...

**0**

votes

**0**answers

30 views

### Sub optimal algorithm for linear programming

Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...

**2**

votes

**0**answers

44 views

### Proving the existence of a dual for an infinite linear program

I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...

**0**

votes

**0**answers

26 views

### ADMM for solving linear systems

I would like to use ADMM for solving $Mx=b$, where $M\in \mathbb{R}^{R\times R}$ is symmetric and positive definite. I know that a lot of methods will do for me in this case, but I'm specially ...

**1**

vote

**1**answer

90 views

### Log Fractional optimization problem

Let $\mathbf{x}$ be a vector of $N$ variables. Then, how can I solve the following optimization problem?
\begin{align}
\max_\mathbf{x}&\quad \sum_{n} \log(1+\frac{x_n}{\alpha+\sum_{m}\beta_m^{(n)}...

**5**

votes

**1**answer

85 views

### When is the log-permanent concave?

Let $\operatorname{PSD}_n$ be the cone of $n\times n$ semidefinite positive matrices. For any $X\in \operatorname{PSD}_n$, define $$f(X)=\log(\det(X)).$$ Then $f$ is a concave function on $\...

**2**

votes

**0**answers

120 views

### Optimization with parametric constraints: solution maps

For constrained optimization problems
$$ \begin{array}{ll} \min\limits_{x \in \mathbb R^n} & f(p, x) \\
\text{s.t.} & x \in C \end{array} $$
where $p \in \mathbb R$ is a parameter, we can ...

**2**

votes

**1**answer

119 views

### Is the optimum of this problem convex in the constraint parameter?

Let $f:\mathbb R^+ \to \mathbb R$ be a smooth function, satisfying $f(1)=0$, and suppose that
$|f|$ grows with the distance from $1$: $|f(x)|$ is strictly increasing when $x \ge 1$, and strictly ...

**0**

votes

**0**answers

44 views

### Lagrange multiplier theorem for nonnegative integral functional (fix issue with infinite integral)

Let
$(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space;
$N\in\mathbb N$;
$p_i$ be a probability density on $(E,\mathcal E,\lambda)$ for $i\in\{1,\ldots,N\}$;
$w_i:E\to\mathbb R$ be $\mathcal ...

**0**

votes

**0**answers

46 views

### Find minimizer of nonnegative integral functional over a closed convex subset of $L^2$

Let
$(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space and $$\lambda f:=\int f\:{\rm d}\lambda$$ for $\lambda$-integrable $f:E\to\mathbb R$;
$p:E\to[0,\infty)$ be $\mathcal E$-measurable ...

**0**

votes

**0**answers

20 views

### Help finding sufficient conditions for unique maximizer to constrained maximization problem

I am working on a paper, and I have run into a constrained maximization problem. I would like to find some sufficient conditions for the maximizer (particularly, p) to be unique. Given my limited ...

**0**

votes

**1**answer

67 views

### positivity of quadratic form minus linear form on the simplex

Let us $a_{ij}$ be the elements of a n dimensional covariance matrix. Can we prove that:
$ 1-\sum_{k=1}^n a_{ik} \lambda_k + \sum_{j=1}^n \sum_{k=1}^n \lambda_j a_{jk} \lambda_k >0$
for $i=1 \...

**0**

votes

**0**answers

35 views

### Computational complexity of optimization algorithms using random algorithm theory

A fundamental and undoubtedly much-studied problem is that of determining not only whether or not an optimization algorithm converges to its optimum but also how fast it converges (see a discussion on ...

**1**

vote

**0**answers

34 views

### Pros and cons of using integer programming alone or combined integer and global optimization?

First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...

**3**

votes

**1**answer

112 views

### Maximum of sum of exponential function

Let $x_1,\dots,x_n$ be a set of given vectors in $\mathbb{R}_{+}^d$. Let $c_1,\dots,c_n$ be given positive constants. I am interested in finding the vectors $w_1,\dots,w_n$ in $\mathbb{R}_{+}^d$ that ...

**2**

votes

**1**answer

98 views

### Hardness of concave minimization problem

I have an optimization problem $\underset{x}{\min} ~ c(x) - k \cdot x$ where $c(x)$ is a non-decreasing concave function with $c(0) = 0$, $x \in C \subseteq \mathbb{R}^d_{\geq 0}$. By non-decreasing, ...

**0**

votes

**1**answer

126 views

### Finding the conjugate of a function

I know that the Fenchel conjugate of a function is
$$f^*(x^*) = \sup_x\{\langle x, x^*\rangle - f(x)\}.$$
However, how do I find the Fenchel conjugate of the function
$$f(x) = \frac{1}{p}\sum\limits_{...

**2**

votes

**1**answer

242 views

### When does $\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$ hold for a real function $f(x,y)$?

Let $f(x,y)$ be a real function of the variables $x,y$ (which can be real vectors). Under what conditions do we have the following equality:
$$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$$
For ...

**5**

votes

**1**answer

176 views

### Generalization of minimal selection theorem

Consider a metric space $X$ and a set-valued map $F : X \to \mathbb{R}^{n}$. We define the minimal selection
\begin{equation*}
m(F(x)) := \arg\min \big\{ \lvert u \rvert : u \in F(x) \big\},
\end{...

**1**

vote

**0**answers

38 views

### Subgradient chain rule

Suppose $$F:\mathbb{R}^n \to \mathbb{R},\; F(x)=\mathrm{max}_\mathrm{eig}(C-\mbox{diag}(x)).$$
I am trying to find a subgradient of $F$ at $x_0$. A subgradient of $\mathrm{max}_\mathrm{eig}$ is given ...

**1**

vote

**1**answer

89 views

### A close-form solution for a simple quadratic optimization problem

Is there any closed form solution for the following optimization problem:
\begin{align}
&\min_{\mathbf{X},\alpha} \mathrm{Tr}[(\mathbf{A}-\mathbf{B}\mathbf{X})(\mathbf{A}-\mathbf{B}\mathbf{X})^{\...

**0**

votes

**0**answers

77 views

### Finding a specific solution to $X^T\Sigma X = D$

I'm looking to solve for a specific $X$ in the following equation:
$$X^T\Sigma X = D,$$
where $\Sigma \succ 0$, $D$ is a diagonal matrix with strictly positive entries, and all matrices are square. It ...

**2**

votes

**0**answers

45 views

### Variational forms of non-convex functions

I am trying to understand what kind of variational forms exist for non-convex functions. Alternatively, are there conjugate forms which attain strong duality? For a non-convex function $f$, I am ...

**2**

votes

**1**answer

121 views

### Joint convexity of trace of matrices

Let $\Gamma_{m\times m}$ be a diagonal matrix with positive diagonal entries and $\mathbf{A}_{m\times m}$ be an arbitrary matrix. Then, is the following trace function jointly convex on $\Gamma_{m\...

**2**

votes

**0**answers

47 views

### Zeroth order method with near-optimal rate that works in practice?

I want to find a ZO (zeroth-order, i.e. no access to gradient) algorithm to minimize a strongly-convex deterministic objective (say, as a sum of smooth and nonsmooth proximable functions). I want such ...

**1**

vote

**0**answers

114 views

### Minimax optimization of diagonal entries of function of matrix

Let $\mathbf{A}$ and $\mathbf{U}$ be arbitrary complex $M\times N$ and $N\times M$ matrices, respectively. Let denote superscript $(\cdot)^{\dagger}$ and $(\cdot)^{\mathrm{H}}$ as pseudo-inverse and ...

**2**

votes

**0**answers

26 views

### Criterion for optimality in two-step optimization procedure

Fix $n\in \mathbb{N}$ with $n>1$, let $X$ be an infinite-dimensional topological vector space and suppose that one is given:
continuous functions $F_0,\dots,F_n:X\rightarrow [0,\infty)$ for which $...

**4**

votes

**0**answers

188 views

### analytic approximations of the min and max operators

Question:
What is the state of the art on analytic approximations of $\min$ and $\max$? My hunch is that numerical analysts probably have a better solution than the one I propose here.
For any $\...

**1**

vote

**1**answer

111 views

### Matrix Completion SDP Relaxation and Duality

I am studying the matrix Completion problem, as well as its SDP relaxation. However, I am having trouble deriving the final SDP form of the matrix completion problem. I will give some background, ...

**1**

vote

**0**answers

94 views

### Showing existence of a solution to an underdetermined system of equations with non-negativity constraints

Let $K$ be a positive integer, let $p\in (0,1)$, and let $\{W(k,i),W^B(k,i), \varphi_k(i)\}_{1\leq i\leq k\leq K}$ be variables.
I need to prove that there exists a solution to the following system ...

**0**

votes

**0**answers

57 views

### Can we numerically solve this saddle-point problem?

Let
$(E,\mathcal E,\lambda)$ be a measure space;
$f:E\to[0,\infty)^3$ be $\mathcal E$-measurable with $\|f\|\in\mathcal L^2(\lambda)$;
$\tilde p:=\alpha_1f_1+\alpha_2f_2+\alpha_3f_3$ for some $\...

**0**

votes

**0**answers

53 views

### Numerically solve a specific saddle-point problem

Let $(\Omega,\mathcal E,\mu)$ be a probability space, $k\in\mathbb N$, $$W:=\left\{w:E\to[0,\infty)^k:\sum_{i=1}^kw_i=1\;\mu\text{-almost surely}\right\},$$ $G$ be a finite nonempty set and $a^{(g)}:E\...

**1**

vote

**2**answers

98 views

### Monotonicity of maximum of convex combination of two scaled concave functions

Let $f:R\rightarrow R$ be a concave function with a unique and finite maximum. Let $$g(x, \beta) = \beta f(\alpha \cdot x) + (1-\beta) f((1-\alpha) \cdot x), $$ where $\alpha \in [0,1/2]$ and $\beta \...

**3**

votes

**0**answers

54 views

### subgradient in a predual under weak* continuity

Let $X$ be a Banach space. Suppose $f:X^*\to\mathbb R\cup\{\infty\}$ is convex, has closed and bounded (and so weak*-compact) effective domain, and is weak*-continuous on its effective domain. In ...

**0**

votes

**0**answers

94 views

### How are the $L^2$ and $\sup$ norms related on the space of strongly convex functions?

Given a convex compact set $X \subset \mathbb R^d$ with interior containing the orign let $V$ be the space of all smooth functions $f: X \to \mathbb R$ with the properties:
The function is strongly ...

**0**

votes

**0**answers

39 views

### Strict complementarity for quadratic programming

Consider the quadratic program
\begin{align*}
\text{min}_{x\in \mathbb{R}^n} \ &\tfrac{1}{2}x^THx + f^Tx\\
\text{st.} \ & Ax \leq a \\
& Cx = c \\
\end{align*}
for matrices $A\in \mathbb{R}...

**0**

votes

**0**answers

30 views

### Characterization of global subdifferentiability

Let $X$ be a locally convex space, $D \subseteq X$ a nonempty compact convex set, and $f: D\to\mathbb R$ a continuous convex function.
Question: Is there any known, interesting, alternative ...

**0**

votes

**0**answers

119 views

### Can we find a minimizer of this linear smooth integral functional?

Let
$(E,\mathcal E,\lambda)$ be a measure space;
$f:E\to[0,\infty)^3$ be $\mathcal E$-measurable with $\|f\|\in\mathcal L^2(\lambda)$;
$\tilde p:=\alpha_1f_1+\alpha_2f_2+\alpha_3f_3$ for some $\...