Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
12 views

How to write a good heuristic function

I have a game, that works based on the following rulesets: I have a 3x3 size board, with enemies on some of the spaces Each enemy has a type, and 3 values, to differentiate between them: health [H], ...
1
vote
0answers
25 views

Difference between Ax-b and f(A)x-f(b)?

I have an understanding how the solution of the following convex optimization behaves for a particular data: $min(norm(Ax-b),2)+norm(x,1))$. In this case $A$ is a known matrix and $b$ is a known ...
0
votes
1answer
22 views

how to use KKT conditions for an exponential function

our teacher gave us a problem in the exam that I failed to answer it even after passing it, and I ask for an explanation from people here please... this is the problem : let K be a subset of $\Bbb R^...
0
votes
0answers
6 views

Flowshop with parallel machines model

I am working on an integer programming model for a flowshop problem with different number of parallel machines. I have to schedule $i=1,..,n$ jobs in $j=1,..,m$ activities where each $j$ activity has ...
0
votes
0answers
14 views

Generalizing the Solution to the Lagrangian for Risk Averse Portfolio Construction

I'm interested in generalizing the Lagrangian in Herold (2005) for portfolio construction in finance: which finds the portfolio $h_p$ that maximizes the utility subject to the fully invested $h'_p ...
0
votes
0answers
29 views

Solving mixed-integer non-linear optimization problem

I would like to solve the following optimization problem: \begin{array}{ll} \underset{x_{i}\geq0,\, \pi_{i}\in\{0,1\}}{\text{minimize}} & \displaystyle\sum_{i=1}^n x_i\\ \text{subject to} & \...
1
vote
1answer
21 views

Why does NLopt have L-BFGS but not BFGS?

NLopt, the "free/open-source library for nonlinear optimization, providing a common interface for a number of different free optimization routines..." has a L-BFGS ...
1
vote
0answers
32 views

Nonlinear optimization with parametric constraint

Is there any way of reformulating the following problem so that it can be solved by means of e.g. Matlab's fmincon? $\min f(x_1,\dots,x_n)$ subject to $c(x_1,\dots,...
1
vote
1answer
17 views

Find rigid transformation with noisy data, simple approach

I have two set of points $\left\{ a_j \right\}_{j=1...n},\left\{ b_j \right\}_{j=1...n}$, you can assume $a_j$ are noisy. I want to find a rotation matrix $R$ and a translation vector $T$ such that $$...
2
votes
0answers
17 views

Existence minimizer for total variation over measures

I want to prove that there exists a minimizer to the following problem $$ \min || \mu ||_{\text{TV}} \text{ such that } \mathcal{F} \mu = y $$ where $\mu \in \mathcal{M}([0,1])$, the space of Radon ...
4
votes
0answers
13 views

Optimization of nonlinear $f(x)$ where $x$ is a vector of binary variables

I'd like to find a solution (potentially approximate) to the problem $$ \max_{x_{i,j}} \sum_{k=0}^K\left[ 1 - \prod_{i=1}^{I} \left(1 - \prod_{j=1}^{J}(1-b_{k,i,j} \, x_{i,j}) \right)\right] $$ ...
1
vote
0answers
22 views

How is the spanning tree constructed in the Minimum Cost Flow Problem?

Could someone please explain how the spanning tree was constructed? Notation aclaration. $[40]$ denotes the supply on node $A$. $[-30]$ denotes the demand on node $D$. $c_{AD}=9\iff 9$ denotes the ...
0
votes
1answer
24 views

Optimizing a sum of functions

I'm not an expert in optimization, but I am currently working on a problem where I need to maximize/minimize a function of the form, \begin{equation*} g(\alpha_0, \alpha_1) = \displaystyle \sum_{i=1}^...
0
votes
0answers
8 views

How to solve the tensor approximation optimization problem?

Given a third-order tensor $\mathcal{X}\in\mathbb{R}^{I_1\times I_2\times I_3}$, we want to find an approximation tensor $\hat{\mathcal{X}}$ of $\mathcal{X}$ with $R$ rank-one components, and some ...
1
vote
0answers
27 views

minimise the trace of a matrix over all column permutations

I have a 10x10 positive symmetric matrix, I need to find the optimal permutation of the columns in order to minimise the trace. I can't try all permutations because that would be a 10! problem. Any ...
1
vote
0answers
12 views

Identifying changes in new data using previously trained regression model

I would like some ideas on the following problem. I have a data $x$: $$x(y,z) = [x_1(y,z), x_2(y,z), x_3(y,z)]$$ such that they are function of $(y,z)$, but neither of $(y,z)$ is available. Therefore ...
-2
votes
0answers
28 views

maximum of a function of three variables [on hold]

I would like if you can help me to check if the maximum of this function is always less than or equal to zero , even with a numerical calculator $f(x,y,z)=\dfrac{\sqrt{zy}+\sqrt{\frac{1}{x}\sqrt{z(\...
2
votes
0answers
9 views

Efficient SQP with more equality constraints than parameters

My question is both a math and (computer) programming one so answers related to either are fine. Problem Setup I have the nonlinear programming problem $$ \begin{aligned} \min \;\; &f(X) \\ \...
1
vote
2answers
49 views
+150

How to optimize three numbers such that their sum is always equal?

I know the real numbers $a,b,c$ and $d$ and I am trying to find three more numbers - $x, y, z$ - such that their average is equal to $d$ and the sum $|a-x| + |b-y| + |c-z|$ is minimal. How would I do ...
2
votes
1answer
26 views

Find $k$-clique with max min weight.

I have a problem with the following equivalent formulation in graph theory: Take $G(V, E, W)$ a complete weighted graph, where $w_{ij} > 0$ is the weight of edge $e_{ij}$. For a given $k$, find ...
3
votes
1answer
109 views

Maximizing $x^4+y^4+z^4 + p(xy+xz+yz)$ on a sphere

What values of $x,y,z$ maximize $f(x,y,z,p) = x^4+y^4+z^4 + p(xy+xz+yz)$ with constant $p \geq 0$ with the constraint $x^2+y^2+z^2=1$? Some preliminary studies in Mathematica showed that the behavior ...
0
votes
1answer
39 views

Calculating the minimum distance to the origin from a curve defined by $\frac{x^2}{4}+y^2+\frac{z^2}{4}=1$ and $x+y+z=1$

I want to calculate the points of the curve given by $$\frac{x^2}{4}+y^2+\frac{z^2}{4}=1,\qquad x+y+z=1$$ which are minimum and maximum distance to the origin. Using Lagrange multipliers, the maximum ...
1
vote
0answers
33 views

Binary Optimization Problems that can be easily solved?

As far as I have researched, even linear programs with binary constraints on the decision variables are in general NP hard. However, I wounder if there are some (non-trivial) binary optimization ...
1
vote
0answers
37 views

Rewrite $ \min_{q\in Q_0} \sum_{x=1}^X |m_x(q)| $ with linear objective function

I have the following optimization problem $$ \min_{q\in Q_0} \sum_{x=1}^X |m_x(q_{1})| $$ where $q\equiv (q_1,q_2)$ is a vector that should satisfy a bunch of non-linear constraints collected in $...
0
votes
0answers
12 views

Prove Unique Lagrange Multipliers Equality Constraint

I am working through some old test papers in preparation for exams an am trying to scout out potential sneaky questions that might be asked. I've stumbled across this one. Would you please verify or ...
1
vote
0answers
12 views

knapsack with multiple constraints and some negative weights

I'm trying to solve an integer linear programming problem of the following form $max$ $\sum_{i=1}^n v_i \cdot x_i$ $s.t. \sum_{i=1}^n w_{i1} \cdot x_i \leq 0$ and $\sum_{i=1}^n w_{i2} \cdot x_i \...
0
votes
0answers
15 views

Transform the problem to EQ constrained problem with simple bounds

\begin{align} min && x_1^2 + x_2^2\\ s.t. && (x_1 -3)^2+1 \leq x_2\\ &&x_1-2x_2+2=0\\ &&x_2 \geq0.5 \end{align} SOLUTION. \begin{align} min && x_1^2 + x_2^2\\ ...
0
votes
0answers
15 views

optimization exercise to find the maximum area of a rectangle formed by two rectangles with a line. Literal exercise.

A rectangle R in the plane has corners at (+-8, +-12), and a 100 by 100 square S is positioned in the plane so that its sides are paralleul to the coordinate axes and the lower left corner of S is on ...
3
votes
0answers
36 views

Projection onto the weighted $\ell$2 norm ball

Projection onto the $\ell$2 norm ball is known. Let the norm ball set reads $C = \left\{x \in \mathbb{R}^n: \left\| x - c \right\|_2^2 \leq d^2 \right\}$, where $c \in \mathbb{R}^n$ and $d \in \...
0
votes
0answers
24 views

proving if player 1 has a pure optimal strategy, player 2 should as well

Problem: Prove that if in a matrix game 2x2 if the player 1 has a pure optimal strategy, so has player 2 Attempt: Given: We know that player 1 has pure optimal strategy, meaning: $$P(x, \overline{...
8
votes
3answers
181 views
+50

Find a point $X$, in the plane of regular pentagon $ABCDE$, that minimizes $\frac{XA+XB}{XC+XD+XE}$.

Find such a point $X$, in the plane of the regular pentagon $ABCDE$, that the value of expression $$\frac{XA+XB}{XC+XD+XE}$$ is the lowest. I tried using Ptolemy's theorem but don't know how to make ...
0
votes
2answers
41 views

Constrained Optimization problem with Lagrange Multiplier

I came across an example in a text, maximum volume of a rectangular box in $\mathbb{R^3}$, with sides parallel to the coordinate axes, whose vertices are all a distance $R$ from the origin. So I am ...
1
vote
0answers
50 views

If $f$ is $\beta$-smooth and non-negative, then $|f'(x)|^2\le 2\beta f(x)$?

I am reading a paper, and I found this conclusion from a proof. I am wondering why we can conclude that if a function $f$ is $\beta$-smooth and non-negative, then $|f'(x)|^2\le 2\beta f(x)$. A ...
0
votes
0answers
14 views

Expensive combinatorial optimization of choice of subset from a large finite space

I have a fairly general question -- what's a good (gradient-free) approach to optimizing an expensive function whose input is a choice of subset from a large finite population? That is, I have a set ...
0
votes
0answers
13 views

Concerning the idea of Trust Region methods

As far as I understood is that the idea of TR methods is that at the current iterate $x_k$ we build a model "usually quadratic", of the objective function $f$ to be optimized, $m_k(s)$ of $f(x_k +s)$ ...
0
votes
0answers
18 views

knapsack with changing value function

I recently was looking at the knapsack problem and was wondering, if a slight modification can be done. Let's say that if my bag is empty, I have values $[x_{10},x_{20},x_{30},... ,x_{n0}]$ for n ...
0
votes
2answers
39 views

Global extrema of $f(x,y,z) = x^2-y^2+z$ on $x^2+y^2+z^2\leq 1$ and $f(x,y)=\frac{x^2}{2}+\frac{y^2}{2}$ on $\frac{x^2}{2}+y^2\leq 1$

(See edits below about what I did wrong) I'm asked to find the global extrema of two functions each in a different region. I think my results are correct, but I have no solutions, so I don't know if ...
0
votes
0answers
14 views

Pseudo Expectation Maximization

Can someone give me a detailed discription of the Pseudo Expectation Maximization algorithm? I'm taking a course that includes the EM algorithm in its curriculum as well as a variant of the algorithm ...
1
vote
1answer
23 views

How to find most likely family of probability density polynomials given prior data?

If we imagine we have a bunch of polynomials $P_n(t)$, each describe probability densities that an event happening at some time $t$ and we know that exactly one of the $N$ events will happen during ...
0
votes
0answers
20 views

In-exact line search

In my class notes, the author says: "If $f:\mathbb{R}^n \to \mathbb{R}$ is bounded below and $p_k$ is a descent direction and the $\alpha-\beta$ also known as Armijo-Goldstein condition is met then ...
0
votes
1answer
30 views

Two Mixed Integer Linear Programs (MILP) with different objectives and same constraints

There are two Mixed Integer Linear Programs. They have the same set of linear constraints constraints, but different objectives with variables $\mathbf{z}$ and $\mathbf{x}$. The first objective is: $...
1
vote
0answers
20 views

How to write Frank-Wolfe algorithm in two steps optimization problems?

Let $g(x)$ be a function. Frank-Wolfe algorithm over a convex set $C$ is defined so as as to find the local minimum of the function: $$ s_{t+1}=\arg\min_{s \in C} \langle s, \nabla g(x) \rangle \tag{...
1
vote
1answer
50 views

Math optimization riddle

You have been given the task of transporting 3,000 apples 1,000 miles from Appleland to Bananaville. Your truck can carry 1,000 apples at a time. Every time you travel a mile towards Bananaville ...
1
vote
1answer
39 views

Semidefinite programming relaxation of linear dynamical system to find Lyapunov function

I am considering a linear dynamical system of the form $$x_{k+1} = Ax_k$$ I know that when we have stability (that is, that $x_k$ goes to $0$ as $k$ approaches infinity), there exists an $n$-by-$n$ ...
3
votes
1answer
57 views

Maximum number of ufo that can visit any planet

Consider an infinite alien 2d world consisting of infinite planet, so that distance between any two planets is not same. Now at some point of time, a ufo leaves each planet and goes to planet nearest ...
-1
votes
0answers
14 views
0
votes
1answer
25 views

For a given number n, Maximize product of numbers such that sum of these equals n

For some ${n \in \mathbb{N}}$ and ${f(x_1, x_2, x_3, x_5,...) = 1^{x_1}.2^{x_2}.3^{x_3}.5^{x_5}.7^{x_7}....}$ ${x_i \in \mathbb{W}}$ Find ${x_1, x_2, x_3, x_5,...}$ such that ${f(x_1, x_2, x_3, ...
1
vote
2answers
31 views

How is the dual cone of a subspace its orthogonal complement?

From Boyd and Vandenberghe's Convex Optimization: A dual cone of a subspace $V \subseteq \Bbb R^n$ is it's orthogonal complement. $V^{*} = \{y : v^Ty = 0, \forall v \in V\}$ but the dual ...
1
vote
2answers
39 views

Proximal gradient method justification

If $f$ and $g$ are respectively a differentiable function and a convex, lower semi-continuous function, then the algorithm defined by: $$ x^{k+1} = \text{prox}_{\gamma{g}}[x^{k} - \gamma\nabla{f(x^{k}...
2
votes
1answer
55 views

Candy machines and optimal strategy in terms of expected value

Problem We have three candy machines: call them G (good), B (bad) and M (mixed) . G always gives you a candy when you put 1\$. B never gives you a candy when you put 1\$. M gives you a candy with ...