Questions about optimization problems subject to additional constraints.
4
votes
0answers
92 views
An invertible matrix that minimizes the norm of the product with a given matrix
Given a fat matrix $B \in \mathbb{C}^{n \times m}$ (where $m > n$) with full row rank, I would like to find (numerically) a full-rank matrix $A$ that minimizes the Frobenius norm of the product $A ...
3
votes
1answer
75 views
How does fmincon in MATLAB calculate gradients?
I am trying to solve numerically a constrained optimisation problem in MATLAB, and I am wondering how the fmincon function calculates gradients when one isn't ...
1
vote
1answer
50 views
Piecewise-Linear Quadratic Optimization for an “Almost Convex” Problem
I have a 7-14 dimensional piecewise linear cost function I'd like to minimize with two quadratic terms of the form:
$$
f(X) = X^tCX + d \sum_i |x_i-x^*_i|^2 + \sum_i P_i(x_i-x^0_i)
$$
$$ \sum_i x_i ...
0
votes
1answer
63 views
Simulation-based Optimization vs PDE-constrained Optimization
What is the difference between Simulation-based Optimization and PDE-constrained Optimization?
Would studying a text on Simulation-based optimization be sufficient to understand and apply both?
0
votes
0answers
39 views
Metric selection and scale-based preconditioning in quadratic optimization problem
I'm going to use scale-based preconditioning in a quadratic optimization problem: minimize $ x^T Q x + p^T x$ such that $ A x + b = 0$ and $D x + E \leq 0$, I want to speed up finding the optimal $x$ (...
2
votes
0answers
55 views
Convergence of a very large non-linear least squares optimization
(note: I also posted this question on stackoverflow before finding this community here, which seems a better place for it)
I'm trying to solve the following problem: I have a lot (~80000) surface ...
5
votes
1answer
71 views
Solvers for Quadratically Constrained Quadratic Programs (QCQP) with complex variables
I'd like to know whether there are any publicly available tools for solving QCQP with complex variables (and constraints therefore expressed through Hermitian matrices). What I have found so far is ...
1
vote
1answer
169 views
How to use CSDP to express a semidefinite program?
I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program
$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
1
vote
1answer
68 views
FMINCON Step Size Tolerance
I get following error after implementing the attached code.
Error Message
"fmincon stopped because the size of the current step is less than
the default value of the step size tolerance but ...
1
vote
0answers
38 views
Space covering optimization
I have the following problem:
In the space $E=\{1, 2, \dots, N_x\} \times \{1, 2, \dots, N_y\}$, I want to define $N_R$ rectangles $R_k=\{x_k^0, \dots, x_k^1\}\times\{y_k^0, \dots, y_k^1\}$ which ...
0
votes
0answers
40 views
Optimization of a continuous function
This is more like an optimization problem but any solution is appreciated.
I have a data set with input specifying power(demand) to be generated for a particular time period(TP).
Input:
Time --- ...
3
votes
2answers
129 views
How do I check if a loss function can achieve its minimum?
For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its ...
2
votes
1answer
25 views
Constraints 'exactly/at most one non-zero element' without binary variables
In a much larger MINLP problem, I have set of variables $\{a_{ij}\}_{m,n}$, such that $0 \leq a_{ij} \leq 1 $ for all $i$, $j$, which I could think of as a matrix, for which I have two requirements:
...
6
votes
1answer
198 views
What is required of the objective function in order to use Gauss Newton method?
From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.
In addition to that, are the following ...
1
vote
1answer
151 views
How to Solve Optimisation Problems using Penalty Functions in Python
I am working on a implementing a simple quadratic optimisation problem:
$$\min _x \; {\underline{x}}^T Q {\underline{x}}$$
$$s.t. \,\quad {\underline{\mu}}^T{\underline{x}} = R^*$$
$$ \quad \quad \...
0
votes
1answer
104 views
Defining a soft constraint in cvxpy
I am using cvxpy to do a simple portfolio optimization.
I implemented the following dummy code
...
2
votes
1answer
90 views
What is the fastest way to solve Ax=b (subject to constraints and an absolute term)
I am trying to solve/optimize $Ax=b$ in the least squares sense subject to
box constraints;
a few (less than 5) equality/inequality constraints; and
an absolute function penalty (or some other ...
1
vote
2answers
63 views
Making difference of log constraints convex
I have the discrete likelihood estimation problem $\max \sum m_i\log p_i $ where $m$ is a given vector of length $n$. The constraints are $0 \preceq p \preceq 1$, $\sum_{i=1}^n p_i = 1, $ and one ...
3
votes
1answer
94 views
Linear constraints for L-BFGS-B
I know L-BFGS-B only supports simple box constrains of the form: $l_i \leq x_i \leq u_i$, where $l_i$ and $u_i$ are constants. For my specific optimization problem, I need to specify some simple ...
0
votes
1answer
54 views
reduced system: primal-dual interior point method for nonconvex constrained problem
When solving a reduced KKT system of a nonlinear (and nonconvex) constrained program after eliminating slack and dual variables, how do we actually take the next step in a primal-dual method?
For ...
4
votes
1answer
77 views
Obtaining a feasible solution for underdetermined system of linear equations satisfying inequality constraints
I would like to obtain a feasible solution for an under-determined system of linear equations,
$$Ax=b$$
where, $A \in \mathbb{R}^{7\times9}, \, x \in \mathbb{R}^{9\times1}\text{and } b\in\mathbb{R}^...
1
vote
0answers
88 views
Optimization of a blackbox function with an equality constraint?
I believe this would be an interesting problem.
I have a blackbox function which can take 2-60 input variables $(X_1,X_2,...X_n)$ which are to be optimized. I'm calling this objective function as a ...
4
votes
1answer
106 views
Ways to speed up solving an LP with Google's ortools
I'm having an issue solving an LP of the form:
$$\min z = c^Tx$$
$$\text{s.t.}$$
$$Ax \geq b$$
$$x\geq p$$
$1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$
The specific problems I'm running into ...
1
vote
3answers
152 views
Optimization of a blackbox function
Let's say that we have an objective function $f(\mathbf x,\mathbf y)$ which has the parameters $\mathbf x=[x_1\ldots x_n]$ and $\mathbf y=[y_1\ldots y_n]$. Here, $\mathbf y$ is a blackbox variable ...
1
vote
0answers
44 views
Sequential Quadratic Programming for Quadratically Constrained Quadratic Programs
A standard Quadratically Constrained Quadratic Program (QCQP) is of the form:
$$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x
$$
$$
subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{...
2
votes
2answers
168 views
Knapsack problem with fixed number of elements?
I am looking at an optimization problem that looks like this:
$$
\text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\
\text{subject to}\;\; ||...
4
votes
0answers
34 views
Obtainting KKT for QSDP for the trace inequality constraint
I am working on developing my own solver(for implementation on hardware), based on IPM for following problem:
\begin{equation}
\begin{split}
\min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\
\text{...
1
vote
0answers
84 views
functional second derivative
I'm trying to build a numerical solution for a parameter estimation problem of reaction-diffusion equation, using the adjoint method.
To summarize it, I'm trying to minimize the function
$$ G=\frac{...
4
votes
0answers
100 views
How to apply an integrated constrain condition in FEM?
I'm running some simulation using FEM. In my model I need to apply a constraint condition to the governing equation. My governing equation similar to the diffusion equation as below:
$$\frac{\...
1
vote
0answers
44 views
Obtaining the lagrangian multipliers in an optimization problem
Suppose we have this simple optimization problem
\begin{align*}
\underset{x\in V}{\text{min}} &~ f(x) \\
\text{s.t.}& ~x \leq \beta
\end{align*}
Using slack variables
\begin{align*}
...
5
votes
1answer
80 views
Constrained simulated annealing
Simulated annealing is a useful technique for finding near-optimal solutions to combinatorial problems. I have found a lot of tutorials on implementing the basic algorithm, but miss a general guide as ...
4
votes
1answer
206 views
adjoint method for reaction-diffusion problem
I'm trying to code a parameter estimation for a reaction-diffusion problem. Namely, knowing the distribution of tumor density $u$ at time $0$ and $T_f$ ($u^0$ and $u^f$), what are the best ...
0
votes
1answer
112 views
pde-constrained optimization
I'm trying to solve a problem where I have a initial and final distribution of tumor, and my goal is to find the best map of parameters (diffusion and reaction terms) for a reaction-diffusion equation,...
1
vote
0answers
62 views
What are the numerical properties to consider between Augmented Lagrangian and the Penalty Method?
I'm interested in (locally) minimizing a smooth nonconvex objective function:
$$
f(\textbf{x}_1, \textbf{y}_1,\cdots, \textbf{x}_n, \textbf{y}_n)=\sum_{i=1}^ng(\textbf{x}_i, \textbf{y}_i)
$$
Subject ...
1
vote
1answer
175 views
Minimization of least square function together with a nonlinear function
I have the linear underdetermined system $$Ax=b$$ and I need to find $x$ constrained by the maximization of a score function $g(x)$.
I could find the minimum of a function like $$|Ax-b|^2+1/g(x)$$ ...
4
votes
3answers
134 views
How can I use Projected Gradient Descent for this optimization problem with constraint?
Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that
$$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
3
votes
1answer
118 views
Why do active set methods or the simplex method pivot only one variable at a time?
Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
3
votes
1answer
281 views
Scaling/nondimensionalization for numerical optimization
I have a numerical optimization problem that I am trying to scale appropriately, in order to allow for the solver to achieve faster and more accurate results. I found a paper here that had a short ...
3
votes
1answer
69 views
Description of algorithm for small scale linear least squares with box constraints
I have small scale dense least squares problem with box constraints
$$\mbox{argmin}||Ax - b||^2 \quad $$
$$\mbox{subject to} \quad l_i \leq x_i \leq u_i,$$
Number of variables is about 10-50, ...
1
vote
2answers
84 views
How can i solve this non-convex multi-variable optimization problem?
I want to solve the following optimization problem:
$$\min_{A,B,X} \|Y-AX\|_F^2 + \lambda_1 \|Z-BX\|_F^2+ \lambda_2 \|B\|_F^2$$
$$s.t ~~x_{ij}~ \geq 0$$
in which, $Y$ and $Z$ are data matrices and ...
2
votes
0answers
77 views
Minimize number of rectangles that cover all the points
I have a 2d distribution of moving points with known trajectories represented in a 640x480 image. Here is the initial state:
I have to find the minimum number of rectangles with fixed dimensions (...
0
votes
1answer
48 views
Mixed Integer Nonlinear Programming Problem
There is a problem I want to solve. The function is:
\begin{align}
&\underset{a,b,\textbf{vec}}{\text{minimize} \text{ }\text{ }\text{ }\text{ } } f=\sum_{i=1}^{b}(\textbf{vec}_i)^{a}\\
&\...
0
votes
1answer
109 views
How to create an optimal pizza delivery plan and how to visualize it
This question is quite open, and the actual problem comes from something you would probably consider an everyday niche (something you'd probably take for granted without really thinking about it). ...
1
vote
1answer
150 views
How can I solve on a computer a large projection problem with redundant constraints?
This question is the essence of this one. After we remove all the cruft, we can recast it as follows:
Problem: Given $b \in \mathbb{R}^n$, $C\in \mathbb{R}^{n\times m}$, and $g\in \mathrm{Range}(C^...
2
votes
1answer
92 views
Optimization of multiple functions
I have 3 functions which consist of 6 variables $p_1,p_2,p_3,p_4,p_5,p_6$. The value of each function is equal to $x$ (say):
\begin{align}
f_1 &= \operatorname{sign}(2-p_1) \sqrt{|2-p_1|} + \...
3
votes
0answers
156 views
Optimal Control using Dynamic Programming - Optimizing for Furthest Distance
So I have been investigating a problem to get a glider with control of its elevator to fly as far as possible from any given initial state. To keep this simple, we will view this in 2D space with the ...
1
vote
1answer
322 views
Regularization vs constrained optimization of an ill posed tomography problem
I am trying to solve an ill-posed linear system of equations. The particular system has 160 equations and 400 variables. Moreover, the condition number of the left hand side matrix is of order $10^{16}...
3
votes
1answer
66 views
Solving multiple least-square problems with the same constraints
The following least-square problem can be solved efficiently (e.g. using matlab's lsqlin):
$$\vec{x}^*=\arg\min_\vec{x} ||C\vec{x}-\vec{t}||^2\,\ s.t.\ Ax \le \vec{b}$$
where the parameters of the ...
3
votes
1answer
48 views
Linear programming with stochasticity?
Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution.
Now, I would like to solve the same problem but with stochasticity ...
7
votes
1answer
88 views
Intersections of supports constraint
Let $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ and $\text{supp}(\mathbf{x}) \subset \{1,2,...,n\}$ denote the set of indices such that $\mathbf{x}$ is non-zero.
What type of optimization problem can ...
