Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with linear-programming
Search options not deleted
user 9022
Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.
1
vote
SDP Algorithms/ maximally complementary solutions
The standard approach is to embed the original SDP in a self dual formulation that has strictly feasible primal/dual solutions, solve the self dual formulation and then reach conclusions about the ori …
- 3,934
3
votes
Accepted
Cascading minimization problems
You can solve the first LP, obtain the optimal value, and then add a constraint that the first objective has that optimal value. Then you can add your second set of constraints to the original set of …
- 3,934
2
votes
Levenberg-Marquadt near the minima for non-zero-residual problems
The technique of multiplying the diagonal by $(1+\lambda)$ fails when you've got a 0 on the diagonal of $J^{T}J$. Having a zero on the diagonal of $J^{T}J$ can happen when you're far away from the op …
- 3,934
1
vote
Accepted
Nonstandard Hessian approximations in Gauss-Newton
You could certainly try this, but you'd have to do a lot of careful analysis to derive any convergence results. Among other things to consider:
Your objective E(x) is more likely to have local mini …
- 3,934
1
vote
Accepted
What does "Vertex Solution" mean?
In the context of linear programming, and assuming that you're using the simplex method to solve your LP's rather than an interior point method, it's most likely that the author means "basic feasible …
- 3,934
2
votes
Accepted
Model for shipping widgets in an optimal way
Is the routing from factory to distributor to location fixed, or are you considering optimizing this too? In particular, are there costs associated with using a distributor? If the answers to one or …
- 3,934
3
votes
Accepted
linear programming with OR restrictions
Your additional constraints make the feasible region for your problem nonconvex, and thus it cannot be represented as a linear programming problem.
If you can obtain an upper bound $M_{i}$ on the max …
- 3,934
1
vote
Accepted
Large scale least squares of non symmetric and non square problems
A widely used iterative method for large scale linear least squares problems that allows for regularization if you want/need it is the LSQR algorithm of Paige and Saunders. See
http://www.stanford.ed …
- 3,934
1
vote
positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix
This is easy to formulate as a semidefinite programming problem.
First, let $X=xx^{T}$. The semidefiniteness constraint becomes
$A-\lambda X \succeq 0$
Next, use a standard technique to handle t …
- 3,934
1
vote
generalization from linear programming solution
You should look into the topic of "parameteric linear programming". In certain situations where the problem data vary linearly with parameters, you can derive formulas for the optimal solution and op …
- 3,934
1
vote
Efficient Algorithm For Projection Onto A Convex Set
You haven't told us anything about the size of your problem instances. How many terms are there in the sum of norms? What is $n$?
Your problem is an example of a "sum of norms" optimization probl …
- 3,934
1
vote
Continuity of Lexicographic Minimum Solution of a parametrized LP problem
You've chosen a somewhat limited form of "parametric LP" here. It's more common to allow $F$ to vary as $F=F_{0}+tF_{1}$. For that more general variety of parametric LP, the conjecture is false- it' …
- 3,934
0
votes
Existence of nonnegative solutions to an underdetermined system of linear equations
Algorithmically, you can solve the linear programming problem:
$\max \sum_{i=1}^{n} x_{i} $
$Ax=0$
$x \geq 0$
If the maximum is strictly greater than zero, then there's a nonzero solution that sa …
- 3,934
9
votes
How do you tell if a system of linear inequalities has a solution?
You haven't said whether you're interested in theoretical analysis or practical computation. At the practical level, you also haven't specified whether you can live with an approximate floating poin …
- 3,934
2
votes
Sensitivity analysis in conic optimization
In general, your problem can become infeasible under arbitrarily small perturbations $\Delta b$. For example, consider the problem
$\min X_{11}+X_{22}$
subject to
$X_{11}=0$
$X_{22}=0$
$X \suc …
- 3,934