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.
17,979
questions
0
votes
0answers
10 views
Given area of parallelogram, find smallest distance from origin to furthest point (complex numbers)
On the complex plane, the parallelogram formed by the points 0, $z,$
$\frac{1}{z},$ and $z + \frac{1}{z}$ has area $\frac{35}{37}.$ If the
real part of $z$ is positive, let $d$ be the smallest ...
0
votes
0answers
2 views
Anything we can say about properties of the optimal solutions?
I'm working with the expression
$DROT(a,b) = \max_{f,g} \int f(x)\,dP(x) + \int g(y)\,dQ(y) - \frac{1}{\gamma}(\phi(f)+\varphi(g))$ subject to $f(x)+g(y)\leq c(x,y)$ where $\phi$ and $\varphi$ are ...
1
vote
0answers
13 views
How to maximize both of these expressions with respect to $A$ and $B$
I wish to maximize
\begin{equation}
f(A,B) = \dfrac{\dbinom{A+B-a-b}{A-a}}{\dbinom{A+B}{A}}\qquad\text{and}\qquad g(A,B) = \dfrac{\dbinom{A-a}{x-m}\dbinom{B-b}{y-n}}{\dbinom{A+B}{x+y}}
\end{equation}
...
-1
votes
0answers
12 views
What does min(0,M(x0) and -min(0,M(x)) mean? [closed]
I wonder what does min(0,M(x)) and -min(0,M(x)) mean?
any help will be appreacited!
0
votes
0answers
14 views
Completeness with Hilbert's metric
This picture was taken from this P. J. Bushell's paper. Here $E=\mathbb{S}^{n-1}\cap\mbox{int} K$, $M(x/y)=\max\{x_i/y_i\}_{i=1}^n$, $m(x/y)=\min\{x_i/y_i\}_{i=1}^n$ and $d(x,y)=\log\frac{M(x/y)}{m(x/...
1
vote
0answers
21 views
Minimizing trace of pseudoinverse of a matrix
Given symmetric positive semidefinite diagonal rank-$r$ matrix $R \in \mathbb{C}^{m \times m}$, where $r < m$, and scalar $p \geq 0$, I have the following optimization problem in matrix $X \in \...
-1
votes
0answers
17 views
Show that $\psi$ is minimized if $\alpha=x^Ty/y^Ty.$
I have the following problem:
Let $x$ and $y$ be in $\mathbb{R}^n$ and define $\psi :\mathbb{R} \to \mathbb{R}$ by $\psi (\alpha )=||x-\alpha y||_2$. Show that $\psi$ is minimized if $\alpha=x^Ty/y^Ty....
0
votes
0answers
11 views
maximizing $F(a_1,a_2,…,a_N)=\sum_{i=1}^N E[X(a_i)]$?
Define
$$F(a_1,a_2,...,a_N)=\sum_{i=1}^N E[X(a_i)]$$
where $X(a_i)$ are sampled from some distribution and $a_i$ are real numbers. My question is not seeking an exact solution but I was wondering ...
0
votes
1answer
30 views
Unbounded convex hull is possible?
I'm reading this lecture note for additional study.(https://people.orie.cornell.edu/dpw/orie6300/fall2008/Lectures/lec05.pdf)
For Q the convex hull of a finite number of vectors v1, v2, . . . , vk, Q ...
0
votes
0answers
9 views
Given $x \in {\rm int}(K)$ (covered by nondecreasing cones $\{K^r\}$), does there exist $r_0$ s.t. $x \in {\rm int}(K^{r_0})$?
Let $K\ (\subseteq \mathbb{R}^n)$ be a closed convex cone and $\{K^r\}_{r=0}^\infty$ be a family of closed convex cones satisfying $K^r \subseteq K^{r+1} \subseteq K\ (\forall r)$.
Assume that ${\rm ...
-1
votes
0answers
14 views
Calculus Optimization- volume [closed]
A closed rectangular box has a volume of 2253.818cm^3 and has the dimensions L=22.9cm, H=7.4cm, W=13.3cm. Find the dimension of the box so that it holds the same volume but minimizes the material to ...
2
votes
0answers
36 views
Find $g(x,y,z);p(x,y,z)\ge 0$ so that $f(x,y,z):=x\cdot g(x,y,z)+p(x,y,z)$
We all know the following fact:
If $f(x)$ is nonnegative-polynomials for $x\ge 0,$ then $f(x)=g(x)+x\cdot h(x),$
where $g(x)$ and $h(x)$ are SOS.
So I wanna know how the way you usually use to make $...
1
vote
0answers
10 views
Bound on the difference between BFGS approx-Hessian and the exact Hessian
Given a strongly convex function $f(x)$ with Lipschitz continuous gradient and Lipschitz Hessian, i.e.,
$$\mu I \leq \nabla ^2 f(x)\leq LI,\quad ||\nabla^2f(x)-\nabla f^2(y)||\leq M||x-y||^2,$$
and if ...
1
vote
0answers
16 views
Expectation-Maximization (EM): M-step
The goal is to calculate
$$\min_q \text{KL}\big(q(z | x) \parallel p(z|x, \theta)\big) = \min_q \sum_{x \in \mathcal{D}}\sum_{z} \log\big(\frac{q(z | x)}{p(z|x, \theta)}\big) \cdot q(z | x)$$
where $\...
1
vote
0answers
14 views
Resources for “non-computational” and “non-algorithmic” optimisation problems?
I have seen on this site some nice recommendations on books of optimisation. Most of them and most of the books I find includes a lot of analysis of algorithms.
However, certainly there are plenty of ...
1
vote
1answer
52 views
Maximize $\binom{N-m}{n-k}/\binom{N}{n}$ with respect to $N$
The question is actually in the title. I wish to maximize this function with respect to $N$, where $m, n$ and $k$ are fixed naturals less than $N$ and also $k\le \min(m,n)$. How do I go about proving ...
-3
votes
0answers
32 views
AP Calculus Optimization Problem Help [closed]
I have no clue.
A closed box with a square base is to have a volume of $2000$ cubic inches. The material for the top and bottom of the box costs $\$3$ per square inch. The material for the sides is ...
0
votes
0answers
13 views
Show that $C = D$ if and only if their support functions are equal.
Suppose that $C$ and $D$ are closed convex sets in $R^n$. Show that $C = D$ if and only if their support functions are equal. The support function of a set is defined as $S_C(y) = \sup\{y^Tx : x \in C\...
-1
votes
0answers
37 views
Optimization Bird Problem
I'm having trouble with an Optimization problem, the problem is as follows: $$ E(t) = \frac{3000t}{t+4} $$
A bird is foraging for berries. If it stays too long in any one patch it will be spending ...
0
votes
0answers
13 views
Understand Proximal maps
I am reading about Bregman Proximal Gradient Methods to minimize $f(x) + h(x)$, and the proximal maps of different functions https://arxiv.org/abs/1808.03045. For example, with ...
0
votes
0answers
15 views
do we use $-\mathbb{Z}$ or $\mathbb{Z}$ (obj function) when it comes to the simplex tableau method or it doesn't matter?
Okay I came across lots of resources, some of them use $-\mathbb{Z}$ and some others use $\mathbb{Z}$ in the last row of the objective function, I know that it depends on the standard form and how we ...
5
votes
1answer
114 views
The inverse type of Bernhard Leeb's solution for IMOā1983āinequality
Given three side-lengths $a, b, c$ of a triangle. Prove that
$$a^{2}b\left ( a- b \right )+ b^{2}c\left ( b- c \right )+ c^{2}a\left ( c- a \right )\geq 3\left ( a+ b- c \right )c\left ( a- b \right )\...
0
votes
0answers
18 views
If one of these LPs to be unbounded, and the other to be unbounded? [closed]
$A : max \{cx+hx : Ax + Gy \leq b,(x,y) : R^n_+ \times R^p_+ \}$
$B : max \{cx+hx : A'x + G'y \leq b',(x,y) : R^n_+ \times R^p_+ \}$
where these LPs formulated from mixed integer linear set,
$S :=\...
0
votes
0answers
9 views
Finding the optimal insertion points
Consider the infinite string $S = aaa\ldots$
I want to insert the character $b$ in $S$ such the resultant $S$ will have approximately $p\%$ $b$'s ($p$ is known)
I also want the inserted $b$ to be as ...
1
vote
1answer
97 views
Optimization : Solve $4$ unknowns using $4$ equations
Suppose we have 4 points say A($x_1,y_1,z_1$), B($x_2,y_2,z_2$),C($x_3,y_3,z_3$), D($x_4,y_4,z_4$). Where $x_1,x_2,x_3,x_4,y_1,y_2,y_3,y_4$ are known points and rest $z_1,z_2,z_3,z_4$ are unknown ...
1
vote
0answers
23 views
Convexity of argmax
Suppose that the function $F(x,y)$ is supermodular in $(x,y)$. We know that this implies that $x^* =\operatorname{arg\, max} F(x,y)$ is increasing in $y$. Under which conditions (if any) do we have ...
2
votes
1answer
25 views
Best polynomial approximation of a partially constant function
Suppose $\alpha \in [0;1]$. Let's define $f_\alpha$ as the function $[0;1] \to [0;1]$ with the following formula:
$$f_\alpha(x) = \begin{cases} 0 & \quad x < \alpha \\ 1 & \quad x \geq \...
2
votes
1answer
23 views
Is the following inequality in the form of integer linear programming?
Since I'm using an element of an array as an index of another array, is the following inequality still considered as ILP representation?
$1 - M[s[i], s[k]] + M[s[i], s[j]] >= 1$
M and S are ...
0
votes
0answers
16 views
Margin size and Support Vectors in Soft SVM
Suppose we have binary data $(x_{i},y_{i})$ and train a soft SVM for classification:
$$\min_{\omega,\zeta} ||\omega||_{2}^2 + C ||\zeta||_{1} \\
\text{s.t.}\\ 1-\zeta_{i} \le y_{i}(\omega^{T}x_{i} + b)...
1
vote
1answer
19 views
Programming connectedness of a graph
I have to model the following problem as an optimization problem with constant objecive function and I am stuck at one of the restrictions.
Say that we have an $n\times n$ table for a fixed $n$. We ...
1
vote
0answers
27 views
Maximizing tr(AB) under a rotation matrix constraint for B? Related to von Neumann's trace inequality
Let $\mathbf{A}$ and $\mathbf{B}$ be real matrices with $\mathbf{A}\overset{\mathrm{SVD}}{=}\mathbf{U}_A \mathbf{S}_A \mathbf{V}_A^\mathrm{T}$. I want to maximize
\begin{align}
\max_B \mathrm{trace}(\...
2
votes
1answer
51 views
Maximize quadratic function over unit sphere
In lecture, we proved that, given a symmetric matrix $A$, the
$$\max_{\|x\|_2 = 1} x^T A x$$
is the largest eigenvalue $\lambda_{\max}$ of matrix $A$: we diagonalize the matrix $A$ and show that for ...
2
votes
0answers
73 views
Find $m\!\left(a,b,c\right)\!,n\!\left(a,b,c\right)\!\geq 0$ so $H:=m\!\left(a,b,c\right)\!-n\!\left(a,b,c\right)\!\left(a-b\right)\!\left(b-c\right)$
I'm doing research on creating an SOS new method, I need to the help.
Introduction. Given three non-negative numbers $a,\!b,\!c,$ we have a symmetric polynomial
$$a\left ( ab+ 1- b \right )\!\left ( ...
1
vote
0answers
27 views
Unique solution in a quasi-convex optimization problem?
Let $f:\mathbb{R}^n\mapsto \mathbb{R}$ and $g:\mathbb{R}^m\mapsto \mathbb{R}$ be two differentiable functions and consider the optimization problem
$$
\min_{x\in \mathbb{R}^n} f(x)
$$
subject to
$$
g(...
0
votes
1answer
16 views
Can LP with bounded feasible region be converted to LP with unbounded feasible region after adding artificial variables?
In Big-M method we add artificial variables to a linear programming problem(call it $p$) to convert it to a secondary problem(call it $p^\prime$) so we can find basic feasible solution to start ...
1
vote
0answers
23 views
What minimizing challenges arise for functions which are not convex?
I am trying to figure out why functions that are convex (convex everywhere) are easier to minimize than functions that are NOT convex everywhere.
My main theory was that non-convex functions have ...
0
votes
0answers
11 views
KKT Maximization problem corresponding lambda values [closed]
Maximize: x1 + 4āx2
Subject to: 3x1 + 4x2 ā¤ 12
x1 ā„ 0
x2 ā„ 1
a. Find all the points in the constraint set and the corresponding lambda values
that satisfies the Karush-Kuhn-Tucker conditions.
b. Does ...
0
votes
1answer
10 views
reducing a feasible solution to a basic feasible solution
I have a doubt in Switching the solutions in linear programming. Here, we are reducing a feasible solution to a basic feasible solution. I know the result that in an LP, the optimal solution always ...
0
votes
0answers
11 views
Validity of proof concerning inequality
The objective is to prove the inequality using the Lagrange Multiplier:
$$
\Biggl(\prod_{i=1}^{n} \alpha_i \Biggr)^\frac{1}{n} \leq \frac{\sum_{i=1}^{n}\alpha_i}{n}
\ \ \ \text{for} \ \ \
\alpha_1,\...
3
votes
0answers
33 views
Efficiently finding the minimizer of a quadratic function over a finite subset of $\Bbb R^m$
Given matrix $A \in \Bbb R^{m \times m}$, let function $f : \Bbb R^m \to \Bbb R$ defined by
$$f(x) := x^T A x$$
Suppose there are $n \gg m$ points $a_i \in \Bbb R^m$. I seek to find
$$\min_{i \in [n]} ...
0
votes
1answer
23 views
Conversion of minimization to maximization objective under Frobenius norm
I want to understand how Schnass $^\dagger$ arrived at the maximising objective as described below (on page 5)
\begin{aligned} \displaystyle \min_{D,A} \Vert X-DA \Vert_F^2 &= \min_D \sum_n \min_{|...
0
votes
0answers
24 views
Integral of the product of two nonnegative functions
So I am having some difficulty trying to show the following;
Suppose $\int_a^b \frac{\partial^2}{\partial y'^2}L(x,y,y') w^2 dx \ge 0$, $\forall w$ s.t. $w(a)=w(b)=0$, show this implies $\frac{\...
0
votes
0answers
14 views
How to get the least number of cuts to be made without bending a frame to get straight segments?
The problem is as follows:
A locksmith has a rectangular iron frame, along with its diagonal,
which is represented in the figure from below, and an electric grinder
that can cut such metal. In an ...
0
votes
1answer
35 views
What is the least amount of straight cuts that should be made to get squares from a rectangle?
The problem is as follows:
Rachel has a rectangular piece of cloth which measures $2$ meters
large and $0.2$ meters wide. She is to use a guillotin which can only
makes cuts of $60$ cm of maximum in ...
0
votes
0answers
15 views
What is the least amount of cuts that should be made to make the word WABCTV7.1?
The problem is as follows:
The figure from below represents a solid which is made by 22 cubes.
How many cuts should be made in this object at minimum using a
circular saw to get all the cubes which ...
0
votes
2answers
22 views
What is the least number of cuts that should be made to obtain the maximum pieces possible in a parallelogram?
The problem is as follows:
The figure from below represents a piece of wood that has the shape of
a parallelogram. whose sides are of equal length. If we want to cut
piece of wood in the maximum ...
0
votes
0answers
19 views
Conjugate gradient and the eigenvectors corresponding to the large eigenvalues
I am working on an optimization problem (for example, conjugate gradient) to solve $Ax=b$, where $A$ is a symmetric positive definite matrix. I can understand that the CG (conjugate gradient) has ...
0
votes
2answers
23 views
Can linear programs in canonical form be infeasible?
Is one of the stipulations of putting a linear program in canonical form that it must have at least one feasible solution? Also, if a canonical linear program can be infeasible, does that mean any ...
0
votes
0answers
24 views
Maximum Optimization Problem with Coins
So, on this online game, there's this currency system where you want to break down these large coins into smaller denominations because of their desirability, but you can only do so by purchasing ...
1
vote
1answer
35 views
Approximating large quadratic optimization problems
For some positive-definite matrix $A \in \mathbb{R}^{K \times K}$ I want to solve the quadratic optimization problem
$$\max_{x\in [0,1]^K} x^T A x \\ \text{s.t.} \\ \sum_{i=1}^{K}x_{i}=1$$
The problem ...
