Questions tagged [optimization]
Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.
22,553
questions
10
votes
2
answers
318
views
Applications of Linear Programming to pure mathematics
This semester I'm taking a course in Linear Programming. While the topic is very interesting, all the applications I can find about this topic seem to be outside of mathematics. What are some ...
0
votes
0
answers
21
views
SQP and first order Taylor approximation
I am trying to use the SQP solver with a nonlinear constraint. The solver requires a linear constraint so I am trying to approximate the constraint with the first-order Taylor approximation. Is this ...
0
votes
0
answers
36
views
3 Cicles Problem: Minimizing the Distances Cost Function
I appreciate your assistance!
I’m working on locating a point that minimizes the sum of squared distances from a set of circles. The objective function to minimize is:
$$
E(x,y) = \sum_i \big( (x-w_i)^...
3
votes
1
answer
97
views
A trajectory optimization problem [closed]
The following problem comes from information theory. Specifically, for an impossibility bound I need to supply the decoder with side information and the answer will say what policy gives the tightest ...
0
votes
0
answers
15
views
Optimization problem with highly coupling objects and inequality constraints.
For a better vision, see this image:
We have the optimization problem $$\begin{align}
\min_{[a_1,a_2,\ldots,a_N]}&\prod_{i=1}^{N}\left[1-{A\over\prod_{n=1}^{R}\left(\lambda_n+{\sum_{u\ne i}|C_i\...
0
votes
1
answer
44
views
How do I know when a point is a max or a min (multivariable optimisation problem)?
I am stuck in understanding how I can deduce if the solution I found is a max or a min. The exercise reads:
$$\max \quad f(x, y) = 2x - y \qquad \text{subject to} \qquad \begin{cases} x^2+y = 2 \\ x+y ...
1
vote
1
answer
63
views
Max and min in many variables (Lagrange multipliers)
I have doubts for what concerns the end of this exercise. I have the function $f(x, y, z) = x$ and I have to find min and max subject to the constraints $x^2+y^2+z^2 = \frac{5}{2}$ and $y + z = 1$.
I ...
1
vote
0
answers
114
views
Penalty method and the question of equivalence in a specific optimization problem
I encountered an interesting problem in “Practical Methods of Optimization” by R. Fletcher, which utilizes the penalty method to solve the following constrained optimization problem
\begin{align}
{\...
5
votes
1
answer
189
views
Optimality condition inspired by subdifferential of square root: $y\in \text{argmin}(g(x)-a^Tx ) \Rightarrow y\in \text{argmin}(g^2(x)-2g(y)a^Tx).$
Let $f:\mathbb R^d\to\mathbb R\cup\{+\infty\}$ be a proper convex lower semicontinuous function. Suppose that $f$ is bounded by below, and for simplicity that $\inf f = 0$. Set $\varphi:\mathbb R^d\to\...
2
votes
1
answer
170
views
Effect of rank-one update on the smallest eigenvalue and its eigenvector
Suppose diagonal $D\in \mathbb R^{n\times n}$ with $D\succeq 0, v\in \mathbb R^n,$ and $\alpha>0$ are given. Can we $\textit{exactly}$ identify the smallest eigenvalue of $D+\alpha vv^T$ and its ...
1
vote
0
answers
22
views
Approximating Linear Combination of Independent Random Variables
Let $X_i$ be independent, discrete random variables each with a known distribution and $\lambda_i$ be unknown real numbers. I am interested in running a linear optimisation over the $\lambda_i$ ...
0
votes
1
answer
37
views
How to show that the set of minimizers for a convex function over a convex set is closed?
It is well known that the set of minimizers of a convex function over a convex set is convex.
It is also true that it is closed. But I have not been able to show this result.
Let $f$ be a convex ...
0
votes
0
answers
21
views
maximize combination(n, x) * combination(n, y)
I have 3x + y = 1100, the combination x samples out of 500 C(500, x) and the combination y samples out of 500 ...
2
votes
0
answers
30
views
Gradient descent for solving complex-valued $Ax = b$?
Suppose that $A \in \mathbb{R}^{n \times n}$ is symmetric positive definite. In this case, solving $Ax = b$ with $x,b \in \mathbb{R}^{n}$ is equivalent to find
\begin{align}
\underset{x \in \mathbb{R}^...
0
votes
0
answers
40
views
Maximising a quadratic expression in 3 variables
If $x^2 + y^2 + z^2 = 1$
Maximise $(cy-bz)^2 + (az-cx)^2 + (bx-ay)^2$
This can be written as the square of the magnitude of the determinant:
$$
\begin{vmatrix}
\widehat{i} & \widehat{j} & \...
7
votes
1
answer
714
views
Where is the optimal point to “hide” in a shape?
A puzzle I’ve wondered about but never got around to solving/verifying:
In the game Pokemon Let’s Go, the Pokemon Abra instantly teleports away if the player is detected within its line of sight.
Let’...
0
votes
0
answers
9
views
Stress Vector Tracing algorithm: paper clues and thoughts
I'm looking for someone to aid me in understanding the undefined vectors of this paper I'm hoping that the answer will seem intuitive to someone with a strong understanding of computational geometry. ...
0
votes
1
answer
17
views
Find smallest step size so that gradient descent will diverge
Suppose I want to use fixed-sized gradient descent for a function like $y=x^2$ using the formula starting at some point (for example $x_0=4$):
$x_{i+1}=x_{i}-\alpha*f'_{x}(x_i)$
I am trying to figure ...
0
votes
0
answers
39
views
Giving each student a set of questions so that any two would have minimal number of common questions
I need to create an algorithm that would give a set of questions to each student based on students` majors, number of students, possible questions.
I am hosting an exam for my students.
Each student ...
2
votes
1
answer
34
views
Minimizing the functional $J[y]=\int_0^1 (\frac{1}{2}y'^2+yy'+y'+y)dx$ with undetermined boundary values
I'm trying to find the minimum to the functional $$J[y]=\int_0^1 \left(\frac{1}{2}y'^2+yy'+y'+y\right)\, \mathrm dx$$ where the values for $y$ at the boundary values are not specified.
My first idea ...
0
votes
0
answers
23
views
Non-negative QP
I have a rather peculiar contrained quadratic programming problem where I try to fit a left-stochastic matrix and I am not sure how to properly solve it. Consider matrices $S\in\mathbb R^{D\times N}$, ...
1
vote
0
answers
52
views
How to calculate $E(X|X\ge Y)$ if X is dependent with Y
Now we have several independent and identically distributed random variables following the uniform distribution on the interval [0, 1].They are denoted as $x_1, x_2, x_3, ..., x_m$ and $y_1, y_2, ..., ...
2
votes
1
answer
43
views
Global minimization of finite Laurent series (rational function) in $\mathbb{R}^+$
Context: I am creating a special ballistics simulation with nonstandard physics, and I have reached a step where I need to find the global minimum of a rational function very fast to be able to run ...
2
votes
2
answers
95
views
Find transformation between two sets of points by minimizing the maximum distance
There are two sets of four 2D points.
There is a 1 to 1 correspondence between the two sets.
The points in both sets are close to the following nominal positions, only deviate with a random value in ...
0
votes
0
answers
28
views
Minimax theorem for convex quadratic programming
I have a simple and stupid question if I have a convex quadratic optimization problem with polyhedral constraints as follows:
$$
\begin{aligned}
\inf_{x \in \mathbb{R}^{n}} & x^{\top} Ax + b^{\top}...
0
votes
1
answer
76
views
Linear programming with $XX^T=Identity$ constraint
I have the following system of equations
$$X R a - c_1 = 0$$
$$X a - c_2 = 0$$
$$X X^T=Identity$$
where $X\in\mathbb{R}^{3x3}$, $a,c_1,c_2\in\mathbb{R}^{3x1}$, $R\in\mathbb{R}^{3,3}$ is a rotation ...
2
votes
0
answers
48
views
Dynamic programming, prove function is monotone non-decreasing
I am currently studying dynamic programming using the Bersketas book: Dynamic programming and optimal control, volume 1. The question is regarding the notation used, but is the following:
The ...
0
votes
1
answer
35
views
Farkas lemma query
I had a query related to Farkas's lemma. As i understand as per the lemma the following two statements are equivalent:
For a matrix $A \in \mathbb{R}^{m \times n}$,and vector $c \in \mathbb{R}^{n}$ ...
0
votes
0
answers
15
views
conjugate duality involving sum of convex functions
Consider the primal problem
$$
\min_x \{f(x):G(x)\in Y\}\tag{$P$}
$$
rewritten as
$$
\nu(P^\prime) = \min_x \{f(x):y\in Y,\;y=G(x)\}\tag{$P^\prime$}
$$
where $G:\mathbb{R}^n\to \mathbb{R}^m$ with $G(x)...
0
votes
0
answers
32
views
Bath towel on the spheric rope: minimize the area of self-intersection of a 'folded' spheric rectangle
Some time ago I was curious about a question related to my bath towel, which I hang on a rope to have fun (you can use your own towel to do this experiment in bath-o if you want):
'There is this ...
1
vote
0
answers
50
views
Given matrix A with $A_{i,j} = f(i,j)$, how can I find out if A is positive semidefinite?
I'm working on a problem whose solution relies on finding if an arbitrary matrix A is positive semi-definite. A is real valued, square and symmetric, and each of its entries are given by:
$A_{ii} = f(...
4
votes
1
answer
343
views
Optimizing sum of a quadratic function and $l_1$ norm on a sphere
I am currently attempting to derive the dual and KKT conditions for the following optimization problem:
\begin{equation}
\min_{x\in \mathbb R^n} \quad x^TMx+a ||x||_1^2 \quad \text{subject to} \quad ||...
0
votes
0
answers
27
views
Deriving the dual problem from the complex primal problem
I faced the following problem recently. When I was working on an electricity market clearing problem, it is hard for me to derive the dual problem of it, which is necessary to obtain the optimal price....
1
vote
1
answer
62
views
reduction from QCQP to SOCP
Suppose a QCQP problem :
$$ \min_{x\in\mathbb{R}^{n}}f\left(x\right)=\frac{1}{2}x^{T}P_{0}x+q_{0}^{T}x$$
$$ s.t:\begin{cases}
\frac{1}{2}x^{T}P_{i}x+q_{i}^{T}x+r_{i}\le0 & i=1,2\dots,m:m\le n
\...
1
vote
0
answers
19
views
LCP of KKT from a QP without non-negativity constraint and semidefinite Q matrix
Most formulations of the LCP derived from the KKT conditions of a QP tackle problems with non-negativity constraints $x\ge 0$. Wikipedia presents an alternative without the non-negative constraints ...
0
votes
1
answer
95
views
Finding the maximum volume of a cuboid in a sphere
A cuboid, length of whose one edge is √2 units, is inscribed in a sphere of radius of √2 units. If maximum possible volume of suboid is V cubic units, then V/2√2 is
I took the equation of sphere to be ...
0
votes
0
answers
53
views
Deterministic optimisation problem with inequality constraint
Let's consider the following deterministic constrained optimisation problem, where $c(t)$ is the control, and $x(t)$ and $y(t)$ are the state variables:
\begin{align}
J(t) = \inf_{c(t)} \ &\int_0^\...
0
votes
0
answers
20
views
largest ratio between 2 points' Euclidean distance and edge distance over all pairs of points on a planar polygon's edges
A geometry problem I worked on in a REU program from years ago just came to my mind.
Let's define a constant called "chord-arc constant" for any planar polygon as the largest ratio between 2 ...
6
votes
0
answers
145
views
Maximal Convex Hull in Integer Grid
What set of points on the $256 \times 256$ integer grid maximizes the number of vertices in its convex hull?
For the full context, I was given an assignment to test algorithms that find the vertices ...
0
votes
2
answers
37
views
Algorithm for allocating numbers into groups such that the maximum number of elements in the groups is minimized
Suppose there is a set of arrays $S= [A_1, A_2, ..., A_k] $, where $A_i$ is a finite subset of $\mathbb{Z}$. Given a positive integer $g$, I want to build $g$ sets $G_1,G_2,\dots,G_g$ such that $\...
0
votes
0
answers
40
views
A linearization in optimization problem
The step $\boldsymbol{\beta}^{t+1}$ in solving an optimization problem
is given below.
$$\boldsymbol{\beta}^{t+1}=\mathrm{argmin}_{\boldsymbol{\beta}}\frac{1}{2}\left\Vert \mathbf{u}^{t}-\boldsymbol{\...
0
votes
1
answer
38
views
Why it is not possible for both primal and dual LP to be unbounded?
I already read this post and its answers and I am still not satisfied.
I want to know how to use weak duality to explain why it is not possible for both primal and dual LP to be unbounded.
Here is one ...
1
vote
1
answer
46
views
Is the Uniqueness of Minimum Norm Elements in $L^2$ Spaces a Consequence of Strict Convexity?
I'm delving into the concept of strict convexity within $L^2$ spaces and its implications for the existence and uniqueness of elements with minimum $L^2$ norms. Given $L^2(\mathbb{R})$'s role as a ...
0
votes
1
answer
29
views
Do Karush Kuhn Tucker $\mu$ conditions have to be unique?
In KKT, we have some optimal point $x^*$ with associated $\mu^*$ value for inequality constraints. Are these $\mu^*$ values unique for a given $x^*$ (for the primal problem)?
It seems that when these ...
0
votes
0
answers
48
views
Optimization word problem involving perimeter and area of an arched window
I'm working through an optimization problem in my textbook about maximizing the area of a rectangular window with an arched top.
My question is concerns how to think about a certian variable. I'm torn ...
0
votes
2
answers
71
views
Help with reformulating linear programming with rounding numbers
I have the following problem, abstracting away a few details from a real-world application, that I want to solve with linear programming (or any other mathematical optimization with constraints, ...
8
votes
4
answers
322
views
Proving a multivariate normal distribution gets the maximum entropy when mean and covariance are given
I'm working on a homework question. The first part was:
Given an unbounded one dimensional continuous random variable: $X\in\left(-\infty,\infty\right)$, that satisfies:$\left\langle X\right\rangle =\...
0
votes
1
answer
57
views
How to prove or disprove a function is Lipschitz continuity?
Because I am not majoring in math, I wonder if there is a standard approach to prove or disprove Lipschitz continuity.
In my case, I want to prove that the Mean Squared Error (MSE) loss function for ...
0
votes
0
answers
31
views
Equivalence of optimization problems
In Boyd and Vandenberghe (https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf), section 4.1.3, they say:
We call two problems equivalent if from a solution of one, a solution
of the other is ...
1
vote
0
answers
14
views
Maximum number of local minima in k-means
Suppose $\mathcal{Z} = \{z_1, \dots, z_n\}$ is the set of points in $d$-dimensional Euclidean space. The aim is to partition the dataset into $(K\leq n)$ distinct clusters $R_1,\dots, R_K$ where $R_i\...