# Questions tagged [convex-optimization]

The tag has no usage guidance.

97 questions
Filter by
Sorted by
Tagged with
1 vote
30 views

### ML Gradient Descent Convergence Theorem

Does there exist a generalization of this theorem, by Yurii Nesterov in Introductory Lectures on Convex Optimization (2004) which relaxes the assumption that the loss function is convex and shows that ...
115 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$ ...
95 views

### Minimizing a submodular function containing summation and production under partition matroid constraint

I'm having difficulty solving the following problem: We're given $n$ sets $X_1,\ldots, X_n$. Each set $X_i=\{(a_i,b_i)\}$ contains poly(n) many ordered pairs of non-negatives with $0\le a_i+b_i\le 1$. ...
1 vote
97 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 ...
30 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 ...
55 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 ...
1 vote
47 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 ...
Crossposted at Mathematics SE and MathOverflow In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\... 4 votes 1 answer 520 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 ... 22 votes 1 answer 3k views ### Solving semidefinite programs in polynomial time We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (... 4 votes 0 answers 150 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 ... 4 votes 0 answers 138 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 ... 0 votes 1 answer 72 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.~~~~~~~~~~~~~~~~~~~~~~~~~~~~... 2 votes 2 answers 143 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*}... 4 votes 0 answers 138 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*} &\... 1 vote 0 answers 43 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 ... 3 votes 1 answer 234 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 ... 0 votes 0 answers 98 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 ... 3 votes 1 answer 114 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 ... 4 votes 1 answer 200 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 ... 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 ... 3 votes 0 answers 114 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(... 2 votes 0 answers 58 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 ... 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}\... 3 votes 0 answers 198 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,\... 0 votes 0 answers 78 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 ... 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 ... 1 vote 0 answers 60 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 ... 2 votes 0 answers 31 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, \... 3 votes 0 answers 175 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 \... -1 votes 1 answer 78 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(\... 2 votes 1 answer 272 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 ... 8 votes 2 answers 5k views ### A Question on Convex Conjugate Duality for KL Divergence The convex conjugate of a function, say, f:X\mapsto \mathbb{R} is a function f^*:X^*\mapsto \mathbb{R} defined as$$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$where X^* is the ... 10 votes 3 answers 776 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 ... 0 votes 0 answers 91 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 ... 4 votes 0 answers 107 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, ... 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, \... 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, \... 1 vote 2 answers 3k views ### Derive logitboost using the logistic loss function An additive model constructed using the exponential loss function$$L(y, f (x)) = \exp(−yf (x))$$gives Adaboost. How can we derive the corresponding additive model (known as logitboost) using ... 6 votes 1 answer 169 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 ... 1 vote 1 answer 442 views ### Optimal value of a semidefinite program Is a local optimum value of a SDP always the global one? If not, what are the conditions for that? 6 votes 1 answer 954 views ### Analytic solutions in semidefinite programming (SDP) From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,... 10 votes 2 answers 611 views ### What can be solved with semidefinite programming that can't be solved with linear programming? I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I ... 8 votes 1 answer 595 views ### Is the feasible region of this SDP polyhedral? We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-1 matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ... 3 votes 1 answer 217 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 ... -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_{... 1 vote 0 answers 70 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-... 6 votes 0 answers 102 views ### Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization In September1989$, 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 ... 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$...
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$ ...