Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [convex-optimization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
87 views

Non-convex optimization with correlated minima

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in ...
Omar Shehab's user avatar
0 votes
0 answers
27 views

Variants of weak optimization problems for convex sets

In their famous book, Grotschel Lovasz and Schrijver (1993) present several algorithmic problems on convex sets. Each of these problems has a strong variant and a weak variant. In particular, the ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
47 views

cutting plane method for convex optimization

The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
MMH's user avatar
  • 101
1 vote
0 answers
40 views

Convergence rates for the iterates of SGD on Lipschitz convex functions

Let $f:X \rightarrow \mathbb{R}$ be a convex and $L$-Lipschitz continuous function. Suppose $f^* = \min_{x \in X} f(x) \in \mathbb{R}$ and let $X^* = \{x \in X : f(x) = f^*\}$. For a non-negative ...
Andrea's user avatar
  • 319
4 votes
1 answer
506 views

Deciding whether a convex region is empty

Let $S\subseteq \mathbb{R}^n$ be a convex region defined by $$g_i(x)\leq 0, ~~i\in 1,\ldots,m,$$ where $g_i$ are convex functions. The goal is to decide whether $S$ is empty, and if not - find a point ...
Erel Segal-Halevi's user avatar
4 votes
0 answers
134 views

Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?

In Nemirovxki's lecture notes on interior point methods, I found the following. He defines an approximate solution as satisfying the following, for any given $\epsilon>0$: that is: the ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
68 views

Solving non-linear programming with large number of variables

Let $n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$ and consider the following optimization problem: $$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$ $$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
John's user avatar
  • 412
2 votes
2 answers
133 views

Linear Programming Sensitivity to Matrix

Consider a linear program in the following standard form: \begin{align*} &\max c^T x &\\ &\mbox{subject to:}\\ &A x \preceq b\\ &x \succeq 0 \end{align*} Its dual is \begin{align*}...
sd234's user avatar
  • 575
4 votes
0 answers
134 views

Which variant of the ellipsoid method was used for the Santa Claus problem?

As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual): \begin{align*} &\...
eden hartman's user avatar
1 vote
0 answers
42 views

What is the meaning of loss in online convex optimization?

I am studying online convex optimization, and it is stated that when we make a decision, we observe loss corresponding to our decision. In some problems like multi-armed bandit problems, we know the ...
Amin's user avatar
  • 111
3 votes
1 answer
225 views

Can the ellipsoid method be used with a randomized separation oracle?

Suppose we are trying to solve the following optimization problem: $$ \text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S $$ where the region $S$ is described by an exponential number of ...
eden hartman's user avatar
0 votes
0 answers
95 views

How to prove that a given class of convex programs cannot be solved by linear programming?

Given the following program, where $f, g$ are convex functions: $$ \text{minimize}~~ f(x) \\ \text{subject to}~~ g(x)\leq 0 $$ the problem can be solved by convex programming algorithms, but it would ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
93 views

How to solve the following continuous optimization problem?

Consider a function $f: X\times Y\times N$, where $X, Y \subseteq \mathbb{R}^m$ are convex sets, and $N = \{1,2,\dots,n\}$. We additionally know that $f(\cdot,y,S)$ is convex for fixed $y,S$ $f(x,\...
ashtavakra's user avatar
3 votes
1 answer
112 views

Strongly polynomial time algorithm for shortest convex combination

Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$. Reference 1 gives an algorithm for this problem that is finite-time (Section ...
user76284's user avatar
  • 662
4 votes
1 answer
195 views

Restriction of a convex function to {0, 1}^n

Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
Sean L.'s user avatar
  • 43
4 votes
0 answers
141 views

Maximum volume ellipsoid in an intersection of ellipsoids

Given a collection of $m$ ellipsoids in $\Bbb R^n$, compute the maximum volume ellipsoid inscribed in their intersection. In section 8.4.2 of Boyd & Vandenberghe's Convex Optimization, this ...
Andrea's user avatar
  • 319
1 vote
0 answers
32 views

Reference showing global optimality of local minima for matrix factorization

Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized. I have heard it ...
user2684957's user avatar
3 votes
0 answers
112 views

SVM perturbation bounds

Let $B$ be the unit ball of $\mathbb{R}^d$. Suppose that $x_1,\ldots,x_n$ are vectors in $B$ with labels $y_i\in\{-1,1\}$. We say that $w\in B$ separates this labeled set with margin $\gamma$ if $y_i(...
Aryeh's user avatar
  • 10.6k
2 votes
0 answers
56 views

program search with optimization methods for (resource bounded) Kolmogorov complexity

Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
dorikolmo's user avatar
3 votes
0 answers
192 views

Hessian of non differentiable convex function

The motivation of the question is the following: Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\...
Sudipta Roy's user avatar
0 votes
0 answers
77 views

A variant of randomized co-ordinate descent

Let us consider the following optimization problem. $\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
Sudipta Roy's user avatar
3 votes
1 answer
234 views

An optimization problem

I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$ maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
Sudipta Roy's user avatar
3 votes
1 answer
116 views

Parametrized complexity of sparse optimization

Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
Aryeh's user avatar
  • 10.6k
1 vote
0 answers
57 views

Tight estimates on the Lovász and Multilinear extensions of a submodular function

I assume here some familiarity with the jargon used in submodular optimization (please let me know if something is unclear). Let $f:2^V \to \mathbb{R}$ be monotone, normalized and submodular. For ...
MathematicsStudent1122's user avatar
2 votes
0 answers
30 views

Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets

Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
Alex Coventry's user avatar
3 votes
0 answers
167 views

Gradient descent step size for strongly convex functions

Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \...
Zuza's user avatar
  • 141
-1 votes
1 answer
76 views

Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$

Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...
user avatar
2 votes
1 answer
262 views

Is the Chi-square divergence a Bregman divergence?

Is the Chi-squared divergence $\sum_{i} \frac{(x(i)-y(i))^2}{x(i)}$ a Bregman divergence? I.e., can it be written as $\phi(x) - \phi(y) - \langle\phi'(y),x-y\rangle$? If so, what is the potential ...
Yonatan's user avatar
  • 33
0 votes
0 answers
86 views

When can convex optimization be considered to be exactly solvable?

If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $\epsilon >0$ where $\epsilon$ measures the accuracy of ...
gradstudent's user avatar
  • 1,453
10 votes
1 answer
1k views

Is convex optimisation in P?

Consider a convex optimisation problem in the form $$\begin{align} f_0(x_1, \ldots, x_n) &\to \min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align}$$ where $f_0, f_1, \...
Sergey Dovgal's user avatar
4 votes
0 answers
106 views

Bounding a Solution of an SDP

It's common for convex optimization procedures to require a bounded region containing an optimal solution, either as input, like the initial ellipsoid of the ellipsoid method, or for run time bounds, ...
sbnietert's user avatar
4 votes
1 answer
68 views

Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then $$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$ is a convex piecewise linear function of $(x_1, \...
David E Speyer's user avatar
3 votes
1 answer
214 views

On complexity of linear programming with quadratic equality/inequality constraints?

Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
72 views

Has Khachiyan/Porkolob's convex integer optimization been implemented?

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
Turbo's user avatar
  • 12.9k
-3 votes
1 answer
126 views

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ $$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
69 views

Average case or beyond worse case analysis for non-convex optimization procedures?

I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature. It is known that global optimization of non-convex functions is NP-...
Jake Shellman's user avatar
6 votes
0 answers
102 views

Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization

In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
gradstudent's user avatar
  • 1,453
1 vote
0 answers
35 views

How does one know what is not in a certain class of pseudo-distributions?

We consider working in the function space $\mathbb{R}^{\{ -1,1\}^n}$ where the expectation inner-product makes the juntas form a $2^n$ dimensional orthonormal basis. Now say one has found a degree $...
gradstudent's user avatar
  • 1,453
1 vote
1 answer
96 views

Properties of convex polytope of 0-1 matrices

Problem setting Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$. Consider a $k\times k$ matrix $M$ ...
Vivek Bagaria's user avatar
7 votes
0 answers
117 views

Has compressed sensing been generalized to convex optimization problems?

Has the theory of "compressed sensing" been generalized to any classes of convex optimization problems? I need to analyze a problem of the type $$\min ||x||_0, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$...
Richard P.'s user avatar
10 votes
3 answers
763 views

When is the duality gap of semidefinite programming (SDP) zero?

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
gradstudent's user avatar
  • 1,453
1 vote
0 answers
90 views

Do nested convex bodies have increasing "Volume/Surface Area" ratios? [closed]

Suppose we have two convex bodies $A$ and $B$, where $A \subseteq B$. Is it always true that $\mathrm{Vol}(A)/\mathrm{SurfaceArea}(A) \leq \mathrm{Vol}(B)/\mathrm{SurfaceArea}(B)$? It's true in all ...
Maximinus's user avatar
6 votes
1 answer
168 views

Brute force search algorithm for semidefinite programming (representation of spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
Steve's user avatar
  • 451
2 votes
0 answers
161 views

Non-Linear Programming with \min operator in the constraint

Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1. \begin{align} \text{maximize } &\sum_{i,j=1}^{m,n} c_{ij}...
Vadapalli Adithya's user avatar
6 votes
1 answer
2k views

The Average-case Complexity of Simplex Algorithm

I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
Steve's user avatar
  • 451
3 votes
0 answers
88 views

First-order methods for solving SDP with geometric convergence or better

Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
Minkov's user avatar
  • 852
2 votes
1 answer
267 views

When can a convex function induce submodularity?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
Student's user avatar
  • 654
2 votes
0 answers
206 views

Convergence of online convex optimization methods

I am new to this subject so this question might seem a bit trivial Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for ...
rabe's user avatar
  • 21
1 vote
1 answer
106 views

Assignment of values for a set

Consider the following problem: Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$. ...
Star's user avatar
  • 253
2 votes
0 answers
217 views

Runtime of Gomory's Cutting Plane Algorithm

I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown ...
Sidharth Ghoshal's user avatar