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.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
360