# Tag Info

Accepted

### Linear programming with matrix constraints

Overview You might want to try a variant of the Alternating Directions Method of Multipliers (ADMM), which has been found to converge surprisingly quickly for $l_1$ lasso type problems. The strategy ...
• 3,003
Accepted

### Implementation of LP with separation oracle?

Here's a longer answer that summarizes my earlier comments: I'm not aware of any implementations of the ellipsoid algorithm that are practically usable for solving LP's. It's easy enough to cook up ...
• 17.6k

### What's the fastest software(open source) to solve mixed integer programming problem

If you want to try a bunch of different solvers, give Julia's JuMP modeling framework a try. It lets you write your model as a JuMP model, and then switch out the solvers with one line of code. For ...
• 11.4k

### Mathematical optimization software free/openSource

Is there any real free alternative to AMPL? Yes! (Sorry to contradict you, Geoff.) There is a real free alternative to AMPL. JuMP is a free and open-source modeling language built on top of Julia. It ...
• 181

### Starting at a Given Basic Feasible Solution in the Simplex Method

If your problem is in standard form (that is, with constraints $Ax = b$, $x \geq 0$), and you know a BFS, then you should know which columns of the standard form $A$ matrix to select to form a basis, ...
• 29.8k
Accepted

### Linear system solution with inequality constraints - methods?

This is a linear programming feasibility problem (since you don't have an objective function to minimize or maximize.) You can simply use an objective function of $0$ and hand this off to any ...
• 17.6k

### How do I simultaneously minimize two different functions who have the same inputs?

The problem posed is a multiobjective optimization problem, and the usual notion of optimality for these types of problems is Pareto optimality. Scalarization (as proposed in the comments by ...
• 29.8k
Accepted

### 0,1 binary polynomial programming

If the $s_{i}$ are integers, there are reformulations of integer polynomial terms that result in mixed-integer (linear) programs, at the cost of introducing additional variables and constraints. Fred ...
• 29.8k
Accepted

### Mathematical optimization software free/openSource

Is there any free alternative to AMPL? (Edit: I spoke too soon; thanks to mlubin for pointing this out.) If you don't care too much about convenience, there are open-source formats for specifying ...
• 29.8k

### Can we express max constraint as a linear constraint?

First note that because your $x_{i}$ are binary variables you aren't really in the world of linear programming any more. Rather, this problem is a mixed integer linear programming problem (MILP). ...
• 17.6k

### Is the "practical" complexity of linsolve direct solver O(n^2) ?

Your matrices are far too small to see the asymptoptic $O(n^3)$ running time behavior of the LU factorization used by linsolve. For very small matrices the overhead of computations surrounding the LU ...
• 17.6k
Accepted

• 2,002

### Constraints involving $\max$ in a linear program?

In order to formulate the constraints $f \le \max \{ f_1, f_2,...,f_n \}$, we create $n$ binary variables, $b_i \in \{0,1\}$, $1 \le i \le n$. Let $M$ be the bound of variable $f$, then we only need ...
• 161
Accepted

### Solving a problem using multiple threads using CLP

By Clp, I assume that you're referring to the linear programming code that is part of the COIN-OR project: http://www.coin-or.org/Clp/ Clp's primal and dual simplex codes aren't multithreaded so ...
• 17.6k

### difference of polytopes in $\mathbb{R}^n$

That heavily depends on the representation. If you're given $P_1$ and $P_2$ as systems of linear inequalities (or, dually, as the convex hull of a finite set of points) with finite precision, you can ...
• 372
Accepted

### LP and SDP nomenclature

$x$ is primal variable, $y$ is dual variable ($y$ is usually not referred to as Lagrange multiplier unless you form Lagrangian explicitly). Others are usually referred by symbol directly rather than ...
• 408
Accepted

### Use scipy to get any vertex of polytope

If you use a 0 objective function, then the solver should stop as soon as it encounters a feasible solution (because that solution will be optimal.) If the solver is using a 2-phase primal simplex ...
• 17.6k

### Can Variance be replaced by absolute value in this optimization problem

Without knowing much about your question it is hard to answer more specifically. So first and foremost - no. These are not equivalent. Minimizing variangce will generally make you converge to some ...
• 261

### Simplex method - cycling and condition ">=" or ">" in choice of pivot row

The short answer to your question is that "nonnegative" is correct. 0 ratios do occur and it is sometimes necessary to perform degenerate pivots in order to ultimately reach a solution which will ...
• 17.6k

### How to solve a constrained optimization problem using minFunc or minConf

Not a direct answer to your title question, but I think you are better off attacking this problem from the semidefinite domain instead. Trivial approach is to linearize the objective at some initial ...
• 1,763

### How to solve a constrained optimization problem using minFunc or minConf

Adding another answer, as I just realized that the problem is easily solved as a linear SDP. Let $Q=S^TS$ and you have the objective $\mathrm{trace}~Q + \mathrm{trace}~Q^{-2}$. Introduce an upper ...
• 1,763
Accepted

### linear programming feasiblity checking

The short answer to your question is: kind of. There are methods called "preprocessing" or "presolve", that will take a problem with constraints $b_{l} \leq Ax \leq b_{u}$ and $l \leq x \leq u$ as ...
• 29.8k

### Checking the feasibility of a system of inequalities

I agree with Stelios' answer, but it could use some fleshing out. This problem is called the "Phase One" problem. First, convert your problem into "standard form". \begin{align*} \min_x 0 \\ s.t. \;\...
• 1,522