Skip to main content

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

Filter by
Sorted by
Tagged with
0 votes
0 answers
28 views

Hessian matrix negative definite except in a finite number of points

I'm dealing with optimization problems and I have found myself wondering on this statement: If $f$ is twice differenciable on $\mathcal{D}$ and its hessian matrix $\mathbf{H}_f$ is negative definite ...
Goug's user avatar
  • 31
-2 votes
0 answers
21 views

Convexity of zero of partial derivative of a convex fonction. [closed]

Is there an integer d, an integer $1 \le i \le d$ and a convex function $f : \mathbb{R}^d \rightarrow \mathbb{R}$. Such that the set $\{x \in \mathbb{R}^d / \frac{\partial f}{\partial x_i}(x) =0 \}$ ...
MikeProgrammeur's user avatar
2 votes
0 answers
36 views

Finding the optimal distribution that maximises

Consider two discrete random variables $X$ and $Y$. Let $Q$ be a distribution over $X, W$ be a conditional distribution $Y$ given $X, U$ be a conditional distribution $X$ given $Y$, and $s$ and $r$ be ...
pmoi's user avatar
  • 97
0 votes
0 answers
33 views

Gradient and intermediate value theorem

I'm having trouble with an optimization problem. I have a continuous and concave objective function $\mathcal{O} : \mathbb{R}^n \longrightarrow \mathbb{R}$. I have strong evidence (numerical ...
Goug's user avatar
  • 31
-1 votes
0 answers
43 views

Is a quadratic program convex with respect to its parameters? [closed]

Consider a quadratic program $$ \min_z \quad \frac{1}{2} z^T A z + b^T z $$ $$ s.t. \quad Cz \leq d $$ with $A$ positive definite. For any choice of $A$ and $b$ we get a solution $z^*$. Is the ...
FlavioRed's user avatar
1 vote
0 answers
19 views

Quadratic Optimization with positivity, equality constraints - Literature Review?

I'm trying to solve a problem of the form $\min x^T Q x$ such that $Ax = b$ and $x_i \ge 0$ for all components $i$; $x, b$ are vectors; and $Q, A$ are matrices. In this case $Q$ is square and positive ...
Faraz Masroor's user avatar
0 votes
0 answers
27 views

Minimizing a Function with Nonlinear Constraints

I am trying to minimize the function $f(x, y) = \frac{1}{x} + \frac{1}{y}$ subject to the constraints: $$ x^3 + \frac{x}{x + y} y^3 - c \leq 0, $$ $$ x \geq 0, $$ $$ y \geq 0. $$ I have attempted to ...
Resting Platypus's user avatar
0 votes
0 answers
49 views

Is there a way to project onto the intersection of a box and a half-space in closed form?

My problem is to project a fixed point $\hat{x}\in\mathbb{R}^n$ onto the intersection of two convex closed sets, in particular a box and an half-space. Formally, we want to find $$ \arg\min_y\|\hat{x}-...
alice owo's user avatar
0 votes
0 answers
38 views

Degrees of freedom in mirror descent

The mirror descent algorithm makes certain choices which appear somewhat arbitrary, and so for each of them I am hoping for an understanding (maybe a proof) of why they are necessary, or at least some ...
oat's user avatar
  • 1
1 vote
0 answers
40 views

How does this optimal x change with this parameter?

Consider an optimization problem $$\max_x V = f(x,a) + g(x,a)$$ where $\frac{\partial^2 f}{\partial x^2},\frac{\partial^2 g}{\partial x^2} < 0$ Let $x^*$ (the optimal $x$) be such that $$\frac{\...
Mwazr A's user avatar
  • 51
1 vote
0 answers
64 views

Converting $x^3$ Optimization to an Equivalent LP Problem

Suppose we want to find the minimum of a a strictly increasing function $f: [-a, a] \to \mathbb{R} $, for some $a > 0$, which is also concave in $[-a, 0]$ and convex in $[0, a]$ (exactly like the $...
Apostolos's user avatar
0 votes
0 answers
28 views

Proximal point operator of maximum of functions

I want to know whether the proximal point operator of a function with a special structure can be expressed in terms of simpler proximal point operators. Setup: For a proper, convex and lower ...
AverageJoe's user avatar
0 votes
0 answers
25 views

How to express fractional programming problem with DCP

Let $f(\theta) \triangleq \mathbf{a}^T(\theta) \mathbf{x} + b(\theta)$, where $\mathbf{a}(\theta) \in \mathbb{C}^N$, $\mathbf{x} \in [0,1]^N$, $b(\theta) \in \mathbb{C}$, with $\theta \in [-\pi,\pi[$. ...
I. Iudice's user avatar
1 vote
1 answer
24 views

Question on nestorovs theorem dealing with the oracle lower bound for the iteration complexity

Right now I am studying the nesterov accelrated gradient where my objective is convex and has lipschitz continuous gradients. In my lecture notes it is mentioned that the NAG is special in the sense ...
Sen90's user avatar
  • 453
0 votes
1 answer
41 views

Concavity of Distance-to-Boundary Function

Let $B := \bar{B}_{R}(0) \subseteq \mathbb{R}^2$ be the closed ball of radius $R$. The distance-to-boundary function $d: \mathbb{R} \rightarrow \mathbb{R}$ gives the distance of any point $x_0$ to the ...
V. Elizabeth's user avatar
1 vote
1 answer
49 views

Why does $\textbf{tr}(F_{i}(\nabla\,\text{log}\,\text{det}(F))) = \textbf{tr}(F_{i}F^{-1})$?

In Example A.3 of Convex Optimization by Boyd and Vandenberghe, they write that $$\textbf{tr}(F_{i}(\nabla\,\text{log}\,\text{det}(F))) = \textbf{tr}(F_{i}F^{-1})$$ where $F \in R^{\,p,p}$ is positive ...
Tim's user avatar
  • 187
1 vote
1 answer
32 views

Positive semi-definitiveness condition for multidimensional minimization case

We study the nonlinear problem \begin{equation} \underset{\mathbb{R}^2}{\text{min}}f(x) \end{equation} where $f(x)=x_1^2+x_2e^{x_1}-x_1x_2+x_2^2$ Evaluate whether the problem is convex. For a ...
Superunknown's user avatar
  • 2,973
0 votes
0 answers
18 views

Regarding convergence rates, is it important to distinguish between convergence rate of $(x^t)$ and $(f(x^t))$?

Right now I am dealing with iteration complexity of different gradient descent and stochastic gradient descent algorithms. Most of the time one assumes (strongly) convex objectives and smooth ...
Sen90's user avatar
  • 453
1 vote
1 answer
63 views

Proving the two optimization are equivalent or not

Here are two optimization problems: $$ (P) : \inf_{x} [ f(x)|g(x) \leq 0 ] \text{ where } g(x) = \inf_{y} [ h(x,y)|y \in Y ] $$ $$ (Q) : \inf_{x,y} [f(x)|h(x, y) \leq 0, y \in Y ] $$ Are they ...
Albertvosky's user avatar
0 votes
0 answers
24 views

Minimize $\mathrm{tr}((FK + G)^TQ(FK + G) + K^TRK)$ over block lower-triangular matrices $K$

I want to solve the minimization problem $$ \inf_{K\in\mathcal{K}}\mathrm{tr}\left(\left((FK + G)^TQ(FK + G) + K^TRK\right)\Sigma\right) $$ where $\mathcal{K}$ is the set of block lower triangular ...
calculus_crusader's user avatar
-1 votes
1 answer
66 views

Steepest descent direction

Consider the unconstrained optimization problem $$\underset{\mathbb{R}^n}{\text{min}} f(x) $$ with $$ f (x) = \frac12 x^T Qx - c^T x + \frac{1}{2\mu}(a^T x - \beta)^2 , $$ in which $c$ and $a$ ...
Superunknown's user avatar
  • 2,973
0 votes
0 answers
54 views

$||Ax|| \leq ||x||_{*} \leq \sqrt{n} ||Ax||_2$

Show that exists a norm $||.||_{*}$ such that for each matrix satisfying $$||Ax||_2 \leq ||x||_{*} \leq \sqrt{n} ||Ax||_2$$ exists a vector $x$ such that $||x||_{*} = \sqrt{n}||Ax||_2$. This is ...
jacopoburelli's user avatar
2 votes
0 answers
57 views

Covariances not below $\Sigma$

$\Sigma_0,\Sigma_1,\dots,\Sigma_K$ are real covariance matrices. I’m interested in the set of matrices $$\bigcap_{k=1}^K \left\{x: 0 \preceq x \preceq \Sigma_0, \ x\not\prec\Sigma_k\right\}.$$ I’m ...
Christian Chapman's user avatar
3 votes
0 answers
135 views

Improving Ellipsoid Theorem $t+\mathcal{E} \subseteq K \subset t + c\cdot n \mathcal{E}$

Setting: Definition (ellipsoid): An ellipsoid is $\mathcal{E} := \{y \in \mathbb{R}^n : ||A^{-1}(y-t)|| \leq 1\}$, i.e images under a given $A$ of full rank of the unit closed ball of $\mathbb{R}^n$. ...
jacopoburelli's user avatar
2 votes
1 answer
98 views

How to deal with ill conditioned optimization problem (Sinkhorn barycenter)

Problematic (Debiased Sinkhorn barycenter, proposed by H.Janti et al.): Let $\alpha_1, \ldots, \alpha_K \in \Delta_n$ and $\mathbf{K}=e^{-\frac{\mathrm{C}}{\varepsilon}}$. Let $\pi$ denote a sequence ...
Tung Nguyen's user avatar
  • 1,238
0 votes
0 answers
44 views

Least Squares Function Approximation and Convexity of Functions

I have been reading about Least Squares function approximation and am dealing with the following definition: Let $f$ be continuous on $[a,b]$ and let $W$ be a finite dimensional subspace of $C[a,b]$. ...
MattKuehr's user avatar
  • 197
0 votes
0 answers
20 views

Concave maximization over $d$-dimensional simplex.

Can either an analytic solution or the dual be characterized for the following concave maximization: $v:= \underset{w \in \Delta_d}{\max} \sum^{d}_{i=1}\frac{1}{\sqrt{1+b_i/w_i}}$ where $\Delta_d$ ...
Sushant Vijayan's user avatar
1 vote
0 answers
60 views

Prove $f(x)=\log\left(\frac{1-x^a}{1-x}\right)$ is convex

Prove that $f(x)=\log\left(\frac{1-x^a}{1-x}\right)$, $x\in (0,1)$ is convex for $a\geq 5$. I've tried with the classical characterization of convex functions: $$f(\theta x + (1-\theta)y) \leq \theta ...
Pablo Yeste Blesa's user avatar
0 votes
0 answers
15 views

SOCP and polynomial time constraints

Given a multi-variable function $f$ to minimize subject to some constraints, I am confused after reading few papers and the Wikipedia entry about SOCP(second order cone programming). I already know ...
user avatar
-1 votes
2 answers
38 views

Suspicious function for calculating cardinality via $\ell_0$ norm [duplicate]

I'm confused about a function for calculating a vector's cardinality via the $\ell_0$ norm as described in an "Optimization Models" textbook (ISBN: 9781107050877). Here's a photo of that ...
MilesF's user avatar
  • 9
0 votes
1 answer
24 views

Orthogonal Projection onto a Polyhedron (Matrix Inequality)

How to efficiently solve: $$\begin{align*} \arg \min_{\boldsymbol{X}} \quad & \frac{1}{2} {\left\| \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} \\ \text{subject to} \quad & \begin{aligned}...
Royi's user avatar
  • 8,984
0 votes
0 answers
17 views

Counter-example request: set such that bilinear optimisation against ellipsoid is hard

I'm reviewing a paper that has a pretty obvious false claim, but I'm really blanking on a simple counterexample. The claim is that for any $X$ subset of the closed Euclidean $n$-dimensional unit ball ...
Oxonon's user avatar
  • 266
0 votes
0 answers
18 views

PCA with two subspace

Given $N$ data points $[a_1,\dots,a_N]$, mathematically the PCA is to find a rank-r subspace $S$ such that the distances between these points and the subspace are minimized, i.e., \begin{equation} S = ...
Yunfei's user avatar
  • 145
1 vote
2 answers
48 views

Orthogonal Projection onto the Convex Hull of Permutation Matrix

Given a matrix $\boldsymbol{Y} \in \mathbb{R}^{m \times n}$ where $n \leq m$. I want to find its projection onto the Convex Hull of Permutation Matrices: $$ \mathcal{P} = \left\{ \boldsymbol{P} \mid \...
Royi's user avatar
  • 8,984
1 vote
2 answers
57 views

Is $X \mapsto \operatorname{tr}( DXAX^TD^T - DXCD - DC^TX^TD)$ a convex function?

I know that $ g \left( X \right) = \operatorname{tr}( XAX^T - XC - C^TX^T )$ is a convex function. Is $ h \left( X \right) = \operatorname{tr}( DXAX^TD^T - DXCD - DC^TX^TD )$ still a convex function? ...
Josh Bolton's user avatar
1 vote
0 answers
58 views

How to set up a convex concave procedure for the minimization of $abc$?

From this post, it seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure. Out of curiosity, suppose that I have a simple problem that is $\begin{...
Tuong Nguyen Minh's user avatar
0 votes
2 answers
63 views

How to show that the set $ M = \{ (x,y) \mid x + 4y^2 \leq 4 \} $ is convex?

I need to show that the following set is convex using the definition: $ M = \{ (x,y) \mid x + 4y^2 \leq 4 \} $. I have considered 2 points: $ (x_1, y_1) \in M $, $ (x_2, y_2) \in M $. Then, we have ...
36n's user avatar
  • 15
0 votes
1 answer
21 views

How to bound scalarized gradient difference norm in terms of smoothness in convex optimization?

We know if a convex function is $\mu$-smooth, the following inequality is true: $\| \nabla g (u) - \nabla g(v) \| \leq \mu \|u-v\|$ I want to derive an bound for the following slightly different term ...
randomprime's user avatar
0 votes
1 answer
30 views

Sundaram Theorem 8.5

I have one question about this theorem. I do not understand the part after "In particular," in the picture. I assume that ``any monotone transformation'' means that this includes ...
Tucker's user avatar
  • 36
0 votes
0 answers
30 views

Incremental algorithm for 2D Linear Programming question for feasible points

I have the following problem that I want to solve using linear programming: $\max\{-3x+12y\}$ (objective function) and 4 contraints: $-x+2y\leq-1$, $2x-3y \leq 6$, $x-3y \leq 0$, $x+y\leq12$ I start ...
average_discrete_math_enjoyer's user avatar
1 vote
1 answer
145 views

A hard optimization problem

Consider the following function, for $1\leq j \leq N$ $$\tag{1} y_j=\sum_{k=0}^{M} \frac{e^{-\sum_{|i|\leq k}(k-|i|)x_{j+i}/v}-e^{-\sum_{|i|\leq k}(k+1-|i|)x_{j+i}/v}}{\sum_{|i|\leq k} x_{j+i}} $$ for ...
sam wolfe's user avatar
  • 3,435
0 votes
0 answers
25 views

Questions relating to the definition of the Frechet derivative

My knowledge in multivarible calculas or real analysis is very limited. Please excuse the possibly ill-posed question and the use of intuivive explanation. Thanks for your understanding. As I ...
Tim's user avatar
  • 187
1 vote
1 answer
45 views

Lattice width of $conv(0,ne_1,\cdots,n e_n)$

Given a subset $K \subseteq \mathbb{R}^n$ we define the lattice width of $K$ : $$\omega(K) = \min_{d\in \mathbb{Z}^n - \{0\}} \max_{x,y \in K} d^t(x-y)$$ With $K = conv(0,ne_1,\cdots,n e_n)$ how to ...
jacopoburelli's user avatar
4 votes
1 answer
112 views

Conceptual difference between regularized and constrained optimization.

In the literature of compressed sensing, one encounters optimization problems as shown in equation (1) and (2). focusing on the conceptual differences between regularized optimization and constrained ...
ACR's user avatar
  • 297
3 votes
1 answer
107 views

Efficient algorithm to solve a sparse recovery problem

I come across with a problem of the form $y=Hx + z \in \mathbb{R}^m$, where $z\in \mathbb{R}^m$ is the noise vector, and $x \in \mathbb{R}^N$ is partially known. $H\in \mathbb{R}^{m \times N}$ can be ...
南洋小學生's user avatar
2 votes
3 answers
102 views

Is $C = \{ x \in \mathbb{R}^n \:|\: \textbf{1}^T(x)_- \leq \frac{1}{2}\textbf{1}^T(x)_+ \}$ a convex set?

We define $(x)_+ = \textbf{max}\{0, x\}$ and $(x)_- = \textbf{max}\{0, -x\}$, so $x = (x)_+ - (x)_-$. Let $\textbf{1} \in \mathbb{R}^n$ be a column vector whose entries are $1$. The $\textbf{max}$ ...
tcm's user avatar
  • 23
1 vote
1 answer
67 views

Convexity of $\ln(a^\top x) - \sum_{i=1}^n \ln(x_i) $

Given $f:\mathbb{R}^n_{>0}\rightarrow \mathbb{R}$, defined as $f(x)=ln(a^\top x) - \sum_{i=1}^n \ln(x_i)$, for all $x \in \mathbb{R}^n_{>0}$, where also $a\in \mathbb{R}^n_{>0}$. Is the ...
Pepe's user avatar
  • 126
1 vote
0 answers
18 views

Expectation value given a convex order

I want to know if the following proof is correct. Let $M,N$ and $X$ be random variables. If the following inequality holds for any concave non-decreasing function $u$ \begin{equation} \mathbb{E}[u(N)]\...
Don P.'s user avatar
  • 366
4 votes
0 answers
33 views

Existence and Uniqueness of Equilibrium points for Concave N-Person Games

I am reading a paper. I have a problems with understanding their lemma Lemma: The nonzero elements of every vector $u \in U(x)$ are given by a vector $\bar{u} \in E^k, \bar{k} \leqslant k$, where $\...
Pipnap's user avatar
  • 431
1 vote
0 answers
32 views

Slack Variables and Duality in Convex Optimization

In context of convex optimization the slack variable $\vec{s} \ge 0$ can be used to convert inequality $A \vec{x} \le \vec{b}$ to the equality $A \vec{x} + \vec{s}= \vec{b}$. Now in wikipedia is ...
user267839's user avatar
  • 7,589

1
2 3 4 5
151