The tag has no wiki summary.

learn more… | top users | synonyms

13
votes
2answers
779 views

0-1 Linear Programming: computing the Optimal Formulation

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
11
votes
1answer
405 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 ...
8
votes
2answers
185 views

Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but ...
8
votes
1answer
448 views

Convexity and efficient algorithms.

[Edit 21 July 2011: I edited the question to ask for more examples] This question is asking for documented discussion of or more examples of a heuristic observation. Some mathematical problems that ...
6
votes
3answers
188 views

Neural Networks: what's the point of learning features that don't linearly separate?

Unless I'm mistaken, deep neural networks are good for learning functions that are nonlinear in the input. In such cases, the input set is linearly inseparable, so the optimisation problem that ...
6
votes
0answers
117 views

What's the state of the art for matrix nuclear/trace norm optimization

I am interested in simple matrix optimizations with nuclear/trace norm: $\min_X \left(f(X) + \|X\|_*\right)$ where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth ...
4
votes
1answer
126 views

Gradient descent-like optimization on a convex landscape with noisy sampling

We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$. The goal is to approximate the minimum. E.g. $$f: [0,\pi]^2 \to \mathbb{R}$$ $$f(\theta,\phi) = t_1 \sin \theta + t_2 ...
4
votes
1answer
164 views

Active learning for inferring a convex optimization formulation

I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation. As a specific example, I am thinking ...
4
votes
0answers
247 views

Time complexity of standard semidefinite programming solvers

I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs. (I am not interested in algorithms like multiplicative weights updates method.)
3
votes
2answers
131 views

On facets of 01-polytope

$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ...
3
votes
1answer
158 views

Objective function for stochastic optimization

Stochastic Optimization problems in general deals with random variables in the 'loss function'. Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
3
votes
1answer
386 views

Maximizing a convex function with linear constraints

I have the following optimization problem: $$ \arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\} \mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq ...
3
votes
0answers
163 views

Computing the convex hull of several polyhedra

Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities. How easy is it to compute an ...
3
votes
0answers
66 views

What is the state-of-the-art asymptotics for convex optimization?

I've got a convex program of the form: Choose $v \in \mathbb{R}^n$ to minimize $vAv^T$ subject to $O(n)$ linear contraints (including $v \ge 0$). $A$ is a square binary matrix. What algorithm gives ...
3
votes
0answers
227 views

Linear programming optimization problems using parallel algorithms

I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches ...
2
votes
2answers
676 views

Minimizing the maximum dot product among k unit vectors in an n-dimensional space

Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let, $$\alpha = \max_{1 ...
2
votes
1answer
215 views

Linear programming, a non standard handling of absolute value

This is really a basic (undergrad) question in LP but still i would like to clarify it for myself to be sure. I have a minimization problem from the sort $\min \sum_i |x_i|$ s.t $Ax \le b$. I've seen ...
2
votes
1answer
78 views

On the stopping criterion of coordinate descent method

I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion. Consider the optimization problem \begin{equation} \min ...
2
votes
0answers
71 views

KKT-like conditions for values close to optimal solution

The KKT conditions are necessary and sufficient conditions for problems where we maximize over a convex function subject to linear inequality and equality constraints. That is $x^*$ is an optimal ...
2
votes
0answers
191 views

Maximizing a convex function where the objective function is separable but the search space is not

The problem statement is Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$ Does this kind of problem structure allow one to use specific strategies to solve the ...
1
vote
1answer
113 views

Looking for algorithm (or at least name) for this optimization problem

Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$. Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$ The ...
1
vote
1answer
528 views

Primal vs dual decomposition methods

I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
1
vote
1answer
289 views

why are the constraints in the following paper tight?

My question is about the following paper: http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf In section 2 they show Equation 3 (which is just an optimization problem), which ...
1
vote
1answer
693 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 ...
1
vote
0answers
81 views

Definition of convex optimization problem by Stephen Boyd and Lieven Vandenberghe

Boyd and Vandenberghe say that a convex optimization problem is one of the form: minimize $f_0(x)$ subject to $$f_i(x)\le 0, i=1,\ldots m$$ $$a_i^\top x=b_i, i=1,\ldots p$$ ...
1
vote
0answers
84 views

Optimization as LP on the convex hull of its solution space

I have heard claims that for a certain class of optimization problems, one can re-write the problem as a linear-programming problem on the convex hull of the solution space of the original problem ...
1
vote
0answers
244 views

Confusion related to L1 and L2 svm [closed]

I have this confusion related to L1 and L2 svm. It is given in this paper that The dual problem is given by $$ min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha $$ subject to $$ 0 <= \alpha_i ...
1
vote
0answers
90 views

Poly-time Algorithm for Non-Linear Optimization

As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this ...
1
vote
0answers
96 views

Extended Formulaiton and Integer Programming

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints $Ex + Fy = g, y\geq 0$ in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real matrices ...
1
vote
0answers
158 views

Properties of the subgradient method

The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule $$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and $\alpha(t)$ is a ...
1
vote
0answers
164 views

Maximizing a convex function with linear constraint

The problem is $$\max f(\mathbf{x}) \text{ subject to } \mathbf{Ax} = \mathbf{b}$$ where $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$, $\mathbf{x} = ...
0
votes
1answer
187 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

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) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
0
votes
0answers
41 views

LP solver for sparse, PSD and strictly diagonally dominant matrix

I have a linear problem with a sparse, psd and strictly diagonally dominant matrix. Can you please point me to some known best solvers (in terms of runtime, or easy to be practically optimized for ...
-1
votes
1answer
284 views

Upper bound of an optimization problem

Please let me know whether there are closed-form optimal results (or upper bound) for the following optimization problem: $$\max (\prod_{1\leq i\leq n}(x_i)^{y_i}-\prod_{1\leq i\leq ...