All Questions
227 questions with no upvoted or accepted answers
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
1
vote
0
answers
322
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
- 13.9k
1
vote
0
answers
147
views
Convergence of infinite linear programming
Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
- 53
1
vote
0
answers
82
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
- 1,826
1
vote
0
answers
78
views
Reference for the algorithm to find the intersection between a subspace and positive orthant
I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...
1
vote
0
answers
67
views
What are the corners of this polytope?
Let $f$ be a non-negative function on the positive integers such that $f(s+t)\geq f(s) + f(t)$ for all $s,t\in\mathbb{Z}^+$. Consider the polytope consisting of all $x\in \mathbb{R}^n$ such that $$\...
- 11
1
vote
0
answers
75
views
Joint optimization of the order 1 moment of a function and its Fourier transform
For the purpose of a quantum optics experiment, I come to the following problem :
Let $X,P \in \mathbf{R}^2$
\begin{equation}
J(\psi) = | \int_{-X}^{X} x |\psi^2(x) | dx + \int_{-P}^{P} p |Tf(\...
- 11
1
vote
0
answers
72
views
Distance between value function of deterministic and stochastic control problems
Suppose that one wants to control a diffusion process
$$
dX_t^u = \mu(X_t^u,u)dt + \sigma dW_t; \qquad X_0^u=x
$$
in order to optimize a stochastic control problem with value function
$$
V_T(u)=\...
- 5,405
1
vote
0
answers
282
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
1
vote
0
answers
105
views
Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related?
I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy:
$$
\inf_{x\in\mathbb{R}^n}\quad p(x),
$$
where $p$ is a polynomial of even degree ...
- 617
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
1
vote
0
answers
25
views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
- 11
1
vote
0
answers
36
views
Linear programming with a convergent coefficient
The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...
- 19
1
vote
0
answers
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
1
vote
0
answers
24
views
Simple monotonicity property for coordinate descent and linear objective functions
Let $S \subset \mathbb{R}^n$ satisfy $0\leq x_1\leq\dots\leq x_n$ for all $\mathbf{x}\in S$, among other (possibly nonconvex) constraints, and suppose in addition that $\sum_{i=1}^n x_i \geq 1$ for ...
- 4,049
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
1
vote
0
answers
102
views
When are quadratic integer programs "easy to solve"?
Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form
$$
f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...
- 379
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
1
vote
0
answers
66
views
On number of solutions by simplex and number of solutions in total in a linear optimization problem?
This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...
- 13.9k
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
- 13.2k
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
- 41.8k
1
vote
0
answers
86
views
Infinite system of equations with finitely many constraints
During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
- 1,151
1
vote
0
answers
44
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
- 19
1
vote
0
answers
261
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
- 31
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
1
vote
0
answers
40
views
Linear cost traveling salesman heuristic
I have a sequence of points $y_1,\ldots,y_n\in \mathbb{R}^3$ and want to approximately minimise
$$
\sum_{i=1}^{n-1}|y_{\pi(i)}-y_{\pi(i+1)}|
$$
by choosing a permutation $\pi$ of $\{1,\ldots,n\}$.
I ...
- 435
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
1
vote
0
answers
190
views
linear relaxation of an optimization problem
I'm reading an article lately, and there is one point which confuses me.
So, we have the following constrained binary quadratic problem.
min $x^{T}Qx$
with the constraints that $Ax\leq b$ and $x\in ...
- 11
1
vote
0
answers
83
views
Nonconvex Optimization of inner product objective
Does there exist any result on the following minimization,
$$\min_{x\in P} \langle x, F(x)\rangle\equiv \sum_i x_i F_i(x), $$ where $P$ is a convex polytope and $F_i(\cdot)$s are convex functions of $...
- 133
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
1
vote
0
answers
83
views
What is optimal distance between inverse of convolution operator?
I am looking for a measure to find the optimal distance measure between inverse of an convolution operator $A$ and say another convolution operator $B$. I want my measure to be sharp that mean when $B$...
1
vote
0
answers
232
views
Semi-convex problem and almost convex problem
I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...
- 355
1
vote
0
answers
94
views
About a particular definition of a Hessian of a function of tuples of matrices
Say I have a function $L : (W_1,..,W_{H+1}) \rightarrow \mathbb{R}$ i.e it takes a tuple of $n$ matrices of different dimensions and computes a number from them.
Then I see being defined a ...
- 2,246
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
1
vote
0
answers
90
views
Separable Least squares - is there a notion of conjugate directions?
I have a general question.
Suppose I have the following to optimize
$$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$
where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
- 61
1
vote
0
answers
36
views
Deterministic global solution to find the Optimal-knot placements for continuous piecewise linear functions to fit nonlinear data
I have been searching lately for a deterministic global technique to linearize a nonlinear function with continuous piecewise linear regions.
I've a univariate nonlinear function y=f(x). where f(x) ...
- 11
1
vote
0
answers
88
views
solution of an infinite horizon optimization problem
Give the following formulation:
$\min_{\{x_s(t):\forall s,t\}} \sum_{s \in \mathcal{S}} \mathbf{1}\left(\lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=1}^T \frac{y_s(t)}{x_s(t)}\leq 1\right)$
$s.t. ...
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
1
vote
0
answers
100
views
Changing a nonlinear equality constraint into some conic inequality plus rank constraint
If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
- 33