# Tagged Questions

The tag has no usage guidance.

19 views

### Approximability of convex programming (convex optimization)

Apologies for multiple posting (also posted at cs.SE), but I think this question is more relevant here at cstheory: Convex optimization is defined here. The problem is NP-hard. But is anything known ...
40 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 ...
121 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}...
200 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 ...
88 views

815 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 (...
1k 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 ...
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 ...