Questions tagged [constrained-optimization]

Questions about optimization problems subject to additional constraints.

Filter by
Sorted by
Tagged with
2
votes
1answer
58 views

Gradient descent in constrained optimization of barrier function

This question may be too basic, but I was wondering if it is possible to implement simple methods such as gradient descent or its variations to find the minimum of barrier functions in constrained ...
6
votes
2answers
126 views

How to solve calculus of variations problems numerically?

For example, how to solve the well-known isoperimetric problem (i.e., to enclose the largest area with a fixed-length curve)? We can simplify things a bit and fix the two ends of the curve at $[a,0]$,...
0
votes
1answer
53 views

Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$

Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$ Question What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\...
1
vote
0answers
62 views

Ramp least squares estimation

With some given $s$ value, let \begin{equation} \begin{aligned} h(\beta)&=\min(\sum_{i=1}^n(Y_i - X_i\beta)^2, s)\\ &=\sum_{i=1}^n(Y_i - X_i\beta)^2-\max(0, \sum_{i=1}^n(Y_i - X_i\beta)...
4
votes
3answers
97 views

Maximize a function of an orthogonal matrix

I'm trying to write up a small code that, given a set of normal vibrational modes for a molecule, will convert them to localized vibrational modes. To do this I'm following the procedure from J. Chem. ...
0
votes
0answers
35 views

Least square approximation of a polynomial with a constraint on the derivative in Python

I'm trying to fit a polynomial of the third degree through a number of points. This could be a very simple problem when not constraining the derivative. I found some promising solutions using CVXPY to ...
1
vote
0answers
11 views

Long AMPL model preparation time

We deal with a large-scale linear optimization problem (~50000 variables and ~4000000 constraints). We use AMPL Studio modeling environment for problem modeling and then calling linear solver (CPLEX, ...
1
vote
0answers
33 views

Minimizing a polynomial with millions of monomials

I need to minimize a single polynomial $P(x_1,x_2,...,x_n)$ with the constraint that for each $i$, $0\leq x_i \leq 1$. The number of variables in my practical problem is at most $50$. The degree is at ...
3
votes
0answers
27 views

How to set up and solve acceleration-limited trajectory optimization problems?

I've been trying to learn how to solve simple acceleration-limited trajectory planning problems. I'm working in C++ and I've been using the Eigen library to do linear systems solving. I'm doing the ...
3
votes
0answers
20 views

Sequence planning with 3 machines

together! First of all, I have to mention that because of my background as an Industrial Engineer, I have limited abilities in mathematics, but am disciplined enough to expand myself from ...
2
votes
1answer
129 views

Simultaneously maximize and minimize

I am virtually new to optimization (saw it years ago in a very shallow course) and now I came across a problem that I believe would require from it. The problem is I don't know exactly how to proceed. ...
3
votes
0answers
48 views

Constraint solver vs Bayesian optimizer for fast discontinuous processes

I have a complex domain-specific process that accepts inputs: 10-500 inputs, where each input is of type: enum: choice between multiple string or numeric values int: integers float: floating point ...
0
votes
0answers
42 views

Optimization (best input variables search) for a non-smooth non-linear unknown function

I am trying to optimize a system that monitors and advises a user multiple times over a certain period of time depending on changing outside factors. The systems behavior can be altered by 5 ...
5
votes
0answers
94 views

How to solve a 4th order nonnegative LASSO problem?

I need to solve the following 4th order nonnegative LASSO problem: $$ \min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1 $$ where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
4
votes
0answers
61 views

Fast approximate solver for vehicle routing problem

I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
2
votes
1answer
79 views

How to add extra constraints to a linear system for probabilities?

Background: I have an equation which looks like as follows: $W \times P = R$ $$\left[\begin{array} &{1}&{0}&{0}&-\frac{w_{1}}{w_{o1}} &\dots &{0} &-\frac{w_{1}}{w_{0} } \...
0
votes
0answers
109 views

Solving a non-convex optimization problem using fmincon

I am trying to solve a non-convex optimization problem using fmincon(). At each iteration, I am iteratively looking for the optimum value and when the termination ...
3
votes
1answer
99 views

Why would BFGS converge to a local minima of a non-convex function but maintain a large gradient?

I'm using BFGS to optimize a smooth but non-convex function $f$ that is computed by a simulation. The simulation also gives me a semi-analytical gradient $g$, which is verified by the numerical ...
0
votes
0answers
98 views

Augmented Lagrangian Techniques Frank-Wolfe Algorithm [python]

I'm trying to solve the convex quadratic problem (quadratic min cost flow problem) using the Frank-Wolfe algorithm. $$ \min\{x^TQx+qx: Ex=b,\quad 0\leq x \leq u\} $$ The standard algorithm is okay ...
3
votes
0answers
67 views

Solve ODE with non-negative and maximization constraints

My task is to solve $$\eta_k\frac{d^2C_k}{dz}(z)=-e_k, k = 1,2,3$$ $$C_k\ge0$$ $$C_1(0)=0, C_2(0)=A, C_3(0)=0$$ $$C_1(L)=B, \frac{dC_2}{dz}(L)=0, \frac{dC_3}{dz}(L)=0$$ with $$e_1 = -\beta_1-\beta_3$...
1
vote
1answer
159 views

How do I solve the matrix equality constrained optimization problem using Lagrangian multipliers?

Solve the following minimization problem in $\mathbf{X} \in \mathbb{R}^{m \times n}$ $$\begin{array}{ll} \text{minimize} & \frac 12 \| \mathbf{X}\mathbf{X}^T -\mathbf{A} \|^2_\mathcal{F}\\ \text{...
2
votes
0answers
40 views

Biconvex problem whose objective function depends on only one variable

I am solving the following biconvex problem: $$\min_{x,y} f(y)$$ $$s.t. ~~ g(x) \leq 0$$ $$~~~~~h(x,y) = 0$$ $$x \in X, y \in Y$$ where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
1
vote
1answer
51 views

Vehicle Route assignment with capacity constraint

Problem Background I'm trying to find a solution/model to the following problem: Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each ...
1
vote
1answer
46 views

Research articles on MultiObjective Non-Linear Programming (MONLP)

I'm looking for papers dealing with multi-objective non-linear programming which could help me implement an algorithm to solve my problem. My problem is : Maximize $f(x) = c \cdot x$, while ...
0
votes
1answer
60 views

Formulate and solve a simple conic programs in cvxpy language [closed]

Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $\|a\|_2 \le r$. Define $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$, and assume it is non-empty. Question (A)...
2
votes
1answer
68 views

Question about strange outputs from the CVXPY solver

I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem: ...
2
votes
0answers
52 views

How to find two points within defined region in this constrained optimization problem?

I am doing a project related to robotics where I am using fmincon function from matlab to minimize the distance between the points ...
4
votes
0answers
74 views

Solution of constrained system of ODEs

Can someone point me in a direction to solve this kind of integral constrained system of ODEs. \begin{align} &\int_0^{1/2}\dot{y}^2(t)=p\\ &2\lambda_1\ddot{y}(t)+\pi cos(\pi y(t))=0\\ &y(...
0
votes
1answer
36 views

Can LINCS algorithm be used for colliding molecules?

Supposing that one molecule is static and one is dynamic, can the dynamic one be solved with LINCS for its shape (angle, bond length) constraints and also keep collisions with static molecule off, ...
0
votes
1answer
102 views

Is this a knapsack problem?

I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
3
votes
1answer
44 views

Improve optimization speed for a set of similar problems: Quadratic programming with a warm start

I am repeatedly solving quadratic program, $x^T Q x$ with time dependent linear constraints $Ax=b_t$. Dimension of $x$ is around 10000 and there are around 50 constraints. I want to solve the ...
1
vote
1answer
169 views

sum of absolute difference constraint in optimization problem

I am writing a model for an optimization problem. I need to write the following constraint: $$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$$ How to write this constraint (or linearize)? ...
1
vote
1answer
140 views

Nature of stationary points of a Lagrangian fuction

I would like to extremize a certain function $f$ with respect to a parameter $x$, under constraints $g_1(x) = 0, ..., g_m(x)=0$. In order to achieve this, I consider the Lagrangian function $L(x, \...
2
votes
1answer
54 views

Techniques to remove a function from Levenberg-Marquardt when it is against box constraints

I have a somewhat large (20+ dimensional) root finding problem that I'm solving with Levenberg-Marquardt. One of the functions has box constraints on [0, 2]. When it is against those bounds it will ...
1
vote
1answer
187 views

Why does Newton's method with Linear Equality Constraints use KKT condition?

Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint. The problem only has equality constraint. Why ...
1
vote
0answers
34 views

Logging vs outputs in iterative optimisation

I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
2
votes
0answers
37 views

Sensitivity Lagrangian solution general case

I have asked this question already on maths and mathoverflow. Just a question about a literature reference. I am writing a paper for engineers. Usually for the Lagrange multiplier problem $$ \...
1
vote
0answers
35 views

Efficient numerical optimization of an “almost separable” function

I have come across an optimization problem with the following objective function: $$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
6
votes
0answers
143 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 ...
4
votes
1answer
994 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
211 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
92 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?
2
votes
0answers
268 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 ...
6
votes
1answer
320 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
200 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
500 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
44 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 ...
3
votes
2answers
167 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
30 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
254 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 ...