Skip to main content

Questions tagged [linear-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
19 votes
4 answers
2k views

PhD-level textbooks on linear programming

My graduate Linear Programming class uses Bertsimas & Tsitsiklis's Introduction to Linear Optimization. Are there any alternative texts that I could use to supplement this textbook (mainly the ...
tiger123's user avatar
  • 191
16 votes
1 answer
3k views

IPOPT with HSL vs MUMPS

What are the advantages (if any) of using IPOPT with HSL vs MUMPS? HSL has a reputation of being faster, but does it walk the walk? In particular, does HSL scale better for large-scale problems? We ...
Nikos Kazazakis's user avatar
12 votes
1 answer
872 views

Simplest way to eliminate redundant constraints due to a new cut

I have a polyhedral set for constraining $x$: \begin{align} \mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \} \end{align} where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the ...
independentvariable's user avatar
9 votes
2 answers
554 views

Convexity of a QP

In quadratic programming (QP), you encounter an objective of the following form: $$x^TQx + c^Tx$$ and often it's desirable to know if the QP is convex. One method to check for convexity is by ...
Josh Allen's user avatar
4 votes
1 answer
244 views

Algorithms for sparse linear systems

I've long wondered this, but what is the algorithm(s) implemented in modern linear equation solvers for sparse systems? The obvious answer I can think of is Gauss-Jordan with a bunch of tricks to make ...
Nikos Kazazakis's user avatar
4 votes
0 answers
119 views

Weighted nuclear norm minimization

The problem. Let $X,A \in\mathbb{R}^{n\times m}$ and let $W\in\mathbb{R}^{nm\times nm}$ be a positive definite matrix. I want to know if there is a closed-form solution to this problem $$ \min_{X} \...
Apprentice's user avatar
3 votes
1 answer
463 views

How to reduce an LP problem already in its standard form?

Suppose we have a feasible LP problem in its standard form. From Ax=b we can directly determine some of its variables and thus we can reduce the problem. For example, from two constraints: x+y+z=2 and ...
andy's user avatar
  • 77
3 votes
2 answers
277 views

Convexity of a function

I would like to show that this function $$2x^2 + 8y^2$$ is convex or concave by using the definition $$f(θx+(1−θ)y) \le θf(x)+(1−θ)f(y)$$ From my understanding, using the Hessian matrix, I believe ...
george's user avatar
  • 135
2 votes
1 answer
223 views

Finding all left inverses of a matrix

For large rectangular matrices, is this something that is easy or possible to achieve in the programming language R? Or to get all possible equations, must one solve equations by hand? I see notes ...
Christopher Turnbull's user avatar
2 votes
1 answer
428 views

Can't understand K-Truss Graph properties

Cross-posted on Mathematics SE. Since I have to implement an algorithm in the language of linear algebra, I'm trying to understand K-Truss Graphs which are defined as such The k-truss is a subset of ...
karalis1's user avatar
  • 131
2 votes
1 answer
84 views

Optimizing for an unknown conjugation matrix

I am trying to find the invertible matrix $M$ satisfying: $$v_t'= MA_tM^{-1}v_t$$ For a dataset of observed transformations $(v_t',A_t,v_t)_t$. Note, there is a different linear transformation $A_t$ ...
hamza keurti's user avatar
1 vote
1 answer
3k views

complexity order of the interior point method

I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5? Much appreciate your time and consideration.
Shayan zargari's user avatar
1 vote
1 answer
51 views

Computing simplex tableu for a given basis

I found the following problem in my book. I know that I can compute the simplex tableau , let's call it S for a basis X_b=(x_1, x2, x_5)^T as ...
tonythestark's user avatar
1 vote
2 answers
65 views

Solving regularized least squares problem using black-box computation of $\mathbf{A}\mathbf{x}$ and $\mathbf{A}^T\mathbf{x}$

Let $\mathbf{A} \in \mathbb{R}^{n \times n}$. I'm working in a problem where I have a black-box algorithmic solution to compute the products $\mathbf{A}\mathbf{x}$ and $\mathbf{A}^T \mathbf{x}$ given ...
mlbj's user avatar
  • 13
1 vote
0 answers
52 views

explain Givens rotation chain for maintaining Cholesky factorization

I'm attempting to implement the dual face algorithm from Pan's book chapter 22 (https://link.springer.com/book/10.1007/978-981-19-0147-8). The part in question is pasted here: Can you please explain ...
Brannon's user avatar
  • 900